Skip to content

Baffling Birthdays

Find whether two people in a group share a birthday, draw random groups of birthdates, and estimate how likely a shared birthday is by simulation.

Adapted from Exercism’s problem specification (MIT). Listed under Dates & Time.

// FILE: baffling_birthdays.nomi
//# The birthday problem: how likely it is that two people in a group share
//# a birthday, estimated by drawing random groups and counting.

import
    std::calendar.{Date, Days}
    std::random.Generator
end

/// 1 January of each year a random birthdate falls in: the years from 1900
/// to 2023 without a 29 February, so every day of the year is as likely.
once new_years_days =
    1900..=2023
    |> Iter.reject(Date.is_leap_year)
    |> Iter.map(fn year -> Date.new(year, 1, 1)!)
    |> Iter.to_vector()

/// Whether two of `birthdates` fall on the same day of the year, whatever
/// the years.
pub fn has_shared_birthday(birthdates: List<Date>) -> Bool
    repeats(birthdates, [])
end

/// `group_size` birthdates, each a uniformly random day of a random year
/// that is not a leap year.
pub fn random_birthdates(group_size: NonNegativeInt) -> Generator<List<Date>>
    Generator.list(birthdate(), group_size)
end

/// The percentage of `trials` random groups of `group_size` people in
/// which two share a birthday.
pub fn estimated_probability_of_shared_birthday(
    group_size: NonNegativeInt,
    trials:     NonNegativeInt = 10000,
) -> Generator<Float>
    random_birthdates(group_size)
    |> Generator.map(has_shared_birthday)
    |> Generator.list(trials)
    |> Generator.map(fn shared ->
        hits = Iter.count_by(shared, fn yes -> yes)
        100.0 * Int.to_float(hits) / Int.to_float(trials)
    end)
end

/// Whether a date in `birthdates` falls on a day of the year in `seen`, or
/// on the day of an earlier date in `birthdates`. It stops at the first
/// repeat.
fn repeats(birthdates: List<Date>, seen: Set<(Int, Int)>) -> Bool
    case birthdates
        [] ->
            False

        [date, ..rest] ->
            day = (Date.month(date), Date.day(date))

            day in seen or repeats(rest, Set.insert(seen, day))
    end
end

/// A uniformly random day of a random common year. Each year has 365 days,
/// so one draw below 365 times the number of years picks both.
fn birthdate() -> Generator<Date>
    // The number of years is computed, so the range goes through try_from;
    // the list of years is never empty.
    Generator.int(BoundedRange.try_from(0..Vector.length(new_years_days) * 365)!)
    |> Generator.map(fn n -> Vector.get(new_years_days, n / 365)! + Days(n % 365))
end

// FILE: baffling_birthdays_test.nomi
import
    std::calendar.Date
    std::random.{Generator, Seed}
    baffling_birthdays
end

/// The value `generator` draws from a fixed seed.
fn draw<T>(generator: Generator<T>) -> T
    (value, _seed) = Generator.step(generator, Seed.from_int(2024))
    value
end

test "shared birthday"
    [
        ("one birthdate", [Date"2000-01-01"], False),
        (
            "two birthdates with same year, month, and day",
            [Date"2000-01-01", Date"2000-01-01"],
            True,
        ),
        (
            "two birthdates with same year and month, but different day",
            [Date"2012-05-09", Date"2012-05-17"],
            False,
        ),
        (
            "two birthdates with same month and day, but different year",
            [Date"1999-10-23", Date"1988-10-23"],
            True,
        ),
        (
            "two birthdates with same year, but different month and day",
            [Date"2007-12-19", Date"2007-04-27"],
            False,
        ),
        (
            "two birthdates with different year, month, and day",
            [Date"1997-08-04", Date"1963-11-23"],
            False,
        ),
        (
            "multiple birthdates without shared birthday",
            [Date"1966-07-29", Date"1977-02-12", Date"2001-12-25", Date"1980-11-10"],
            False,
        ),
        (
            "multiple birthdates with one shared birthday",
            [Date"1966-07-29", Date"1977-02-12", Date"2001-07-29", Date"1980-11-10"],
            True,
        ),
        (
            "multiple birthdates with more than one shared birthday",
            [
                Date"1966-07-29",
                Date"1977-02-12",
                Date"2001-12-25",
                Date"1980-07-29",
                Date"2019-02-12",
            ],
            True,
        ),
    ]
    |> subtests (description, birthdates, expected), description
        assert baffling_birthdays.has_shared_birthday(birthdates) == expected
    end
end

group "random birthdates"
    setup draw(baffling_birthdays.random_birthdates(100))

    test "generate requested number of birthdates"
        sizes: Range<NonNegativeInt> = 1..=20

        assert sizes
            |> Iter.all_match(fn size ->
                Iter.count(draw(baffling_birthdays.random_birthdates(size))) == size
            end)
    end

    test "years are not leap years", birthdates
        refute birthdates |> Iter.any_match(fn date -> date |> Date.year() |> Date.is_leap_year())
    end

    test "months are random", birthdates
        assert birthdates |> Iter.map(Date.month) |> Iter.to_set() |> Set.size() > 1
    end

    test "days are random", birthdates
        assert birthdates |> Iter.map(Date.day) |> Iter.to_set() |> Set.size() > 1
    end
end

test "estimated probability of at least one shared birthday"
    groups: List<(String, NonNegativeInt, Float)> = [
        ("for one person",            1,  0.0),
        ("among ten people",          10, 11.694818),
        ("among twenty-three people", 23, 50.729723),
        ("among seventy people",      70, 99.915958),
    ]

    groups
    |> subtests (description, group_size, expected), description
        estimate = draw(baffling_birthdays.estimated_probability_of_shared_birthday(group_size))

        assert Float.equal_within(estimate, expected, 1.0)
    end
end
  • Birthdates are std::calendar Dates, written in the tests as Date"2000-01-01" literals, which the compiler checks. has_shared_birthday walks the group with a set of the (month, day) pairs it has seen and stops at the first repeat, so a large group is seldom read to the end.
  • Randomness is std::random’s. random_birthdates and estimated_probability_of_shared_birthday return Generators, and the tests run them against one fixed Seed, so every run checks the same draws.
  • A birthdate is a uniformly random day of a year from 1900 to 2023 that Date.is_leap_year says has no 29 February. With no 29 February, every year has 365 days, so one Generator.int draw n below 365 times the number of years picks both: the year’s 1 January is new_years_days’s entry n / 365, and the day is n % 365 days after it. Every day of the year is equally likely, and each date costs one draw.
  • The estimate draws trials groups (10,000 by default), checks each with has_shared_birthday, and returns the percentage that share. The four estimate cases draw over a million dates, which takes seconds in a browser, so the page shows the recorded report and runs the example only when you press Run. The canonical expectations are the exact probabilities; the tests accept an estimate within one percentage point, which the canonical comments leave to the track.
  • The canonical “generate requested number of birthdates” case names no size; the test draws groups of 1 to 20. The other three random cases share one group of 100, drawn in the group’s setup.
  • The shared-birthday and estimate cases are subtests tables named by the description column; the random-birthdates cases are a group of that name, since each checks something different of the same draw.