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
endok shared birthday (9 cases)
ok random birthdates / generate requested number of birthdates
ok random birthdates / years are not leap years
ok random birthdates / months are random
ok random birthdates / days are random
ok estimated probability of at least one shared birthday (4 cases)
test result: ok. 17 passed, 0 failed
How it’s written
Section titled “How it’s written”- Birthdates are
std::calendarDates, written in the tests asDate"2000-01-01"literals, which the compiler checks.has_shared_birthdaywalks 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_birthdatesandestimated_probability_of_shared_birthdayreturnGenerators, and the tests run them against one fixedSeed, 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_yearsays has no 29 February. With no 29 February, every year has 365 days, so oneGenerator.intdrawnbelow 365 times the number of years picks both: the year’s 1 January isnew_years_days’s entryn / 365, and the day isn % 365days after it. Every day of the year is equally likely, and each date costs one draw. - The estimate draws
trialsgroups (10,000 by default), checks each withhas_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
subteststables named by the description column; the random-birthdates cases are agroupof that name, since each checks something different of the same draw.