Tuesday, May 20, 2014

A Better Bank Statement

Regular bank statements are presented in a very unhelpful way - simply sorted by date, with no analysis of the items to assist you to understand them.

View my Better Bank Statement.ipynb in nbviewer or download the .ipynb file.

The iPython Notebook uses Pandas to analyse your bank statement (downloaded as a .csv) and produces output like the following.

New items that haven't been seen before are separated out so they can be checked easily:


Items to payees that have been seen before but with amounts that are different are displayed graphically to let you see at a glance which are truly problematic and which are normal variations.


Recurring items are usually going to be fine, but you may want to check that an automatic payment hasn't been missed:


The same breakdown is done for credits.

You have to ask yourself: why can't the bank do something like this? Until then, see how you go playing with this notebook.

Monday, November 25, 2013

Adidas Adipure Adapt 2 review

I've had a pair of Adidas Adipure Adapt 2 shoes for a couple of months now and they instantly became my everyday regular running shoes.

Zero drop, light weight and minimal, they're pretty much perfect. The neoprene(?) uppers slip on easily and are the first shoes I've ever had that didn't rub in the slightest. I wear all my running shoes without socks & the first day I wore them I ran 25km (in 2 sessions) without a single bit of skin feeling anything at all.

The upper is a bit thicker than the Hattoris, so I suspect they'll be a little sweatier when the weather warms up, but they're not smelling too bad so far and wash easily.

The sole, like the Saucony Hattoris, is much more robust than it appears. No noticeable wear after 500km.

I liked them so much I bought a second pair pretty much straight away. Saucony had ceased production of the Hattoris by the time I'd done 2200km and started to wear them out, so I didn't want that to happen again!

And, they're nice and cheap too. I can't recommend them highly enough.

Tuesday, February 12, 2013

iPhone and Garmin GPS accuracy tests

Following on from my accuracy testing of the Magellan Switch Up, I've done a couple more tests that show some interesting results.

First, in response to mjs's query about Wi-Fi assisted GPS affecting the iPhone results, I ran the same route with Wi-Fi on (green track) and off (red track):



This is really interesting as it's clear that with the Wi-Fi on, the track "snaps" to the middle of the street, which is where the Google street view car (or similar) would have driven when scanning access points to generate Wi-Fi positioning system data. (This is using my iPhone 3GS, so newer iPhones might behave differently.)

Interesting as this is, the accuracy isn't improved sufficiently with Wi-Fi off to make the iPhone competitive with a dedicated GPS logger.

The second thing I've noticed is the difference in behaviour between my Locosys Genie GT-31 and my Garmin Forerunner 210 when the GPS signal is blocked or poor.

This map shows 10 tracks recorded with the GT-31 along a running track that is suspended below an 8 lane freeway. The concrete roof severely limits the amount of sky that can be seen and the track jumps about and takes a while to get back to normal:



The behaviour of the Garmin is vastly different (the following map shows another 10 tracks):



Garmin has obviously tuned their GPS error correction algorithms specifically for running, and if the GPS data is varying wildly they can assume you're generally going to keep heading in the same direction at the same speed.

The Magellan Switch Up actually performs pretty well in this regard too, I only have 4 logs to map here, but aside from it's "wobble", it doesn't do too badly with a poor signal:



These maps were all produced with my site GPSLog Labs, which has the ability to filter and clean up GPS data, though I'll be needing that feature much less now I'm getting good quality data from the Garmin!

Sunday, January 06, 2013

Magellan Switch Up GPS watch accuracy comparison [UPDATED]

My Locosys Genie GT-31 died after logging nearly 100 days of data in 2.5 years.

For a few weeks I used my iPhone and was very unhappy with the accuracy of the resulting logs, having been spoiled by the extremely accurate GT-31.

So it was time to get a running watch and the choice was between a Garmin Forerunner 210 and the Magellan Switch Up. The Switch Up has a lot more features than the Forerunner but is much newer and less tried and true.

DC Rainmaker did a full review of the Switch Up, so I'll only look at a few tests that show the accuracy of the resulting logs, which was my main concern when buying it and as it happens, not really a strong point of the Switch Up.

