1. 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!

2. Originally Posted by Zeus_
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. 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:
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)

4. 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....

5. It takes about 3 seconds on my laptop.
Nah, it doesn't work on all kinds of inputs.

CodeWars - Sample Problems
HP CodeWars 2020

6. Originally Posted by Zeus_
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. 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. Originally Posted by Zeus_
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. @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. 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.

11. 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. @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.

13. Originally Posted by Zeus_
@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. Cool, thanks, just placed the order. Will arrive by tomorrow.

15. Originally Posted by Zeus_
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