Thread: Wonka Factory Password

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302

    Wonka Factory Password

    http://www.hpcodewars.org/past/cw22/...ProblemSet.pdf

    Hey, so I revisited a few problems I'd left while I was solving this question set last time and I'm stuck at prob29 - Wonka Factory Password.

    How would you guys attempt to solve this @john.c and @Hodor (I mention you guys because of the interest in the ProjectEuler question you showed in one of the other threads)?

    I initially just used strings and tried solving the problem but the solution is inefficient and hard-coded, something most people can do. If you've read the question, you'll see the "At some point during the iterations, you will find that the pattern repeats but is shifted from aprevious state. Once you find this, you can predict mathematically what the final state will be. Going through the process above 50 billion times without using this shortcut will take a very long time. Your program will be marked as a PASS if it takes less than 1 minute." Well, I haven't been able to figure any mathematical hack just yet so maybe y'all can help with that. I'd like to come up with a logic with the help of you guys that I can then code out.

    I'm thinking about a different solution, something along the lines of using bits, every . is 0 and # is 1 and then try and do something with that but that's about it for my thinking. I don't know how I'd proceed further from here.....

    Thanks for your time and help!
    Last edited by Zeus_; 12-16-2019 at 11:44 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

  2. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    I'm actually having trouble understanding the problem description, probably because I have the oompa loompa song stuck in my head I'll read it again when I get home

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    @Zeus_ did you try the example solution given at the bottom? All my rows appear to be the same except for t = 20

    Code:
    ..#....##....#####...#######....#.#..#..  (my t = 20)
    ..#....##....#####...#######....#.#..##. (from PDF)
    Edit: I think I'm missing something because even doing it by hand I can't see how they went from t=19 to t=20 and ended up with the extra # near the end

    Nevermind, I have to add padding if necessary for every step. Is that correct? They're not showing it in their example output... weird
    Last edited by Hodor; 12-16-2019 at 11:42 PM.

  4. #4
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    I've tried a tonne of stuff but I'm definitely blundering somewhere because I get the correct results for some values and get wrong ones for some other values. I'm going to scrap my current code because it's inefficient af, uses 8 bits for what can be done with 1 bit, takes about 27:38 minutes for 50 million iterations and misses the correct value by 20011487. It does produce correct password value for time 11 and 12 but it's still wrong if you look closely at the pattern it produces, definitely missing something. It's missing the correct value of time 20 by 38. For time 1001, I get value 854 which is indicative that the parsing is defo wrong.I'll rework on a new solution when I find time again but for now this is what I've got from my last attempt at it spending about 19 minutes:

    Wonka Factory Password-prob29-jpg

    > Nevermind, I have to add padding if necessary for every step. Is that correct?

    Yep. But I'm not sure that you have to remove padding if you have something like "......#" and make it "....#". Because the question says: "Pad the current state with periods until you have ....# at the beginning of the line and #.... at the end. Keep track of index number.....so on. Does it mean I need to remove the extra periods, if any, and get to ....# because that's what my current padding code does or does it mean I should do nothing if its something like .........#?
    Last edited by Zeus_; 12-17-2019 at 04:36 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

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Yeah, I was thinking about this on the way home and I think that I can just add padding even if it's not necessary (e.g. just always add "...." to the start and end of the string regardless and remove it later). I think that should work because the main thing is the "offset" (can't think of a better term) where index 0 is. I think that might work. I also put some thought (yes, my drive home is long lol) into representing things as a number, as you suggested, rather than a string but I tentatively concluded that doing that might actually make the pattern matching harder because of leading zeroes. I haven't discarded the idea, but what I would like to do first is get it working for the first 1001 generations so that I can see if a pattern emerges in either the pattern itself or the "password" for each generation.

    My current output is (generation, string, "password") but I have to fix the padding issue -- haven't had time yet. 19 generations is not enough for me to see a pattern so I'll have to get the padding working. Since the "password" increases over time I believe the offset must also increase and maybe the pattern is there, but I'll wait and see

    Code:
    t =    0,"....#..#.#..##......###...###...........",145
    t =    1,"....#...#....#.....#..#..#..#..........",91
    t =    2,"....##..##...##....#..#..#..##.........",132
    t =    3,"...#.#...#..#.#....#..#..#...#.........",102
    t =    4,"....#.#..#...#.#...#..#..##..##........",154
    t =    5,".....#...##...#.#..#..#...#...#........",115
    t =    6,".....##.#.#....#...#..##..##..##.......",174
    t =    7,"....#..###.#...##..#...#...#...#.......",126
    t =    8,"....#....##.#.#.#..##..##..##..##......",213
    t =    9,"....##..#..#####....#...#...#...#......",138
    t =   10,"...#.#..#...#.##....##..##..##..##.....",213
    t =   11,"....#...##...#.#...#.#...#...#...#.....",136
    t =   12,"....##.#.#....#.#...#.#..##..##..##....",218
    t =   13,"...#..###.#....#.#...#....#...#...#....",133
    t =   14,"...#....##.#....#.#..##...##..##..##...",235
    t =   15,"...##..#..#.#....#....#..#.#...#...#...",149
    t =   16,"..#.#..#...#.#...##...#...#.#..##..##..",226
    t =   17,"...#...##...#.#.#.#...##...#....#...#..",170
    t =   18,"...##.#.#....#####.#.#.#...##...##..#..",247
    t =   19,"..#..###.#..#.#.#######.#.#.#..#.#..#..",286
    Edit, t = 3 and 13 to 18 are probably wrong because of the padding issue but interestingly t = 19 is nevertheless correct
    Last edited by Hodor; 12-17-2019 at 05:25 AM.

  6. #6
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Quote Originally Posted by Zeus_ View Post
    Does it mean I need to remove the extra periods, if any, and get to ....# because that's what my current padding code does or does it mean I should do nothing if its something like .........#?
    My hunch is that if the value "offset" (see my last post) is maintained then, yes, leading and trailing dots can be removed to calculate the password, but another 4 leading and trailing dots added back to generate the next generation. I actually don't think it would matter if there was 15 (or whatever, so long as >= 4) leading or trailing dots so long as the offset position (of where 0 is) is tracked. It wouldn't make a difference, as far as I can currently see. So, when I get back to this (tomorrow I hope) I'll probably add four dots to the start and the end of the string -- doesn't matter, I don't think, if there ends up being more than 4 leading/trailing dots -- regardless of where the first and last '#' are and discard them afterwards.

    I.e. I think that the idea here is that there is a moving/sliding "window" of values (and offset will increase, but that's just a guess)

    Edit (again): Actually converting the string to a binary representation is probably a good idea after all. Can then look at if there is a pattern in the base-10 representation of the string (rather than the "password"), but I'll probably do that in addition to manipulating strings just to see if there is a pattern there
    Last edited by Hodor; 12-17-2019 at 05:29 AM.

  7. #7
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    The padding is definitely necessary as far as I see because you may always have a sub-pattern in input that's something like "....." or "....#" or "#...." (those 5 character patterns) which will then affect your CurrentState string for the next generation and make it "..#.." and then you'd need to pad again. When a submission is made they do check with other massively sized input files to check the efficiency of the underlying algorithm.

    I get all values same as yours till generation 12 but it's pretty much wrong everywhere else (the patterns in mine get messed up from generation 4 itself but it doesn't make a difference until a little while longer in "Password" because there are no standing Oompa Loompas before the offset of index zero that's get added as negative indices).

    Edit: Would you mind PMing me your current code using strings so I can compare it with mine and check what I'm missing that produces the faulty States?
    Last edited by Zeus_; 12-17-2019 at 08:07 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

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    943
    I didn't see this until now. Why is it in "general discussion"? I never look here. It should be in the C forum.
    Anyway, I'll give it a shot.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  9. #9
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    Oompa Loompas do not come under C/C++ so thought it'd be better off in general discussions
    And more importantly, I'm not trying to get help with the code or anything, just want a way to work a logic out with the help of y'all. The problem description is pretty trash (Hodor agrees). Thanks for taking part!
    Also, you can use the "What's New" tab to see the latest threads.
    "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

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    943
    You're not kidding about the problem description. So far with a simple brute-force solution I can get the right answer for 12 and 20, but not 1001.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  11. #11
    Registered User
    Join Date
    Dec 2017
    Posts
    943
    Just got the correct answer for 1001.
    Anyone want to compare answers for 10001 ?
    I'll turn on PM. Send me your answer.

    And it looks like you don't need to use bits since the pattern is already repeating at this point.
    Last edited by john.c; 12-17-2019 at 11:37 AM.
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,776
    Quote Originally Posted by john.c
    I didn't see this until now. Why is it in "general discussion"? I never look here. It should be in the C forum.
    We uh, never did have a forum properly designated for general programming discussion that did not have a particular language, platform, or area as its focus. So on one hand General Discussions is not the right place because it isn't supposed to be for programming; on the other hand the C programming forum is also not the right place because someone could approach this using say... the Go programming language.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    Your PMs still seem to be turned off....
    Would you mind sharing your brute force method so I can compare with my brute force method and find what I'm doing wrong that you are not? Thanks!

    Also, my answer at time 1001: 19394
    at time 10001: 199394

    EDIT:

    Wonka Factory Password-prob29-jpg

    Nevermind, something is still wrong as my output is now 331 instead of 325 for time 20. Can't figure out what's missing.... if I change code somewhere something else gets messed up. After the current changes I made to my code, I've got the most accurate results tho, better than all my previous outputs. Except for one time generation all my other values are correct. I think we can now try and figure out the mathematical hack that the question mentions and develop an algo that is not brute force.
    Last edited by Zeus_; 12-18-2019 at 06:34 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

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,058
    I always thought the "Tech board" was for stuff that wasn't programming language specific, but was rather more interesting than water cooler wibble of general discussions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  15. #15
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    @Zeus Sorry I haven't gotten back to this yet, but with Christmas so close things have been very hectic. Hopefully this evening (about 8 hours from now) will leave me a small window of opportunity to get back to it. Although I haven't written code, in my head the padding is just so that the pattern matching part works and I can see that it'll work, once I pad, for at least t=20 just by glancing at it.

    Edit: 331 instead of 335 might just be because you're not moving your "offset" (or whatever you call it) of index 0 properly, if you're using the same approach as me... it kind of sounds like you are. My PMs are turned on if you need to send spoilers

    I dunno which sub-forum board I'd place this under either. Doesn't seem too bad here because it's general problem solving and probably isn't the best language to be solving this in either. Once the pattern is found maybe I'll switch to Excel

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