Unfortunately, without another GPS watch to compare it to directly, it's hard to know if this is a failure of the Switch Up in particular or running watches in general.

The best I could do was to run two laps of the same route, the first with the Switch Up in a shoulder pouch, the second with it worn as a watch.

I then compared these two logs against one recorded by the iPhone and one from the GT-31. All maps and graphs were generated with my site, GPSLog Labs.

MAPS

The route I ran is all straight segments up and down a series of increasingly steep streets. This makes a good comparison as it's obvious if the logger is recording the straight path. There aren't too many trees along the streets and no tall buildings to block the GPS signal.

GT-31

The GT-31 records the streets as nice straight lines, doesn't cut off the corners and the segments that are re-run generally overlap. The south side of each street seems to waver a little more than the north, possibly because when running west with the logger on my left shoulder, there are less satellites in view.

iPhone

The iPhone really "rounds" out the log, cutting the turnarounds short and generally doing a very rough job. It almost certainly isn't getting a position fix every second like the other loggers. It's only a 3GS and suspect a newer iPhone would probably do better.

Switch Up (shoulder pouch)

The Switch Up records a very wobbly path. The turnarounds are at the right points, but repeated segments don't overlap, and again, the north side of the streets seems to be slightly straighter than the south.

Switch Up (watch)

Thankfully, when the Switch Up is worn as a watch it seems that it actually performs slightly better, probably due to a more all round view of the sky, otherwise many of it's useful features would be negated.


DISTANCE

This inaccuracy in the recorded position has a fairly negative effect on the resulting recorded distance, all those little wobbles increase the distance by about 2%. If this was your only watch then you wouldn't care, but if you've got a few thousands of kilometers of running logged already, it's annoying to no longer be able to compare them easily.

The following table compares the iPhone and the Switch Up to the 29 logs of this route I got with the GT-31:

Count Average Distance Standard Dev Difference
Locosys Genie GT-31 29 6067.6 m 33.13
iPhone 3GS 3 5973.3 m 70.24 98.45%
Magellan Switch Up 2 6190.0 m 42.43 102.02%

Obviously, with only 2 logs from the Switch Up it's a bit early to nail down the extra distance, but in both cases the measured distance would be a far outlier for the GT-31:



SPEED

GT-31

The GT-31 sets the baseline, but even it's recorded speed bounces around a bit. The dark blue line shows the median over a 25 second window, the pale blue line is the actual speed from the logger.

The histogram has a fairly tight cluster of speeds, bearing in mind that this route is up and down hills so the speed should vary a bit.

iPhone

The worst case is the iPhone, with the speeds varying by more than 10km/h in a few seconds. Even after taking the median the speed still jumps around wildly and the histogram is a mess.

Switch Up (shoulder pouch)

The Switch Up's speed is much better than the iPhone, especially once an average is taken.

Switch Up (watch)


There's no appreciable difference between wearing it on your wrist or in a shoulder pouch, but in practice it still means that if you look at the instantaneous pace readout you're likely to be seeing a value that's incorrect by anywhere up to 1 min/km. This means that the only way to really pace yourself is to use the auto-lap timer and use the lap averages.

HEADING

The Heading vs Time graphs really should be alternating between steady east and steady west and the Distance vs Heading should be a nice sharp elongated cross.

GT-31



iPhone


The iPhone actually performs quite well on this measure because it's obviously taking less frequent readings and doing some kind of interpolation between them.

Switch Up (shoulder pouch)



Switch Up (watch)



ALTITUDE
Thankfully, there is one area where the Switch Up shines due to it's barometric altitude sensor.



The green and red lines are from the Switch Up, both laps are nearly identical and the hills look nice and symmetrical.

The yellow line is from the GT-31, and the blue from the iPhone.

When all records from the GT-31 are plotted together, the overall shape becomes clearer, though it seems that the Switch Up is still only providing consistent relative altitudes rather than an accurate absolute altitude:


There aren't many laps recorded on the iPhone, but the altitude is all over the place anyway:


CONCLUSION

