Thursday, October 08, 2009

[IF Competition] The Grand Quest - Appendix

My review of Owen Parish's The Grand Quest contained an analysis of its playing card puzzle. I couldn't stop myself from doing some more calculations, which I present here. (This post also contains a walkthrough for the card puzzle that is shorter than that in the official walkthrough. It's right at the end.)

You won't understand this discussion if you haven't read the previous post.

Which also means that it's not too bad if it turns out that I haven't provided anough spoiler space.

In my previous post, I defined the four operations A, B, C and D, and we saw that 4A + B + 5C + D was a solution of the puzzle; it is also the solution of the walkthrough. But of course, we would like to find all solutions by construction, rather than check a single given solution.

The way to go is linear algebra. The four operations form a matrix, and we can get four linear equations out of it. If the Four of Diamonds is supposed to turn into the Ace of Clubs, we get the following equations:

a - b + c + 2d = 10
a + 2b + c + 2d = 1 mod 4
-a + b +2c + d = 8
2a + b + 2c + d = 0 mod 4

I'll leave the calculations as an excercise to the reader, but we will find that d = 1 or 5, b = 1, 5, 9, ..., c = 6 - d, and a can then be gotten from the top equation. One solution is b = 1, d = 1, c = 5, a = 4, which is the solution from the walkthrough. But there is another, better solution: b = 1, d = 5, c = 1, a = 0. Only seven operations, instead of the eleven from the walkthrough! I'll write out the explicit solution below.

We can also say that the Six of Spades must become the Ace of Clubs. This gives us slightly different equations, and leads to d = 1 or 5, b = 3, 7, ..., c = 6 - d, and a is again given by the top equation. The best solution here is b = 3, d = 5, c = 1, a = 2, which are eleven steps, exactly as efficient as the solution from the walkthrough.

Explicit most efficient solution

I adopt the notation from the walkthrough.

Closed 4D, 6S -> 5C, 8C
Open 8C, 5C -> 4S, 9H
Closed 9H, 4S -> 10S, 6C
Closed 10S, 6C -> JD, 8S
Closed JD, 8S -> QC, 10C
Closed QC, 10C -> KH, QS
Closed KH, QS -> AS, AC.

5 comments:

  1. By the way, the "10" and "8" in those equations are really "10 mod 13" and "8 mod 13", but I suspect that this will not lead to more efficient solutions.

    ReplyDelete
  2. Wow. I applaud your thoroughness! I didn't take it *nearly* that far, choosing instead to grumble that the puzzle even existed, and wonder how anybody in their right mind would be able to solve it.

    Victor... are you indeed in your right mind? :)

    --- Merk

    ReplyDelete
  3. Is anybody why managed to get a master's degree in physics in his right mind? :)

    Seriously, though, part of me is an exact scientist who loves to do calculations, and that part of me gets little chance to express itself nowadays. So when it comes across a puzzle that you have to solve by solving a system of linear equations... well, it smiles gleefully and gets to work!

    Still, I'm not sure how happy I am about this puzzle. It seems to me that it is not served well by being cast into the form of parser based interactive fiction. A graphical, clickable interface would have been much clearer and easier to work with.

    ReplyDelete
  4. Well, credit for figuring out that there *was* a set of rules behind it. By the time I reached the puzzle, my fun was about gone and I probably wouldn't have even realized that some kind of card transformation algorithm was even at work.

    See, you've got me beaten. I'm a computer programmer, and believe it or not, there are many areas in which you needn't be strong in math to make a healthy go of it. :)

    --- Merk

    ReplyDelete