https://www.codingame.com/training/medium/photo-booth-transformation
Send your feedback or ask for help here!
Created by @Niako,validated by @JBM,@selenae and @BenjaminUrquhart.
If you have any issues, feel free to ping them.
A most interesting puzzle, once again seems to me more math than coding!
I am wondering if there is a closed math formula for the answer. I avoided full simulation and greatly reduced computation cost with a math-based consideration, but still the 2 building blocks (partial answers) of my solution are coming from a simple simulation code. For specific inputs (powers of 2) I have a closed formula but not for the others.
(If I sound a bit cryptic, it is because I don’t want to fully spoiler my solution here.)
So, can the cycle-finding simulation be avoided completely?
1 Like
Finished it long time ago. Reviewing my answer, it was 100% maths. I wrote a v1 solution by simulation (relatively easy) to produce sample outputs, from which I spotted the pattern. I wrote a v2 solution to calculate the answers by maths operations, then a v3 solution with a more succinct maths algorithm. There was roughly 50 lines of code in Java.
1 Like
@TBali My official solution answers to all that. As it was only in Python, I’ve just published a PHP version that you can check out.
1 Like
Thanks! From your 3 solutions, I found the second one (and skipped the brute). The 3rd one is the best, this is what my original question was referring to. In restrospect, I think I was so close, but did not figure it out correctly.
Lovely puzzle. A few test with ~1000000 width and height would have been real fun and challenging. 