search

thewca / tnoodle-lib

scrambling code portion of TNoodle
GNU General Public License v3.0
39 stars 15 forks source link

Implement optimal SQ-1 solver based on recent `sq12phase` changes #5

Closed gregorbg closed 4 years ago

gregorbg commented 4 years ago

Square-1 is now using the optimal solver as backend, thanks to the lightning-fast fixes from @cs0x7f :)

Requesting review from experienced people because this roots deep into the solver

gregorbg commented 4 years ago

Come to think of it, I don't need to alter the test cases. But now there's an added layer of complexity in order to make sq1 states "slashable" for min2phase to process.

cf https://github.com/cs0x7f/sq12phase/issues/5

gregorbg commented 4 years ago

Maven has whitelisted more IPs in the hopes of resolving Travis issues. Rebuilding.

gregorbg commented 4 years ago

Ping email sent; merging in T-72 hours if there are no further comments or reviews.

gregorbg commented 4 years ago

@viroulep I have refactored the cost maps to carry more intuitive (and less frightening) names.

The glob import seems to be common practice for java.util if you import > N classes, where N is a treshold usually between 5 and 7. I expect this won't be a problem since it's unlikely we will ever create a class that collides with a name found in java.util.

The "leftover" comment may or may not be required, depending on what peoples' tastes are regarding https://github.com/thewca/tnoodle-lib/pull/5#discussion_r376738143

Testing is already performed in an extensive manner over at HugeScrambleTest.java (hence the name). It tests both scramble filtering and the solveIn methods, so if these tests pass there is really nothing to worry about.

viroulep commented 4 years ago

Thanks for the quick fix and detailed explanation!

The glob import seems to be common practice for java.util if you import > N classes, where N is a treshold usually between 5 and 7. I expect this won't be a problem since it's unlikely we will ever create a class that collides with a name found in java.util.

In general I wouldn't worry too much about that indeed, it's just not very nice to throw the whole java.util at the compiler ^^ But yeah I was just wondering about the common practice.

gregorbg commented 4 years ago

Merging due to lack of substantial feedback (and all deadlines long having passed). Welcome SQ1 to the family of reasonably fast solvers!

viroulep commented 4 years ago

Could you describe a bit what was the "quirk" you mentioned in the last commits? Even reading the tests I have trouble understanding what was the wrong behavior compared to the expected one.

gregorbg commented 4 years ago

Sure! The AlgorithmBuilder at https://github.com/thewca/tnoodle-lib/pull/5/commits/943fd306819b26bc6d4b53a8d5238d38b15aea59#diff-9230152573c468cd8acaf707beb730e2R411 requires a "starting state" and checks that moves are valid from that state onwards.

I had accidentally inserted the "already slashable" state as a starting point, but since the slashability setup move is also included in the total move cost computation (obviously), this resulted in re-applying the slashability move to the already-slashable state.

The commit fixes this quirk by using the proper original unslashable state as starting point, but it still also requires holding a reference to the slashable state to be able to compute a solution from there by invoking the Chuang Shen solver. (NB: We could compute the latter state out of the former, but that would go against the spirit of the rest of the code being as computation-friendly as possible. So we pass two partially redundant states around to save computation time from deriving the same slashable state again and again every recursion step.)

Reason why this was not discovered previously: The WCA defines min scramble distance at 11 moves. All random test scrambles in the test suite were unsolvable within 11 moves, so the code never reached that part where an actual solution string had to be build (it already gave up here).

The tests are manually crafted "minimal examples" of the two scenarios that can occur (either it cancels or it doesn't, q.e.d. by exhaustion) where the solver is forced to solve them irrespective of whether they are within WCA scramble bounds or not. In essence, it's almost what you suggested here, except that I only care about the new, WCA-relevant metric and not the old metric.