Monday, April 22, 2013

Keeping OS X Awake

Wake up and smell the coffee...

OS X 10.8 has quite an agressive sleep strategy. Quite often, when writing programs for the Enigmatic Code site, I need to stop my laptop sleeping while it runs a program to generate a solution to one of the problems.

I found out last year about the caffeinate command in OS X, which stops the system from sleeping while a command is running. So I often use something like this:
time caffeinate pypy 6

if I want to leave my laptop running something when I'm out, or overnight (and know how long it took).

But what happens if a program has been running for a while and you forgot caffeinate it before you started? You don't want to kill it off and lose all the work it's done, just so you can restart it under caffeinate.

Well the answer is simple, just write a quick Python¹ program to monitor the process you are interested in, and caffeinate that instead.

Here's my quick Python program - I called it pid-exists - it just monitors a process (using the pid specified as the command line argument), until it disappears, and then exits itself.
import sys
import os
import time

PID = int(sys.argv[1])

while True:
    os.kill(PID, 0)
  except OSError:

Then you caffeinate that instead. For example:
caffeinate pid-exists 57905

will stop the laptop from sleeping while the process while pid 57905 is active. Once the process 57905 terminates then so will the pid-exists process and the parent caffeinate process and the laptop will go back to it's normal sleep strategy.

Note: On OS X 10.11 you can now just use:
caffeinate -w <pid>
to keep the computer awake while process <pid> is running.

¹ Other scripting languages are available.

Wednesday, April 10, 2013

Sliding Puzzle in Python

As part of making a constructive solution to Enigma 1444 I wrote a some Python code to capture a simple "sliding puzzle" solving algorithm. (You can see my code on the Enigmatic Code site).

This is all very well, but I wanted to see the algorithm in action. So instead of cutting up pieces of paper and sliding them around my desk, I wrote a Tk app using Python.

You need to specify the puzzle dimensions on the command line when you start the program. In this case for a 5×5 grid I used:
python 5 5

A window should show up with the puzzle in it, and you can interact with it by clicking on a tile (adjacent to the blank square) and it should move appropriately. It will keep track of the number of moves and the elapsed time, and if you select an appropriate Target from the drop-down menu it will tell you when you achieve it as a solution. You can choose from "Normal", which is the tiles in their "natural" position, or "Reversed", which is the tiles in reverse order. Note that it is not possible to solve a grid into the "Reversed" configuration for all puzzle dimensions, but that's what the Enigma is about, so that's the default.

There's a button marked Scramble. If you press that the grid will be placed into a random (but not impossible to reach from the initial position) configuration.

There's also a button marked Solve, which if you click it will start solving the puzzle using the algorithm I wrote for the Enigma puzzle.

When you click Solve the puzzle shows you the piece it is currently trying to place (by highlighting the piece in yellow), and also the position it is trying to place it in (by placing a yellow highlighted border around it). Once a piece is placed it is slightly greyed out. Also the Solve button changes to a Stop button, should you wish to abandon the automated solution.

If the target configuration is not possible, the message area will display Impossible Target, and the app will beep.

I used this to demonstrate that the smallest solution for Enigma 1444 - a 10×5 puzzle - is indeed possible in less than 15 minutes, and this is the configuration that the program is set to solve by default. Just fire it up, hit Solve and sit back and enjoy the show. It takes 1300 moves and on my machine it runs in about 4 minutes.

The default animation speeds mean you would have to pretty nimble-fingered to keep up with the program in real life (or use a cleverer algorithm to solve puzzles in fewer moves), as it makes around 5 moves/s. (There are command line parameters if you want to change the speed of moves). I manually reversed a 5×5 puzzle in 3 minutes (three times slower than my program), so a 10×5 puzzle should certainly be possible in under 15 minutes by hand. (Update: I reversed the 10×5 puzzle manually using this program in 824 moves, in 10m27s).

The next smallest solutions are also solved in less than 15 minutes by the program (but only just). A 14×7 puzzle is solved in 3828 moves, and a 11×10 puzzle is solved in 4122 moves. These both take about 14 minutes. After that a 22×5 solution is solved in 6344 moves and takes about 21 minutes.

If you like you can specify a target configuration on the command line. For example you can try to solve the puzzle for which Sam Lloyd offered $1,000 by running:
python 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14

and then clicking Solve - but you'll find the solution is impossible.

There's still a few rough edges in the program, and it's not particularly efficient, but it's works sufficiently well for me to see my solution to Enigma 1444 working, so I'm unlikely to take it further.

I've tested it on Mac OS X 10.8.3 under Python 2.7.4 and Python 3.3.1 with Tk 8.5.9, and on Linux (Ubuntu 12.04.2) under Python 2.7.3 and Python 3.2.3.