Without using another GPS watch in a direct comparison, it's hard to really rate the accuracy of the Switch Up. My only other experience with GPS watches is with the GlobalSat GH-615M, which created a very similar log to that of the GT-31 when I did a run with them together a couple of years ago (both use the same SiRF Star III chipset).

Feature and price-wise the Switch Up is fine, so maybe the accuracy can be improved with a firmware update since it's using the SiRF Star IV chipset which is hopefully better than the III. (Note that these logs were created with the version 19.48 firmware.)

YMMV.

UPDATE 1-Feb-2013

Unfortunately there was something faulty with my Switch Up and I've returned it. It was freezing up, sometimes after only a few hundred meters, and had to be turned on and off and the activity reset before it would record again. This was pretty frustrating, but before it died, I made a few more tests and did find I was able to improve the accuracy some what by ensuring I wore the watch on the hand that was going to "see the most sky" on the particular route I was running.

I decided to replace the Switch Up with a Garmin Forerunner 210, which I'm very happy with. The Garmin has fewer features than the Switch Up, but it's very easy to use and reliable. I also purchased another Locosys Genie GT-31 for use as a non-running logger, since it's accuracy and long battery life are fantastic.

The accuracy of the Garmin has been very good: The distances are pretty much spot on what I was getting from the GT-31, the instantaneous pace is pretty good. It's altitude readings can't compare to the Switch Up, and the heart rate logs seem a little less detailed but overall it's great value.

One thing I've found is that it pays to wait around a bit after the satellite signal has been acquired before you start (e.g. until it displays a zero speed) as it's pretty optimistic about when it has a "lock".

Saturday, March 17, 2012

Adding "Search at point" function to Notepad++

Notepad++ with the Python Script plugin is a great code editor for windows.

After adding the following two files to your Notepad++ scripts folder you can make it even better with what I'm quickly finding to be an indispensable feature:

By using the Alt+left and Alt+right keys you can move to the previous and next occurrences of the symbol under the cursor. e.g. you can move quickly between all usages of a variable or function name in a file.

# goto_next_occurrence.py
"""Move cursor to next occurrence of the current word in the file, wrap around if possible."""

from Npp import editor, FINDOPTION
symbol = editor.getCurrentWord()
editor.wordRight()
editor.searchAnchor()
pos = editor.searchNext(FINDOPTION.MATCHCASE+FINDOPTION.WHOLEWORD+FINDOPTION.WORDSTART, symbol)
editor.scrollCaret()
# goto_prev_occurrence.py
"""Move cursor to previous occurrence of the current word in the file, wrap around if possible."""

from Npp import editor, FINDOPTION
symbol = editor.getCurrentWord()
editor.wordLeft()
editor.searchAnchor()
pos = editor.searchPrev(FINDOPTION.MATCHCASE+FINDOPTION.WHOLEWORD+FINDOPTION.WORDSTART, symbol)
editor.scrollCaret()

Then add them to the menu:

And bind them to keys, Alt-right and Alt-left work well for me:

Back in Linux-land, there are a bunch of ways to add similar functionality to Emacs, I like this one.

Thursday, December 22, 2011

Saucony Hattori review

I've just bought a pair of Saucony Hattoris and they really good!



They're minimal, but have a lot more cushioning than Vibrams or the Evos since the EVA+ sole is quite soft and about 10mm thick. They're zero-drop and ultra light weight (250g/pair), about half the weight of the Evos and lighter than Vibram Sprints.

They're a really comfy fit, with no laces they are held on by a tight, thin "lycra" upper. Mine are maybe a little on the small side, so the velcro straps don't do anything useful.

The tight fitting upper has another advantage that no other shoes I've got come close too: It's virtually impossible to get sand in them, which is great as that's extra annoying when running sock-less.

Time will tell how the sole wears, but the hard reinforcements are in all the places I usually wear through, so I can't see why they won't last a fair while.

[Update, 7-June-2013] It slipped my mind to do an update on these, but I've been wearing them on my shorter runs pretty much all the time over the last 18 months. They've racked up more than 1,800km and though getting quite worn I'm sure they'll go past 2,000km without any problems.

As I suspected, I bought them a tiny bit too small, which has occasionally given me a blister on the tips of my toes and I've now got a couple of holes in the upper where my big toe sticks out. This doesn't cause any problems however and the extra ventilation can't hurt!

