Challenge 19

Challenge 19.1


In [110]:
myinput = 3001330

In [111]:
def white_elephant(a):
    if a == 1:
        return 1
    elif a % 2 == 0:
        return (2 * white_elephant(a // 2) - 1)
    else:
        return (2 * white_elephant((a - 1) // 2) + 1)

In [112]:
white_elephant(myinput)


Out[112]:
1808357

One-line


In [113]:
f = lambda a: 1 if a == 1 else (2 * f(a // 2) - 1) if a % 2 == 0 else (2 * f(a // 2) + 1)

In [114]:
f(myinput)


Out[114]:
1808357

Challenge 19.2


In [115]:
import numpy as np

def slow_white_elephant(a):
    elves = np.array([i+1 for i in range(a)])
    l = a
    while l > 1:
        if l % 2 == 0:
            elves = np.delete(elves, l // 2)
            elves = np.roll(elves, -1)
        if l % 2 == 1:
            elves = np.delete(elves, (l-1) // 2)
            elves = np.roll(elves, -1)
        l = l-1
    return elves[0]

In [116]:
%%time
slow_white_elephant(10000)


CPU times: user 280 ms, sys: 4 ms, total: 284 ms
Wall time: 283 ms
Out[116]:
3439

A bit too slow... let's implement a better one!


In [117]:
def fast_white_elephant(a):
    elves = np.array([i+1 for i in range(a)])
    l = a
    while l > 1:
        if l == 2:
            return elves[0]
        elif l % 2 == 0:
            deleter = [(l // 2) + i for i in range(l // 2) if i % 3 != 2]
        else:
            deleter = [(l // 2) + i for i in range((l + 1) // 2) if i % 3 != 1]
        elves = np.delete(elves, deleter)
        dels = len(deleter)
        elves = np.roll(elves, -dels)
        l -= dels
    return elves[0]

In [118]:
%%time
fast_white_elephant(10000)


CPU times: user 8 ms, sys: 4 ms, total: 12 ms
Wall time: 12.4 ms
Out[118]:
3439

Result

It seems a bit faster!


In [119]:
fast_white_elephant(myinput)


Out[119]:
1407007