Probability lab

== Probability lab ==
Each experiment is worked out exactly, then tried many times with random numbers.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 0
Pick a number from 1 to 5.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> x
Pick a number from 1 to 5.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 1
people in the group (2 to 100)> 1
Type a whole number from 2 to 100.
people in the group (2 to 100)> 101
Type a whole number from 2 to 100.
people in the group (2 to 100)> x
Type a whole number from 2 to 100.
people in the group (2 to 100)> 
Cancelled.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 1
people in the group (2 to 100)> 10
groups to try (100 to 5000)> 99
Type a whole number from 100 to 5000.
groups to try (100 to 5000)> 5001
Type a whole number from 100 to 5000.
groups to try (100 to 5000)> 
Cancelled.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 2
games (100 to 5000)> 
Cancelled.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 3
throws (100 to 5000)> 
Cancelled.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 4
seed (0 to 999999999)> -1
Type a whole number from 0 to 999999999.
seed (0 to 999999999)> abc
Type a whole number from 0 to 999999999.
seed (0 to 999999999)> 
Cancelled.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 4
seed (0 to 999999999)> 7
The experiments now draw from seed 7.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 1
people in the group (2 to 100)> 5
groups to try (100 to 5000)> 100
Exactly: 2.71% of groups of 5 have two people sharing a birthday.
Tried:   4 of 100 random groups did, 4.00%.
From 23 people on, a shared birthday is more likely than not.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 5
Bye.

0
x
1
1
101
x

1
10
99
5001

2

3

4
-1
abc

4
7
1
5
100
5

== Probability lab ==
Each experiment is worked out exactly, then tried many times with random numbers.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 1
people in the group (2 to 100)> 23
groups to try (100 to 5000)> 2000
Exactly: 50.73% of groups of 23 have two people sharing a birthday.
Tried:   1030 of 2000 random groups did, 51.50%.
From 23 people on, a shared birthday is more likely than not.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 1
people in the group (2 to 100)> 50
groups to try (100 to 5000)> 500
Exactly: 97.04% of groups of 50 have two people sharing a birthday.
Tried:   478 of 500 random groups did, 95.60%.
From 23 people on, a shared birthday is more likely than not.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 2
games (100 to 5000)> 3000
A host who knows where the car is always opens a door with a goat:
  staying won 1013 of 3000 (33.77%), switching 1987 (66.23%); exactly 1/3 and 2/3.
A host who opens one of the other doors at random, counting only the games where that door had a goat:
  2068 of 3000 games counted; staying won 977 (47.24%), switching 1091 (52.76%); exactly 1/2 each.
Same doors, same goat shown - what the host knew is what makes switching pay.

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 3
throws (100 to 5000)> 3600
sum  exactly       thrown
  2  1/36   2.78%     90   2.50%  #
  3  2/36   5.56%    194   5.39%  ###
  4  3/36   8.33%    307   8.53%  ####
  5  4/36  11.11%    402  11.17%  ######
  6  5/36  13.89%    521  14.47%  #######
  7  6/36  16.67%    586  16.28%  ########
  8  5/36  13.89%    500  13.89%  #######
  9  4/36  11.11%    387  10.75%  #####
 10  3/36   8.33%    313   8.69%  ####
 11  2/36   5.56%    200   5.56%  ###
 12  1/36   2.78%    100   2.78%  #

1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit
choice> 5
Bye.

1
23
2000
1
50
500
2
3000
3
3600
5

