Tuesday, November 3. 2009
Here's a query that probably seems less than obvious:
with recursive h as (
select 1::int as move, '{99,5,4,3,2,1}'::int[] as a,
'{99}'::int[] as b, '{99}'::int[] as c
union all
select move + 1 ,
case when move % 2 = 1 then
case when 1 = any(a) then
a[array_lower(a,1):array_upper(a,1)-1]
when 1 = any(c) then
a || 1
else a
end
else
case when 1 = any(a) then
a
when 1 = any(c) then
case when array_length(a,1) = 1 then
a || b[array_upper(b,1)]
when array_length(b,1) = 1 then
a[array_lower(a,1):array_upper(a,1)-1]
when a[array_upper(a,1)] < b[array_upper(b,1)] then
a[array_lower(a,1):array_upper(a,1)-1]
else
a || b[array_upper(b,1)]
end
else
case when array_length(a,1) = 1 then
a || c[array_upper(c,1)]
when array_length(c,1) = 1 then
a[array_lower(a,1):array_upper(a,1)-1]
when a[array_upper(a,1)] < c[array_upper(c,1)] then
a[array_lower(a,1):array_upper(a,1)-1]
else
a || c[array_upper(c,1)]
end
end
end,
case when move % 2 = 1 then
case when 1 = any(b) then
b[array_lower(b,1):array_upper(b,1)-1]
when 1 = any(a) then
b || 1
else b
end
else
case when 1 = any(b) then
b
when 1 = any(a) then
case when array_length(b,1) = 1 then
b || c[array_upper(c,1)]
when array_length(c,1) = 1 then
b[array_lower(b,1):array_upper(b,1)-1]
when b[array_upper(b,1)] < c[array_upper(c,1)] then
b[array_lower(b,1):array_upper(b,1)-1]
else
b || c[array_upper(c,1)]
end
else
case when array_length(b,1) = 1 then
b || a[array_upper(a,1)]
when array_length(a,1) = 1 then
b[array_lower(b,1):array_upper(b,1)-1]
when b[array_upper(b,1)] < a[array_upper(a,1)] then
b[array_lower(b,1):array_upper(b,1)-1]
else
b || a[array_upper(a,1)]
end
end
end,
case when move % 2 = 1 then
case when 1 = any(c) then
c[array_lower(c,1):array_upper(c,1)-1]
when 1 = any(b) then
c || 1
else c
end
else
case when 1 = any(c) then
c
when 1 = any(b) then
case when array_length(c,1) = 1 then
c || a[array_upper(a,1)]
when array_length(a,1) = 1 then
c[array_lower(c,1):array_upper(c,1)-1]
when c[array_upper(c,1)] < a[array_upper(a,1)] then
c[array_lower(c,1):array_upper(c,1)-1]
else
c || a[array_upper(a,1)]
end
else
case when array_length(c,1) = 1 then
c || b[array_upper(b,1)]
when array_length(b,1) = 1 then
c[array_lower(c,1):array_upper(c,1)-1]
when c[array_upper(c,1)] < b[array_upper(b,1)] then
c[array_lower(c,1):array_upper(c,1)-1]
else
c || b[array_upper(b,1)]
end
end
end
from h
where array_length(b,1) < 6
)
select move, a[2:6] as a, b[2:6] as b, c[2:6] as c
from h
order by move
and here is the output:
move | a | b | c
------+-------------+-------------+-----------
1 | {5,4,3,2,1} | {} | {}
2 | {5,4,3,2} | {1} | {}
3 | {5,4,3} | {1} | {2}
4 | {5,4,3} | {} | {2,1}
5 | {5,4} | {3} | {2,1}
6 | {5,4,1} | {3} | {2}
7 | {5,4,1} | {3,2} | {}
8 | {5,4} | {3,2,1} | {}
9 | {5} | {3,2,1} | {4}
10 | {5} | {3,2} | {4,1}
11 | {5,2} | {3} | {4,1}
12 | {5,2,1} | {3} | {4}
13 | {5,2,1} | {} | {4,3}
14 | {5,2} | {1} | {4,3}
15 | {5} | {1} | {4,3,2}
16 | {5} | {} | {4,3,2,1}
17 | {} | {5} | {4,3,2,1}
18 | {1} | {5} | {4,3,2}
19 | {1} | {5,2} | {4,3}
20 | {} | {5,2,1} | {4,3}
21 | {3} | {5,2,1} | {4}
22 | {3} | {5,2} | {4,1}
23 | {3,2} | {5} | {4,1}
24 | {3,2,1} | {5} | {4}
25 | {3,2,1} | {5,4} | {}
26 | {3,2} | {5,4,1} | {}
27 | {3} | {5,4,1} | {2}
28 | {3} | {5,4} | {2,1}
29 | {} | {5,4,3} | {2,1}
30 | {1} | {5,4,3} | {2}
31 | {1} | {5,4,3,2} | {}
32 | {} | {5,4,3,2,1} | {}
which some at least will recognize as the sequence of states of a Towers of Hanoi game.
While this probably seems fairly useless, I actually learned a thing or two while writing it.
First, when I used UNION instead of UNION ALL I got this somewhat obscure error:
ERROR: could not implement recursive UNION
DETAIL: All column datatypes must be hashable.
h/t RhodiumToad (a.k.a. Andrew Gierth) for diagnosing that.
Second, array_length() on an empty array annoyingly returns NULL. That's what the '99' entries in the arrays above are there to prevent.
So never underestimate the usefulness of silly demos (this is written for a talk next week) to teach things worth knowing.
Incidentally, the Towers of Hanoi is an interesting problem for this reason: that the recursive algorithm for implementing it is far, far more intuitive to grasp than any non-recursive algorithm I know of, which makes it an excellent vehicle for teaching recursion to students who often don't get recursion immediately.
Note that while I have used recursion above to accumulate the states, the actual algorithm used for calculating one state from the previous state is not recursive.
The simple recursive algorithm is this: to move N disks from stick A to stick B, do:
- move N - 1 disks from stick A to stick C
- move 1 disk from stick A to stick B
- move N - 1 disks from stick C to stick B
The non-recursive algorithm I used is this:
- on odd numbered moves, move the smallest disk one stick clockwise, wrapping around
- on even numbered moves, make the only move possible of a disk that is not the smallest
Not so obvious, at least to me.
What, fun, eh?
Update
There's actually a small bug in the non-recursive algorithm as I stated it (and implemented it). When the number of discs is even, the smallest disc should move counter-clockwise, not clockwise. Otherwise, a solution is reached but it's not the smallest solution.
|