They get smelly fairly quickly, but washing them in warm water with a few tablespoons of white vinegar seems to clean them up nicely.

They're a great shoe & fantastic value for money.

Friday, August 12, 2011

Please unsubscribe me from the World Vision newsletter

God knows I've tried enough times, maybe posting it to a blog is how you get off the list?

Sunday, August 07, 2011

Terra Plana Evo review

My Vibrams are worn out (or through) so after having a good experience with the Merrell Trail Gloves I decided to get a pair of Terra Plana Evos.

It's a pain to get Vibram FiveFingers in Australia at the moment. They're hard to find in shops, can't be shipped here from the USA and they're about twice the price even though our dollar is currently trading higher than the USD.

The Evos are more expensive than the Vibrams but a little less "freaky" and provide a similar minimal experience to the Merrells. That is, your toes are free, there's no support or cushioning and you get a fair degree of "ground feel".

I considered a pair of Merrell True Gloves (the "road" equivalent of the Trail Gloves) but they had too much cushioning for my liking and unlike the Evos, they didn't have removable inner soles.

I bought them in the black/red style, which was probably not that smart. They contrast too much against my skin and tend to look a bit odd, they're a very small shoe and black emphasises that.

One thing to note, is that the women's model is identical to the men's, but quite a bit cheaper! Unfortunately they only go up to size 41, but it's something to take advantage of if you have small feet. Speaking of which, the Evos are sized pretty small, the 42 is plenty big enough for me, which is a size or two smaller than my regular shoes.

The lacing is the same as for the Merrell Trail Gloves, holding snuggly to the middle of the foot and leaving your toes free to splay. They don't lock onto my heel as nicely however and they tend to feel a little loose after running a few kms.

They are a minimal shoe and still a long way from barefoot, with less ground feel than Vibrams, even wearing them without socks and taking out the inner soles. Still, you feel pebbles and the contrast between concrete, asphalt, gravel, dirt, grass surfaces well enough and it doesn't seem to interfere with my stride. They don't have a lot of grip however and slip pretty easily if it gets muddy. While they'd probably do fine on dry trails, I don't think they feel very suitable for general trail running.

Not wearing socks did cause some significant rubbing issues however. That was partly due to me jumping straight into 12km runs with them, and I have to resort to prepping with vaseline. It's definitely something to be aware of as they press on different parts of your foot than the Five Fingers do.

I've done about 85km in them now and they feel good. They don't feel like they'll wear out too quickly, aren't too cold (though our winter has been fairly mild so far), and don't soak up water between the toes like the Five Fingers. They feel like they'll be fine in warmer weather too, the upper is a very thin and breathable mesh.

Overall, other than the price, they're great and I'd recommend them to any experienced minimalist shoe runners.

Wednesday, June 22, 2011

No, wait, that's not right, here's how I really solved it.

Yesterday I posted the solution to a puzzle in response to one created by Reilly. The solution is fine, but I explained it badly. The explanation just describes the finished code, which is all well and good, but it doesn't elucidate the steps I took to get there and isn't likely to help anyone as a result.

The following steps are much closer to what I actually did:

1. While reading Reilly's Prolog version I realized that SQL could probably solve the puzzle by generating a list of all the possible combinations of pieces (either by a join or in a temporary table) and then filtering those in some way to remove invalid solutions.

2. I left it at that for a while, but a few thoughts popped into my head during the day on the structure of a "pieces" table and an INSERT statement that could generate the 4 possible rotations of each piece. I also ran the numbers in my head and realized there were 4^9 = 2^18 = 262,144 combinations which is not many at all really.

3. I initially ran into a bit of a dead end imagining how a SELECT statement would generate all the combinations of pieces, but decided to just start writing it out and see where that led.

This was the crucial step: Starting with the desired result and working backwards.

So, I started with what I wanted: A list of piece numbers and rotations in each position of the puzzle:

