Skip to content

Zebra Puzzle

Solve the zebra puzzle: from fifteen statements about five houses, find who drinks water and who owns the zebra.

Adapted from Exercism’s problem specification (MIT). Listed under Games & Simulation.

// FILE: zebra_puzzle.nomi
//# The zebra puzzle, solved by search. Each of the five attributes is an
//# order: the house, 0 to 4 from the left, of each of its five values. The
//# search adds one attribute at a time, keeping only the orders that fit the
//# statements about the attributes added so far.

/// Where a resident comes from.
pub enum Nationality
    Englishman
    Spaniard
    Ukrainian
    Norwegian
    Japanese
end

/// The puzzle's two answers.
pub struct Solution
    drinks_water: Nationality
    owns_zebra:   Nationality
end

/// The houses of the five values of one attribute, in the order the
/// attribute lists them.
typealias Order (Int, Int, Int, Int, Int)

/// Every way to put five values in five houses.
once orders: List<Order> =
    0..=4
    |> Iter.permutations()
    |> Iter.map(fn houses ->
        [a, b, c, d, e] = houses else unreachable "a permutation of five houses has five"
        (a, b, c, d, e)
    end)
    |> Iter.to_list()

/// The resident who drinks water.
pub fn drinks_water() -> Nationality
    solve().drinks_water
end

/// The resident who owns the zebra.
pub fn owns_zebra() -> Nationality
    solve().owns_zebra
end

/// The one street the fifteen statements allow. The statement numbers are
/// the puzzle's; 1 is the five houses themselves, and 6 is the only one
/// about colors alone.
fn solve() -> Solution
    solutions =
        orders
        |> Iter.filter(fn (_red, green, ivory, _yellow, _blue) -> green == ivory + 1)
        |> Iter.flat_map(add_nations)
        |> Iter.flat_map(add_drinks)
        |> Iter.flat_map(add_hobbies)
        |> Iter.flat_map(add_pets)
        |> Iter.to_list()

    [solution] = solutions else unreachable "the puzzle has exactly one solution"

    solution
end

/// Each way to add the nationalities to `colors` that fits statements 2,
/// 10 and 15.
fn add_nations(colors: Order) -> List<(Order, Order)>
    (red, _green, _ivory, _yellow, blue) = colors

    orders
    |> Iter.filter(fn (english, _spaniard, _ukrainian, norwegian, _japanese) ->
        english == red and norwegian == 0 and is_next_to(norwegian, blue)
    end)
    |> Iter.map(&(colors, &1))
    |> Iter.to_list()
end

/// Each way to add the drinks that fits statements 4, 5 and 9.
fn add_drinks((colors, nations): (Order, Order)) -> List<(Order, Order, Order)>
    (_red, green, _ivory, _yellow, _blue) = colors
    (_english, _spaniard, ukrainian, _norwegian, _japanese) = nations

    orders
    |> Iter.filter(fn (coffee, tea, milk, _orange_juice, _water) ->
        coffee == green and tea == ukrainian and milk == 2
    end)
    |> Iter.map(&(colors, nations, &1))
    |> Iter.to_list()
end

/// Each way to add the hobbies that fits statements 8, 13 and 14.
fn add_hobbies(
    (colors, nations, drinks): (Order, Order, Order),
) -> List<(Order, Order, Order, Order)>
    (_red, _green, _ivory, yellow, _blue) = colors
    (_english, _spaniard, _ukrainian, _norwegian, japanese) = nations
    (_coffee, _tea, _milk, orange_juice, _water) = drinks

    orders
    |> Iter.filter(fn (_dancing, painting, _reading, football, chess) ->
        painting == yellow and football == orange_juice and chess == japanese
    end)
    |> Iter.map(&(colors, nations, drinks, &1))
    |> Iter.to_list()
end

/// The answers for each way to add the pets that fits statements 3, 7, 11
/// and 12.
fn add_pets((_colors, nations, drinks, hobbies): (Order, Order, Order, Order)) -> List<Solution>
    (_english, spaniard, _ukrainian, _norwegian, _japanese) = nations
    (_coffee, _tea, _milk, _orange_juice, water) = drinks
    (dancing, painting, reading, _football, _chess) = hobbies

    orders
    |> Iter.filter(fn (dog, snail, fox, horse, _zebra) ->
        dog == spaniard
            and snail == dancing
            and is_next_to(reading, fox)
            and is_next_to(painting, horse)
    end)
    |> Iter.map(fn (_dog, _snail, _fox, _horse, zebra) ->
        Solution{drinks_water: resident(nations, water), owns_zebra: resident(nations, zebra)}
    end)
    |> Iter.to_list()
end

/// The nationality of whoever lives in `house`.
fn resident(nations: Order, house: Int) -> Nationality
    (english, spaniard, ukrainian, norwegian, japanese) = nations

    case
        house == english   -> .Englishman
        house == spaniard  -> .Spaniard
        house == ukrainian -> .Ukrainian
        house == norwegian -> .Norwegian
        house == japanese  -> .Japanese
        _                  -> unreachable "the five nationalities live in the five houses"
    end
end

fn is_next_to(one: Int, other: Int) -> Bool
    Int.abs(one - other) == 1
end

// FILE: zebra_puzzle_test.nomi
import zebra_puzzle

test "resident who drinks water"
    assert zebra_puzzle.drinks_water() == .Norwegian
end

test "resident who owns zebra"
    assert zebra_puzzle.owns_zebra() == .Japanese
end
  • The two answers are a Nationality enum, and drinks_water and owns_zebra read them from one solve, as the canonical data’s two properties ask.
  • Each attribute is an Order, a five-tuple of houses named with a typealias: an order of the colors says where the red, green, ivory, yellow and blue houses are. Tuple patterns name each value’s house where a statement uses it ((red, _green, _ivory, _yellow, blue)), so each statement reads as a comparison of houses: english == red, is_next_to(reading, fox).
  • The search adds one attribute at a time: the color orders that fit statement 6, then add_nations, add_drinks, add_hobbies and add_pets, each a flat_map stage answering every way to extend what came before that fits the statements about the attributes it can now see. Ordering the stages by which statements become checkable prunes the 120⁵ combinations to a few thousand.
  • Each stage carries what came before as a tuple of orders, (colors, nations, drinks), and takes it apart in its parameter pattern.
  • The puzzle has one solution, so solve takes the list of solutions apart with [solution], and anything else is an unreachable that says so.
  • orders is a once of the 120 permutations of the five houses, computed once and shared by every stage. They come from std’s Iter.permutations.
  • resident finds the nationality in a house with a case of conditions, one arm per nationality (style §27).