[Community Puzzle] Jumping Frog

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @clxm,validated by @Dyd,@OHER and @Achess.
If you have any issues, feel free to ping them.

The puzzle is intersting but the validators are a bit too tailored to work with the expected cut.
It’s easy to create small validators that make the expected cut fail, for example this one:

5
##..#
####.
####.
####.
##..#
0
0

makes the author’s solution timeout (and this kind of validator would be hard to deal with, it probably requires a bridges study to make proper cuts).

2 Likes

Indeed, always “funny” to see a clearly NP-hard problem labeled “medium”. The goal is to guess in which way the test cases are not general enough to allow finding an answer quickly. Even “funnier” here, where the reason is not the same in the visible test cases (where the Full 3x3 is small enough to allow the general solution to work) and in the validator (where the case of easily jumping everywhere can be used to shortcut, but as you’ve shown this is a very special situation).

Also, again as you stated, with a max size of 15x15, it is probable that there cannot be that many bridges, so that solving on each component once the order in which the bridges are “burnt” is decided may work in many more cases, possibly even always. But that’s definitely no longer in the “medium” ballpark…

Beware: only the last validator has more than 64 lilies.
(My original solution used a single int64 as bitboard to track the visited lilies, trying to avoid having to copy a larger data structure during the search such as a proper ‘set’.)