# P060 probability lab: three classic experiments, each worked out exactly
# and then run many times on EML's own random numbers - the birthday
# problem, the Monty Hall game under two kinds of host, and the sum of two
# dice.
import frac
import lab
import rng

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def ask_number(prompt, low, high):
    while True:
        trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => answer
        if answer == "":
            return -1
        True => ok
        if len(answer) > 9:
            False => ok
        for c in answer:
            if not (c >= "0" and c <= "9"):
                False => ok
        if ok and int(answer) >= low and int(answer) <= high:
            return int(answer)
        ("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0

def share(count, trials):
    return lab.percent(frac.make(count, trials))

def birthday(state):
    ask_number("people in the group", 2, 100) => n
    if n == -1:
        "Cancelled." ^0
        return
    ask_number("groups to try", 100, 5000) => trials
    if trials == -1:
        "Cancelled." ^0
        return
    lab.birthday_exact(n) => p
    lab.birthday_trials(n, trials, state[0]) => hits
    ("Exactly: " + lab.percent(p) + " of groups of " + str(n) + " have two people sharing a birthday.") ^0
    ("Tried:   " + str(hits) + " of " + str(trials) + " random groups did, " + share(hits, trials) + ".") ^0
    ("From " + str(lab.birthday_threshold()) + " people on, a shared birthday is more likely than not.") ^0

def monty(state):
    ask_number("games", 100, 5000) => trials
    if trials == -1:
        "Cancelled." ^0
        return
    lab.monty_trials(trials, state[0], False) => a
    "A host who knows where the car is always opens a door with a goat:" ^0
    ("  staying won " + str(a[1]) + " of " + str(a[0]) + " (" + share(a[1], a[0]) + "), switching " + str(a[2]) + " (" + share(a[2], a[0]) + "); exactly 1/3 and 2/3.") ^0
    lab.monty_trials(trials, state[0], True) => b
    "A host who opens one of the other doors at random, counting only the games where that door had a goat:" ^0
    ("  " + str(b[0]) + " of " + str(trials) + " games counted; staying won " + str(b[1]) + " (" + share(b[1], b[0]) + "), switching " + str(b[2]) + " (" + share(b[2], b[0]) + "); exactly 1/2 each.") ^0
    "Same doors, same goat shown - what the host knew is what makes switching pay." ^0

def dice(state):
    ask_number("throws", 100, 5000) => trials
    if trials == -1:
        "Cancelled." ^0
        return
    lab.dice_exact() => ways
    lab.dice_trials(trials, state[0]) => tally
    "sum  exactly       thrown" ^0
    for s in [2:12]:
        str(s) => a
        if len(a) == 1:
            " " + a => a
        lab.percent(frac.make(ways[s], 36)) => e
        while len(e) < 7:
            " " + e => e
        str(tally[s]) => c
        while len(c) < 5:
            " " + c => c
        share(tally[s], trials) => f
        while len(f) < 7:
            " " + f => f
        int((tally[s] * 100 + trials) / (2 * trials)) => marks
        (" " + a + "  " + str(ways[s]) + "/36 " + e + "  " + c + " " + f + "  " + "#" * marks) ^0

def set_seed(state):
    ask_number("seed", 0, 999999999) => seed
    if seed == -1:
        "Cancelled." ^0
        return
    rng.Rng(seed) => state[0]
    ("The experiments now draw from seed " + str(seed) + ".") ^0

"== Probability lab ==" ^0
"Each experiment is worked out exactly, then tried many times with random numbers." ^0
# [the generator]
[rng.Rng(2026)] => state
True => running
while running:
    "" ^0
    "1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        birthday(state)
    elif choice == "2":
        monty(state)
    elif choice == "3":
        dice(state)
    elif choice == "4":
        set_seed(state)
    elif choice == "5":
        False => running
    else:
        "Pick a number from 1 to 5." ^0
"Bye." ^0

import frac
import lab
import rng

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def ask_number(prompt, low, high):
    while True:
        answer = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
        if answer == "":
            return -1
        ok = True
        if len(answer) > 9:
            ok = False
        for c in answer:
            if not (c >= "0" and c <= "9"):
                ok = False
        if ok and int(answer) >= low and int(answer) <= high:
            return int(answer)
        print("Type a whole number from " + str(low) + " to " + str(high) + ".")

def share(count, trials):
    return lab.percent(frac.make(count, trials))

def birthday(state):
    n = ask_number("people in the group", 2, 100)
    if n == -1:
        print("Cancelled.")
        return
    trials = ask_number("groups to try", 100, 5000)
    if trials == -1:
        print("Cancelled.")
        return
    p = lab.birthday_exact(n)
    hits = lab.birthday_trials(n, trials, state[0])
    print("Exactly: " + lab.percent(p) + " of groups of " + str(n) + " have two people sharing a birthday.")
    print("Tried:   " + str(hits) + " of " + str(trials) + " random groups did, " + share(hits, trials) + ".")
    print("From " + str(lab.birthday_threshold()) + " people on, a shared birthday is more likely than not.")

def monty(state):
    trials = ask_number("games", 100, 5000)
    if trials == -1:
        print("Cancelled.")
        return
    a = lab.monty_trials(trials, state[0], False)
    print("A host who knows where the car is always opens a door with a goat:")
    print("  staying won " + str(a[1]) + " of " + str(a[0]) + " (" + share(a[1], a[0]) + "), switching " + str(a[2]) + " (" + share(a[2], a[0]) + "); exactly 1/3 and 2/3.")
    b = lab.monty_trials(trials, state[0], True)
    print("A host who opens one of the other doors at random, counting only the games where that door had a goat:")
    print("  " + str(b[0]) + " of " + str(trials) + " games counted; staying won " + str(b[1]) + " (" + share(b[1], b[0]) + "), switching " + str(b[2]) + " (" + share(b[2], b[0]) + "); exactly 1/2 each.")
    print("Same doors, same goat shown - what the host knew is what makes switching pay.")

def dice(state):
    trials = ask_number("throws", 100, 5000)
    if trials == -1:
        print("Cancelled.")
        return
    ways = lab.dice_exact()
    tally = lab.dice_trials(trials, state[0])
    print("sum  exactly       thrown")
    for s in range(2, 13):
        a = str(s)
        if len(a) == 1:
            a = " " + a
        e = lab.percent(frac.make(ways[s], 36))
        while len(e) < 7:
            e = " " + e
        c = str(tally[s])
        while len(c) < 5:
            c = " " + c
        f = share(tally[s], trials)
        while len(f) < 7:
            f = " " + f
        marks = int((tally[s] * 100 + trials) / (2 * trials))
        print(" " + a + "  " + str(ways[s]) + "/36 " + e + "  " + c + " " + f + "  " + "#" * marks)

def set_seed(state):
    seed = ask_number("seed", 0, 999999999)
    if seed == -1:
        print("Cancelled.")
        return
    state[0] = rng.Rng(seed)
    print("The experiments now draw from seed " + str(seed) + ".")

print("== Probability lab ==")
print("Each experiment is worked out exactly, then tried many times with random numbers.")
state = [rng.Rng(2026)]
running = True
while running:
    print("")
    print("1) birthdays  2) Monty Hall  3) two dice  4) seed  5) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        birthday(state)
    elif choice == "2":
        monty(state)
    elif choice == "3":
        dice(state)
    elif choice == "4":
        set_seed(state)
    elif choice == "5":
        running = False
    else:
        print("Pick a number from 1 to 5.")
print("Bye.")

# P060 probability lab - each experiment worked out exactly, as a fraction,
# and run many times on EML's own random numbers.
import frac

def percent(x):
    # A fraction [numerator, denominator] from 0 to 1 as a percentage, two
    # decimal places. The fraction need not be in lowest terms.
    frac.decimal([x[0] * 100, x[1]], 2) => s
    if len(s) > 6 and s[0:6] == "about ":
        s[6:len(s)] => s
    # always two places, so the columns line up: 2.5 -> 2.50, 50 -> 50.00
    0 => k
    while k < len(s) and s[k] != ".":
        k + 1 => k
    if k == len(s):
        s + ".00" => s
    elif len(s) - k == 2:
        s + "0" => s
    return s + "%"

def birthday_exact(n):
    # The chance that among n people (365 equally likely birthdays, no 29
    # February) at least two share one: 1 minus the chance that all differ,
    # 365/365 x 364/365 x ... x (366 - n)/365. Kept as one exact fraction,
    # not reduced: the numbers reach 60 digits, and reducing them takes long
    # division, which only showing the result needs, once.
    1 => differ
    1 => all
    for k in [0:n - 1]:
        differ * (365 - k) => differ
        all * 365 => all
    return [all - differ, all]

def birthday_threshold():
    # The smallest group where a shared birthday is more likely than not:
    # shared / all >= 1/2, compared as 2 x shared >= all - no division.
    1 => n
    birthday_exact(n) => p
    while 2 * p[0] < p[1]:
        n + 1 => n
        birthday_exact(n) => p
    return n

def birthday_trials(n, trials, g):
    # How many of `trials` random groups of n have a shared birthday.
    0 => shared
    for t in [1:trials]:
        [False] * 365 => seen
        False => hit
        for k in [1:n]:
            g.below(365) => day
            if seen[day]:
                True => hit
            True => seen[day]
        if hit:
            shared + 1 => shared
    return shared

def monty_trials(trials, g, host_random):
    # [games counted, wins by staying, wins by switching]. The car is behind
    # one of three doors and you pick one. The usual host knows where the car
    # is and opens another door with a goat (choosing at random when both
    # are goats). A host who opens one of the other two doors at random
    # sometimes shows the car; those games are not counted, so the rest are
    # the games where he happened to show a goat.
    0 => counted
    0 => stay
    0 => switch
    for t in [1:trials]:
        g.below(3) => car
        g.below(3) => pick
        # one more draw, used by either host to choose between two doors
        g.below(2) => r
        # the two doors you did not pick, in order
        [] => others
        for d in [0:2]:
            if d != pick:
                others + [d] => others
        if host_random:
            others[r] => opened
        elif others[0] == car:
            others[1] => opened
        elif others[1] == car:
            others[0] => opened
        else:
            others[r] => opened
        if opened != car:
            counted + 1 => counted
            if pick == car:
                stay + 1 => stay
            else:
                switch + 1 => switch
    return [counted, stay, switch]

def dice_exact():
    # How many of the 36 equally likely throws of two dice give each sum,
    # sums 2 to 12 at indexes 2 to 12.
    [0] * 13 => ways
    for a in [1:6]:
        for b in [1:6]:
            ways[a + b] + 1 => ways[a + b]
    return ways

def dice_trials(trials, g):
    # Throws of two dice tallied by their sum in a dict, as the corpus case
    # dice-roll-tally tallies faces: read the count, write it back plus one.
    {} => tally
    for s in [2:12]:
        0 => tally[s]
    for t in [1:trials]:
        g.below(6) + 1 + g.below(6) + 1 => s
        tally[s] + 1 => tally[s]
    return tally

import frac

def percent(x):
    s = frac.decimal([x[0] * 100, x[1]], 2)
    if len(s) > 6 and s[0:6] == "about ":
        s = s[6:len(s)]
    k = 0
    while k < len(s) and s[k] != ".":
        k = k + 1
    if k == len(s):
        s = s + ".00"
    elif len(s) - k == 2:
        s = s + "0"
    return s + "%"

def birthday_exact(n):
    differ = 1
    all = 1
    for k in range(0, n):
        differ = differ * (365 - k)
        all = all * 365
    return [all - differ, all]

def birthday_threshold():
    n = 1
    p = birthday_exact(n)
    while 2 * p[0] < p[1]:
        n = n + 1
        p = birthday_exact(n)
    return n

def birthday_trials(n, trials, g):
    shared = 0
    for t in range(1, trials+1):
        seen = [False] * 365
        hit = False
        for k in range(1, n+1):
            day = g.below(365)
            if seen[day]:
                hit = True
            seen[day] = True
        if hit:
            shared = shared + 1
    return shared

def monty_trials(trials, g, host_random):
    counted = 0
    stay = 0
    switch = 0
    for t in range(1, trials+1):
        car = g.below(3)
        pick = g.below(3)
        r = g.below(2)
        others = []
        for d in range(0, 3):
            if d != pick:
                others = others + [d]
        if host_random:
            opened = others[r]
        elif others[0] == car:
            opened = others[1]
        elif others[1] == car:
            opened = others[0]
        else:
            opened = others[r]
        if opened != car:
            counted = counted + 1
            if pick == car:
                stay = stay + 1
            else:
                switch = switch + 1
    return [counted, stay, switch]

def dice_exact():
    ways = [0] * 13
    for a in range(1, 7):
        for b in range(1, 7):
            ways[a + b] = ways[a + b] + 1
    return ways

def dice_trials(trials, g):
    tally = {}
    for s in range(2, 13):
        tally[s] = 0
    for t in range(1, trials+1):
        s = g.below(6) + 1 + g.below(6) + 1
        tally[s] = tally[s] + 1
    return tally

# P060 probability lab - exact fractions, from P007 (calculator) by way of
# P038, P044 and P056.
# A number is a list [n, d]: n / d in lowest terms with d > 0. Integers have
# no size limit, but EML has no //, and a / b goes through a float that cannot
# hold a large quotient exactly, so whole-number division is written out.

def quotient(a, b):
    # a // b for whole numbers a >= 0 and b > 0, exact at any size. Long
    # division by doubling: take away the largest b * 2^k that still fits.
    0 => q
    while a >= b:
        b => m
        1 => k
        while m + m <= a:
            m + m => m
            k + k => k
        a - m => a
        q + k => q
    return q

def gcd(a, b):
    while b != 0:
        a % b => r
        b => a
        r => b
    return a

def make(n, d):
    # n / d in lowest terms with a positive denominator (d != 0).
    if d < 0:
        0 - n => n
        0 - d => d
    abs(n) => a
    gcd(a, d) => g
    if n < 0:
        return [0 - quotient(a, g), quotient(d, g)]
    return [quotient(a, g), quotient(d, g)]

def plus(x, y):
    return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])