SELECT A.piece_id AS A, A.rotation AS Ar, B.piece_id AS B, B.rotation AS Br, C.piece_id AS C, C.rotation AS Cr,
       D.piece_id AS D, D.rotation AS Dr, E.piece_id AS E, E.rotation AS Er, F.piece_id AS F, F.rotation AS Fr,
       G.piece_id AS G, G.rotation AS Gr, H.piece_id AS H, H.rotation AS Hr, I.piece_id AS I, I.rotation AS Ir

Then I started joining tables together to match the constraints of the puzzle (i.e. the animals on the adjacent edges match head-to-tail.) At this point I didn't know what fields were going to be in the table, or what it would be called, so I just made them up so the SELECT statement read nicely. First, I'll show the overall structure and come back to the "matches" bits:

FROM rotated_pieces A 
INNER JOIN rotated_pieces B ON -- A.right matches B.left --
INNER JOIN rotated_pieces C ON -- B.right matches C.left --
INNER JOIN rotated_pieces D ON -- A.bottom matches D.top --
INNER JOIN rotated_pieces E ON -- D.right matches E.left AND B.bottom matches E.top --
INNER JOIN rotated_pieces F ON -- E.right matches F.left AND C.bottom matches F.top --
INNER JOIN rotated_pieces G ON -- D.bottom matches G.top --
INNER JOIN rotated_pieces H ON -- G.right matches H.left AND E.bottom matches H.top --
INNER JOIN rotated_pieces I ON -- H.right matches I.left AND F.bottom matches I.top --

My "matches" criteria was initially something like:

(   (A.right = B.left AND A.right_head = 'head' AND B.left_head = 'tail')
 OR (A.right = B.left AND A.right_head = 'tail' AND B.left_head = 'head'))

This makes sure the animals are the same and it's either head-tail or tail-head.

That seemed like it might work which was a pretty good sign I was on the right track. I wasn't sure how many combinations this would match, so decided to leave a WHERE clause for later. I was hoping this would be a unique solution, or there may be just a couple and I could pick the proper solution out by hand. Either way, that was a problem for later.

4. From this sketch of a SELECT statement I was able to come up with an appropriate table structure for rotated_pieces:

CREATE TABLE rotated_pieces (
  piece_id     INTEGER, # unique piece id
  rotation     INTEGER, # 0 - top, 1 - left, 2 - bottom, 3 - right
  top         CHAR(10), # animal at top edge
  top_head    CHAR(10), # head or tail at top edge
  `right`     CHAR(10),
  right_head  CHAR(10),
  bottom      CHAR(10),
  bottom_head CHAR(10),
  `left`      CHAR(10),
  left_head   CHAR(10));

And then I started on an INSERT statement to populate the table with the piece layouts:

INSERT INTO rotated_pieces 
       (piece_id, rotation, 
              top,       top_head, `right`,   right_head, bottom,    bottom_head, `left`,    left_head) 
VALUES (1, 0, 'cheetah', 'tail',   'tiger',   'tail',     'lion',    'head',      'tiger',   'head'),
       (2, 0, 'lion',    'tail',   'lion',    'head',     'tiger',   'tail',      'cheetah', 'head'),
       (3, 0, 'tiger',   'tail',   'lion',    'head',     'panther', 'head',      'tiger',   'tail'),
       (4, 0, 'panther', 'tail',   'cheetah', 'head',     'panther', 'tail',      'lion',    'tail'),
       (5, 0, 'tiger',   'head',   'tiger',   'head',     'cheetah', 'head',      'lion',    'tail'),
       (6, 0, 'panther', 'tail',   'panther', 'head',     'cheetah', 'tail',      'tiger',   'head'),
       (7, 0, 'panther', 'head',   'cheetah', 'tail',     'cheetah', 'head',      'lion',    'tail'),
       (8, 0, 'panther', 'tail',   'lion',    'head',     'panther', 'head',      'cheetah', 'tail'),
       (9, 0, 'cheetah', 'head',   'tiger',   'head',     'panther', 'head',      'lion',    'tail');

While I was doing this I copy/pasted Reilly's equivalent bit of Prolog code and it was a simple text transformation between the two languages, another very good sign:

Prolog:
tile(1,     cheetah_tail,     tiger_tail,     lion_head,     tiger_head).
SQL:
    (1, 0, 'cheetah','tail', 'tiger','tail', 'lion','head', 'tiger','head'),

