Every heist is a running-time problem.

1 The door

Banco Infinito's vault opens with a 5-digit code. There is no lockout after wrong guesses, which is their first mistake. You know nothing about the code, so the only plan is the one from the slides: process all possibilities.

def crack(check, d):
    for n in range(10**d):      # every code
        guess = str(n).zfill(d)
        if check(guess):
            return guess

2 Now scale it

The loop body runs once per code, so the cost model is one line: T(d) = c · 10^d, where c is the time per guess. In the lecture, doubling N multiplied the time by a constant 2^b. Here, adding one digit multiplies it by 10. That is the signature of exponential growth, and it is the whole reason codes work.

Times use the rig you picked above. The average case is half the worst case: same order of growth.

3 The inside job: the lock leaks

A contractor wrote the comparison like this. It is correct. It is also a disaster.

def check(guess, secret):
    for g, s in zip(guess, secret):
        if g != s:
            return False        # gives up early
    return True

A guess with the right first digit survives one more comparison before it is rejected, so the door answers a hair later. Measure the response time for each of the ten candidates, keep the slowest, move to the next position. The digits stop being a product and become a sum.

Real attackers see nanoseconds buried in noise, so they repeat each guess many times and average, which is the same reason you repeat timing experiments. The fix is a comparison whose running time does not depend on the data (hmac.compare_digest in Python), plus a lockout.

4 Debrief

You're in. On to Job 2 →

1 Cook the books

The money is out. To keep the audit quiet you need sets of three ledger entries that cancel to exactly zero, so you can bury the withdrawal among them. That is the three-sum problem. The brute-force plan checks every triple with i < j < k, so each one is seen once instead of six times.

The lecture's array. 20 triples to check.

def count(a):
    N = len(a)
    cnt = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                if a[i] + a[j] + a[k] == 0:
                    cnt += 1
    return cnt

2 Commit to a guess

The real ledger has 1,000,000 entries and the only computer you have is the device in your hand. Before measuring anything: how long will count take?

3 Run the doubling experiment

You can't afford to run N = 1,000,000 to find out. You can afford small N. Hypothesis: T(N) ~ a·N^b. Then T(2N) / T(N) → 2^b, and a cancels. This runs the real code on your machine, doubling N while it stays affordable.

4 Hire a better algorithm

A faster laptop buys you a constant factor. A better idea buys you an exponent. Sort the ledger once, then for each i walk two pointers inward from both ends: the inner two loops collapse into one.

def count_fast(a):
    a = sorted(a)               # N log N, once
    N, cnt = len(a), 0
    for i in range(N - 2):
        lo, hi = i + 1, N - 1
        while lo < hi:          # at most N steps
            s = a[i] + a[lo] + a[hi]
            if s == 0:
                cnt += 1; lo += 1; hi -= 1
            elif s < 0:
                lo += 1         # sum too small
            else:
                hi -= 1         # sum too big
    return cnt                  # entries distinct

5 Debrief