Thread: 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!

@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

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:



> 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 .........#?

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

Originally Posted by Zeus_

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

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?

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.

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.

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.

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.

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.

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:



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.

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.