Entry #5 - Predicting Machines

This was a self-challenge I created in CSC165 to understand better how to calculate the value of the input in a machine. The way these notes were formatted helped me to understand better the way in which to find the big-Oh of a function. 

######################################################

Machine 1: How can we find z assuming x > 1?

For this, we will use x-y-z charts.

2:

x	y	z
2	1+1	+1
2-1	2	+1
1	2	2

3:

x	y	z
3	1+1	+1
3-1	2	+1
2	2	2

4:

x	y	z
4	1+1	+1
4-1	2	+1
3	2	+0
3	2+1	+1
3	3	3

5:

x	y	z
5	1+1	+1
5-1	2	+1
4	2	+0
4	2+1	+1
4-1	3	+1
3	3	4

We can simplify this for the next few numbers by pointing out when z increases for each condition (x > y, x > z) and compare it to the previous results:

2: 1, 1 = 2
3: 1, 1 = 2
4: 1, 1, 0, 1 = 3
5: 1, 1, 0, 1, 1 = 4
6: 1, 1, 0, 1, 1, 0, 1 = 5
7: 1, 1, 0, 1, 1, 0, 1, 0, 1 = 6
8: 1, 1, 0, 1, 1, 0, 1, 1, 1 = 7

It can be gathered that z = x – 1 except at x = 2 when z = x. This means that at some point a condition that isn’t met before does get met or a new condition is met, adding to the chain.

Machine 2: How can we find a assuming x > -1?

We know that machine_2(-1) returns 0. What does machine_2(0) return?

x = x + 2 so x = 2
Since y = 1 and x > y, a goes up by 1 and so does y.
Since z = 2 and y == z, a goes up by 1 and z goes up by 2.
x > y is not in effect anymore, therefore machine_2(0) returns 2 (which is what a is).

Now what happens when machine_2(1) is executed? The same as machine_2(0) but we can add 1 to a since x = 3 and x still is greater than y when y = 2 making the function  return 3. How about machine_2(2)? Again the same as before apply but x now equals 4 meaning that y has to increase by 1 in order to break the loop (which makes a increase by 1). By doing so, y = 4 and z = 4 making the y == z statement true and allowing a to go up by 1 again, meaning the function returns 5.

The table illustrates this pattern:

x	m_2(x)
0	2
1	3
2	5
3	6
4	8
5	9
6	11

When x goes from odd to even, 2 is added. When x goes from even to odd, 1 is added. So machine_2(x) creates this pattern:
2 + 1 + 2 + 1 + 2 + 1 + 2 . . .
(based on 2, 3, 5, 6, 8, 9, 11 . . . )

To put it another way:

0 / 1  turns to 2 / 3        # by adding 2
2 / 3  turns to 5 / 6        # by adding 3
4 / 5  turns to 8 / 9        # by adding 4
6 / 7  turns to 11 / 12      # by adding 5
etc.

Another interesting element is that the even and odd sets all differ by 3.

We can re-write the results of machine_2 like so:

-1: 0 + 0 // 0 + 2(0)
0 : 0 + 2 // 0 + 2(1)
1 : 1 + 2 // 1 + 2(1)
2 : 1 + 4 // 1 + 2(2)
3 : 2 + 4 // 2 + 2(2)
4 : 2 + 6 // 2 + 2(3)
5 : 3 + 6 // 3 + 2(3)
6 : 3 + 8 // 3 + 2(4)
7 : 4 + 8 // 4 + 2(4)

We can split this through conditions:
if x % 2 == 0 then a = x/2 + 2 * ceiling((x + 1)/2)
if x % 2 == 1 then a = ceiling(x/2) + 2 * ceiling((x + 1)/2)

So we can combine the two to get:

a = ceiling(x/2) + 2 * ceiling((x + 1)/2)

Machine 3: How can we find b assuming x > 3?

The while x > a loop indicates how many steps it takes for a to equal x using the a + 1 approach, making b = (x - a).

Since a = 3, b = (x - 3).

Now x_α = x + 2.

The while x_α > z loop indicates how long it takes for x_α == z (provided x_α % 2 == 0) or x_α < z (x_α % 2 == 1) following the x_α – 1 // z + 1 approach:

X	z	B
xα (x + 2)	2 (z)	+ 0
xα - 1 (x + 2 - 1)	2 + 1 (z + 1)	+ 1
xα - 2  (x + 2 - 1)	2 + 2 (z + 2)	+ 2
-	-	-
xα-final (x + 2 – n)	zfinal (z + n or 2 + n)	+ n

