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ā.)