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!
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
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.)
... 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.Code:initial state: ## 2 64 ....# #.... 0
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") :/
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:
where the bit between the cycles in linear as well but it fails when the bit between cycles is not linear.
For example:
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)Code:initial state: #..#.#..##......###...### 105 4140 ...## ..#.. .#... .#.## .##.. .#### #.#.# ###.. 0
Last edited by Hodor; 01-02-2020 at 11:43 PM.
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
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
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)
Removing the last line of patterns:Code:initial state: ###..##.#.#.##.##.#####..####.#.##.....#..#.#.#...###..#..###.##.#..##.#.#.....##..#####.#.#.##....# 2389 48039 .###. ..##. #.### .#..# .#.## .#### ####. ##... ###.. #.##. #..## ...#. ..#.# ..#.. .#.#. 0
The Python program failsCode:initial state: ###..##.#.#.##.##.#####..####.#.##.....#..#.#.#...###..#..###.##.#..##.#.#.....##..#####.#.#.##....# 837 -8213 .###. ..##. #.### .#..# .#.## .#### ####. ##... ###.. #.##. #..## ...#. ..#.# ..#.. 0
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.Code:File "./oomp.py", line 85, in <module> raise Exception('{} failed. expected = {}. actual = {}.'.format(val, expected, actual)) Exception: 1000 failed. expected = -8213. actual = -16994.
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; }
Times for prob29.txt
Python
C++Code:$ time python3 oomp.py 1874 48087 2400000000039 real 0m0.032s user 0m0.029s sys 0m0.003s
Pity that didn't specify US or SI billion. Pity about a lot of things really haha. Anyway, I'm calling it doneCode:$ time ./oompa 1874 48087 2400000000039 real 0m0.002s user 0m0.002s sys 0m0.000s
@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
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
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
@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
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