def minus(x, y):
    return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])

def times(x, y):
    return make(x[0] * y[0], x[1] * y[1])

def over(x, y):
    # x / y; the caller has checked that y is not zero.
    return make(x[0] * y[1], x[1] * y[0])

def is_zero(x):
    return x[0] == 0

def digits_value(s):
    # The value of a string of 1 to 9 digits, otherwise -1.
    if s == "" or len(s) > 9:
        return -1
    0 => n
    for c in s:
        if not (c in "0123456789"):
            return -1
        n * 10 + int(c) => n
    return n

def parse(s):
    # "3", "-2", "3/4", "-0.25" as a fraction; [] if it is not a number.
    1 => sign
    if len(s) > 0 and s[0] == "-":
        -1 => sign
        s[1:len(s)] => s
    0 => k
    while k < len(s) and s[k] != "/" and s[k] != ".":
        k + 1 => k
    if k == len(s):
        digits_value(s) => n
        if n < 0:
            return []
        return make(sign * n, 1)
    digits_value(s[0:k]) => whole
    s[k + 1:len(s)] => rest
    digits_value(rest) => part
    if whole < 0 or part < 0:
        return []
    if s[k] == "/":
        if part == 0:
            return []
        return make(sign * whole, part)
    # a decimal point: 0.25 is 25 / 100
    1 => scale
    for c in rest:
        scale * 10 => scale
    return make(sign * (whole * scale + part), scale)