5. At this point, I realized that the "matches" criteria could be simplified a lot:

A.right = B.left AND A.right_head != B.left_head

6. Now I was able to write out the "rotation" function I'd envisioned earlier in the day and realized I wasn't going to need a "pieces" table at all, this program was only going to need the 36 rotated_pieces records, another good sign that I was on the right track.

# rotate (top --> left)
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head) 
  SELECT piece_id, rotation+1, 
         `right` AS top, right_head AS top_head, 
         bottom AS `right`, bottom_head AS right_head, 
         `left` AS bottom, left_head AS bottom_head, 
         top AS `left`, top_head AS left_head 
    FROM rotated_pieces;

# rotate (top --> bottom, left --> right) 
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head) 
  SELECT piece_id, rotation+2, 
         bottom AS top, bottom_head AS top_head, 
         `left` AS `right`, left_head AS right_head, 
         top AS bottom, top_head AS bottom_head, 
         `right` AS `left`, right_head AS left_head 
    FROM rotated_pieces;

7. Finally, I had all the code sketched out. I checked the syntax for a few things since I'd just been doing it off the top of my head and then executed it. After escaping `right` and `left` as they're keywords (not necessarily the best choice of field names...) the CREATE TABLE and INSERT statements ran. I did a sanity check of the rotated_pieces table and it looked good.

The result of my SELECT statement was disappointing though. As I sort of suspected, there are lots of solutions if you allow a piece to be used more than once and the SELECT returned 1272 rows.

8. I couldn't think of a neat way to check for duplicates so ended up just writing a WHERE clause to do it by brute force:

WHERE A.piece_id != B.piece_id AND A.piece_id != C.piece_id AND A.piece_id != D.piece_id
  AND A.piece_id != E.piece_id AND A.piece_id != F.piece_id AND A.piece_id != G.piece_id
  AND A.piece_id != H.piece_id AND A.piece_id != I.piece_id
  AND B.piece_id != C.piece_id AND B.piece_id != D.piece_id AND B.piece_id != E.piece_id
  AND B.piece_id != F.piece_id AND B.piece_id != G.piece_id AND B.piece_id != H.piece_id
  AND B.piece_id != I.piece_id AND C.piece_id != D.piece_id AND C.piece_id != E.piece_id
  AND C.piece_id != F.piece_id AND C.piece_id != G.piece_id AND C.piece_id != H.piece_id
  AND C.piece_id != I.piece_id
  AND D.piece_id != E.piece_id AND D.piece_id != F.piece_id AND D.piece_id != G.piece_id
  AND D.piece_id != H.piece_id AND D.piece_id != I.piece_id
  AND E.piece_id != F.piece_id AND E.piece_id != G.piece_id AND E.piece_id != H.piece_id
  AND E.piece_id != I.piece_id
  AND F.piece_id != G.piece_id AND F.piece_id != H.piece_id AND F.piece_id != I.piece_id
  AND G.piece_id != H.piece_id AND G.piece_id != I.piece_id
  AND H.piece_id != I.piece_id;

9. This had the desired result and I got back 4 rows.

'A', 'Ar', 'B', 'Br', 'C', 'Cr', 'D', 'Dr', 'E', 'Er', 'F', 'Fr', 'G', 'Gr', 'H', 'Hr', 'I', 'Ir'
2, 1, 1, 0, 6, 0, 8, 3, 9, 3, 7, 2, 5, 3, 3, 0, 4, 0
6, 1, 7, 3, 4, 1, 1, 1, 9, 0, 3, 1, 2, 2, 8, 0, 5, 0
4, 2, 3, 2, 5, 1, 7, 0, 9, 1, 8, 1, 6, 2, 1, 2, 2, 3
5, 2, 8, 2, 2, 0, 3, 3, 9, 2, 1, 3, 4, 3, 7, 1, 6, 3

The first row clearly matched Reilly's solution, but it wasn't immediately obvious what the other 3 rows were. After reformatting them into a 3x3 grid and staring for a little while I picked out the pattern of pieces 2-1-6 around the edges and realized it was the whole board being rotated. So there was a single solution after all.

