Thread: Wonka Factory Password

  1. #31
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Where did you get it?
    Does it seem to work?
    How long does it take to solve the original problem?
    Does it work on other input?
    It looks like it uses a tremendous amount of memory!
    A little inaccuracy saves tons of explanation. - H.H. Munro

  2. #32
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by Zeus_ View Post
    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:
    
    

    That does exactly the same as my solution and uses a linear formula once a cycle (repeat) is detected.

    It doesn't work for the more general case (e.g. john.c's example; just tested to confirm). I expect the problem cannot be solved in the more general case, because for (e.g.)

    Code:
    initial state: ##
    2
    64
    ....#
    #....
    0
    ... starting with this state and using those patterns 2 standing and 2 sitting oompahs will be added to the start and end of the state for each iteration and therefore a cycle cannot occur in the state.

    If that's an official solution then they only want the problem solved for special case inputs where the state does cycle and if that's the case I guess the problem is solved. They could have stated that in the problem description if that's the case though (something like "we will only give the program inputs that we know will lead to a cycle, your program may give up if a cycle is not detected less than t=100000") :/

  3. #33
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    That python solution solves the same two special cases where cycles occur the the sub-cycles are also linear (that's what the remainder stuff is for... same as mine y=mx+c to get to the start of the cycle and then same linear for the remainder the bit within the cycle.


    That works fine when the cycle is a simple "step" like this:

    Wonka Factory Password-capture-jpg

    where the bit between the cycles in linear as well but it fails when the bit between cycles is not linear.

    For example:
    Code:
    initial state: #..#.#..##......###...###
    105
    4140
    ...##
    ..#..
    .#...
    .#.##
    .##..
    .####
    #.#.#
    ###..
    0
    My code fails on that, and so does the Python code. But it does cycle (starting at t=45 to t=49). The graph for that input looks like below. Both my code and the python code work if 't' is evenly divisible by the cycle length (t2 - t1), but otherwise my code and the python code both fail even though there the pattern does cycle (the passwords in between the cycle length, the sub cycles, are not linear). I suspect that if that's the official answer they only want it to work in very limited situations (where the cycle and sub-cycle are both linear)

    Wonka Factory Password-capture-jpg
    Last edited by Hodor; 01-02-2020 at 11:43 PM.

  4. #34
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    I think the Python solution was from one of the student teams that submitted the solution. Yes, it doesn't work as you mention. I tried doing different things too, and matched with my brute force implementation. The Python code seems to be working only if certain conditions are satisfied, like you mention. It just feel bad that the problem statement is not well described, solution on their website is wrong and that I've spent quite a lot of time thinking about it for nothing....
    "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

  5. #35
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    It takes about 3 seconds on my laptop.
    Nah, it doesn't work on all kinds of inputs.

    CodeWars - Sample Problems
    HP CodeWars 2020
    "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. #36
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by Zeus_ View Post
    It takes about 3 seconds on my laptop.
    Nah, it doesn't work on all kinds of inputs.

    CodeWars - Sample Problems
    HP CodeWars 2020
    It doesn't seem to work on lines with decreasing slope either. I'd made a post (because I found the sample input data) but deleted it because I realised that /my/ program might be calculating the password wrong, but I can't see how. Removing just the last pattern of prob29.txt I get

    Original (my program matches the Python)
    Code:
    initial state: ###..##.#.#.##.##.#####..####.#.##.....#..#.#.#...###..#..###.##.#..##.#.#.....##..#####.#.#.##....#
    2389
    48039
    .###.
    ..##.
    #.###
    .#..#
    .#.##
    .####
    ####.
    ##...
    ###..
    #.##.
    #..##
    ...#.
    ..#.#
    ..#..
    .#.#.
    0
    Removing the last line of patterns:
    Code:
    initial state: ###..##.#.#.##.##.#####..####.#.##.....#..#.#.#...###..#..###.##.#..##.#.#.....##..#####.#.#.##....#
    837
    -8213
    .###.
    ..##.
    #.###
    .#..#
    .#.##
    .####
    ####.
    ##...
    ###..
    #.##.
    #..##
    ...#.
    ..#.#
    ..#..
    0
    The Python program fails

    Code:
      File "./oomp.py", line 85, in <module>
        raise Exception('{} failed. expected = {}. actual = {}.'.format(val, expected, actual))
    Exception: 1000 failed. expected = -8213. actual = -16994.
    There are two possibilities here: a) my function to calculate the passcode, which I used to get 837 and -8213, is wrong; or b) the Python program is wrong. Can't really tell which because for trends with increasing/positive slope I get identical results.

    Either way, I think the problem is as solved as it can be. I can add a vector of slopes for the sub-cycle case and solve for the graph given in post #33, but if the goal is only to solve 2 specific special cases, why bother? My program gives the correct result for the input given in the problem description and for the input given in prob29.txt so I consider it done :P They really should say that they only want answers for specific inputs

    My function for calculating the password if given a state string and offset. If there's a mistake then please correct me. If there's not then the Python in the solution has a bug. I'm happy either way

    Code:
    long makePass(const std::string& state, long offset)
    {
        long index = offset;
        long pass = 0;
        for (char ch: state) {
            if (ch == '#') pass += index;
            index++;
        }
        return pass;
    }

  7. #37
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Times for prob29.txt

    Python
    Code:
    $ time python3 oomp.py 
    1874
    48087
    2400000000039
    
    real    0m0.032s
    user    0m0.029s
    sys     0m0.003s
    C++
    Code:
    $ time ./oompa 
    1874
    48087
    2400000000039
    
    real    0m0.002s
    user    0m0.002s
    sys     0m0.000s
    Pity that didn't specify US or SI billion. Pity about a lot of things really haha. Anyway, I'm calling it done

  8. #38
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by Zeus_ View Post
    It takes about 3 seconds on my laptop.
    Nah, it doesn't work on all kinds of inputs.
    I actually wouldn't mind if it didn't work on all inputs. But I kind of expected it to work on all inputs that end up repeating the state. Oh well, just expecting too much I guess

  9. #39
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    @Zeus_ Just for reference, I was lying in bed last night half asleep and it occurred to me that there might be a similar problem to this wonka thing described in GEB.

    Godel, Escher, Bach - Wikipedia

    I can't be sure there is something similar in there though because I can't find my copy. But certainly the "theme" is the same. A damn oompa loompah has stolen my copy of the book I expect.

    Anyway, even if there is not a similar problem in that book you should probably grab a copy from the library (or buy one) if you're interested in algorithms, maths, problem solving and stuff. It's fun to read as well

  10. #40
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Thanks for the reference! I'll look it up at the school library tomorrow (I doubt that I will find it). Yes, I'm interested in algos and math (math is my favourite subject i.e. people who have no lives if you ask someone at my school), good guess, but I refer to a different book that I have. I'll read what Wiki has got for now.
    "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

  11. #41
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    I just noticed that the python code is calculating the offset using a linear equation, rather than the passcode like I do in my solution, which is why it uses that remainder calculation. The offset is messier to calculate compared to just calculating the password -- graph the changing values of offset using the input from the problem description to see what I mean; offset it stepped while password is completely linear

  12. #42
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    @Hodor, I'll be ordering the book you mentioned above in post #39. Is it this Buy Godel, Escher, Bach: An Eternal Golden Braid Book Online at Low Prices in India | Godel, Escher, Bach: An Eternal Golden Braid Reviews & Ratings - Amazon.in ?

    Checked at the school library and couldn't find it. Thought it'd be better to just buy it instead.

    Also, do you know of any app I could download on my laptop to help me improve my typing speed? Like a tutor sort of thing with courses for various finger placement techniques that I can use without being online (I should probably try coding one myself as a project soon). I'm averaging out at 45-50 WPM but I'd like to see how much I can push my max to with practice.
    "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

  13. #43
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by Zeus_ View Post
    @Hodor, I'll be ordering the book you mentioned above in post #39. Is it this Buy Godel, Escher, Bach: An Eternal Golden Braid Book Online at Low Prices in India | Godel, Escher, Bach: An Eternal Golden Braid Reviews & Ratings - Amazon.in ?

    Checked at the school library and couldn't find it. Thought it'd be better to just buy it instead.

    Also, do you know of any app I could download on my laptop to help me improve my typing speed? Like a tutor sort of thing with courses for various finger placement techniques that I can use without being online (I should probably try coding one myself as a project soon). I'm averaging out at 45-50 WPM but I'd like to see how much I can push my max to with practice.
    Yeah, that's the book

    I don't know of any typing apps unfortunately

  14. #44
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Cool, thanks, just placed the order. Will arrive by tomorrow.
    "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

  15. #45
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by Zeus_ View Post
    Cool, thanks, just placed the order. Will arrive by tomorrow.
    That quick?! Wow, cool. Every now and then you read something that changes your outlook on things. I can't promise that the book will do that for you, but it did for me. I hope you enjoy it

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