Thread: Wonka Factory Password

Hey, no problem at all. Feel free to get back to it whenever you can, there's no hurry. I think we've all got brute force algos working but the key here would be finding the pattern of repetition and optimising the algorithm. Brute force is probably O(N^2) for all of us or maybe O(N^log(N)) but neither of us have implemented the optimal required solution of doing the 50 billion iterations in less than a minute so I think we can start working on that. I could take this question to a CP forum for help but the reason why I post here is because I've become accustomed to the people here and I find discussing things here more valuable than elsewhere.

Also, I've fixed my code. I realised there was a problem with my padding loop at the end of the string. I'm getting all correct values for the sample input cases provided. I'm waiting on john to see if our time 10001 values match. If that's positive, we'll all be on pretty much the same page to discuss what the "hack" is.

I turned my PMs on all day Tuesday and nobody got back to me. With the addition of no activity here, I lost interest. Toss in a pos like ivory and I'm losing interest in these forums in general.

Anyway, remember to try different inputs. I found this one interesting:

Code:

initial state: #........#
36
1152
....#
#....
0

Finally got a chance to look at it. Pretty sure mine is working now (I get the correct values for t = 325 and 1001 at least). The rest... I'm not sure if I should post it here. @john.c can you PM me your values for t = 10001 and 100001? I tried to PM you but I can't I don't want to paste the values here because if my brute force is correct the pattern I'm getting is pretty clear once you get above t = 1000

Originally Posted by john.c

I turned my PMs on all day Tuesday and nobody got back to me. With the addition of no activity here, I lost interest. Toss in a pos like ivory and I'm losing interest in these forums in general.

Anyway, remember to try different inputs. I found this one interesting:

Code:

initial state: #........#
36
1152
....#
#....
0

Yeah that one is interesting... I think my password is overflowing after t = 2001.

Code:

idx_offset     0 t =     0,  passcode = 9
idx_offset    -2 t =     1, passcode = 18
idx_offset   -22 t =    11, passcode = 54
idx_offset   -24 t =    12, passcode = 36
idx_offset -2002 t =  1001, passcode = 1152
idx_offset -4002 t =  2001, passcode = 1152
idx_offset -6002 t =  3001, passcode = <redacted>
idx_offset -8002 t =  4001, passcode = <redacted>
idx_offset -10002 t =  5001, passcode = <redacted>
time passes...
idx_offset -20002 t = 10001, passcode = <redacted>

Edit: Actually it wasn't overflowing... signed vs unsigned problem. Fixed now

This is what I've got for john's test case. It's interesting to see definitely. I was doing many simple test cases to come up with a binary math equation to predict the value at any time given the password at t = 1. Haven't come up with anything solid yet. Also, this problem always keeps me stuck and makes me want to come back to it repeatedly so I only have been able to practice 7 other problems in the last two days

Code:

t =      1 :       18 00000000000000000000000000010010
t =      2 :       18 00000000000000000000000000010010
t =     11 :       54 00000000000000000000000000110110
t =    101 :      108 00000000000000000000000001101100
t =   1001 :     1152 00000000000000000000010010000000
t =   2001 :     1152 00000000000000000000010010000000
t =   3001 :     2304 00000000000000000000100100000000
t =   4001 :     1152 00000000000000000000010010000000
t =   5001 :      576 00000000000000000000001001000000
t =  10001 :      576 00000000000000000000001001000000
t = 100001 :     1152 00000000000000000000010010000000

Really, graphing gave a solution? That's probably the last thing I would have thought about if I were you lol. Thanks for the idea. I'll do the same and see what I can arrive at. I think it makes sense when you think of the problem. An average programmer like myself will try and find some sort of way to relate it to binary form (I say this because I asked two of friends interested in CP to solve the problem and they too arrived at the "think of a binary form equation" after testing brute force). Not many would think to graph things like that or it's probably just because we aren't very experienced yet and haven't practised many problems of this type. This may not be the only way though, right?

I had another quick look at this and my solution seems to work for all patterns that start repeating (with the only the shift value changing). I don't know if all inputs will produce a repeating pattern though; some appear not to. My other source of uneasiness is that I tried to prove, mathematically, that if the pattern does repeat then the password is linear but couldn't. So, my solution might work -- it does for the 6 or so inputs that I tested at least -- but I don't know why.

I guess that I'm not satisfied because I can't work out what's going on and "how"/"why" it becomes linear. It's a pity that there is no discussion or analysis that you can look at after producing the answer like you can on Project Euler

