ILP Part 90 — Turkey

This is the ninetieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the Turkey riddle. We have some shape which we need to cut in two halves which are exactly the same shapes.

We’ll solve just the last part of it: verifying if two parts are the same shapes. Everything else is rather straightforward and was explained on this blog many times. So let’s take the solution first:

We’re going to develop a generic solution capable of working with any shape and array of any size. The idea is: we’ll extract the part of Xs, shift it left and up by some delta calculated by the solver. We are going to do the same for all four possible rotations. Finally, we just add the goal that Os must match at least one of the shifted and rotated Xs. The code:

We start with encoding Os and Xs (lines 1-26). Next, we implement a couple of helper functions to manipulate the arrays. Two extractors for iterating via rows or columns (28, 29), and one function to rotate the array in a counter-clockwise direction (31).

Next, we implement the shifts. Shift left is rather straightforward, we just iterate over rows and move them to the left (lines 33-38). We could implement shift up the same way but we’ll use rotations instead: first rotate the array counter-clockwise, shift it left, and then rotate it counter-clockwise three more times (line 39).

We then implement a comparison function (line 41).

That’s it for helpers, now we implement the business logic. We iterate over all rotations (lines 51-61), shift left and up the Xs (lines 52,54), and compare the result with Os (58). Finally, we make sure that at least one of the transformations matched Os (line 63).


We can see that the first array (Os) matches the last one (Xs).