JamCoders

 💾 Download

Runs this cell first!

In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
    import base64
    code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
    exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f

def check(fn, *input, expected):
    result = fn(*input)
    if expected != result:
        print(
            f"{fn.__name__}({", ".join(input)}) should be {expected}, not {result}.")
    else:
        print(f"Test case passed!")

Week 3, Day 1

Imagine you are the boss who runs the JamCoders Premier League. You have the following teams competing for the top prize in the league: "Manchester United", "Arsenal", "Chelsea", "Liverpool", "Manchester City", "Tottenham Hotspur", "Everton".

The clubs have the following points in the league:

Club Name Points
Manchester United 66
Arsenal 67
Chelsea 71
Liverpool 94
Manchester City 95
Tottenham Hotspur 70
Everton 53

Question 0: List + recursion review

0.1

Create a list called club_points_list that contains 5 integers.

In [ ]:
# Write your solution here

0.2

Print every element in that list (club_points_list) using a for loop.

In [ ]:
#Write your answer here

0.3

The function minimum(L) finds the minimum element in a list L :

def minimum(L):
    min_so_far = L[0]
    for element in L:
        if element < min_so_far :
            min_so_far = element     
    return min_so_far

Write a non recursive function maximum(L) that takes a list of integers L and returns the largest integer in that list.

In [ ]:
def maximum(L):
    #Write your solution here
    return
In [ ]:
# TEST_CASE
L = [23, 45, 56, 88, 19, 10]
check(maximum(L), 88)

L = [0, 12, 44, 5, 6, 7]
check(maximum(L), 44)

0.4

Let's write a recursive function recursive_max(L) that takes a list of integers L and returns the largest integer in that list.

In [ ]:
def recursive_max(L):
    # Write your solution here
    return
In [ ]:
# TEST_CASE
L = [23, 45, 56, 88, 19, 10]
check(recursive_max(L), 88)


L = [0, 12, 44, 5, 6, 7]
check(recursive_max(L), 44)

Question 1: Logarithms

1.0 Logarithms Rules!!1

Logarithms are the opposite (inverse) of exponents. For any two numbers $a > 0$ and $z$, the $a$-ary logarithm of $z$ is a number such that $$a^x = z.$$ Just like with exponents, we have mathematical notation to denote the logarithm: $x=\log_{a}(z)$.

Some examples:

  • Since $2^{5} = 32$ then $\log_2(32) = 5$.
  • Since $2^{0} = 1$ then $\log_2(1) = 0$. Actually, for any number $a \neq 0$ it holds that $\log_a(1) = 0$...

As you may remember, there are some nice tricks (sometimes called rules) for working with expressions involving exponents. Specifically, for any three numbers $x, y$

  1. $$a^x \cdot a^y = a^{x + y}$$
  2. $${\left(a^x\right)}^y = a^{x \cdot y}$$

(If you haven't seen these before, try to convince yourself of why they are true. You can try out some small examples, such as $2^3 \cdot 2^2 = 2^5$; write down the exponents as repeated multiplication.)

Because logarithm is an opposite (inverse) of exponent, each of the rules above have a corresponding rule for working with logarithms.

  1. $$ \log_a(x \cdot y) = \log_a(x) + \log_a(y)$$
  2. $$ \log_a(x^y) = y \cdot \log_a(x)$$

It's not terribly important that we remeber all these rules now. But it's nice to think about them as a way to get comfortable with logarithms. Can you convince yourself of the two logarithm rules based on the corresponding exponent rule?

In [ ]:
# Optional: Your thoughts here.

1.1 Logarithm Algorithm

The integer (binary) logarithm of a number $x$ is the smallest integer $y$ such that $$2^{y+1} > x.$$

It's just like the logarithm, except rounded down to the nearest integer.

Write a function the computes the integer (binary) logarithm.

(Hint: You can refer back to the code for the integer square root function isqrt() in day 5 lecture 12.)

In [ ]:
def ilog_binary(x):
    """Finds the smallest integer y for which 2 ** (y+1) > x.
    Arguments: x (int)
    Returns: (int)
    """
    # Your code here
Out[ ]:
332192
In [ ]:
check(ilog_binary, 2, 1)
check(ilog_binary, 1, 0)
check(ilog_binary, 4, 2)
check(ilog_binary, 8, 3)
check(ilog_binary, 10, 3)
check(ilog_binary, 100, )

1.2 Turn up the base

The reason why we called our function the binary integer logarithm is because it works for base 2; the base is the base of the exponent in the condition $\mathbf{2}^{y+1} > x$ (notice the bold 2).

But we can define the logarithm for any base. For example, the decimal integer logarithm of $x$ is the smallest integer $y$ such that $10^{y+1} > x$.

In general, for any positive integer $a$, the $a$-ary integer logairithm of $x$ is the smallest integer $y$ such that $$a^{y+1} > x.$$

Next, we'll define this function.

In [ ]:
def ilog(x, a):
    """Finds the smallest integer y for which a ** (y+1) > x.
    Arguments: x (int), a (positive integer)
    Returns: (int)
    """
    # Your code here

check(ilog, 2, 2, 1)
check(ilog, 1, 2, 0)
check(ilog, 4, 2, 2)
check(ilog, 8, 2, 3)
check(ilog, 10, 2, 3)
check(ilog, 100, 2, 6)
check(ilog, 10, 10, 1)
check(ilog, 1, 10, 0)
check(ilog, 9, 10 , 0)
check(ilog, 100, 10, 2)
check(ilog, 215, 10, 2)
check(ilog, 3, 3, 1)
check(ilog, 4, 3, 1)
check(ilog, 9, 3, 2)
check(ilog, 10, 3, 2)

Question 2: Shall we play a game?

Let us introduce a "very fun" game called Guess The Number. There are two players: the Host and the Seeker. The game goes as follows:

  • The Host chooses a range of integers $[a,b]$ and a target integer $x$ in that range.
  • The Host tells the Seeker about the range $[a,b]$. The Seeker's goal is to find $x$.
  • In each turn, the Seeker chooses a number $y$. If $y = x$, the Seeker wins and the game is over. Else, the the Host tells the seeker whether $y$ is greater than $x$ or less than $x$.

Try playing the game by running the code below using different inputs.

In [ ]:
def seek(x, a, b):
    """Plays Guess The Number.
    Arguments: x (int), a (int), b (int)
    Returns: The number of rounds played (int).
    Effects: Prints dialogue between the Host and the Seeker.
    """

    if x > b or x < a:
        print("Invalid number!")
        return -1

    mid = (a + b) // 2

    print("Seeker: I choose", mid)

    if mid == x:
        print("Host: Exactly!")
        return 1

    if mid > x:
        print("Host: Too big!")
        return 1 + seek(x, a, mid-1)

    if mid < x:
        print("Host: Too small!")
        return 1 + seek(x, mid+1, b)

2.1

Let's play!

In [ ]:
x, a, b = 56, 1, 100
print(f"Host: Let's play! The range is [{a}, {b}].")
print(f"Seeker wins in {seek(x, a, b)} rounds.")

What are the left and right values for each of the 4 guesses made in guess(56,1,100) ?

In [ ]:
# Your answer here

2.2

That was so fun! Let's play again!

In [ ]:
x, a, b = 1, 1, 100
print(f"Host: Let's play! The range is [{a}, {b}].")
print(f"Seeker wins in {seek(x, a, b)} rounds.")

What are the left and right values for each of the guesses made in guess(1,1,100) ?

In [ ]:
# Your answer here

Here is an implementation of binary search using a while loop. Run this cell before continuing:

In [ ]:
def binarySearch(lst, x):
    """Finds x in a sorted list lst.
    Arguments: lst (list of ints), x (int)
    Returns: index of x in lst (int)
    Effects: Prints the number of iterations taken to find x.
    """
    cnt = 0
    left = 0
    right = len(a) - 1

    while left <= right:
        # print(f"left={left}, right={right}") # Question 3.2
        cnt += 1
        mid = (left+right)//2
        # print(f"Looking at {lst[mid]}") # Question 3.1
        if lst[mid] == x:
            break
        if lst[mid] > x:
            right = mid - 1
        else:
            left = mid + 1

    print("Number of iterations:", cnt)
    return mid


binarySearch([1, 2, 4, 6, 7, 10], 4)

3.1

What values of the array are looked at when searching for 10 in the list [−1,3,6,10,15]? You may uncomment a line in the above code to see if you are right (just be sure to re-run that cell).

In [ ]:
# Your answer here
In [ ]:
binarySearch([−1, 3, 6, 10, 15], 10) # If you would like to check your answer.

3.2

What values do left and right take when searching for 5 in the list [-1, 0, 1, 3, 5, 7]? You may uncomment a line in the above code to see if you are right (just be sure to re-run that cell).

In [ ]:
# Your answer here

3.3

What will happen if we run binarySearch([1, 9, 8, -1, 4, 11], 4)? Why does this not work? How would you fix it?

Question 4: isqrt() -- bigger, better, faster, binary-search-ier!

The integer square root of $x$ is the smallest integer $y$ such that $$ (y+1)^2 > x.$$

Here is an implementation of the integer square root function, similar to the one we saw in week 1.

In [ ]:
def isqrt(x):
    """Computes the smallest integer y such that (y + 1) ** 2 > x.
    Arguments: x (int)
    Returns: (int)
    """
    for y in range(x):
        if (y + 1) ** 2 > x:
            return y

4.1

Let's try to use our function to find the square root of a big number. Run the following cell.

In [ ]:
big_number = 14472334024676221 # 14,472,334,024,676,221
# isqrt(4)
isqrt(big_number)

While the cell is running, take a moment to reflect on this poem by Dick King-Smith:

Patience is a virtue,
Virtue is a grace.
Grace is a little girl
Who would not wash her face.

4.2

Whew, that was pretty awful! Luckily, we can speed things up using binary search.

You can think of computing the integer square root of $x$ as a search problem on the array $[0, 1, 2, ..., x]$. Our old implementation of isqrt() is doing linear search. However, since this array is sorted, we know that we can use binary search!

Wait a minute... Usually, we're used to using binary search to find a given (already-known) number; for example, find the index of $71$ in the array $[-3, 21, 35, 71, 101]$. But we don't know what the integer square root is yet! So we'll do things a bit differently.

Here is the pseudo-code for fast_isqrt(x):

  • Initialize variables low = 0 and high = x.
  • While low + 1 < high:
  • Let mid = (low + high) // 2.
  • If (mid + 1) ** 2 <= x:
    • Set low = mid.
  • Else:
    • Set high = mid.
  • Return low.
In [ ]:
def fast_isqrt(x):
    """Computes the smallest integer y such that (y + 1) ** 2 > x.
    Arguments: x (int)
    Returns: (int)
    """
    # Your code here

Now let's try again.

In [ ]:
fast_isqrt(big_number)

Much better! Let's celebrate with a tiny poem for our tiny runtime; this one is by Ogden Nash, and is title Fleas.

Adam
Had'em

Optional: Faster Logarithm

Optional.1

Use binary-search to speed up our implementation of ilog(x, a). Here is the pseudo-code.

  • Initialize variables low = 0 and high = x.
  • While low + 1 < high:
  • Let mid = (low + high) // 2.
  • If 2 ** (mid + 1) <= x:
    • Set low = mid.
  • Else:
    • Set high = mid.
  • Return low.
In [ ]:
def fast_ilog_binary(x):
    """Finds the smallest integer y for which 2 ** (y+1) > x.
    Arguments: x (int), a (positive integer)
    Returns: (int)
    """
In [ ]:
check(fast_ilog_binary, 2, 2, 1)
check(fast_ilog_binary, 1, 2, 0)
check(fast_ilog_binary, 4, 2, 2)
check(fast_ilog_binary, 8, 2, 3)
check(fast_ilog_binary, 10, 2, 3)
check(fast_ilog_binary, 100, 2, 6)

Optional.2

So you have a faster implementation of the binary integer logarithm. Fantastic! But does it matter? That is, can you find a number $x$ for which ilog_binary(x) takes a while (say, 30 seconds) to run, but fast_ilog_binary(x) is quick (say, under 1 second)?

In [ ]:
big_number = # Choose a big number
%timeit -r1 -n1 ilog_binary(big_number)
%timeit -r1 -n1 fast_ilog_binary(big_number)

1 loop, best of 1: 198 µs per loop

If you're punching in big numbers, then you'll probably notice that ilog_binary() (not the fast version) returns in under one second even for very large inputs.

Why do you think that is? Hint / answer: the number of iterations in ilog_binary() is proportional to the output. For example, since ilog_binary(2 ** 265) outputs 265, then only $\log_2(2^{265}) = 265$ iterations will be run in the function -- despite the fact that $2^{265}$ is more than the number of atoms in the universe!

Since the output is the integer logarithm of the input, we see that the logarithm of even really big numbers is still very small!

In [ ]:
# Your thoughts here