I was not quite correct with what I wrote earlier. After identifying that the standalone ‘A’ must cover the 1st ‘A’, both of the remaining words (‘AB’ and ‘ABA’) each have two remaining candidate positions. To solve this with logic, I had to look at each of the uncovered letters in the original string. It turns out the last ‘A’ in the string can only be covered by a single candidate word, leading to the full solution with no guessing.
Just to be clear, I don’t recommend anyone do what I did. This puzzle is definitely a better fit for backtracking which provides a much more concise and fast solution. The logic approach was just fun!
To break it you just have to try to put “two choices for each furthest_right and furthest_left” and insert some fun in the middle.
ABABABA
AB ABA BA
Expected solution
AB ABA BA
Your first logic won’t work since ABA_ocurrences = 1 < ABA_possible positions and same for AB and BA. The second logic won’t work since ABA and BA mess with the furthest_right and AB and ABA with the furthest_left.
Note that your current implementation doesn’t solve this one either:
ABABABA
ABA B ABA
Expected solution
ABA B ABA
Embrace the braindead backtrack my friend.
NB: Apparently I don’t know how to reply to a post? I just clicked the reply button under the comment but it doesn’t show the top box with the quote to the post I replied. Help.
Ended up adding two tests (yes… again…), nº12 (Actually solvable 4) and nº13 (Actually solvable 5). For the reasoning behind you can see the previous conversation . As usual sorry to anyone involved. The tests are nº12:
ABABABA
AB ABA BA
Expected solution
AB ABA BA
and nº13:
ABABABA
ABA B ABA
Expected solution
ABA B ABA
They might seem almost equal yet the second one can give a different result from the first in some implementations (I’m mainly talking about @Timinator’s, where the first gives unsolvable while in the second we get a “ValueError: min() arg is an empty sequence”).
And that will be all. Until a new contender appears I guess.
Added another test (nº14, Actually solvable 6). I don’t think I can explain the rationale behind it without spoiling (even more than what I already have) the solution of the puzzle so I’ll just put the test here. If you are curious you can solve it in cpp and check if the solution that passes every test but this one is still there:
Also, you’d probably assume that it’s the case, but there’s a hidden constraint (that I should have stated somewhere, but I don’t see how, without, again, spoiling it even more) that the underlying graphs are simple enough to not timeout when backtracking.
Now I won’t add such a test because it’s supposed to be an easy puzzle, but if anyone wants to give it a try, here’s one that times out every python / cpp solution that I’ve tested (except for @Timinator’s solution, funnily enough) while respecting all the constraints (the expected solution is just the second line):
AAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAABAAAAAAAAAAAAAABAAAAAAAAAAAAABAAAAAAAAAAAABAAAAAAAAAAABAAAAAAAAAABAAAAAAAAABAAAAAAAABAAAAAAABAAAAAABAAAAABAAAABAAABAABAB
AAAAAAAAAAAAAAAAAAAA B AAAAAAAAAAAAAAAAAAA B AAAAAAAAAAAAAAAAAA B AAAAAAAAAAAAAAAAA B AAAAAAAAAAAAAAAA B AAAAAAAAAAAAAAA B AAAAAAAAAAAAAA B AAAAAAAAAAAAA B AAAAAAAAAAAA B AAAAAAAAAAA B AAAAAAAAAA B AAAAAAAAA B AAAAAAAA B AAAAAAA B AAAAAA B AAAAA B AAAA B AAA B AA B A B
Nono I won’t add it. In all truth I don’t think the puzzle is solvable in that case, at least not with the 200 words constraint. It’s not hard to add a “non logically solvable” bit to the previous test to make the logical solution fail (like adding XYXYXYX to the end plus the words XY XYX YX as in test 12). The only fully working solution I see is to backtrack and then you are at the will of graph structure. Maybe you could add some clever heuristics along the way but even then I don’t see how you could entirely explore every possible remaining option in the allowed time limit.
I’m not laughing. I’m grinning ear to ear! Who’s ready for the next logic challenge? With my puzzle “Killer Sudoku Extreme Challenge”, my goal all along was to create a puzzle that required significant amounts of logic before backtracking would even have a chance. For the hardcore, a solution with zero backtracking is indeed possible:
