""" TAI 100, Week 4: Computation under finite resources. Part A Searching: count the steps taken by linear and binary search. Part B The same question answered two ways. "How likely is it that we are in the rainy season today, given the rain so far?" Brute force checks every possible season history; the Week 2 belief agent reuses yesterday's answer. Same answer, very different cost. Part C Memory has a cost too: a lookup table of raw weather histories against the Week 1 rainy-day count. Part D Good enough: estimating the answer by random sampling with a fixed budget. Run: python3 week04_compute.py Only the Python standard library is needed. Takes about half a minute. """ import itertools import random import time RAIN_PROB = {"rainy": 0.7, "dry": 0.15} CLOUDY_IF_RAIN, CLOUDY_IF_DRY = 0.6, 0.3 PERSISTENCE = 0.98 # -------------------------------------------------------------------------- # Part A: searching a sorted list # -------------------------------------------------------------------------- def linear_search(items, target): steps = 0 for x in items: steps += 1 if x == target: break return steps def binary_search(items, target): lo, hi, steps = 0, len(items) - 1, 0 while lo <= hi: steps += 1 mid = (lo + hi) // 2 if items[mid] == target: break if items[mid] < target: lo = mid + 1 else: hi = mid - 1 return steps # -------------------------------------------------------------------------- # Part B: brute force against the belief agent # -------------------------------------------------------------------------- def simulate(days, persistence, rng): season = "rainy" out = [] for _ in range(days): if rng.random() > persistence: season = "dry" if season == "rainy" else "rainy" rained = rng.random() < RAIN_PROB[season] cloudy = rng.random() < (CLOUDY_IF_RAIN if rained else CLOUDY_IF_DRY) out.append((cloudy, rained)) return out def like(season, rained): return RAIN_PROB[season] if rained else 1 - RAIN_PROB[season] def brute_force(rains): """P(rainy season on the last day), by listing every season history.""" steps, top, total = 0, 0.0, 0.0 for history in itertools.product(("rainy", "dry"), repeat=len(rains)): p = 0.5 * like(history[0], rains[0]) for t in range(1, len(rains)): stay = PERSISTENCE if history[t] == history[t - 1] else 1 - PERSISTENCE p *= stay * like(history[t], rains[t]) steps += 1 total += p if history[-1] == "rainy": top += p return top / total, steps def belief_filter(rains): """The same answer, the Week 2 way: carry one number forward.""" belief, steps = 0.5, 0 for t, rained in enumerate(rains): if t > 0: belief = PERSISTENCE * belief + (1 - PERSISTENCE) * (1 - belief) top = like("rainy", rained) * belief belief = top / (top + like("dry", rained) * (1 - belief)) steps += 1 return belief, steps # -------------------------------------------------------------------------- # Part C: a table of raw histories against a count # -------------------------------------------------------------------------- def learn_and_test(train, test, k, summary): counts = {} for t in range(k, len(train)): key = (train[t][0], summary(train, t, k)) r, n = counts.get(key, (0, 0)) counts[key] = (r + train[t][1], n + 1) rule = {key: r / n > 0.5 for key, (r, n) in counts.items()} right = unseen = 0 for t in range(k, len(test)): key = (test[t][0], summary(test, t, k)) if key not in rule: unseen += 1 right += rule.get(key, False) == test[t][1] n = len(test) - k return right / n, unseen / n, len(rule) def raw_history(days, t, k): return tuple(days[t - i][1] for i in range(1, k + 1)) def rainy_count(days, t, k): return sum(days[t - i][1] for i in range(1, k + 1)) # -------------------------------------------------------------------------- # Part D: estimating by sampling, with a budget # -------------------------------------------------------------------------- def sample_estimate(rains, samples, rng): """Draw random season histories, weight each by how well it explains the rain.""" top = total = 0.0 for _ in range(samples): season = "rainy" if rng.random() < 0.5 else "dry" w = like(season, rains[0]) for rained in rains[1:]: if rng.random() > PERSISTENCE: season = "dry" if season == "rainy" else "rainy" w *= like(season, rained) total += w if season == "rainy": top += w return top / total if total else 0.5 if __name__ == "__main__": print("Part A: steps to find the last item in a sorted list") print(" items linear binary") for n in (10, 1_000, 1_000_000): items = list(range(n)) print(f" {n:>9,} {linear_search(items, n - 1):>9,} {binary_search(items, n - 1):>6}") rng = random.Random(2026) days = simulate(40, PERSISTENCE, rng) rains = [r for _, r in days] print("\nPart B: P(rainy season today | rain so far), two ways") print(" days brute force steps seconds belief filter steps") for n in (4, 8, 12, 16, 20): t0 = time.perf_counter() bf, bs = brute_force(rains[:n]) secs = time.perf_counter() - t0 f, fs = belief_filter(rains[:n]) print(f" {n:>4} {bf:.6f} {bs:>14,} {secs:>8.3f} {f:.6f} {fs:>3}") print("\nPart C: raw history table against a rainy-day count (20,000 training days)") train = simulate(20_000, PERSISTENCE, rng) test = simulate(20_000, PERSISTENCE, rng) print(" k raw: entries unseen accuracy count: entries unseen accuracy") for k in (1, 3, 7, 10, 14): ra, ru, rn = learn_and_test(train, test, k, raw_history) ca, cu, cn = learn_and_test(train, test, k, rainy_count) print(f" {k:>2} {rn:>11,} {ru:>6.3f} {ra:>8.3f} {cn:>13} {cu:>6.3f} {ca:>8.3f}") print("\nPart D: estimating by sampling, 40 days of rain, 50 repeats per budget") exact, _ = belief_filter(rains) print(f" exact answer: {exact:.4f}") for samples in (10, 100, 1_000, 10_000): errs = [abs(sample_estimate(rains, samples, rng) - exact) for _ in range(50)] print(f" {samples:>6,} samples: average error {sum(errs) / len(errs):.4f}")