2, 1, 6, 
8, 9, 7, 
5, 3, 4

6, 7, 4, 
1, 9, 3, 
2, 8, 5

4, 3, 5, 
7, 9, 8, 
6, 1, 2

5, 8, 2, 
3, 9, 1, 
4, 7, 6

10. The next step was to pretend I knew all that from the beginning and write it up in the previous blog post. Later that evening I thought again and realized that wasn't so truthful and that I should have another shot at writing it up.

Postscript: The ugly WHERE clause was still bugging me and I realized that it could be improved by making some kind of function involving all of the piece ids and checking the answer e.g. if they all add to 45 then that's a solution. Unfortunately, addition isn't a uniquely identifying function, and neither is multiplication or addition of 2^piece_id. What will work though is changing the piece ids to prime numbers and multiplying them all together. Keeping the first digit the same the ids are now:

11, 23, 31, 41, 53, 61, 71, 83, 97

The product of these primes has no other factors and we don't care about the order since multiplication is cummutative, so to ensure each piece appears only once the WHERE can now simply be:

WHERE A.piece_id * B.piece_id * C.piece_id 
    * D.piece_id * E.piece_id * F.piece_id 
    * G.piece_id * H.piece_id * I.piece_id
    = 11*23*31*41*53*61*71*83*97;

Tuesday, June 21, 2011

SQL: 3x3 Square Picture-Puzzle Solution

Update: A second attempt at a write up.

After Reilly solved a 3x3 square picture puzzle using Prolog I made a flippant remark that it would be interesting to solve using SQL and well, here goes...

First, create a table and populate it with the pieces:

# table of all pieces in all possible rotations
CREATE TABLE rotated_pieces (
  piece_id     INTEGER, # unique piece id
  rotation     INTEGER, # 0 - top, 1 - left, 2 - bottom, 3 - right
  top         CHAR(10), # animal at top edge
  top_head    CHAR(10), # head or tail at top edge
  `right`     CHAR(10),
  right_head  CHAR(10),
  bottom      CHAR(10),
  bottom_head CHAR(10),
  `left`      CHAR(10),
  left_head   CHAR(10));

# unrotated pieces (top)
INSERT INTO rotated_pieces 
       (piece_id, rotation, 
              top,       top_head, `right`,   right_head, bottom,    bottom_head, `left`,    left_head) 
VALUES (1, 0, 'cheetah', 'tail',   'tiger',   'tail',     'lion',    'head',      'tiger',   'head'),
       (2, 0, 'lion',    'tail',   'lion',    'head',     'tiger',   'tail',      'cheetah', 'head'),
       (3, 0, 'tiger',   'tail',   'lion',    'head',     'panther', 'head',      'tiger',   'tail'),
       (4, 0, 'panther', 'tail',   'cheetah', 'head',     'panther', 'tail',      'lion',    'tail'),
       (5, 0, 'tiger',   'head',   'tiger',   'head',     'cheetah', 'head',      'lion',    'tail'),
       (6, 0, 'panther', 'tail',   'panther', 'head',     'cheetah', 'tail',      'tiger',   'head'),
       (7, 0, 'panther', 'head',   'cheetah', 'tail',     'cheetah', 'head',      'lion',    'tail'),
       (8, 0, 'panther', 'tail',   'lion',    'head',     'panther', 'head',      'cheetah', 'tail'),
       (9, 0, 'cheetah', 'head',   'tiger',   'head',     'panther', 'head',      'lion',    'tail');

Then, rotate each of those pieces so we have all 36 variations:

# rotate (top --> left)
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head) 
  SELECT piece_id, rotation+1, 
         `right` AS top, right_head AS top_head, 
         bottom AS `right`, bottom_head AS right_head, 
         `left` AS bottom, left_head AS bottom_head, 
         top AS `left`, top_head AS left_head 
    FROM rotated_pieces;

# rotate (top --> bottom, left --> right) 
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head) 
  SELECT piece_id, rotation+2, 
         bottom AS top, bottom_head AS top_head, 
         `left` AS `right`, left_head AS right_head, 
         top AS bottom, top_head AS bottom_head, 
         `right` AS `left`, right_head AS left_head 
    FROM rotated_pieces;

