Solving Aristotle's Number Puzzle Faster

In my last past, I gave a method for solving the Aristole number puzzle by iterating the 19!/12! permutations of 7 variables from {1, 2, ..., 19 }. The problem with this method is that most of the solutions it finds are just rotations or mirrors of solutions already found.

A more efficient method would be to only look for solutions in a standard orientation so that rotations and mirrors aren't found. (We can rotate and mirror those solutions later if we want to see all the solutions.) Since there 6 ways to rotate the board and 2 ways to "mirror", we'd only have to test 1/12th of the permutations we were checking before.

---

Use a, c, h, l, o, q, s for the starting variables. The standard rotation we'll use is for to a to be the smallest of the corner hexes on the border so a = min ({a, c, h, l, q, s}). Also require that h < c, which takes care of mirrors.

Now assign a, c, h, l, o, q, s each permutation of 7 from {1, 2, ..., 19} subject to the above constraints and test as before using these equations.

b = 38 - a - c
g = 38 - c - l
p = 38 - l - s
r = 38 - q - s
m = 38 - q - h
d = 38 - h - a
n = 38 - m - o - p
i = 38 - d - n - r
e = 38 - b - i - m
f = 38 - g - e - d
k = 38 - p - f - b
j = 38 - h - i - k - l

C program that implements the above procedure

The C program above finds all the solutions in around 1 second on my laptop.

Solving Aristotle's Number Puzzle

Aristotle's Number Puzzle by Professor Puzzle is number puzzle involving 19 numbers arranged into a hexagon. The goal of the puzzle is to rearrange the numbers so each of the 15 rows add up to 38.

I managed to solve this puzzle by writing a program to iteratively search for the solution. It might be possible to solve the puzzle using only logic and deduction but I have no idea how. Please leave a comment if you've actually solved it that way! The official solution video on YouTube gives the solution but doesn't explain how it was derived.

What follows is a derivation of the program that solves the puzzle. All the code is available on github at aristotle_puzzle.

---

First, let's get a mathematical description of the problem.

Let the variables a, b, c, ..., s represent the values of each cell like this:

That gives us these equations:

a + b + c         = 38
b + e + i + m     = 38
h + i + j + k + l = 38
m + n + o + p     = 38
q + r + s         = 38

a + d + h         = 38
b + e + i + m     = 38
c + f + j + n + q = 38
g + k + o + r     = 38
l + p + s         = 38

c + g + l         = 38
b + f + k + p     = 38
a + e + j + o + s = 38
d + i + n + r     = 38
h + m + q         = 38

The other constraints are:

• None the values must be equal so a != b, k != q etc.
• Each value comes from the set {1, 2, ..., 19}

One attempt to solve the puzzle would be to take each permutation of {1, 2, ..., 19} assign it to a, b, ..., s and test the against the constraints until finding all the solutions. The problem is that there are 19! = 1.2e17 permutations so it would take hundreds of years for the program to run.

Going back to the equations, apply Guassian Elimination to attain the following:

a = 76 - j - k - n - 2o - p - r - s
b = j + n + o
c = -38 + k + o + p + r + s
d = j + k + o
e = -38 + k + n + o + p + r
f = 38 - j - k - n - o - p
g = 38 - k - o - r
h = -38 + n + o + p + r + s
i = 38 - j - k - n - o - r
l = 38 - p - s
m = 38 - n - o - p
q = 38 - r - s

Python script that derives the above equations.

This gives 7 independent variables: j, k, n, o, p, r, s and the equations to generate the remaining 12 dependent ones.

Now, take each permutation of size 7 from {1, 2, ..., 19}, assign it to the independent variables, generate the dependent ones and test against the constraints until finding solutions. This should be feasible since there are only 19!/12! = 2.5e8 of these to check.

C program that implements the above procedure

It turns out that are only 12 solutions but they are all rotations and/or mirrors of each other. Here is one of them:

Using curl to test ASP.net asmx web services

This is an example of how to use curl to test a classic ASP.net asmx service by hand. In this example, the service is located at http://localhost:52573/Pizza.asmx

1. Go to the web service help page and copy the SOAP 1.2 example request.

2. Paste the example into your favorite text edit and save it as request.xml.

3. Remove the header and fill in the placeholders

4. Open PowerShell at the folder containing your example. And use this command:

curl -H 'Content-Type: application/soap+xml; charset=utf-8' -d '@request.xml' http://localhost:52573/Pizza.asmx

The '@ syntax' used in @request instructs curl to use the file contents as post data. You might have to use the --ntlm and -u if you have authentication problems.

Trimming Trailing Whitespace in Powershell

I needed to remove the trailing spaces from each line in a text file. I came up with this.

    $lines = (Get-Content $filename);
    $lines |
        ForEach-Object { $_.TrimEnd(); } |
        Out-File $_ -Encoding Ascii;

Notice that I specify the encoding on the Out-File cmdlet. This should be set to whatever the encoding of the file is. If that option is omitted, the file is output as double-byte Unicode which is almost never what you'd want.

What I learnt playing "vimgolf: replacing each line of a block selection"

The substitute command can use delimiters other than /.

For example, let's say you want to replace the path a/b/c with d/e in the current line.

You could use the usual / as the delimiter and escape the forward slashes in the pattern and replacement like this:
:s/a\/b\/c/d\/e/

But it would be much easier to another delimiter, say ; and avoid the escaping like this:
:s;a/b/c;d/e;

See :help E146 for more detail

Stashing Changes in Mercurial

Stashing means setting aside changes to a working directory without commiting them.

It's useful if, for example, you're adding a feature to one of your projects when you find a bug that you want to fix immediately. You don't want to not mix the fix up with your feature code and you aren't ready to commit and start a new changeset. The solution is to stash your changes, code the bug fix and commit it and then unstash them to resume working on the feature.

Recipe

hg diff | Out-File -Encoding ascii stash.patch
hg update -C
# other stuff...
hg import --no-commit stash.patch

Explanation

Output of hg diff is a unified diff which we save to file. hg update -C, of course, removes the changes from the working directly. Be careful that you don't accidentally lose work when you're doing this! After other stuff, we use the import command to unstash the changes.

Comparison to Other Methods

There are extensions for stashing but, in my experience, they don't work very well.

mq is used for this as well but that procedure is unnecessarily complicated if you don't normally use mq.

Vim: Reading from stdin

Here is a neat tip for Vim.

To read from stdin use

<other commands> | gvim -R -

-R instructs Vim to read the file in read-only mode.
- is a utility convention that means open from stdin. (See Guideline 13 of Utility Syntax Guidelines from the Posix standard.)

Source: http://stackoverflow.com/questions/230718/redirection-and-vim