Instantly share code, notes, and snippets.

# peter-dolkens/cs50-putting-it-all-together.md

Last active April 4, 2020 03:36
Mathematical solution to https://cdn.cs50.net/2020/x/events/puzzles/puzzles.pdf -> Putting it all together

Mathematical solution to https://cdn.cs50.net/2020/x/events/puzzles/puzzles.pdf -> Putting it all together

First, we encode tiles into binary in low-byte order, assuming an 8-bit row-size.

For example:

`````` J
UN
H
``````

would be encoded as `00000001` `00000011` `00000010` => `66306`

To solve the puzzle then, we would expect to see all (8) rows and all (8) columns filled.

This would mean 64 bits would be filled, which can be represented as `2^64`.

We can move a tile around the puzzle by "shifting" it in the binary space.

If we label the position of each tile `a-r`, then we can represent the "shift" action of tile `a` as `2^a`.

All solutions to this puzzle satisfy this equation:

``````2^64 =
66306 * 2^a +
66305 * 2^b +
769 * 2^c +
771 * 2^d +
65795 * 2^e +
1796 * 2^f +
1794 * 2^g +
1539 * 2^h +
515 * 2^i +
66305 * 2^j +
770 * 2^k +
65793 * 2^l +
770 * 2^m +
65793 * 2^n +
131587 * 2^o +
196865 * 2^p +
259 * 2^q +
770 * 2^r
``````

All solutions to this puzzle are also integers, and must fit within the board, thus we can constrain a-r as such:

``````a-z ∈ ℤ {0, 63}
``````

We will then still have some solutions which are not possible, as a piece may be positioned on a row-boundary.

To solve this, we will encode just the `width` of each tile in similar fashion to the tile encoding.

For example:

`````` J
UN
H
``````

would be encoded as `00000011` => `3`

We can then add the constraints (TODO - these are wrong - fix)

``````0 = (2^8 - 1) AND (3 x 2^a % 2^8) - (3 x 2^a) +
(2^8 - 1) AND (3 x 2^b % 2^8) - (3 x 2^b) +
(2^8 - 1) AND (3 x 2^c % 2^8) - (3 x 2^c) +
(2^8 - 1) AND (3 x 2^d % 2^8) - (3 x 2^d) +
(2^8 - 1) AND (7 x 2^e / 2^8) - (7 x 2^e) +
(2^8 - 1) AND (7 x 2^f / 2^8) - (7 x 2^f) +
(2^8 - 1) AND (7 x 2^g / 2^8) - (7 x 2^g) +
(2^8 - 1) AND (3 x 2^h / 2^8) - (3 x 2^h) +
(2^8 - 1) AND (3 x 2^i / 2^8) - (3 x 2^i) +
(2^8 - 1) AND (3 x 2^j / 2^8) - (3 x 2^j) +
(2^8 - 1) AND (3 x 2^k / 2^8) - (3 x 2^k) +
(2^8 - 1) AND (1 x 2^l / 2^8) - (1 x 2^l) +
(2^8 - 1) AND (3 x 2^m / 2^8) - (3 x 2^m) +
(2^8 - 1) AND (1 x 2^n / 2^8) - (1 x 2^n) +
(2^8 - 1) AND (3 x 2^o / 2^8) - (3 x 2^o) +
(2^8 - 1) AND (3 x 2^p / 2^8) - (3 x 2^p) +
(2^8 - 1) AND (3 x 2^q / 2^8) - (3 x 2^q) +
(2^8 - 1) AND (3 x 2^r / 2^8) - (3 x 2^r)
``````