By manipulating inequalities:

x + 2 - n ≤ 2 + n
x + 2 ≤ 2 + 2n
x + 2 ≤ 2(1 + n)
((x + 2) / 2) ≤ 1 + n
(((x + 2) / 2) – 1) ≤ n

So we have:

b = (x - 3) + (((x + 2) / 2) - 1)  # if x % 2 == 0
b = (x - 3) + ceiling(((x + 2) / 2) - 1)   # if x % 2 == 1

Which means b = (x - 3) + ceiling(((x + 2) / 2) – 1).

We will call n = ceiling(((x + 2) / 2) – 1)  # b = (x + 3) + n

At this point, x_β = x_α – n. Consider x_β = x_β + 3 = x_α – n + 3

The while x_β > y indicates how long it takes for x_β == y (x_β % 2 == 0) or x_β < y (x % 2 == 1) following the x_β - 1 // y + 2 approach:

xβ	y	b
xβ (xα – n + 3)	1 (y)	+ 0
xβ – 1 (xβ – 1) (xα – n + 3 - 1)	1 + 2 (y + 1(2))	+ 1
xβ – 2 (xβ – 2) (xα – n + 3 - 2)	1 + 4 (y + 2(2))	+ 2
-	-	-
xβ-final (xβ – q) (xα – n + 3 - q)	yfinal (y + 2q or 1 + 2q)	+ q

x_β – q ≤ 1 + 2q
x_β ≤ 1 + 3q
x_β – 1 ≤ 3q
(x_β – 1 / 3) ≤ q

So we have:

b = (x - 3) + n + (x_β – 1 / 3)      # if x % 2 == 0
b = (x - 3) + n + ceiling(x_β – 1 / 3)     # if x % 2 == 1

In conclusion, when x > 3:
b = (x – 3) + n + ceiling(x_β – 1 / 3)
b = (x – 3) + n + q    # ultra-simplified
b = (x – 3) + n + ceiling(x_α – n + 2 / 3)   #in “x”-n terms
b = (x – 3) + n + ceiling(x – n + 4 / 3)   #in x-n terms

Machine 4: How can we find b if x > 1?

This one will require checking inputs and outputs:

x	m_4(x)
2	3
3	3
4	4
5	4
6	6
7	6
8	7

In this case we have pairs that produce the same value thus creating a sequence like so:

3, 4, 6, 7, 10, 11, 13, 14, 17, 18 . . .

This has a repeated pattern of + 3 + 1 + 2 + 1 + . . .

When a number is able to accomplish both boolean statements, b increases by 3 (machine_4(2)). When the z % 2 == 0 statement is accomplished by itself, b increases by 2 (machine_4(6)).

Now we can color code the sequence to indicate when b increase by 2 and when it increases by 3:

3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .

Both of these sets are separated by 7 (1 + 3 + 1 + 2 // 1 + 2 + 1 + 3). Let’s look at the pairs of some of these closely.

n ∊  Blue	Pair	n ∊  Red	Pair
3	2, 3	6	6, 7
10	10, 11	13	14, 15
17	18, 19	20	22, 23

These pairs have a difference of 8. If we were to assign a color to the other numbers with a 7 difference in a pattern, we might obtain something more concise:

3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .

We go B, Y, R, G with each pair differentiating by 8. Pooling all this information to calculate b, we first establish the original B-Y-R-G pairs.

B: 2, 3. Y: 4, 5. R: 6, 7. G: 8, 9

Then we say that if your x is an item in the original B-Y-R-G pairs + 8n, then you must get the original B-Y-R-G pair values (3, 4, 6, 7) and add it by 7n

Ex.1: machine_4(29) = b. Calculate b.

Can 29 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
29 % 8 = 5. Does this mean that 29 = 5 + 8n?
Prove: 29 – 5 = 8n. 24 = 8n. 3 = n.
Y: 4, 5 = 4
So therefore 29 could be 4 + 7(3).

check - machine_4(29) == 25. True!
(Note: this also means that machine_4(28) == 25 is True)

Ex.2: machine_3(33) = b. Calculate b.

Can 33 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
33 % 8 = 1. What does this mean? Consider an int such that it can be represented by 8 + 8n. This int % 8 = 0. Does this mean that if an int % 8 = 1, it would have to be represented as 9 + 8n?
Prove: 33 – 9 = 8n. 24 = 8n. 3 = n.
(Note: You can also consider 9 + 8n as 1 + 8 + 8n)
G: 8, 9 = 7
So therefore 33 could be 7 + 7(3).

check – machine_4(33) == 28. True!
(Note: this also means that machine_4(32) == 28 is True)

Basically:
Let x % 8 = m

If m = 2 or 3: x can be written as 2 + 8n or 3 + 8n
Solve for n, then plug in for 3 + 7n = b

If m = 4 or 5: x can be written as 4 + 8n or 5 + 8n
Solve for n, then plug in for 4 + 7n = b

If m = 6 or 7: x can be written as 6 + 8n or 7 + 8n
Solve for n, then plug in for 6 + 7n = b

If m = 0 or 1: x can be written as 8 + 8n or 9 + 8n
Solve for n, then plug in for 7 + 7n = b

Machine 5: How can we find a if x > 2?

The while x > z loop will stop when x ≤ 2 and a increases every time x decreases by 1, meaning a so far equals:

a = (x – 2) + inner while loop

The inner while loop creates the x + x – 1 + x – 2 … + 1 sequence with x – 2. Since that sequence is normally (x)(x – 1)/2 and (x – 1) represents the lowest point, we must change this to (x – 2)(x – 1) / 2. Thus:

a = (x – 2) + ((x – 2)(x – 1) / 2)
a = (x – 2) + ((x² – 3x – 2) / 2)

###################################################################

def machine_1(x):
    y = 1
    z = 0
    while x > y:
        y = y + 1
        z = z + 1
        if x > z:
            x = x - 1
            z = z + 1
    return z
            
def machine_2(x):
    x = x + 2
    y = 1
    z = 2
    a = 0
    while x > y:
        y = y + 1
        if y == z:
            a = a + 1
            z = z + 2
        a = a + 1
    return a

def machine_3(x):
    y = 1
    z = 2
    a = 3
    b = 0
    
    while x > a:
        a = a + 1
        b = b + 1
    
    x = x + 2
    
    while x > z:
        x = x - 1
        z = z + 1
        b = b + 1
    
    x = x + 3

    while x > y:
        y = y + 2
        x = x - 1
        b = b + 1
    
    return b   

def machine_4(x):
    y = 0
    z = 0
    a = 1
    b = 0
    while x > a:
        a = a + 1
        x = x - 1
        b = b + 1
        z = a
        if z % 2 == 0:
            y = y + 1
            b = b + 1
            if y % 2 == 1:
                b = b + 1
    
    return b

def machine_5(x):
    z = 2
    a = 0
    while x > z:
        y = x
        while y > z:
            y = y - 1
            a = a + 1
        x = x - 1
        a = a + 1
    return a

Entry #4 - Using A Linked List In Relation To A Function

Back in CSC108, I created a function that would lead any integer of your choosing to reach 16. It was a relatively simple concept. Seeing linked lists, I figured that it would be interesting if I could adapt it to that ADT. So I imported the code I wrote for linked list (the linked list node .py file from this class works with this too) and modified it to suit my purposes. 

Before I do that, allow me to bring up a random number like 43 and ask you to do the following. I want you to add 1, then divide by two and round down, then subtract 4 twice, double the result of that, and subtract 4 three more times. Did you reach 16? I bet you did. How did those steps come about? Well let's look below.

import math

def linked_list_specific_sts(number):

    ''' (int) -> LinkedList

    

    Return the steps necessary to reach 16

    

    >>> lnk = linked_list_specific_sts(43)

    >>> print(lnk)

    43 -> Add 1 -> Divide by 2 and round down -> Subtract 4 -> Subtract 4 -> Double it -> Subtract 4 -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|

    '''

    

    lnk = LinkedList()

    lnk.append(str(number))

    while number != 16:

            if number % 2 == 0 and number < 16:

                number = number * 2

                lnk.append('Double it')

            elif number % 2 == 1 and number < 16:

                number = number + 1

                lnk.append('Add 1')

            elif number % 2 == 0 and 16 < number < 30:

                number = number - 4

                lnk.append('Subtract 4')

            elif number % 2 == 1 and 16 < number < 30:

                number = number - 1

                lnk.append('Subtract 1')

            elif number % 2 == 0 and 30 <= number < 100:

                number = number//2

                lnk.append('Divide by 2 and round down')

            elif number % 2 == 1 and 30 < number < 100:

                number = number + 1

                lnk.append('Add 1')

            elif number >= 100:

                number = round(math.log(number, 10))

                lnk.append('Round the base 10 log')

    lnk.append('You have reached 16')

    return lnk

As you can see, there are certain restrictions that lead to certain steps. 

• If number is even and less than 16, double it
• If number is odd and less than 16, add 1
• If number is even and greater than 16 but less than 30, subtract 4
• If number is odd and greater than 16 but less than 30, subtract 1
• If number is even and greater than 30 but less than 100, divide by 2 and round down
• If number is odd and greater than 30 but less than 100, add 1
• If number is greater than 100, round the base 10 log

I did get lazy when the number gets higher than 100, but that's just me exercising one of the golden rules of being a computer scientist. Now you can do this on your own without the function above but what if you wanted to be sure that you were following the algorithm correctly after a certain amount of steps? Well, worry not, for obtain_sts_step has you covered.

def obtain_sts_step(lnk, step):

    ''' (LinkedList, int) -> int

    

    Precondition: step != lnk.size - 1 and step > 1

    

    Return what the step would be based on the instructions given

    

    >>> lnk = linked_list_specific_sts(43)

    >>> obtain_sts_step(lnk, 3)

    18

    >>> lnk = linked_list_specific_sts(35375)

    >>> obtain_sts_step(lnk, 5)

    20

    '''

    start = int(lnk[0])

    for i in range(1, step+1):

        if lnk[i] == 'Add 1':

            start = start + 1

        elif lnk[i] == 'Divide by 2 and round down':

            start = start // 2

        elif lnk[i] == 'Subtract 4':

            start = start - 4

        elif lnk[i] == 'Double it':

            start = start * 2

        elif lnk[i] == 'Round the base 10 log':

            start = round(math.log(start, 10))

        elif lnk[i] == 'Subtract 1':

            start = start - 1

    return start

As you can see, it returns to you the number after finally going through all the steps. We know how 43 goes, but what about 35375? Well first we should look at what happens when you enter that number into linked_list_specific_sts:

35375 -> Round the base 10 log -> Add 1 -> Double it -> Double it -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|

We would stop at the first instance of Subtract 4, meaning that the next 5 numbers would be 5, 6, 12, 24, 20. Now that's if you want a quick check to see that your approach with the algorithm was correct. If you simply just want to see the numbers rather than the actions that you need to do, you can use linked_list_sts:

def steps_to_sixteen(number):

    """ (int) ->  list of ints

    Precondition: number != 0

        

    Return a list of steps it takes to get to 16

    >>> steps_to_sixteen(2)

    [2, 4, 8, 16]

    >>> steps_to_sixteen(3)

    [3, 4, 8, 16]

    >>> steps_to_sixteen(10)

    [10, 20, 16]

    >>> steps_to_sixteen(30)

    [30, 15, 16]

    >>> steps_to_sixteen(100)

    [100, 2, 4, 8, 16]

    """

    

    steps = []

    steps.append(number)

    while number != 16:

        if number % 2 == 0 and number < 16:

            number = number * 2

            steps.append(number)

        elif number % 2 == 1 and number < 16:

            number = number + 1

            steps.append(number)

        elif number % 2 == 0 and 16 < number < 30:

            number = number - 4

            steps.append(number)

        elif number % 2 == 1 and 16 < number < 30:

            number = number - 1

            steps.append(number)

        elif number % 2 == 0 and 30 <= number < 100:

            number = number//2

            steps.append(number)

        elif number % 2 == 1 and 30 < number < 100:

            number = number + 1

            steps.append(number)

        elif number >= 100:

            number = round(math.log(number, 10))

            steps.append(number)

    return steps   

def linked_list_sts(number):

    """ (int) -> NoneType

    

    Return steps to take to sixteen as a linked list

    

    >>> lnk = linked_list_sts(43)

    >>> print(lnk)

    43 -> 44 -> 22 -> 18 -> 14 -> 28 -> 24 -> 20 -> 16 ->|

    """

    steps = steps_to_sixteen(number)

    lnk = LinkedList()

    for step in steps:

        lnk.append(step)

    return lnk

As you can see, I used a helper function which simply shows them as a list, and then have each step in the list be appended to the linked list.