def less(x, y):
    return x[0] * y[1] < y[0] * x[1]

def decimal(x, places):
    # x to the given number of decimal places, halves rounded away from zero,
    # with "about " in front when the value does not end there exactly.
    "" => sign
    abs(x[0]) => n
    if x[0] < 0:
        "-" => sign
    1 => scale
    for k in [1:places]:
        scale * 10 => scale
    quotient(2 * n * scale + x[1], 2 * x[1]) => t
    "" => about
    if (n * scale) % x[1] != 0:
        "about " => about
    str(quotient(t, scale)) => whole
    str(t % scale) => part
    while len(part) < places:
        "0" + part => part
    # drop trailing zeros of an exact value
    if about == "":
        while len(part) > 0 and part[len(part) - 1] == "0":
            part[0:len(part) - 1] => part
    if t == 0:
        "" => sign
    if part == "":
        return about + sign + whole
    return about + sign + whole + "." + part

def text(x):
    # "3", "-3", "3/4", "-3/4".
    if x[1] == 1:
        return str(x[0])
    return str(x[0]) + "/" + str(x[1])

def quotient(a, b):
    q = 0
    while a >= b:
        m = b
        k = 1
        while m + m <= a:
            m = m + m
            k = k + k
        a = a - m
        q = q + k
    return q

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def make(n, d):
    if d < 0:
        n = 0 - n
        d = 0 - d
    a = abs(n)
    g = gcd(a, d)
    if n < 0:
        return [0 - quotient(a, g), quotient(d, g)]
    return [quotient(a, g), quotient(d, g)]

