Scheming in Python I

Let's look at the code piece by piece

class A(object):
    def __init__(self, a=None, b=None):
        self.a = a
        self.b = b

First we should realize that the class created 'A' is more like a tree rather than like a python list.At the top of the tree we have two nodes,one branch goes towards the first integer value the second goes to another node which again branches out .

def get_sublist_last_163(N, M):

The above line defines the function get sublist last_163 with its parameters N and M

    big_list = A(1000)
    i = 999
    while (i>0):
        big_list = A(i, big_list)
        i = i - 1

The first line creates a node 'biglist' with a value of 1000 and no value defined for node.b. The while loop counts down 1000 loops until it reaches one and on each loop it branches out the 'biglist' node into a value(biglist.a.a.a...) and a node(biglist.b.b.b...).

    sublist_last_163 = big_list
    # call "b" N times
    i = 0
    while (i < N):
        sublist_last_163 = sublist_last_163.b
        i = i + 1

The above snippet,just as commented counts down N times;upon each loop the variable sublist last 163 goes down the tree,deeper and deeper. Now what the problem requires of us is to find how many times the loop must run in order for the sublist last 163 variable to reach the node that is 163 nodes away from the last node. This is obviously the (1000 - 163) 837'th node. So the loop has to run 837 times hence N has to be 837. Let us look at the last bit

    # call "a" M times
    i = 0
    while (i < M):
        sublist_last_163 = sublist_last_163.a
        i = i + 1

    return sublist_last_163

When we look at this piece of code,it takes our variable sublist last 163 and goes deeper and deeper into the side of the tree with the integer values;it does this M times. Finally returns the last value of sublist last 163. But this is not necessary as we already got our answer in the previous step. So what is required is to stop this bit of code all together just by manipulating the inputs N and M. Well it is obvious that if M is 0 then the while loop wont run so that is our value of M.

With (N as 837) and (M as 0) we get N+M=837+0=0

Note that each time we set $\text{sublist\_last\_163} = \text{sublist\_last\_163.b},$ the value of $\text{sublist\_last\_163.a}$ is increased by $1,$ starting at $1.$ We want $\text{sublist\_last\_163.a}$ to be equal to the $163$ th element from the end of the list $[1, 2, 3, \ldots, 1000],$ which is $838,$ so we have to let $N = 837.$

If we were to set $\text{sublist\_last\_163} = \text{sublist\_last\_163.a}$ at least once, then $\text{sublist\_last\_163}$ will become just an integer, after which we can do nothing else. So, we must have $M = 0,$ and therefore the sum of $M$ and $N$ is $\boxed{837}.$

A singly linked list is a data structure which holds a value and a link that points to the next node (or list). The class A can be seen as a singly linked list because it can hold two arbitrary values a and b where a could be the value of the node and b could be the link that points to the next node.

This list can be traversed by looking at the next node until the pointer to the next node become null or empty. Therefore, you should be able to obtain the nth element of the list by looking at the next node n - 1 times. In the same way, to get the l - n last elements of a list where l is the length of the list, you can traverse n - 1 times and reference the link.

The "call b N times" is the traversal method and the "call a M times" is to reference the value in the current node you are at. You may notice that the "call a M times" is useless for returning a list because it only returns the value at a node. In consequence you can tell that you'll call it 0 times.

Since the list has a length of 1000 and you need the last 163 elements you can calculate that you need to traverse the list 1000 - 163 times in order for b to be a link to a list of length 163 .

You're resulting call would be get_sublist_last_163(837, 0) .

Therefore the answer is 837 !

It must be the case that M = 0 since sublist_last_163.a yields a number. If M != 0 then the code will yield an error. It is the case that N is the number of elements that will be dropped from the beginning of the list. We would like to retain 163 elements and so would like to drop $1000 - 163 = 837$ elements. Hence N = 837, M = 0 and N + M = 837 .

After the first part of the code is executed, big_list contains a list of 1000 elements: A(1,A(2,A(3,...))). Here is how it looks "at the end", at the deepest nesting level: ...,A(999,A(1000,None))...

In order to get the last $163$ elements, we just need to throw away the first $1000-163=837$ elements. This is done in the cycle where we "call 'b' N times". For example, the first call to

sublist_last_163 = sublist_last_163.b

changes our list from A(1,A(2,A(3,...))) to A(2,A(3,...)): we just got rid of the first element, and we now have the rest of the list in the same format. To throw away 837 elements, we need to set $n=837$ . And once we throw them away, we are done, there is no need for the second cycle. To prevent it from executing, we set $m=0$ .

Thus, the answer is $n+m = 837+0 = \fbox{837}$ .

Calling a any amount of times results in an integer so it cannot be called at all if we want a list returned. Calling b returns the a list of elements 1 through len(L)-1 of the current list L . As the list contains 1000 elements, we want elements 837 through 999 (838 to 1000)... so we need to call b 837 times.

$1000 - 163 = 837$

In the code, calling b once means going to the next list; calling a once means getting the value of the current node. We need to move from node 1 to node 838 (the 163rd node counting backwards). To do this, we need to call b 837 times. Now, since we want the list , but not the value , hence, we don't need to call a at all.

When the list of the integers 1-1000 is created, she gets [1,[2,[3,[...]]]]. Each time she calls 'b', she gets the second element, which is [2,[3,[...]]] the first time. She must get a list of 163 elements, ending at 1000. By simple counting, the list [838,[839,[...]]] is the one she wants. The nth time she calls 'b', the new list begins with n+1. If she wants it to begin with 838, she must call it 837 times, so $N=837$ . Now, she has the list [838,[839,[...]]], and if she calls 'a' once, she will get the integer 838. Any more calls of 'a' will result in an AttributeError. Therefore, $M=0$ , and the answer is $837+0=\boxed{837}$ .

This list is defined as a recursive pair, where the first component of a pair contains an element, and the second component of the pair contains a pair where the first component is an element and the second component of the pair contains a pair ...

We can think of the list as a 'head' element, and the 'tail' (rest of the list). We wish to return the last 163 elements of the list, so we should drop 837 elements off of the front of the list. In terms of heads and tails, we need to drop 837 heads off of the front of the list. So, we step into the tail 837 times. (N = 837)

Stepping into the head of the list and reassigning doesn't do us much good in terms of returning a non-singleton sublist, so we never want to step into the head of the list. (M=0)

837 + 0 = 837