Add Reversi hole #1123
Comments
|
currently the description reads "In Reversi, you can only place a tile if there are one or more opponent tiles between it and an opponent's tile either horizontally, vertically, or diagonally." correct me if I'm wrong but shouldn't this read "one or more opponent tiles between it and an allied tile" or something to that effect? |
|
Not sure if it should be worth fixing or not, but I was playing around with a solution and found that I could shave a few bytes and solve pass ~1/20 if I make assumptions about the runs of enemy tiles which isn't typically true. Should this be a multi-run hole like sudoku, etc, to prevent this? |
We probably need a few static test cases that always show up to prevent edge cases. This is how we usually end up handling this kind of thing for poker, mahjong, etc. |
Do you have examples of test cases that would test for this 🧀 ? |
|
@mousetail It seems anecdotally that the maximum length of enemy tiles you need to account for is typically 5 in a row, but semi often its 4, and very occasionally only 3. Having a test case that requires finding a long straight or diagonal in a few directions would work. |
|
For instance, this arg only needs runs of 2 checked |
|
Yes, this is a good example. I think that we need some hard-coded edge cases that always run. For example, I would start with these: and the answers would be That would help to guarantee that the longest runs in all directions can be processed. And that they can be detected at the first and last position in the string. Maybe these board setups couldn't happen in a regular game, but I don't think we care. |
|
Actually we should do this with |
|
Ideally every valid combination of direction and length should be guaranteed to occur. Lengths (number of X): 1, 2, 3, 4, 5, 6 There are 48 of these. If some of them don't occur, then some solutions could take advantage of that by not supporting them. |
|
@SirBogman Currently the description says we guarantee that the input is reachable from the initial state. Seems a lot of your test cases are not actually reachable. |
|
I made a pull request #1171 to add static test cases. I could not figure out a way to create the full diagonal flip from the initial starting position, but if someone can figure that out feel free to add the test case. |
|
We should add test cases where the maximum number of either horizontal, vertical or diagonal moves (16) is possible. Otherwise, you can cheat. For example, the following two inputs rotated by 0, 90, 180 and 270 degrees. These cases are probably not reachable from the initial state. If this requirement is to be kept, we should at least find some test cases with 10 or more possible moves in a single direction. |
|
@nwellnhof I don't think it's possible to reach 16 moves in a single direction from the initial state, so I'd consider this to not be "abuse" but just clever reading of the rules. I also don't see how that assumption specifically would save bytes. Maybe a test case that has two options in the same direction would be good though. Those are possible to reach and could be abused. |
I don't want to reveal too much about possible solutions, but the basic idea is that you repeat an operation 9 times, although it should be repeated 10 or more times to cover all cases. This allows to save one byte and I can demonstrate the issue in at least one language where a wrong solution passes most of the time. |
|
I see what type of code might run into this problem. Still I think limiting at 9 per direction is reasonable unless you can prove it's possible to reach all 10. |
|
Here's a reachable test case allowing 11 horizontal moves: And 11 diagonal moves: |
|
@nwellnhof Thanks! I created a pull request to add those test cases (and their mirrors) |
No description provided.
The text was updated successfully, but these errors were encountered: