Towers of Hanoi

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)