I had some time free this afternoon so I thought I'd give this another shot. Given john.c's example input, for 1 <= t < =10000 nothing repeats and I can't see a pattern except that "offset" is linear, but offset growing linearly is not surprising given the input and not helpful. For the less general case, where the pattern does enter a cycle (but the cycle may have a period > 1) , I've amended my solution and it works... but for the more general case where it seems unlikely that the pattern will hit a cycle quite quickly it doesn't work. I have a gut feeling that john.c's input will not repeat/cycle but cannot prove it. The graph for the input john suggested to try is below. It's possible there is a pattern there for the passcode, but what it is... I have no idea. So, for now I'm going to admit defeat. I'd really love to know more about this. Maybe one day

Graph for

Code:

initial state: #........#
36
1152
....#
#....
0

oops... ignore the blue line... that's just t (i.e. same as the x-axis). Didn't mean to add that to the graph

I do find it interesting that the passcode repeats (there probably is a pattern there but I cannot recognise it)

First few passcodes (for that example above)

Code:

9, 18, 18, 27, 18, 27, 36, 27, 18, 36, 36, 54, 36, 45, 72, 27, 18, 36, 36, 54, 36, 54, 72, 54, 36, 72, 72, 108, 72, 81, 144, 27, 18

I got that exact same graph. It continues like that forever (at least out to a million).
It's a fractal-like pattern.
But even if we solve this one, what other kinds of patterns can arise?
It hurts my head.

I found a solution to the problem in Python, although I don't understand the language much and find it weird. I feel that my choice of C/C++ at school was a good decision.
This works, but I don't see what makes it fast. Will try converting code to C++ and try understanding it while doing so. Will hopefully learn a bit of Python too.

Code:

# !/bin/python3

import sys

def get_bare_oloompas(oloompas):
    offset = oloompas.find('#')
    return oloompas[offset:oloompas.rfind('#') + 1], offset

def parse(data):
    oloompas, offset = get_bare_oloompas(data[0].split()[-1])
    results = {11: int(data[1]), 1000: int(data[2])}
    notes = [d.strip() for d in data[3:-1]]

    return results, oloompas, offset, notes

def age_oloompas(oloompas, notes):
    oloompas = '....' + oloompas + '....'
    new_oloompas = ''
    for i in range(2, len(oloompas) - 2):
        if oloompas[i-2:i+3] in notes:
            new_oloompas += '#'
        else:
            new_oloompas += '.'
    oloompas, offset = get_bare_oloompas(new_oloompas)
    return oloompas, offset - 2

def get_offset(first, last, rounds, results):
    offsets = [val['offset'] for val in results.values() if first <= val['index'] <= last]
    return sum(offsets) * rounds

def get_repeat_count(curr_gen, gens, curr_oloompas, curr_offset, results):
    gens_left = gens - curr_gen

    first_oloompa = results[curr_oloompas]
    last_oloompa = max(results.values(), key=lambda p: p['index'])

    if first_oloompa == last_oloompa:
        rounds = gens_left
        remainder = 0
    else:
        round_len = last_oloompa['index'] - first_oloompa['index']
        rounds = gens_left // round_len
        remainder = gens_left % round_len
    result_index = first_oloompa['index'] + remainder

    for val in results.values():
        if val['index'] == result_index:
            result_oloompas = val
            break

    previous_offset = min([val for val in results.values() if val['oloompas'] == curr_oloompas], key=lambda p: p['index'])['offset']
    rounds_offset = last_oloompa['offset'] - previous_offset
    remainder_offset = result_oloompas['offset'] - previous_offset
    curr_offset += (rounds_offset * rounds) + (remainder_offset * remainder)

    return sum(i for i, val in enumerate(result_oloompas['oloompas'], start=curr_offset) if val == '#')

def age_gens(oloompas, offset, notes, gens):
    results = {}
    for i, _ in enumerate(range(gens), start=1):
        if oloompas in results:
            return get_repeat_count(i-1, gens, results[oloompas]['oloompas'], offset, results)
        new_oloompas, oloompa_offset = age_oloompas(oloompas, notes)
        offset += oloompa_offset
        results[oloompas] = {'index': i, 'oloompas': new_oloompas, 'offset': offset}
        oloompas = new_oloompas
    return sum([i + offset for i, val in enumerate(oloompas) if val == '#'])

if __name__ == '__main__':
    with open("prob29.txt") as f:
        data = f.readlines()
    results, oloompas, offset, notes = parse(data)

    for val, expected in results.items():
           actual = age_gens(oloompas, offset, notes, val)
           if expected != actual:
               raise Exception('{} failed. expected = {}. actual = {}.'.format(val, expected, actual))

    for val in [12, 1001, 50000000000]:
           print(age_gens(oloompas, offset, notes, val))