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.

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.