#light

// Align a polyomino with the bottom and left axes.
let align poly =
    let xmin = poly |> List.map (fun (x, y) -> x) |> List.min in
    let ymin = poly |> List.map (fun (x, y) -> y) |> List.min in
    List.map (fun (x, y) -> (x - xmin, y - ymin)) poly

// Give all four rotations of a polyomino.
let rotations poly =
    [poly;
     List.map (fun (x, y) -> (-y, x)) poly;
     List.map (fun (x, y) -> (-x, -y)) poly;
     List.map (fun (x, y) -> (y, -x)) poly]

// Reflect a polyomino about the Y-axis.
let reflect poly =
    List.map (fun (x, y) -> (-x, y)) poly

// Get all of the rotations and reflections of a polyomino.
let rotationsAndReflections poly =
    let rotated = rotations poly in
    List.append rotated (List.map reflect rotated)

// Get the "minimal" rotation/reflection of a polyomino.
let normalise poly =
    poly |> rotationsAndReflections |> List.map (List.sort compare)
           |> List.map align |> List.min

// The squares adjacent to a square
let adjacent (x, y) =
    [(x + 1, y);
     (x - 1, y);
     (x, y + 1);
     (x, y - 1)]

let list_to_set xs =
    List.fold_right (fun elem set -> Set.add elem set) xs Set.empty

// Get the unique squares that can be glommed onto a polyomino
let newSquares poly =
    let allAdjacent = poly |> List.map adjacent |> List.concat |> list_to_set in
    Set.diff allAdjacent (list_to_set poly) |> Set.to_list 

// Get the unique polyominoes that can be made by glomming a square
// onto an existing polyomino
let newPolys poly =
    poly |> newSquares |> List.map (fun newSquare -> List.Cons (newSquare, poly)
           |> normalise ) |> list_to_set

let monominoes = Set.singleton [(0, 0)]

// Get all the polyominoes of rank n
let rec polys rank =
    if rank = 1 then monominoes
                else polys (rank - 1) |> Set.map newPolys |> Set.union_all

let hexominoes = polys 6

// There are 35 hexominoes
printfn "There are %d hexominoes" (Set.size hexominoes)

System.Console.ReadKey(true)

I’d be surprised if the equivalent Java programme came in at less than four times as long.

This entry was posted on Sunday, October 12th, 2008 at 9:10 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.