Thread: Wonka Factory Password

  1. #16
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  2. #17
    Registered User
    Join Date
    Dec 2017
    Posts
    945
    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
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  3. #18
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    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
    Last edited by Hodor; 12-19-2019 at 10:50 PM.

  4. #19
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Quote Originally Posted by john.c View Post
    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
    Last edited by Hodor; 12-19-2019 at 11:05 PM.

  5. #20
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  6. #21
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Yeah, the step I took after getting the brute force part working was to graph idx_offest (or whatever you've named it... maybe shift like the problem description?) and password. It become obvious to me, after graphing, how to calculate the password for any t after the pattern started. Calculating t = 5 billion was trivial after that

  7. #22
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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?
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  8. #23
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Spoke too soon, it's not working for other inputs. Hmm.

    Anyway, graphing seemed natural to me maybe because I'm a visual person. I'm trying to see a relationship between values that change over time and seeing the shape provides a quick way of visualising potential relationships. Here's a graph of the idx_offset and passcode after the pattern/state/oompaloompah-row starts to repeat (ignore the numbers along the x axis, they're meaningless).

    Wonka Factory Password-capture-jpg

  9. #24
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    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
    Last edited by Hodor; 12-28-2019 at 07:23 PM.

  10. #25
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    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
    Wonka Factory Password-capture-jpg

    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
    Last edited by Hodor; 12-31-2019 at 11:42 PM.

  11. #26
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Something to ponder (maybe)

    Input
    Code:
    initial state: ##
    With match patterns
    Code:
    ....#
    #....

    Passcodes (for 0 <= t <= 511)
    Code:
    1, 1, 2, 1, 2, 2, 4, 1, 2, 2, 4, 2, 4, 4, 8, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 8, 16, 16, 32, 16, 32, 32, 64, 16, 32, 32, 64, 32, 64, 64, 128, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 8, 16, 16, 32, 16, 32, 32, 64, 16, 32, 32, 64, 32, 64, 64, 128, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 8, 16, 16, 32, 16, 32, 32, 64, 16, 32, 32, 64, 32, 64, 64, 128, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 8, 16, 16, 32, 16, 32, 32, 64, 16, 32, 32, 64, 32, 64, 64, 128, 8, 16, 16, 32, 16, 32, 32, 64, 16, 32, 32, 64, 32, 64, 64, 128, 16, 32, 32, 64, 32, 64, 64, 128, 32, 64, 64, 128, 64, 128, 128, 256, 1, 2

  12. #27
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Ok, using the "##" starting state it looks like there is a pattern there (in addition to the obvious powers of 2)

    Wonka Factory Password-capture-jpg

  13. #28
    Registered User
    Join Date
    Dec 2017
    Posts
    945
    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.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  14. #29
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Quote Originally Posted by john.c View Post
    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.
    Hurts my head too

  15. #30
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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))
    Last edited by Zeus_; 01-02-2020 at 04:08 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 06-29-2014, 02:08 AM
  2. Replies: 2
    Last Post: 01-07-2009, 10:35 AM
  3. Question about the Factory pattern.
    By h3ro in forum C++ Programming
    Replies: 14
    Last Post: 11-27-2008, 04:55 PM
  4. Factory Functions HOWTO
    By GuardianDevil in forum Windows Programming
    Replies: 1
    Last Post: 05-01-2004, 01:41 PM
  5. Abstract Factory in C++
    By agrsaurabh in forum C++ Programming
    Replies: 1
    Last Post: 10-06-2003, 02:16 PM

Tags for this Thread