byteland-3-check.py

"""
This program will verify a solution to Bytelandian Exchange 3. To use:

  python byteland-3-check.py < solution.txt

If the program executes with no assertion errors, your solution is correct.

The first line of the file is two integers N and p, with N = the number of the coin you start
  with and p = the smallest coin that Machine #1 will output. (For the basic challenge, p = 1,
  and for the Bonus, p = 2.)
Each line after the first is a single number that represents an exchange:
  -N means to put a coin with a value of N into Machine #1.
      This will add three coins valued N/2, N/3, and N/4 to your collection.
  N means to put a coin with a value of N into Machine #2, along with your smallest-valued coin
      with a value of at least p. This will add a coin with a value of N+1 to your collection.

For example, the input might start like this:
897 1
-897
-224
-56
-14
-3
299
300

This represents 5 uses of Machine #1 followed by 2 uses of Machine #2. At this point, the coins
you have will be: 448 301 112 74 28 18 7 4

At the end you must have at least 2 coins worth >= p, one of which is worth >= N.
"""

import sys, collections

lines = list(sys.stdin)
N, p = map(int,lines[0].split())
coins = collections.Counter()
coins[N] = 1
for line in lines[1:]:
    n = int(line)
    assert abs(n)
    if n < 0:
        # Use Machine 1
        n = -n
        assert coins[n]
        coins[n] -= 1
        coins[n//2] += 1
        coins[n//3] += 1
        coins[n//4] += 1
    else:
        # Use Machine 2
        m = min(coin for coin in coins if coins[coin])
        assert coins[n]
        assert coins[m]
        coins[n] -= 1
        coins[m] -= 1
        if n == m:
            assert coins[n] >= 0
        coins[n+1] += 1
    # Throw out useless coins
    for n in coins:
        if n < p:
            coins[n] = 0
    print("%s | %s" %
        (line.strip(),
        " ".join(map(str, sorted(list(coins.elements()), reverse=True))))
    )
largest = max(coin for coin in coins if coins[coin])
ncoins = sum(coins.values())
assert largest >= N and ncoins > 1