Towers of Hanoi

From PostgreSQL wiki

Revision as of 14:20, 21 November 2009 by Adunstan (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Fun Snippets

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)

Personal tools