Then, it's a pretty simple query to return the result. The code is messed up by the WHERE clause which ensures that each piece is used only once in the solution, if there's a neater way to do this I'd like to know.

# find solution
SELECT A.piece_id AS A, A.rotation AS Ar, B.piece_id AS B, B.rotation AS Br, C.piece_id AS C, C.rotation AS Cr,
       D.piece_id AS D, D.rotation AS Dr, E.piece_id AS E, E.rotation AS Er, F.piece_id AS F, F.rotation AS Fr,
       G.piece_id AS G, G.rotation AS Gr, H.piece_id AS H, H.rotation AS Hr, I.piece_id AS I, I.rotation AS Ir
  FROM rotated_pieces A 
INNER JOIN rotated_pieces B ON (A.`right` = B.`left` AND A.right_head != B.left_head)
INNER JOIN rotated_pieces C ON (B.`right` = C.`left` AND B.right_head != C.left_head)
INNER JOIN rotated_pieces D ON (A.bottom = D.top     AND A.bottom_head != D.top_head)
INNER JOIN rotated_pieces E ON (D.`right` = E.`left` AND D.right_head != E.left_head
                                AND B.bottom = E.top AND B.bottom_head != E.top_head)
INNER JOIN rotated_pieces F ON (E.`right` = F.`left` AND E.right_head != F.left_head
                                AND C.bottom = F.top AND C.bottom_head != F.top_head)
INNER JOIN rotated_pieces G ON (D.bottom = G.top     AND D.bottom_head != G.top_head)
INNER JOIN rotated_pieces H ON (G.`right` = H.`left` AND G.right_head != H.left_head
                                AND E.bottom = H.top AND E.bottom_head != H.top_head)
INNER JOIN rotated_pieces I ON (H.`right` = I.`left` AND H.right_head != I.left_head
                                AND F.bottom = I.top AND F.bottom_head != I.top_head)
WHERE A.piece_id != B.piece_id AND A.piece_id != C.piece_id AND A.piece_id != D.piece_id
  AND A.piece_id != E.piece_id AND A.piece_id != F.piece_id AND A.piece_id != G.piece_id
  AND A.piece_id != H.piece_id AND A.piece_id != I.piece_id
  AND B.piece_id != C.piece_id AND B.piece_id != D.piece_id AND B.piece_id != E.piece_id
  AND B.piece_id != F.piece_id AND B.piece_id != G.piece_id AND B.piece_id != H.piece_id
  AND B.piece_id != I.piece_id AND C.piece_id != D.piece_id AND C.piece_id != E.piece_id
  AND C.piece_id != F.piece_id AND C.piece_id != G.piece_id AND C.piece_id != H.piece_id
  AND C.piece_id != I.piece_id
  AND D.piece_id != E.piece_id AND D.piece_id != F.piece_id AND D.piece_id != G.piece_id
  AND D.piece_id != H.piece_id AND D.piece_id != I.piece_id
  AND E.piece_id != F.piece_id AND E.piece_id != G.piece_id AND E.piece_id != H.piece_id
  AND E.piece_id != I.piece_id
  AND F.piece_id != G.piece_id AND F.piece_id != H.piece_id AND F.piece_id != I.piece_id
  AND G.piece_id != H.piece_id AND G.piece_id != I.piece_id
  AND H.piece_id != I.piece_id;

This returns 4 rows, the first is our solution:

2,1, 1,0, 6,0, 
8,3, 9,3, 7,2, 
5,3, 3,0, 4,0

The remaining 3 are the same solution with the entire board rotated:

6,1, 7,3, 4,1, 
1,1, 9,0, 3,1, 
2,2, 8,0, 5,0

4,2, 3,2, 5,1, 
7,0, 9,1, 8,1, 
6,2, 1,2, 2,3

5,2, 8,2, 2,0, 
3,3, 9,2, 1,3, 
4,3, 7,1, 6,3

I would argue the SQL version is clearer, but the Prolog version is slightly terser and should be easier to extend to a 4x4 puzzle.