Towers of Hanoi

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Towers of Hanoi

Works with PostgreSQL

>=8.4

Written in

SQL

Depends on

Nothing

```-- auxiliary function for towers of hanoi
-- select the next state for a given move for a given stick

CREATE OR REPLACE FUNCTION hnext (move INT, ndiscs INT,
this INT[], RIGHT INT[], LEFT INT[])
RETURNS INT[]
LANGUAGE SQL AS
\$\$
SELECT
CASE WHEN \$1 % 2 = 1 THEN
-- on odd numbered moves move smallest disc,
-- clockwise if ndiscs is odd, counterclockwise if it's even
CASE WHEN 1 = any(\$3) THEN
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
WHEN \$2 %2 = 1 AND 1 = any(\$5) THEN
\$3 || 1
WHEN \$2 %2 = 0 AND 1 = any(\$4) THEN
\$3 || 1
ELSE \$3
END
ELSE
-- on even numbered moves, make the only other move possible
CASE WHEN 1 = any(\$3) THEN
\$3
WHEN 1 = any(\$5) THEN
CASE WHEN array_length(\$3,1) = 1 THEN
\$3 || \$4[array_upper(\$4,1)]
WHEN array_length(\$4,1) = 1 THEN
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
WHEN \$3[array_upper(\$3,1)] < \$4[array_upper(\$4,1)] THEN
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
ELSE
\$3 || \$4[array_upper(\$4,1)]
END
ELSE
CASE WHEN array_length(\$3,1) = 1 THEN
\$3 || \$5[array_upper(\$5,1)]
WHEN array_length(\$5,1) = 1 THEN
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
WHEN \$3[array_upper(\$3,1)] < \$5[array_upper(\$5,1)] THEN
\$3[array_lower(\$3,1):array_upper(\$3,1)-1]
ELSE
\$3|| \$5[array_upper(\$5,1)]
END
END
END
\$\$;

-- main function
-- recursively calculate the next state from the present state

CREATE OR REPLACE FUNCTION hanoi
(discs INTEGER, move OUT INTEGER, a OUT INT[], b OUT INT[], c OUT INT[])
RETURNS setof record
LANGUAGE SQL AS
\$\$
WITH recursive han AS (
SELECT 1::INT AS move, \$1 AS ndiscs,
'{99}'::INT[] || array_agg(discs)AS a,
'{99}'::INT[] AS b, '{99}'::INT[] AS c
FROM generate_series(\$1,1,-1) AS discs
UNION ALL
SELECT move + 1 , ndiscs,
hnext(move, ndiscs, a,b,c),
hnext(move, ndiscs, b,c,a),
hnext(move, ndiscs, c,a,b)
FROM han
WHERE array_length(b,1) < ndiscs + 1
)
SELECT move, a[2:\$1+1] AS a, b[2:\$1+1] AS b, c[2:\$1+1] AS c
FROM han
ORDER BY move
\$\$;

-- see all the states, use a small number here
SELECT * FROM hanoi(5);

-- count the states, can use larger numbers here
SELECT COUNT(*) FROM hanoi(16);```

--Adunstan 14:20, 21 November 2009 (UTC)