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