Project P013
Bill splitter
Share expenses among up to eight people - each paid by one, shared equally or in shares, split to the cent by largest remainder - see who owes whom, and settle up in the fewest transfers possible, found exactly by trying every group - from a text menu.
4 modules · 3 recorded sessionstext-menu UI in the terminalupdated 2026-10-03
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
People share expenses: each expense is paid by one of them and shared by some or all of them, equally or in shares. The program splits every expense to the cent, shows what each person has paid and owes, and settles up in the fewest transfers possible. Up to eight people; everything lives while the program runs.
main.eml- the menu and its questions, with their checks, and what the screen showssplit.eml- splitting one expense to the cent, and each person's paid and share totalssettle.eml- the fewest transfers that make everyone eventext.eml- trimming, lower case, whole numbers, words, and money
Splitting to the cent: every part is first rounded down, and the cents left over go one each to the parts that lost the most in the rounding (largest remainder); on a tie - always the case for equal shares - to the person listed first. So the parts always add up to the expense, and the screen says who got the leftover cents: 10.01 split three ways is 3.34, 3.34 and 3.33, and 64.31 in shares 1:1:2:1 gives its one leftover cent to the double share, whose remainder is the largest.
Settling up: people whose balances add up to zero among themselves can settle inside their own group, and a group of g people needs g - 1 transfers. So the fewest transfers is the number of people with a balance minus the largest number of zero-sum groups they can be split into. With at most eight people that is found exactly by trying every subset (at most 256), and each group then settles by the largest debt paying the largest credit. Paying the largest debt to the largest credit across everyone at once is not always enough: when it needs more transfers, the screen says how many.
What is checked: a name has at most 20 characters and is not already taken in any case; an expense needs at least two people, a description of at most 30 characters, and an amount written like 12.50 that is more than 0 and at most 100,000.00; the payer is a person's number; the sharers are people's numbers, each once (nothing means everyone); the shares are one whole number from 1 to 100 per sharer (nothing means equal). Anything else asks again; an empty description, amount or payer cancels.
Sessions: sessions/basic.in has four friends share a dinner equally, a taxi three ways (two leftover cents), groceries in shares 1:1:2:1 (one leftover cent, to the largest remainder) and a museum visit two ways, then lists the expenses, the balances and three transfers; sessions/fewest-transfers.in has five people whose balances fall into two groups that each add up to zero, so three transfers settle everyone where paying largest debt to largest credit would take four; sessions/bad-input.in asks for an expense, the balances and settling up too early, types names that are empty, too long or taken, amounts that are words, 0, negative or with three decimals, payers and sharers that do not exist or repeat, shares of the wrong number or out of range, and goes past eight people.
Built on the verified corpus cases money-in-cents (amounts kept in whole cents so the parts equal the whole) and apportionment-remainder (largest remainder: parts that add back up to the whole, with the tie broken in a stated order).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 0
Pick a number from 1 to 6.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
Add at least two people first.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 4
No people yet.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 5
Everyone is even.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name>
Cancelled.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> A name that is much too long
At most 20 characters.
name> Ana
Person 1: Ana.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> ana
There is already someone called Ana.
name> Ben
Person 2: Ben.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for>
Cancelled.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Lunch
amount> abc
Type an amount like 12.50, or nothing to cancel.
amount> 0
An amount is more than 0.
amount> 12.345
Type an amount like 12.50, or nothing to cancel.
amount> -5
Type an amount like 12.50, or nothing to cancel.
amount> 12.5
People: 1) Ana 2) Ben
paid by> 3
Type a person's number from 1 to 2, or nothing to cancel.
paid by> x
Type a person's number from 1 to 2, or nothing to cancel.
paid by> 1
shared by (numbers, nothing = everyone)> 1 1
Type the numbers of the people who shared it, 1 to 2, each once - or nothing for everyone.
shared by (numbers, nothing = everyone)> 3
Type the numbers of the people who shared it, 1 to 2, each once - or nothing for everyone.
shared by (numbers, nothing = everyone)> 2,1
shares (nothing = equal)> 1
Type one share from 1 to 100 for each of the 2 people, or nothing for equal shares.
shares (nothing = equal)> 0 1
Type one share from 1 to 100 for each of the 2 people, or nothing for equal shares.
shares (nothing = equal)> a b
Type one share from 1 to 100 for each of the 2 people, or nothing for equal shares.
shares (nothing = equal)>
Added:
1) Lunch 12.50, paid by Ana
Ben 6.25, Ana 6.25
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 3
-- expenses --
1) Lunch 12.50, paid by Ana
Ben 6.25, Ana 6.25
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 4
-- balances --
Ana paid 12.50 share 6.25 is owed 6.25
Ben paid 0.00 share 6.25 owes 6.25
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 5
-- settle up --
Ben pays Ana 6.25
1 transfer settles everyone - the fewest possible.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Chen
Person 3: Chen.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Dev
Person 4: Dev.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Eve
Person 5: Eve.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Fay
Person 6: Fay.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Gus
Person 7: Gus.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Hal
Person 8: Hal.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
At most 8 people.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 6
Bye.
What was typed (48 lines)
0
2
4
5
1
1
A name that is much too long
Ana
1
ana
Ben
2
2
Lunch
abc
0
12.345
-5
12.5
3
x
1
1 1
3
2,1
1
0 1
a b
3
4
5
1
Chen
1
Dev
1
Eve
1
Fay
1
Gus
1
Hal
1
6
basic
interpreter: byte-equal
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Ana
Person 1: Ana.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Ben
Person 2: Ben.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Chen
Person 3: Chen.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Dev
Person 4: Dev.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Dinner
amount> 100
People: 1) Ana 2) Ben 3) Chen 4) Dev
paid by> 1
shared by (numbers, nothing = everyone)>
shares (nothing = equal)>
Added:
1) Dinner 100.00, paid by Ana
Ana 25.00, Ben 25.00, Chen 25.00, Dev 25.00
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Taxi
amount> 10.01
People: 1) Ana 2) Ben 3) Chen 4) Dev
paid by> 2
shared by (numbers, nothing = everyone)> 1 2 3
shares (nothing = equal)>
Added:
2) Taxi 10.01, paid by Ben
Ana 3.34, Ben 3.34, Chen 3.33
2 leftover cents to Ana and Ben
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Groceries
amount> 64.31
People: 1) Ana 2) Ben 3) Chen 4) Dev
paid by> 3
shared by (numbers, nothing = everyone)>
shares (nothing = equal)> 1 1 2 1
Added:
3) Groceries 64.31, paid by Chen
Ana 12.86, Ben 12.86, Chen 25.73, Dev 12.86 (shares 1:1:2:1)
1 leftover cent to Chen
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Museum
amount> 45
People: 1) Ana 2) Ben 3) Chen 4) Dev
paid by> 4
shared by (numbers, nothing = everyone)> 2 4
shares (nothing = equal)>
Added:
4) Museum 45.00, paid by Dev
Ben 22.50, Dev 22.50
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 3
-- expenses --
1) Dinner 100.00, paid by Ana
Ana 25.00, Ben 25.00, Chen 25.00, Dev 25.00
2) Taxi 10.01, paid by Ben
Ana 3.34, Ben 3.34, Chen 3.33
2 leftover cents to Ana and Ben
3) Groceries 64.31, paid by Chen
Ana 12.86, Ben 12.86, Chen 25.73, Dev 12.86 (shares 1:1:2:1)
1 leftover cent to Chen
4) Museum 45.00, paid by Dev
Ben 22.50, Dev 22.50
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 4
-- balances --
Ana paid 100.00 share 41.20 is owed 58.80
Ben paid 10.01 share 63.70 owes 53.69
Chen paid 64.31 share 54.06 is owed 10.25
Dev paid 45.00 share 60.36 owes 15.36
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 5
-- settle up --
Ben pays Ana 53.69
Dev pays Chen 10.25
Dev pays Ana 5.11
3 transfers settle everyone - the fewest possible.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 6
Bye.
What was typed (36 lines)
1
Ana
1
Ben
1
Chen
1
Dev
2
Dinner
100
1
2
Taxi
10.01
2
1 2 3
2
Groceries
64.31
3
1 1 2 1
2
Museum
45
4
2 4
3
4
5
6
fewest-transfers
interpreter: byte-equal
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Ana
Person 1: Ana.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Ben
Person 2: Ben.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Chen
Person 3: Chen.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Dev
Person 4: Dev.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 1
name> Eve
Person 5: Eve.
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Concert tickets
amount> 60
People: 1) Ana 2) Ben 3) Chen 4) Dev 5) Eve
paid by> 2
shared by (numbers, nothing = everyone)> 2 3
shares (nothing = equal)>
Added:
1) Concert tickets 60.00, paid by Ben
Ben 30.00, Chen 30.00
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Boat trip
amount> 60
People: 1) Ana 2) Ben 3) Chen 4) Dev 5) Eve
paid by> 1
shared by (numbers, nothing = everyone)> 1 4 5
shares (nothing = equal)>
Added:
2) Boat trip 60.00, paid by Ana
Ana 20.00, Dev 20.00, Eve 20.00
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 2
what for> Snacks for Dev
amount> 5
People: 1) Ana 2) Ben 3) Chen 4) Dev 5) Eve
paid by> 5
shared by (numbers, nothing = everyone)> 4
Added:
3) Snacks for Dev 5.00, paid by Eve
Dev 5.00
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 4
-- balances --
Ana paid 60.00 share 20.00 is owed 40.00
Ben paid 60.00 share 30.00 is owed 30.00
Chen paid 0.00 share 30.00 owes 30.00
Dev paid 0.00 share 25.00 owes 25.00
Eve paid 5.00 share 20.00 owes 15.00
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 5
-- settle up --
Dev pays Ana 25.00
Eve pays Ana 15.00
Chen pays Ben 30.00
3 transfers settle everyone - the fewest possible (paying the largest debt to the largest credit first would take 4).
== Bill splitter ==
1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit
choice> 6
Bye.
What was typed (30 lines)
1
Ana
1
Ben
1
Chen
1
Dev
1
Eve
2
Concert tickets
60
2
2 3
2
Boat trip
60
1
1 4 5
2
Snacks for Dev
5
5
4
4
5
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P013 bill splitter: people share expenses - each paid by one of them and
# shared by some or all, equally or in shares, to the cent. The balances say
# who is owed and who owes, and settling up finds the fewest transfers that
# make everyone even.
import split
import settle
import text
8 => most_people
def plural(n, word):
if n == 1:
return "1 " + word
return str(n) + " " + word + "s"
def contains(xs, v):
for x in xs:
if x == v:
return True
return False
def join_names(names):
# "Ana", "Ana and Ben", "Ana, Ben and Chen".
if len(names) == 1:
return names[0]
"" => out
for i in [0:len(names) - 2]:
if i > 0:
out + ", " => out
out + names[i] => out
return out + " and " + names[len(names) - 1]
def show_expense(n, e, people):
(" " + str(n) + ") " + e[0] + " " + text.money(e[1]) + ", paid by " + people[e[2]]) ^0
"" => line
False => weighted
for k in [0:len(e[3]) - 1]:
if k > 0:
line + ", " => line
line + people[e[3][k]] + " " + text.money(e[5][k]) => line
if e[4][k] != 1:
True => weighted
if weighted:
"" => ratio
for k in [0:len(e[4]) - 1]:
if k > 0:
ratio + ":" => ratio
ratio + str(e[4][k]) => ratio
line + " (shares " + ratio + ")" => line
(" " + line) ^0
[] => lucky
for k in [0:len(e[3]) - 1]:
if e[6][k]:
lucky + [people[e[3][k]]] => lucky
if len(lucky) > 0:
(" " + plural(len(lucky), "leftover cent") + " to " + join_names(lucky)) ^0
def ask_text(prompt, longest):
# Text of at most longest characters, asked again until it fits; "" cancels.
while True:
text.trim(input(prompt)) => answer
if len(answer) <= longest:
return answer
("At most " + str(longest) + " characters.") ^0
def ask_name(people):
# A new person's name, asked again until a good one is typed; "" cancels.
while True:
ask_text("name> ", 20) => name
if name == "":
return ""
0 => clash
for p in people:
if text.lower(p) == text.lower(name):
1 => clash
("There is already someone called " + p + ".") ^0
if clash == 0:
return name
def ask_amount():
# An amount in cents, asked again until a good one is typed; -1 cancels.
while True:
text.trim(input("amount> ")) => answer
if answer == "":
return 0 - 1
text.parse_cents(answer) => c
if c == 0 - 1:
"Type an amount like 12.50, or nothing to cancel." ^0
elif c == 0:
"An amount is more than 0." ^0
elif c > 10000000:
"An amount is at most 100,000.00." ^0
else:
return c
def ask_payer(people):
# The index of the person who paid; -1 cancels.
while True:
text.trim(input("paid by> ")) => answer
if answer == "":
return 0 - 1
text.number(answer) => n
if n >= 1 and n <= len(people):
return n - 1
("Type a person's number from 1 to " + str(len(people)) + ", or nothing to cancel.") ^0
def ask_sharers(people):
# The indexes of the people who shared it, in the order typed; nothing
# typed means everyone.
while True:
text.words(input("shared by (numbers, nothing = everyone)> ")) => ws
[] => out
if len(ws) == 0:
for i in [0:len(people) - 1]:
out + [i] => out
return out
True => good
for w in ws:
text.number(w) => n
if n < 1 or n > len(people) or contains(out, n - 1):
False => good
else:
out + [n - 1] => out
if good:
return out
("Type the numbers of the people who shared it, 1 to " + str(len(people)) + ", each once - or nothing for everyone.") ^0
def ask_shares(count):
# One share for each of count people; nothing typed means equal shares.
[] => equal
for i in [1:count]:
equal + [1] => equal
if count == 1:
return equal
while True:
text.words(input("shares (nothing = equal)> ")) => ws
if len(ws) == 0:
return equal
[] => out
for w in ws:
text.number(w) => n
if n >= 1 and n <= 100:
out + [n] => out
if len(ws) == count and len(out) == count:
return out
("Type one share from 1 to 100 for each of the " + str(count) + " people, or nothing for equal shares.") ^0
[] => people
[] => expenses
True => running
while running:
"" ^0
"== Bill splitter ==" ^0
"1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit" ^0
text.trim(input("choice> ")) => choice
if choice == "1":
if len(people) == most_people:
("At most " + str(most_people) + " people.") ^0
else:
ask_name(people) => name
if name == "":
"Cancelled." ^0
else:
people + [name] => people
("Person " + str(len(people)) + ": " + name + ".") ^0
elif choice == "2":
if len(people) < 2:
"Add at least two people first." ^0
else:
ask_text("what for> ", 30) => what
0 - 1 => amount
0 - 1 => payer
if what != "":
ask_amount() => amount
if amount != 0 - 1:
"" => listing
for i in [0:len(people) - 1]:
listing + " " + str(i + 1) + ") " + people[i] => listing
("People:" + listing) ^0
ask_payer(people) => payer
if payer == 0 - 1:
"Cancelled." ^0
else:
ask_sharers(people) => sharers
ask_shares(len(sharers)) => weights
split.split(amount, weights) => r
expenses + [[what, amount, payer, sharers, weights, r[0], r[1]]] => expenses
"Added:" ^0
show_expense(len(expenses), expenses[len(expenses) - 1], people)
elif choice == "3":
if len(expenses) == 0:
"No expenses yet." ^0
else:
"" ^0
"-- expenses --" ^0
for i in [0:len(expenses) - 1]:
show_expense(i + 1, expenses[i], people)
elif choice == "4":
if len(people) == 0:
"No people yet." ^0
else:
split.balances(len(people), expenses) => bals
"" ^0
"-- balances --" ^0
for i in [0:len(people) - 1]:
bals[i][0] - bals[i][1] => diff
"even" => status
if diff > 0:
"is owed " + text.money(diff) => status
elif diff < 0:
"owes " + text.money(0 - diff) => status
(" " + ("%-21s" % people[i]) + "paid " + ("%10s" % text.money(bals[i][0])) + " share " + ("%10s" % text.money(bals[i][1])) + " " + status) ^0
elif choice == "5":
split.balances(len(people), expenses) => bals
[] => owed
for i in [0:len(people) - 1]:
if bals[i][0] != bals[i][1]:
owed + [[i, bals[i][0] - bals[i][1]]] => owed
if len(owed) == 0:
"Everyone is even." ^0
else:
settle.fewest(owed) => plan
"" ^0
"-- settle up --" ^0
for t in plan:
(" " + people[t[0]] + " pays " + people[t[1]] + " " + text.money(t[2])) ^0
if len(plan) == 1:
"1 transfer settles everyone - the fewest possible" => line
else:
str(len(plan)) + " transfers settle everyone - the fewest possible" => line
len(settle.pay_largest_first(owed)) => naive
if naive > len(plan):
line + " (paying the largest debt to the largest credit first would take " + str(naive) + ")" => line
(line + ".") ^0
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import split
import settle
import text
most_people = 8
def plural(n, word):
if n == 1:
return "1 " + word
return str(n) + " " + word + "s"
def contains(xs, v):
for x in xs:
if x == v:
return True
return False
def join_names(names):
if len(names) == 1:
return names[0]
out = ""
for i in range(0, len(names) - 2+1):
if i > 0:
out = out + ", "
out = out + names[i]
return out + " and " + names[len(names) - 1]
def show_expense(n, e, people):
print(" " + str(n) + ") " + e[0] + " " + text.money(e[1]) + ", paid by " + people[e[2]])
line = ""
weighted = False
for k in range(0, len(e[3])):
if k > 0:
line = line + ", "
line = line + people[e[3][k]] + " " + text.money(e[5][k])
if e[4][k] != 1:
weighted = True
if weighted:
ratio = ""
for k in range(0, len(e[4])):
if k > 0:
ratio = ratio + ":"
ratio = ratio + str(e[4][k])
line = line + " (shares " + ratio + ")"
print(" " + line)
lucky = []
for k in range(0, len(e[3])):
if e[6][k]:
lucky = lucky + [people[e[3][k]]]
if len(lucky) > 0:
print(" " + plural(len(lucky), "leftover cent") + " to " + join_names(lucky))
def ask_text(prompt, longest):
while True:
answer = text.trim(input(prompt))
if len(answer) <= longest:
return answer
print("At most " + str(longest) + " characters.")
def ask_name(people):
while True:
name = ask_text("name> ", 20)
if name == "":
return ""
clash = 0
for p in people:
if text.lower(p) == text.lower(name):
clash = 1
print("There is already someone called " + p + ".")
if clash == 0:
return name
def ask_amount():
while True:
answer = text.trim(input("amount> "))
if answer == "":
return 0 - 1
c = text.parse_cents(answer)
if c == 0 - 1:
print("Type an amount like 12.50, or nothing to cancel.")
elif c == 0:
print("An amount is more than 0.")
elif c > 10000000:
print("An amount is at most 100,000.00.")
else:
return c
def ask_payer(people):
while True:
answer = text.trim(input("paid by> "))
if answer == "":
return 0 - 1
n = text.number(answer)
if n >= 1 and n <= len(people):
return n - 1
print("Type a person's number from 1 to " + str(len(people)) + ", or nothing to cancel.")
def ask_sharers(people):
while True:
ws = text.words(input("shared by (numbers, nothing = everyone)> "))
out = []
if len(ws) == 0:
for i in range(0, len(people)):
out = out + [i]
return out
good = True
for w in ws:
n = text.number(w)
if n < 1 or n > len(people) or contains(out, n - 1):
good = False
else:
out = out + [n - 1]
if good:
return out
print("Type the numbers of the people who shared it, 1 to " + str(len(people)) + ", each once - or nothing for everyone.")
def ask_shares(count):
equal = []
for i in range(1, count+1):
equal = equal + [1]
if count == 1:
return equal
while True:
ws = text.words(input("shares (nothing = equal)> "))
if len(ws) == 0:
return equal
out = []
for w in ws:
n = text.number(w)
if n >= 1 and n <= 100:
out = out + [n]
if len(ws) == count and len(out) == count:
return out
print("Type one share from 1 to 100 for each of the " + str(count) + " people, or nothing for equal shares.")
people = []
expenses = []
running = True
while running:
print("")
print("== Bill splitter ==")
print("1) add person 2) add expense 3) expenses 4) balances 5) settle up 6) quit")
choice = text.trim(input("choice> "))
if choice == "1":
if len(people) == most_people:
print("At most " + str(most_people) + " people.")
else:
name = ask_name(people)
if name == "":
print("Cancelled.")
else:
people = people + [name]
print("Person " + str(len(people)) + ": " + name + ".")
elif choice == "2":
if len(people) < 2:
print("Add at least two people first.")
else:
what = ask_text("what for> ", 30)
amount = 0 - 1
payer = 0 - 1
if what != "":
amount = ask_amount()
if amount != 0 - 1:
listing = ""
for i in range(0, len(people)):
listing = listing + " " + str(i + 1) + ") " + people[i]
print("People:" + listing)
payer = ask_payer(people)
if payer == 0 - 1:
print("Cancelled.")
else:
sharers = ask_sharers(people)
weights = ask_shares(len(sharers))
r = split.split(amount, weights)
expenses = expenses + [[what, amount, payer, sharers, weights, r[0], r[1]]]
print("Added:")
show_expense(len(expenses), expenses[len(expenses) - 1], people)
elif choice == "3":
if len(expenses) == 0:
print("No expenses yet.")
else:
print("")
print("-- expenses --")
for i in range(0, len(expenses)):
show_expense(i + 1, expenses[i], people)
elif choice == "4":
if len(people) == 0:
print("No people yet.")
else:
bals = split.balances(len(people), expenses)
print("")
print("-- balances --")
for i in range(0, len(people)):
diff = bals[i][0] - bals[i][1]
status = "even"
if diff > 0:
status = "is owed " + text.money(diff)
elif diff < 0:
status = "owes " + text.money(0 - diff)
print(" " + "%-21s" % people[i] + "paid " + "%10s" % text.money(bals[i][0]) + " share " + "%10s" % text.money(bals[i][1]) + " " + status)
elif choice == "5":
bals = split.balances(len(people), expenses)
owed = []
for i in range(0, len(people)):
if bals[i][0] != bals[i][1]:
owed = owed + [[i, bals[i][0] - bals[i][1]]]
if len(owed) == 0:
print("Everyone is even.")
else:
plan = settle.fewest(owed)
print("")
print("-- settle up --")
for t in plan:
print(" " + people[t[0]] + " pays " + people[t[1]] + " " + text.money(t[2]))
if len(plan) == 1:
line = "1 transfer settles everyone - the fewest possible"
else:
line = str(len(plan)) + " transfers settle everyone - the fewest possible"
naive = len(settle.pay_largest_first(owed))
if naive > len(plan):
line = line + " (paying the largest debt to the largest credit first would take " + str(naive) + ")"
print(line + ".")
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
split.eml
eml# P013 bill splitter - sharing one expense out to the cent, and what everyone
# has paid and owes. Money is whole cents.
def split(amount, weights):
# The parts of amount in proportion to weights, adding up to amount
# exactly, as [parts, extra]. Every part is first rounded down; the cents
# left over then go one each to the parts that lost the most in the
# rounding (largest remainder), and on a tie to the one listed first.
# extra[i] says whether part i got one of those cents.
0 => total
for w in weights:
total + w => total
[] => parts
[] => rems
[] => extra
0 => given
for w in weights:
amount * w => x
int((x - x % total) / total) => part
parts + [part] => parts
rems + [x % total] => rems
extra + [False] => extra
given + part => given
amount - given => left
while left > 0:
0 - 1 => best
for i in [0:len(weights) - 1]:
if not extra[i] and (best == 0 - 1 or rems[i] > rems[best]):
i => best
parts[best] + 1 => parts[best]
True => extra[best]
left - 1 => left
return [parts, extra]
def balances(count, expenses):
# [paid, share] for each of count people. An expense is
# [what, amount, payer, sharers, weights, parts, extra].
[] => out
for i in [0:count - 1]:
out + [[0, 0]] => out
for e in expenses:
out[e[2]][0] + e[1] => out[e[2]][0]
for k in [0:len(e[3]) - 1]:
out[e[3][k]][1] + e[5][k] => out[e[3][k]][1]
return out
Python projection (split.py)
def split(amount, weights):
total = 0
for w in weights:
total = total + w
parts = []
rems = []
extra = []
given = 0
for w in weights:
x = amount * w
part = int((x - x % total) / total)
parts = parts + [part]
rems = rems + [x % total]
extra = extra + [False]
given = given + part
left = amount - given
while left > 0:
best = 0 - 1
for i in range(0, len(weights)):
if not extra[i] and (best == 0 - 1 or rems[i] > rems[best]):
best = i
parts[best] = parts[best] + 1
extra[best] = True
left = left - 1
return [parts, extra]
def balances(count, expenses):
out = []
for i in range(0, count):
out = out + [[0, 0]]
for e in expenses:
out[e[2]][0] = out[e[2]][0] + e[1]
for k in range(0, len(e[3])):
out[e[3][k]][1] = out[e[3][k]][1] + e[5][k]
return out
settle.eml
eml# P013 bill splitter - settling up in as few transfers as possible. People
# whose balances add up to zero among themselves can settle inside their own
# group, and a group of g people needs g - 1 transfers. So the fewest
# transfers is the number of people with a balance minus the largest number
# of groups they can be split into, each adding up to zero. With at most
# eight people that is found exactly by trying every subset: a subset is a
# whole number whose bits say who is in it, and pow2[i] is person i's bit.
def has(mask, i, pow2):
return int(mask / pow2[i]) % 2 == 1
def groups(bal):
# bal is a list of [person, cents], none of them zero, adding up to 0.
# The largest set of zero-sum groups it splits into, as lists of entries.
len(bal) => k
[1] => pow2
for i in [1:k]:
pow2 + [pow2[i - 1] * 2] => pow2
pow2[k] => size
# sums[mask]: the balances in mask added up; most[mask]: the most
# zero-sum groups that mask can be split into, counting mask itself.
[0] => sums
[0] => most
for mask in [1:size - 1]:
0 => low
while not has(mask, low, pow2):
low + 1 => low
sums + [sums[mask - pow2[low]] + bal[low][1]] => sums
0 => b
for j in [0:k - 1]:
if has(mask, j, pow2) and most[mask - pow2[j]] > b:
most[mask - pow2[j]] => b
if sums[mask] == 0:
b + 1 => b
most + [b] => most
# Walk back from everyone, taking one person out at a time along a best
# path; each time what is left adds up to zero, the people taken out
# since the last time form one group.
[] => found
[] => current
size - 1 => mask
while mask > 0:
most[mask] => target
if sums[mask] == 0:
target - 1 => target
0 => j
while not (has(mask, j, pow2) and most[mask - pow2[j]] == target):
j + 1 => j
current + [bal[j]] => current
mask - pow2[j] => mask
if sums[mask] == 0:
found + [current] => found
[] => current
return found
def pay_largest_first(group):
# Transfers [from, to, cents] that settle a zero-sum group: the largest
# debt pays the largest credit, again and again, until all are even.
[] => left
for g in group:
left + [[g[0], g[1]]] => left
[] => out
while True:
0 - 1 => c
0 - 1 => d
for i in [0:len(left) - 1]:
if left[i][1] > 0 and (c == 0 - 1 or left[i][1] > left[c][1]):
i => c
if left[i][1] < 0 and (d == 0 - 1 or left[i][1] < left[d][1]):
i => d
if c == 0 - 1:
return out
left[c][1] => amount
if 0 - left[d][1] < amount:
0 - left[d][1] => amount
out + [[left[d][0], left[c][0], amount]] => out
left[c][1] - amount => left[c][1]
left[d][1] + amount => left[d][1]
def fewest(bal):
# The fewest transfers that settle bal: every zero-sum group settles
# inside itself.
[] => out
for g in groups(bal):
out + pay_largest_first(g) => out
return out
Python projection (settle.py)
def has(mask, i, pow2):
return int(mask / pow2[i]) % 2 == 1
def groups(bal):
k = len(bal)
pow2 = [1]
for i in range(1, k+1):
pow2 = pow2 + [pow2[i - 1] * 2]
size = pow2[k]
sums = [0]
most = [0]
for mask in range(1, size):
low = 0
while not has(mask, low, pow2):
low = low + 1
sums = sums + [sums[mask - pow2[low]] + bal[low][1]]
b = 0
for j in range(0, k):
if has(mask, j, pow2) and most[mask - pow2[j]] > b:
b = most[mask - pow2[j]]
if sums[mask] == 0:
b = b + 1
most = most + [b]
found = []
current = []
mask = size - 1
while mask > 0:
target = most[mask]
if sums[mask] == 0:
target = target - 1
j = 0
while not (has(mask, j, pow2) and most[mask - pow2[j]] == target):
j = j + 1
current = current + [bal[j]]
mask = mask - pow2[j]
if sums[mask] == 0:
found = found + [current]
current = []
return found
def pay_largest_first(group):
left = []
for g in group:
left = left + [[g[0], g[1]]]
out = []
while True:
c = 0 - 1
d = 0 - 1
for i in range(0, len(left)):
if left[i][1] > 0 and (c == 0 - 1 or left[i][1] > left[c][1]):
c = i
if left[i][1] < 0 and (d == 0 - 1 or left[i][1] < left[d][1]):
d = i
if c == 0 - 1:
return out
amount = left[c][1]
if 0 - left[d][1] < amount:
amount = 0 - left[d][1]
out = out + [[left[d][0], left[c][0], amount]]
left[c][1] = left[c][1] - amount
left[d][1] = left[d][1] + amount
def fewest(bal):
out = []
for g in groups(bal):
out = out + pay_largest_first(g)
return out
text.eml
eml# P013 bill splitter - reading what is typed and writing money. Money is
# whole cents from the moment it is typed: "12.50" is read digit by digit into
# 1250 and never passes through a float. The interpreter that checks every
# session does not run string methods yet, so the text handling is written
# out here.
def trim(s):
# s without the spaces at either end.
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 lower(s):
# s with A-Z turned into a-z; everything else as it was.
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" => upper_letters
"abcdefghijklmnopqrstuvwxyz" => lower_letters
"" => out
for c in s:
c => d
for i in [0:25]:
if upper_letters[i] == c:
lower_letters[i] => d
out + d => out
return out
def number(s):
# The value of s if it is digits only (at least one), otherwise -1.
if s == "":
return 0 - 1
0 => n
for c in s:
if not (c in "0123456789"):
return 0 - 1
n * 10 + int(c) => n
return n
def words(s):
# The words of s, split at spaces and commas.
[] => out
"" => word
for c in s:
if c == " " or c == ",":
if word != "":
out + [word] => out
"" => word
else:
word + c => word
if word != "":
out + [word] => out
return out
def parse_cents(s):
# The amount in s in whole cents, or -1 if s is not written like 4, 4.5
# or 4.50: digits, then a point and one or two digits if any.
0 => whole
0 => whole_digits
0 => frac
0 => frac_digits
False => point
for c in s:
if c == ".":
if point:
return 0 - 1
True => point
elif c in "0123456789":
if point:
frac * 10 + int(c) => frac
frac_digits + 1 => frac_digits
else:
whole * 10 + int(c) => whole
whole_digits + 1 => whole_digits
else:
return 0 - 1
if whole_digits == 0:
return 0 - 1
if point and (frac_digits == 0 or frac_digits > 2):
return 0 - 1
if frac_digits == 1:
frac * 10 => frac
return whole * 100 + frac
def money(c):
# Whole cents (not negative) as 1,234.50, built from the digits.
str(c) => s
while len(s) < 3:
"0" + s => s
s[0:len(s) - 2] => whole
s[len(s) - 2:len(s)] => cents
"" => grouped
len(whole) => i
while i > 3:
"," + whole[i - 3:i] + grouped => grouped
i - 3 => i
return whole[0:i] + grouped + "." + cents
Python projection (text.py)
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 lower(s):
upper_letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
lower_letters = "abcdefghijklmnopqrstuvwxyz"
out = ""
for c in s:
d = c
for i in range(0, 26):
if upper_letters[i] == c:
d = lower_letters[i]
out = out + d
return out
def number(s):
if s == "":
return 0 - 1
n = 0
for c in s:
if not c in "0123456789":
return 0 - 1
n = n * 10 + int(c)
return n
def words(s):
out = []
word = ""
for c in s:
if c == " " or c == ",":
if word != "":
out = out + [word]
word = ""
else:
word = word + c
if word != "":
out = out + [word]
return out
def parse_cents(s):
whole = 0
whole_digits = 0
frac = 0
frac_digits = 0
point = False
for c in s:
if c == ".":
if point:
return 0 - 1
point = True
elif c in "0123456789":
if point:
frac = frac * 10 + int(c)
frac_digits = frac_digits + 1
else:
whole = whole * 10 + int(c)
whole_digits = whole_digits + 1
else:
return 0 - 1
if whole_digits == 0:
return 0 - 1
if point and (frac_digits == 0 or frac_digits > 2):
return 0 - 1
if frac_digits == 1:
frac = frac * 10
return whole * 100 + frac
def money(c):
s = str(c)
while len(s) < 3:
s = "0" + s
whole = s[0:len(s) - 2]
cents = s[len(s) - 2:len(s)]
grouped = ""
i = len(whole)
while i > 3:
grouped = "," + whole[i - 3:i] + grouped
i = i - 3
return whole[0:i] + grouped + "." + cents