def plus(x, y):
    return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])

def minus(x, y):
    return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])

def times(x, y):
    return make(x[0] * y[0], x[1] * y[1])

def over(x, y):
    return make(x[0] * y[1], x[1] * y[0])

def is_zero(x):
    return x[0] == 0

def digits_value(s):
    if s == "" or len(s) > 9:
        return -1
    n = 0
    for c in s:
        if not c in "0123456789":
            return -1
        n = n * 10 + int(c)
    return n

def parse(s):
    sign = 1
    if len(s) > 0 and s[0] == "-":
        sign = -1
        s = s[1:len(s)]
    k = 0
    while k < len(s) and s[k] != "/" and s[k] != ".":
        k = k + 1
    if k == len(s):
        n = digits_value(s)
        if n < 0:
            return []
        return make(sign * n, 1)
    whole = digits_value(s[0:k])
    rest = s[k + 1:len(s)]
    part = digits_value(rest)
    if whole < 0 or part < 0:
        return []
    if s[k] == "/":
        if part == 0:
            return []
        return make(sign * whole, part)
    scale = 1
    for c in rest:
        scale = scale * 10
    return make(sign * (whole * scale + part), scale)

def less(x, y):
    return x[0] * y[1] < y[0] * x[1]

def decimal(x, places):
    sign = ""
    n = abs(x[0])
    if x[0] < 0:
        sign = "-"
    scale = 1
    for k in range(1, places+1):
        scale = scale * 10
    t = quotient(2 * n * scale + x[1], 2 * x[1])
    about = ""
    if n * scale % x[1] != 0:
        about = "about "
    whole = str(quotient(t, scale))
    part = str(t % scale)
    while len(part) < places:
        part = "0" + part
    if about == "":
        while len(part) > 0 and part[len(part) - 1] == "0":
            part = part[0:len(part) - 1]
    if t == 0:
        sign = ""
    if part == "":
        return about + sign + whole
    return about + sign + whole + "." + part

def text(x):
    if x[1] == 1:
        return str(x[0])
    return str(x[0]) + "/" + str(x[1])

# P060 probability lab - random numbers written in EML: the linear congruential
# generator of P008 (number guessing), with the constants of the C
# standard's example rand(). Python's random module is not used, so a seed
# gives the same experiment on every machine, and the interpreter can check a
# whole session byte for byte.

class Rng:
    def __init__(self, seed):
        seed % 2147483648 => self.state

    def step(self):
        (1103515245 * self.state + 12345) % 2147483648 => self.state
        return self.state

    def below(self, n):
        # A number from 0 to n - 1, taken from the high bits of the state: the
        # low bits of this generator repeat with short periods. Dividing by
        # 65536 is exact in a float for a state below 2^31.
        return int(self.step() / 65536) % n

class Rng:
    def __init__(self, seed):
        self.state = seed % 2147483648
    def step(self):
        self.state = (1103515245 * self.state + 12345) % 2147483648
        return self.state
    def below(self, n):
        return int(self.step() / 65536) % n