Language Atlas (mini-courses for more languages) Module 14 – Capstone: one specification, twelve languages
Capstone: one spec in twelve languages
Implement one exact bill-splitting specification in any atlas language: whole paise, GST and tip per line, shares, leftover paise and 20 public vectors.
What you will learn
- Implement the bill-splitting specification in an atlas language so that it passes the twenty public vectors
- Name the defaults your language had to override: integer division, rounding a half, integer size and the order of names
- Check an implementation with the shared black-box check, and trace a failing vector back to the rule it breaks
- Compare implementations in four atlas languages by their size and by what each one had to override
Before you start
What you’ll learn · Before you start
What you will learn
- Implement the bill-splitting specification in an atlas language so that it passes the twenty public vectors
- Name the defaults your language had to override: integer division, rounding a half, integer size and the order of names
- Check an implementation with the shared black-box check, and trace a failing vector back to the rule it breaks
- Compare implementations in four atlas languages by their size and by what each one had to override
Before you start
On this page
Split a coupon of −1,051 paise between two diners with the integer division each language offers first, and
Crystal’s // and Tcl’s / give −526 each, while Objective-C’s / and Visual Basic’s \ give −525. One paisa per
diner, on one line of one bill, decided by a default nobody chose.
The capstone of the atlas asks for one program in any atlas language that follows one exact specification for splitting a restaurant bill: whole paise, GST and a tip per line, shares, and leftover paise in name order. You will read the specification and its twenty public vectors, see where the defaults of four languages break it, check four implementations that pass all twenty, find the rows for the other eight atlas languages, and then write your own.
The specification leaves nothing to a language’s defaults
A bill is a text file. Each line is a keyword and its words, separated by spaces:
gst Rgives the tax rate, once;tip Rgives a tip rate, at most once, and none means no tip. A rate is a percent from 0 to 50 with at most two decimals, kept as basis point: One hundredth of a percent. A rate of 2.5 % is 250 basis points and 18 % is 1800, so a specification can keep rates with two decimals as whole numbers and never needs a float for them.:2.5is 250.item P D …is one line of the bill: its pricePin paise, an optional minus and digits, at most 1,000,000,000 either way, then one or more diners, each a name of the ASCII letters A to Z and a to z, at most once per line, with an optional weight from 1 to 100 such asAsha:2.- Empty lines and lines that start with
#are skipped. Any other line is an error: the program printserror: line Non standard error and exits with status 2, and so it does witherror: no gst lineanderror: no items.
Every amount is a whole number of paise, and every step is integer arithmetic:
- The tax of a line is its price times the tax rate in basis points, divided by 10,000 and rounded to the nearest
whole paisa with a half going up, towards plus infinity, also below zero: rounding half up: Rounding in which a value exactly halfway between two whole numbers goes to the larger one: 1,252.5 becomes 1,253. For whole numbers a and b, the expression (2a + b) div (2b) rounds a / b this way without any real numbers. More in “Project: a marks report in Object Pascal”, which is
(2a + b) div (2b)with floor division: Integer division that rounds the quotient down, towards minus infinity, so -7 divided by 2 gives -4. Tcl's / on integers and Python's // divide this way, and their remainder takes the divisor's sign. More in “A one-week plan for learning any language”. Its tip is worked out the same way. - The line total is the price plus its tax and its tip. Each diner of the line gets the total times their weight, divided by the sum of the weights and rounded down, also below zero.
- The leftover paise: The paise that remain when an amount is split into whole-paisa shares rounded down. With floor division they are never negative and always fewer than the sharers, and the capstone gives them one each in name order. of the line go one each to its first diners in byte order of the names, so that the shares add up to the line total.
- The report has one line per diner,
Name: amount, in byte order of the names, thenBill: items X, gst Y, tip Z, total T. An amount is rupees with two decimals, a minus sign when it is negative, and Indian digit grouping: Writing the whole rupees of an amount with a comma before the last three digits and then before every two digits further left: 1,00,000.00 for one lakh and 1,00,00,000.00 for one crore.: 1,00,000.00.
The rules make one promise checkable on every bill: the diners’ totals add up to the bill’s total. Step through the
coupon of the opening, the line item -1001 Ravi Meera at 5 % GST:
The drawing shows the whole scene; its 8 steps are listed below.
Every step as text
- A negative price. Vector 07 has a coupon: the line item -1001 Ravi Meera takes 10.01 rupees off the bill, shared by Ravi and Meera. Every rule of the specification has to work below zero too.
- The tax of the line. GST is 5 %, which the specification stores as 500 basis points. The tax is -1001 × 500 / 10000, which is -50.05 paise exactly.
- Half up, also below zero. The tax becomes a whole number of paise by rounding half up, (2a + b) // (2b) with floor division: -50.05 is nearer -50 than -51, so the tax is -50.
- The line. The line total is the price plus its tax and its tip: -1001 - 50 + 0 = -1051 paise, to be shared by two diners of weight 1 each.
- Shares round down. Each share is the line times the diner's weight, divided by the total weight and rounded down: -1051 // 2 is -526, for Ravi and for Meera.
- What truncation would do. Division that truncates, as C, Objective-C and Visual Basic's \ do, gives -525 each. The shares then add up to -1050, one paisa more than the line, and the paise left over would be -1.
- The paise left over. The two floored shares add up to -1052, one paisa less than the line. Floor division always leaves from 0 up to one less than the number of diners, here 1.
- Given in name order. The leftover paisa goes to the first diner in byte order of the names, Meera before Ravi: Meera -525 and Ravi -526, which add up to -1051 again.
Why the tax is called gst
The keyword is gst because restaurant bills in India carry the goods and services tax, and the vectors give it as 0, 2.5, 5, 12 or 18 %. The specification does the arithmetic for whatever rate a bill states; deciding the rate a bill must carry is a matter of tax law, which lies outside this capstone.
Checkpoint
Check: The rules of the specification
Twenty public vectors pin every rule
A vector is a bill with the exact output it must give: the standard output, the standard error and the exit status. The twenty public vectors were written so that each rule has a bill that only a correct implementation gets right:
| Vectors | The rule they pin |
|---|---|
| 01 even, 02 odd paisa, 03 shares, 14 seven diners | shares, weights and the leftover paise in name order |
| 04 tip, 05 decimal rates, 17 tip only | the tip, and rates with decimals as basis points |
| 06 half up, 08 negative half, 15 small negative | halves round up, also below zero, and negative amounts print with a minus |
| 07 coupon | floor division of a negative line, and its leftover |
| 09 name order | byte order of the names: Bilal, Zoya, then asha |
| 10 grouping, 11 large bill | Indian digit grouping, and a product of 1,800,000,000,000 |
| 12 one diner, 13 zero price, 16 comments | a single diner, an item at 0 paise, comments and extra spaces |
| 18 no gst, 19 bad price, 20 bad share | the three error messages and exit status 2 |
check.sh is the shared black-box test: A test that runs the whole program as a user would, with an input file, and compares only what comes out, standard output, standard error and the exit status, with expected files, without looking at the code inside. More in “Project: a marks report in Object Pascal”. It runs a program on every vector and
compares the three outputs with the expected files, so the same check grades every language:
check.sh
#!/bin/sh
# The shared black-box check of the capstone: runs a program on every public vector, with the vector's file as its
# last argument, and compares what it prints on standard output and standard error, and its exit status, with the
# expected files. Usage: sh check.sh <command> [<argument> …]
pass=0
total=0
for input in vectors/*.txt; do
name=${input%.txt}
total=$((total + 1))
"$@" "$input" > check.out 2> check.err
status=$?
if cmp -s check.out "$name.out" && cmp -s check.err "$name.err" && [ "$status" = "$(cat "$name.status")" ]; then
pass=$((pass + 1))
else
echo "differs: ${name#vectors/}"
fi
done
rm -f check.out check.err
echo "$pass of $total vectors pass"
[ "$pass" -eq "$total" ]vectors/07-coupon.txt
gst 5
item 30000 Asha Ravi Meera
item -1001 Ravi Meeravectors/07-coupon.out
Asha: 105.00
Meera: 99.75
Ravi: 99.74
Bill: items 289.99, gst 14.50, tip 0.00, total 304.49Here is the reference in Crystal, the language of the module before this one. Every amount is an Int64, and
half_up puts the Int64 first in each product for a reason the next section shows:
# The bill-splitting specification of the atlas capstone, in Crystal 1.21. Every amount is an Int64 of paise.
RATE = /\A0*([0-9]{1,3})(?:\.([0-9]{1,2}))?\z/
PRICE = /\A-?0*[0-9]{1,10}\z/
DINER = /\A([A-Za-z]+)(?::([1-9][0-9]{0,2}))?\z/
record Item, price : Int64, diners : Array({String, Int64})
class BillError < Exception
end
# A rate from 0 to 50 percent with at most two decimals, as basis points, or nil.
def rate(word : String) : Int64?
m = RATE.match(word) || return nil
bp = m[1].to_i64 * 100 + (m[2]? || "").ljust(2, '0').to_i64
bp <= 5_000 ? bp : nil
end
# a / b to the nearest whole number, a half going up (b > 0); // rounds down, also below zero. The Int64 comes
# first in each product: 2 * a would have the type of 2, Int32.
def half_up(a : Int64, b : Int64) : Int64
(a * 2 + b) // (b * 2)
end
# Paise as rupees with Indian digit grouping: 1,23,456.78.
def rupees(paise : Int64) : String
whole, part = paise.abs.divmod(100)
digits = whole.to_s
if digits.size > 3
head, tail = digits[0...-3], digits[-3..]
groups = [] of String
while head.size > 2
groups.unshift(head[-2..])
head = head[0...-2]
end
groups.unshift(head)
digits = "#{groups.join(",")},#{tail}"
end
"#{paise < 0 ? "-" : ""}#{digits}.#{part.to_s.rjust(2, '0')}"
end
def diners(words : Array(String)) : Array({String, Int64})?
list = words.map do |word|
m = DINER.match(word) || return nil
weight = (m[2]? || "1").to_i64
return nil if weight > 100
{m[1], weight}
end
list.map(&.[0]).uniq.size == list.size ? list : nil
end
def parse(text : String) : {Int64, Int64, Array(Item)}
gst = tip = nil
items = [] of Item
text.split('\n').each_with_index(1) do |line, number|
words = line.split
next if words.empty? || words[0].starts_with?('#')
key, args = words[0], words[1..]
if key == "gst" && args.size == 1 && gst.nil? && (bp = rate(args[0]))
gst = bp
elsif key == "tip" && args.size == 1 && tip.nil? && (bp = rate(args[0]))
tip = bp
elsif key == "item" && args.size >= 2 && args[0].matches?(PRICE) &&
(price = args[0].to_i64?) && price.abs <= 1_000_000_000 && (list = diners(args[1..]))
items << Item.new(price, list)
else
raise BillError.new("error: line #{number}")
end
end
raise BillError.new("error: no gst line") unless gst
raise BillError.new("error: no items") if items.empty?
{gst, tip || 0_i64, items}
end
def report(text : String) : String
gst, tip, items = parse(text)
totals = Hash(String, Int64).new(0_i64)
bill = [0_i64, 0_i64, 0_i64]
items.each do |item|
tax = half_up(item.price * gst, 10_000_i64)
extra = half_up(item.price * tip, 10_000_i64)
line = item.price + tax + extra
bill[0] += item.price
bill[1] += tax
bill[2] += extra
weight = item.diners.sum(&.[1])
shares = item.diners.to_h { |name, w| {name, line * w // weight} }
left = line - shares.values.sum
shares.keys.sort.first(left).each { |name| shares[name] += 1 }
shares.each { |name, share| totals[name] += share }
end
lines = totals.keys.sort.map { |name| "#{name}: #{rupees(totals[name])}" }
lines << "Bill: items #{rupees(bill[0])}, gst #{rupees(bill[1])}, tip #{rupees(bill[2])}, total #{rupees(bill.sum)}"
lines.join('\n')
end
begin
puts report(File.read(ARGV[0]))
rescue e : BillError
STDERR.puts e.message
exit 2
endfrom session import run
# The Crystal implementation built, run on one vector, then checked against all twenty; its size in lines.
run("""
crystal --version | head -1
crystal build crystal/split.cr -o split-cr
./split-cr vectors/07-coupon.txt
sh check.sh ./split-cr
wc -l < crystal/split.cr
""")Output
$ crystal --version | head -1
Crystal 1.21.1 [73ea5c2b1] (2026-09-26)
$ crystal build crystal/split.cr -o split-cr
$ ./split-cr vectors/07-coupon.txt
Asha: 105.00
Meera: 99.75
Ravi: 99.74
Bill: items 289.99, gst 14.50, tip 0.00, total 304.49
$ sh check.sh ./split-cr
20 of 20 vectors pass
$ wc -l < crystal/split.cr
102
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 crystal_session.py
It printed the coupon’s report, Meera 99.75 and Ravi 99.74, and passed all twenty vectors in 102 lines. A first
attempt shows what the vectors are for. naive.cr is the same program with one change: half_up divides into a
Float64 and calls round, the way a Ruby developer might write it.
from session import run
# naive.cr, split.cr with a float and round in half_up, against the same twenty vectors: the check names the two it fails.
run("""
crystal build crystal/naive.cr -o naive-cr
!sh check.sh ./naive-cr
./naive-cr vectors/06-half-up.txt
""")Output
$ crystal build crystal/naive.cr -o naive-cr $ sh check.sh ./naive-cr differs: 06-half-up differs: 08-negative-half 18 of 20 vectors pass [exit status 1] $ ./naive-cr vectors/06-half-up.txt Asha: 0.42 Bilal: 0.52 Bill: items 0.90, gst 0.04, tip 0.00, total 0.94
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 naive_session.py
The check named two vectors, 06 and 08, the only ones whose taxes fall exactly on a half. Crystal’s round takes a
half to the even neighbour, so 0.5 paise of tax became 0 and 2.5 became 2, and vector 06’s bill came to 0.94 instead
of 0.96. Eighteen vectors passed, which a test of a few ordinary bills would have called a success.
Checkpoint
Check: Public vectors and the shared check
Four languages, four sets of defaults
Four small programs ask each language’s defaults the questions the vectors ask: split −1,051 in two, round 2.5 and −0.5, multiply 1,000,000,000 by 1,800 in the default integer type, and sort the names asha, Zoya and Bilal:
Crystal · traps/traps.cr
# The capstone's traps in Crystal: dividing a negative line, rounding halves, a large product, and sorting names.
p -1051 // 2, -1051.tdiv(2)
p 2.5.round, -0.5.round
p typeof(1_000_000_000 * 1800)
begin
p 1_000_000_000 * 1800
rescue e : OverflowError
puts "OverflowError: #{e.message}"
end
p 1_000_000_000_i64 * 1800, typeof(2 * 1_000_000_000_i64)
p ["asha", "Zoya", "Bilal"].sortTcl · traps/traps.tcl
# The capstone's traps in Tcl 9.0: dividing a negative line, rounding halves, a large product, and sorting names.
puts "[expr {-1051 / 2}] [expr {-1051 % 2}]"
puts "[expr {round(2.5)}] [expr {round(-0.5)}]"
puts [expr {1000000000 * 1800}]
puts [lsort {asha Zoya Bilal}]Objective-C · traps/traps.m
// The capstone's traps in Objective-C: dividing a negative line, rounding halves, a large product, and sorting names.
#import <Foundation/Foundation.h>
#include <math.h>
int main(void) {
@autoreleasepool {
printf("%d %d\n", -1051 / 2, -1051 % 2);
printf("%.1f %.1f\n", round(2.5), round(-0.5));
int product;
printf("int: %s\n", __builtin_mul_overflow(1000000000, 1800, &product) ? "overflows" : "fits");
printf("%lld\n", 1000000000LL * 1800);
NSArray<NSString *> *names = @[@"asha", @"Zoya", @"Bilal"];
printf("%s\n", [[names sortedArrayUsingSelector:@selector(compare:)] componentsJoinedByString:@" "].UTF8String);
printf("%s\n", [[names sortedArrayUsingSelector:@selector(localizedCompare:)] componentsJoinedByString:@" "].UTF8String);
}
return 0;
}Visual Basic · traps/vb/Program.vb
' The capstone's traps in Visual Basic: dividing a negative line, rounding halves, a large product, and sorting names.
Module Program
Sub Main()
Console.WriteLine($"{-1051 \ 2} {-1051 Mod 2}")
Console.WriteLine($"{CInt(2.5)} {CInt(-0.5)} {Math.Round(2.5, MidpointRounding.AwayFromZero)}")
Try
Dim price As Integer = 1000000000
Console.WriteLine(price * 1800)
Catch ex As OverflowException
Console.WriteLine($"OverflowException: {ex.Message}")
End Try
Console.WriteLine(1000000000L * 1800)
Dim names As String() = {"asha", "Zoya", "Bilal"}
Array.Sort(names)
Console.WriteLine(String.Join(" ", names))
Array.Sort(names, StringComparer.Ordinal)
Console.WriteLine(String.Join(" ", names))
End Sub
End Modulefrom session import run
# The same four traps in each language's defaults: a negative line split in two, halves rounded, a large product and
# three names sorted.
run("""
crystal run traps/traps.cr
tclsh9.0 traps/traps.tcl
clang -fobjc-arc -framework Foundation traps/traps.m -o traps-objc
./traps-objc
dotnet run --project traps/vb
""")Output
$ crystal run traps/traps.cr -526 -525 2.0 -0.0 Int32 OverflowError: Arithmetic overflow 1800000000000 Int32 ["Bilal", "Zoya", "asha"] $ tclsh9.0 traps/traps.tcl -526 1 3 -1 1800000000000 Bilal Zoya asha $ clang -fobjc-arc -framework Foundation traps/traps.m -o traps-objc $ ./traps-objc -525 -1 3.0 -1.0 int: overflows 1800000000000 Bilal Zoya asha asha Bilal Zoya $ dotnet run --project traps/vb -525 -1 2 0 3 OverflowException: Arithmetic operation resulted in an overflow. 1800000000000 asha Bilal Zoya Bilal Zoya asha
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 traps_session.py
| Trap | Defaults that break it | What the vectors need |
|---|---|---|
| −1,051 split in two | Objective-C’s /, Visual Basic’s \ and Crystal’s tdiv gave −525 |
−526: Crystal’s //, Tcl’s /, a floor helper elsewhere |
| 2.5 and −0.5 rounded | Crystal’s round gave 2.0 and Visual Basic’s CInt 2; Tcl’s and C’s round took −0.5 to −1 |
3 and 0: half up, written with floor division |
| 1,000,000,000 × 1,800 | Crystal’s Int32 and Visual Basic’s Integer raised; Objective-C’s int overflows |
1,800,000,000,000 in Int64, long long or Long; Tcl’s integers grow |
| asha, Zoya, Bilal sorted | Visual Basic’s Array.Sort and localizedCompare: gave asha Bilal Zoya |
Bilal Zoya asha: Crystal’s sort, lsort, compare:, StringComparer.Ordinal |
Two rows hide a second trap. In Crystal, typeof(2 * 1_000_000_000_i64) printed Int32: an arithmetic operator
returns the type of its left operand, so 2 * a can overflow where a * 2 would not, which is why half_up writes
a * 2. And Visual Basic’s Array.Sort follows the rules of the computer’s language setting, so the names of a bill
would sort one way here and perhaps another way elsewhere; ordinal comparison: Comparing strings by the number of each character, as StringComparer.Ordinal and Crystal's sort do, instead of by the rules of a human language: every capital comes before every small letter, so Zoya sorts before asha.
gives byte order everywhere. Objective-C’s int overflow is not even an error: the C standard leaves it undefined,
which is why the probe asks __builtin_mul_overflow instead of printing a wrong number.
Key idea
Every default of a language is a decision someone else made; a specification that names its division, its rounding, its integer range and its string order lets each implementation replace exactly the defaults that differ.
Checkpoint
Check: The defaults that break the specification
Four implementations that pass all twenty
Here are the specification’s other three implementations. Each states in its first comment which defaults it had to replace:
Tcl · tcl/split.tcl
# The bill-splitting specification of the atlas capstone, in Tcl 9.0. Tcl's integers grow as large as a value needs,
# and / on two integers rounds down, also below zero, which is the division the specification asks for.
proc rate {word} {
if {![regexp {^([0-9]+)(?:\.([0-9]{1,2}))?$} $word -> whole frac]} {
return ""
}
# Tcl 9 reads 05 and 007 as decimal numbers; before 9.0 a leading 0 meant octal.
set bp [expr {$whole * 100 + [string range "${frac}00" 0 1]}]
expr {$bp <= 5000 ? $bp : ""}
}
proc half_up {a b} {
expr {(2 * $a + $b) / (2 * $b)}
}
proc rupees {paise} {
set sign [expr {$paise < 0 ? "-" : ""}]
set paise [expr {abs($paise)}]
set digits [expr {$paise / 100}]
if {[string length $digits] > 3} {
set head [string range $digits 0 end-3]
set tail [string range $digits end-2 end]
set groups {}
while {[string length $head] > 2} {
set groups [linsert $groups 0 [string range $head end-1 end]]
set head [string range $head 0 end-2]
}
set digits [join [linsert $groups 0 $head] ,],$tail
}
format %s%s.%02d $sign $digits [expr {$paise % 100}]
}
proc fail {message} {
puts stderr $message
exit 2
}
set f [open [lindex $argv 0] r]
fconfigure $f -encoding utf-8
set text [read $f]
close $f
set gst ""
set tip ""
set items {}
set number 0
foreach line [split $text \n] {
incr number
set words [regexp -all -inline {\S+} $line]
if {[llength $words] == 0 || [string index [lindex $words 0] 0] eq "#"} {
continue
}
set key [lindex $words 0]
set args [lrange $words 1 end]
if {$key in {gst tip} && [llength $args] == 1 && [set $key] eq "" && [rate [lindex $args 0]] ne ""} {
set $key [rate [lindex $args 0]]
continue
}
if {$key eq "item" && [llength $args] >= 2 && [regexp {^-?[0-9]+$} [lindex $args 0]]
&& abs([lindex $args 0]) <= 1000000000} {
set diners {}
foreach word [lrange $args 1 end] {
if {![regexp {^([A-Za-z]+)(?::([1-9][0-9]*))?$} $word -> name weight]} {
fail "error: line $number"
}
if {$weight eq ""} {
set weight 1
}
if {$weight > 100 || [dict exists $diners $name]} {
fail "error: line $number"
}
dict set diners $name $weight
}
lappend items [list [lindex $args 0] $diners]
continue
}
fail "error: line $number"
}
if {$gst eq ""} {
fail "error: no gst line"
}
if {[llength $items] == 0} {
fail "error: no items"
}
if {$tip eq ""} {
set tip 0
}
set totals [dict create]
lassign {0 0 0} prices taxes tips
foreach item $items {
lassign $item price diners
set tax [half_up [expr {$price * $gst}] 10000]
set extra [half_up [expr {$price * $tip}] 10000]
set line [expr {$price + $tax + $extra}]
incr prices $price
incr taxes $tax
incr tips $extra
set weight [tcl::mathop::+ {*}[dict values $diners]]
set shares [dict create]
dict for {name w} $diners {
dict set shares $name [expr {$line * $w / $weight}]
}
set left [expr {$line - [tcl::mathop::+ {*}[dict values $shares]]}]
foreach name [lrange [lsort [dict keys $shares]] 0 [expr {$left - 1}]] {
dict incr shares $name
}
dict for {name share} $shares {
dict incr totals $name $share
}
}
foreach name [lsort [dict keys $totals]] {
puts "$name: [rupees [dict get $totals $name]]"
}
puts "Bill: items [rupees $prices], gst [rupees $taxes], tip [rupees $tips], total [rupees [expr {$prices + $taxes + $tips}]]"Objective-C · objc/split.m
// The bill-splitting specification of the atlas capstone, in Objective-C with Foundation. C's / truncates towards
// zero and int has 32 bits, so the amounts are long long and floor_div rounds down by hand.
#import <Foundation/Foundation.h>
static long long floor_div(long long a, long long b) {
long long q = a / b;
return (a % b != 0 && (a < 0) != (b < 0)) ? q - 1 : q;
}
static long long half_up(long long a, long long b) {
return floor_div(2 * a + b, 2 * b);
}
static NSString *rupees(long long paise) {
long long whole = llabs(paise) / 100;
NSMutableString *digits = [NSMutableString stringWithFormat:@"%lld", whole];
if (digits.length > 3) {
NSString *head = [digits substringToIndex:digits.length - 3];
NSString *tail = [digits substringFromIndex:digits.length - 3];
NSMutableArray<NSString *> *groups = [NSMutableArray array];
while (head.length > 2) {
[groups insertObject:[head substringFromIndex:head.length - 2] atIndex:0];
head = [head substringToIndex:head.length - 2];
}
[groups insertObject:head atIndex:0];
digits = [NSMutableString stringWithFormat:@"%@,%@", [groups componentsJoinedByString:@","], tail];
}
return [NSString stringWithFormat:@"%@%@.%02lld", paise < 0 ? @"-" : @"", digits, llabs(paise) % 100];
}
static NSRegularExpression *pattern(NSString *text) {
return [NSRegularExpression regularExpressionWithPattern:text options:0 error:NULL];
}
// The groups of a whole-word match, @"" for a group that did not take part, or nil when the word does not match.
static NSArray<NSString *> *groups(NSRegularExpression *re, NSString *word) {
NSTextCheckingResult *m = [re firstMatchInString:word options:NSMatchingAnchored range:NSMakeRange(0, word.length)];
if (!m || m.range.length != word.length) return nil;
NSMutableArray<NSString *> *out = [NSMutableArray array];
for (NSUInteger i = 1; i < m.numberOfRanges; i++) {
NSRange r = [m rangeAtIndex:i];
[out addObject:r.location == NSNotFound ? @"" : [word substringWithRange:r]];
}
return out;
}
static long long rate(NSString *word) {
NSArray<NSString *> *g = groups(pattern(@"0*([0-9]+)(?:\\.([0-9]{1,2}))?"), word);
if (!g || g[0].length > 3) return -1;
long long bp = g[0].longLongValue * 100 + [[g[1] stringByPaddingToLength:2 withString:@"0" startingAtIndex:0] longLongValue];
return bp <= 5000 ? bp : -1;
}
static int fail(NSString *message) {
fprintf(stderr, "%s\n", message.UTF8String);
return 2;
}
int main(int argc, const char *argv[]) {
@autoreleasepool {
if (argc != 2) return fail(@"usage: split <bill.txt>");
NSString *text = [NSString stringWithContentsOfFile:@(argv[1]) encoding:NSUTF8StringEncoding error:NULL];
NSRegularExpression *price = pattern(@"-?0*[0-9]{1,10}");
NSRegularExpression *diner = pattern(@"([A-Za-z]+)(?::([1-9][0-9]{0,2}))?");
long long gst = -1, tip = -1;
NSMutableArray *items = [NSMutableArray array];
NSArray<NSString *> *lines = [text componentsSeparatedByString:@"\n"];
for (NSUInteger number = 1; number <= lines.count; number++) {
NSMutableArray<NSString *> *words = [NSMutableArray array];
for (NSString *w in [lines[number - 1] componentsSeparatedByCharactersInSet:NSCharacterSet.whitespaceCharacterSet])
if (w.length > 0) [words addObject:w];
if (words.count == 0 || [words[0] hasPrefix:@"#"]) continue;
NSString *key = words[0];
if (([key isEqualToString:@"gst"] || [key isEqualToString:@"tip"]) && words.count == 2) {
long long *target = [key isEqualToString:@"gst"] ? &gst : &tip;
long long bp = rate(words[1]);
if (*target < 0 && bp >= 0) { *target = bp; continue; }
} else if ([key isEqualToString:@"item"] && words.count >= 3 && groups(price, words[1])
&& llabs(words[1].longLongValue) <= 1000000000LL) {
NSMutableDictionary<NSString *, NSNumber *> *diners = [NSMutableDictionary dictionary];
BOOL ok = YES;
for (NSUInteger i = 2; i < words.count && ok; i++) {
NSArray<NSString *> *g = groups(diner, words[i]);
long long weight = g && g[1].length ? g[1].longLongValue : 1;
ok = g && weight <= 100 && !diners[g[0]];
if (ok) diners[g[0]] = @(weight);
}
if (ok) { [items addObject:@[@(words[1].longLongValue), diners]]; continue; }
}
return fail([NSString stringWithFormat:@"error: line %lu", (unsigned long)number]);
}
if (gst < 0) return fail(@"error: no gst line");
if (items.count == 0) return fail(@"error: no items");
if (tip < 0) tip = 0;
NSMutableDictionary<NSString *, NSNumber *> *totals = [NSMutableDictionary dictionary];
long long prices = 0, taxes = 0, tips = 0;
for (NSArray *item in items) {
long long p = [item[0] longLongValue];
NSDictionary<NSString *, NSNumber *> *diners = item[1];
long long tax = half_up(p * gst, 10000), extra = half_up(p * tip, 10000);
long long line = p + tax + extra, weight = 0, given = 0;
prices += p; taxes += tax; tips += extra;
for (NSNumber *w in diners.allValues) weight += w.longLongValue;
NSArray<NSString *> *names = [diners.allKeys sortedArrayUsingSelector:@selector(compare:)];
NSMutableDictionary<NSString *, NSNumber *> *shares = [NSMutableDictionary dictionary];
for (NSString *name in names) {
long long share = floor_div(line * diners[name].longLongValue, weight);
shares[name] = @(share);
given += share;
}
for (long long i = 0; i < line - given; i++)
shares[names[i]] = @(shares[names[i]].longLongValue + 1);
for (NSString *name in names)
totals[name] = @(totals[name].longLongValue + shares[name].longLongValue);
}
for (NSString *name in [totals.allKeys sortedArrayUsingSelector:@selector(compare:)])
printf("%s: %s\n", name.UTF8String, rupees(totals[name].longLongValue).UTF8String);
printf("Bill: items %s, gst %s, tip %s, total %s\n", rupees(prices).UTF8String, rupees(taxes).UTF8String,
rupees(tips).UTF8String, rupees(prices + taxes + tips).UTF8String);
}
return 0;
}Visual Basic · vb/split/Program.vb
' The bill-splitting specification of the atlas capstone, in Visual Basic on .NET 10. \ truncates towards zero and
' Integer has 32 bits, so the amounts are Long, FloorDiv rounds down by hand and names sort with StringComparer.Ordinal.
Imports System.IO
Imports System.Text.RegularExpressions
Module Program
ReadOnly RatePattern As New Regex("^0*([0-9]{1,3})(?:\.([0-9]{1,2}))?$")
ReadOnly PricePattern As New Regex("^-?0*[0-9]{1,10}$")
ReadOnly DinerPattern As New Regex("^([A-Za-z]+)(?::([1-9][0-9]{0,2}))?$")
Function FloorDiv(a As Long, b As Long) As Long
Dim q As Long = a \ b
If a Mod b <> 0 AndAlso (a < 0) <> (b < 0) Then q -= 1
Return q
End Function
Function HalfUp(a As Long, b As Long) As Long
Return FloorDiv(2 * a + b, 2 * b)
End Function
Function Rate(word As String) As Long
Dim m As Match = RatePattern.Match(word)
If Not m.Success Then Return -1
Dim bp As Long = Long.Parse(m.Groups(1).Value) * 100 + Long.Parse(m.Groups(2).Value.PadRight(2, "0"c))
Return If(bp <= 5000, bp, -1)
End Function
Function Rupees(paise As Long) As String
Dim digits As String = (Math.Abs(paise) \ 100).ToString()
If digits.Length > 3 Then
Dim head As String = digits.Substring(0, digits.Length - 3)
Dim tail As String = digits.Substring(digits.Length - 3)
Dim groups As New List(Of String)
While head.Length > 2
groups.Insert(0, head.Substring(head.Length - 2))
head = head.Substring(0, head.Length - 2)
End While
groups.Insert(0, head)
digits = String.Join(",", groups) & "," & tail
End If
Return If(paise < 0, "-", "") & digits & "." & (Math.Abs(paise) Mod 100).ToString("00")
End Function
Function Fail(message As String) As Integer
Console.Error.WriteLine(message)
Return 2
End Function
Function Main(args As String()) As Integer
If args.Length <> 1 Then Return Fail("usage: split <bill.txt>")
Dim lines As String() = File.ReadAllText(args(0)).Split(ControlChars.Lf)
Dim gst As Long = -1, tip As Long = -1
Dim items As New List(Of (Price As Long, Diners As Dictionary(Of String, Long)))
For number As Integer = 1 To lines.Length
Dim words As String() = lines(number - 1).Split({" "c, ControlChars.Tab}, StringSplitOptions.RemoveEmptyEntries)
If words.Length = 0 OrElse words(0).StartsWith("#") Then Continue For
Dim key As String = words(0)
If (key = "gst" OrElse key = "tip") AndAlso words.Length = 2 AndAlso Rate(words(1)) >= 0 Then
If key = "gst" AndAlso gst < 0 Then gst = Rate(words(1)) : Continue For
If key = "tip" AndAlso tip < 0 Then tip = Rate(words(1)) : Continue For
ElseIf key = "item" AndAlso words.Length >= 3 AndAlso PricePattern.IsMatch(words(1)) _
AndAlso Math.Abs(Long.Parse(words(1))) <= 1000000000L Then
Dim diners As New Dictionary(Of String, Long)
Dim ok As Boolean = True
For i As Integer = 2 To words.Length - 1
Dim m As Match = DinerPattern.Match(words(i))
Dim weight As Long = If(m.Success AndAlso m.Groups(2).Success, Long.Parse(m.Groups(2).Value), 1)
ok = m.Success AndAlso weight <= 100 AndAlso Not diners.ContainsKey(m.Groups(1).Value)
If Not ok Then Exit For
diners(m.Groups(1).Value) = weight
Next
If ok Then items.Add((Long.Parse(words(1)), diners)) : Continue For
End If
Return Fail($"error: line {number}")
Next
If gst < 0 Then Return Fail("error: no gst line")
If items.Count = 0 Then Return Fail("error: no items")
If tip < 0 Then tip = 0
Dim totals As New Dictionary(Of String, Long)
Dim prices As Long = 0, taxes As Long = 0, tips As Long = 0
For Each item In items
Dim tax As Long = HalfUp(item.Price * gst, 10000)
Dim extra As Long = HalfUp(item.Price * tip, 10000)
Dim line As Long = item.Price + tax + extra
prices += item.Price : taxes += tax : tips += extra
Dim weight As Long = item.Diners.Values.Sum()
Dim names As List(Of String) = item.Diners.Keys.ToList()
names.Sort(StringComparer.Ordinal)
Dim shares As New Dictionary(Of String, Long)
For Each name In names
shares(name) = FloorDiv(line * item.Diners(name), weight)
Next
Dim left As Long = line - shares.Values.Sum()
For i As Integer = 0 To CInt(left) - 1
shares(names(i)) += 1
Next
For Each name In names
totals(name) = If(totals.ContainsKey(name), totals(name), 0) + shares(name)
Next
Next
Dim everyone As List(Of String) = totals.Keys.ToList()
everyone.Sort(StringComparer.Ordinal)
For Each name In everyone
Console.WriteLine($"{name}: {Rupees(totals(name))}")
Next
Console.WriteLine($"Bill: items {Rupees(prices)}, gst {Rupees(taxes)}, tip {Rupees(tips)}, total {Rupees(prices + taxes + tips)}")
Return 0
End Function
End Modulefrom session import run
# The Tcl and Objective-C implementations against the twenty vectors, each with its toolchain's version and its size.
run("""
echo 'puts [info patchlevel]' | tclsh9.0
sh check.sh tclsh9.0 tcl/split.tcl
wc -l < tcl/split.tcl
clang --version | head -1
clang -fobjc-arc -Wall -Wextra -Wformat-security -framework Foundation objc/split.m -o split-objc
sh check.sh ./split-objc
wc -l < objc/split.m
""")Output
$ echo 'puts [info patchlevel]' | tclsh9.0
9.0.4
$ sh check.sh tclsh9.0 tcl/split.tcl
20 of 20 vectors pass
$ wc -l < tcl/split.tcl
116
$ clang --version | head -1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang -fobjc-arc -Wall -Wextra -Wformat-security -framework Foundation objc/split.m -o split-objc
$ sh check.sh ./split-objc
20 of 20 vectors pass
$ wc -l < objc/split.m
123
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 tcl_objc_session.py
from session import run
# The Visual Basic implementation built with the .NET SDK and checked against the twenty vectors; its size in lines.
run("""
dotnet --version
dotnet build vb/split -o vb-out --nologo -v quiet
sh check.sh dotnet vb-out/split.dll
wc -l < vb/split/Program.vb
""")Output
$ dotnet --version
10.0.401
$ dotnet build vb/split -o vb-out --nologo -v quiet
Build succeeded.
0 Warning(s)
0 Error(s)
Time Elapsed …
$ sh check.sh dotnet vb-out/split.dll
20 of 20 vectors pass
$ wc -l < vb/split/Program.vb
110
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 vb_session.py
All four passed all twenty, with the toolchains each session named first. Compared side by side:
| Language | Lines | What it replaced |
|---|---|---|
| Crystal 1.21.1 | 102 | Int64 amounts with the Int64 first in each product; // already floors |
| Tcl 9.0.4 | 116 | nothing in the arithmetic: integers grow and / floors; lsort sorts by code point |
| Objective-C (clang 21.0.0) | 123 | long long amounts, a floor_div helper, printf rather than NSLog, which adds a time stamp |
| Visual Basic (.NET 10.0.401) | 110 | Long amounts, a FloorDiv helper, StringComparer.Ordinal |
The line counts measure the code, not the languages’ worth: Tcl’s 116 lines replaced nothing, while Objective-C’s
123 include a helper that C’s truncating / made necessary. What each column shows is where a language’s defaults
and the specification part company, which is exactly what a port has to find.
Checkpoint
Check: Four implementations compared
The other eight atlas languages
Each mini-course of the atlas answered the questions of the concept map with a recorded run. These are its answers for the rows that this specification depends on:
| Language | Integer division | A half | Integers |
|---|---|---|---|
| ABAP | / rounds commercially to the calculation type; DIV keeps the remainder positive |
commercially, away from zero | i stops at 2,147,483,647; int8 holds more |
| Object Pascal | div truncates, mod takes the left sign |
Round goes to even |
Integer is 16 bits in the default mode, 32 in objfpc |
| Ada | / and rem truncate, mod takes the divisor’s sign |
build half up on floor division | Integer'Last + 1 raises Constraint_Error |
| Groovy | / makes a BigDecimal, intdiv truncates |
round() on a BigDecimal: away from zero |
int wraps without a word |
| D | / truncates, % takes the dividend’s sign |
round away from zero, lrint to even |
int.max + 1 == int.min |
| Gleam | / truncates and 7 / 0 is 0; int.floor_divide floors |
float.round away from zero |
the BEAM grows; JavaScript loses past 2^53 |
| Nim | div truncates; floorDiv floors |
round away from zero |
int has 64 bits; overflow is a defect |
| Elm | // truncates and wraps past 2,147,483,647 |
round goes up, towards plus infinity |
Int is a JavaScript number |
Two rows need care beyond floor division. Elm’s // wraps once a quotient passes 2,147,483,647, so the
specification’s limits keep every quotient of one line below that: the largest line, a price of 1,000,000,000 paise
with 50 % GST and a 50 % tip, is 2,000,000,000. A bill of many lines has no such limit on its totals, so an Elm
version should print them from the digits of String.fromInt rather than divide them with //. And Gleam’s division by
zero gives 0 instead of an error, which the specification never needs, because the sum of the weights is at least 1.
The linked lessons, with the rest of each mini-course, show these rows run, so you can repeat them with your own
language’s toolchain before you write a line of the capstone.
Checkpoint
Check: The rows of the other eight languages
Practise: the specification, in Python
The lab builds the specification in three steps, each a part you will need in any atlas language: the amounts, the arithmetic of one line, and the whole program. The sample tests of the last step are the twenty public vectors, the same files that graded the four implementations above:
Code lab · 3 steps
The bill-splitting specification, in Python
Write the Indian grouping of amounts, the tax, shares and leftover paise of one line, and the whole program, so that it passes the twenty public vectors.
- Write paise as rupees with Indian digit grouping To do
- Split one line of the bill To do
- Implement the whole specification and pass the vectors To do
Exercise · Easy · Python
Write paise as rupees with Indian digit grouping
Every amount of the report is written by one rule of the specification. Write rupees(paise) in amounts.py: the amount, a whole number of paise, as rupees with two digits of paise after a point, a minus sign in front of a negative amount, and the rupees in Indian digit grouping: the last three digits, then a comma after every two digits, so 10000000 paise is 1,00,000.00 and 1000000000 is 1,00,00,000.00.
Use only whole numbers: the test of 1,00,00,000.00 has more digits than a float keeps exactly once paise are added. The sample tests are amounts that the twenty public vectors print.
Starter code · amounts.py
def rupees(paise):
"""paise as rupees in Indian digit grouping, such as 1,23,456.78."""
return f"{paise / 100:,.2f}"The sample tests · test_amounts.py
from amounts import rupees
def test_small_amounts():
"""two digits of paise always, and a zero before the point"""
assert rupees(10500) == "105.00"
assert rupees(5) == "0.05"
assert rupees(0) == "0.00"
def test_the_grouping_of_vector_10():
"""999.99, 1,000.00, 99,999.99 and 1,00,000.00"""
assert [rupees(p) for p in [99999, 100000, 9999999, 10000000]] == ["999.99", "1,000.00", "99,999.99", "1,00,000.00"]
assert rupees(20199998) == "2,01,999.98"
def test_a_crore_of_vector_11():
"""the bill of vector 11"""
assert rupees(1000000000) == "1,00,00,000.00"
assert rupees(1280000000) == "1,28,00,000.00"
assert rupees(426666667) == "42,66,666.67"
def test_negative_amounts():
"""the minus sign comes before the grouped rupees"""
assert rupees(-50) == "-0.50"
assert rupees(-123456789) == "-12,34,567.89"A hint
Split the size of the amount with divmod(abs(paise), 100). Write the rupees as a string, keep its last three digits, and take the rest two at a time from the right until one or two digits are left.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Exercise · Medium · Python
Split one line of the bill
Write split_line(price, diners, gst, tip) in line.py, the arithmetic of one item line. price is in paise and may be negative; diners is a list of (name, weight) pairs; gst and tip are rates in basis points, so 5 % is 500. Return (tax, extra, shares), where shares is a dict from name to paise:
taxisprice * gst / 10000andextraisprice * tip / 10000, each rounded to the nearest whole paisa with a half going up, towards plus infinity, also below zero: -50.05 becomes -50 and -0.5 becomes 0.- The line total is
price + tax + extra. Each diner's share is the total times the diner's weight, divided by the sum of the weights and rounded down, also below zero. - The paise left over, the total minus the sum of the shares, go one each to the first diners in byte order of their names (
sorted()of the names gives that order).
Use integers only. The sample tests are lines of the public vectors.
Starter code · line.py
def split_line(price, diners, gst, tip):
"""(tax, extra, shares) of one item line, in paise."""
tax = round(price * gst / 10000)
extra = round(price * tip / 10000)
line = price + tax + extra
weight = sum(w for _, w in diners)
shares = {name: int(line * w / weight) for name, w in diners}
return tax, extra, sharesThe sample tests · test_line.py
from line import split_line
def test_an_even_split():
"""vector 01: 200 rupees and 5 % for two"""
assert split_line(20000, [("Asha", 1), ("Ravi", 1)], 500, 0) == (1000, 0, {"Asha": 10500, "Ravi": 10500})
def test_the_leftover_paisa():
"""vector 02: the odd paisa goes to the first name in byte order"""
tax, extra, shares = split_line(10001, [("Ravi", 1), ("Asha", 1), ("Meera", 1)], 500, 0)
assert (tax, extra) == (500, 0)
assert shares == {"Asha": 3501, "Meera": 3500, "Ravi": 3500}
def test_weights():
"""vector 03: Asha takes two shares of three"""
assert split_line(36000, [("Asha", 2), ("Ravi", 1), ("Meera", 1)], 500, 0)[2] == {"Asha": 18900, "Ravi": 9450, "Meera": 9450}
def test_halves_round_up():
"""vector 06: 0.5, 1.5 and 2.5 paise of tax become 1, 2 and 3"""
assert [split_line(p, [("Asha", 1)], 500, 0)[0] for p in (10, 30, 50)] == [1, 2, 3]
def test_the_coupon():
"""vector 07: -50.05 rounds to -50, and -1051 splits into -525 and -526"""
assert split_line(-1001, [("Ravi", 1), ("Meera", 1)], 500, 0) == (-50, 0, {"Ravi": -526, "Meera": -525})
def test_negative_halves_round_up_too():
"""vector 08: -0.5 becomes 0 and -1.5 becomes -1"""
assert split_line(-10, [("Asha", 1)], 500, 0)[0] == 0
assert split_line(-30, [("Bilal", 1)], 500, 0)[0] == -1
def test_a_crore():
"""vector 11: far past 32 bits before dividing, exact all the same"""
tax, extra, shares = split_line(1000000000, [("Asha", 1), ("Ravi", 1), ("Meera", 1)], 1800, 1000)
assert (tax, extra) == (180000000, 100000000)
assert shares == {"Asha": 426666667, "Ravi": 426666666, "Meera": 426666667}A hint
Python's // already rounds down below zero too. Rounding a / b half up is then (2 * a + b) // (2 * b) for b > 0, and the leftover is never negative and always smaller than the number of diners.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Exercise · Hard · Python
Implement the whole specification and pass the vectors
Implement the whole specification in split.py: split(text) takes the text of a bill and returns (stdout, stderr, status), exactly what the reference implementations print for it.
split.py starts with rupees and split_line from the first two steps. Add the reading of the input, with every rule of the specification's input section and its three error messages, and the report: one line per diner in byte order of the names, then the line that begins Bill:. Every line of the output ends with a line break.
The sample tests are the twenty public vectors, the same files that check.sh gave to the Crystal, Tcl, Objective-C and Visual Basic implementations, which passed all twenty.
Starter code · split.py
def rupees(paise):
"""paise as rupees in Indian digit grouping, such as 1,23,456.78 (step 1)."""
whole, part = divmod(abs(paise), 100)
digits = str(whole)
if len(digits) > 3:
head, tail = digits[:-3], digits[-3:]
groups = []
while len(head) > 2:
groups.insert(0, head[-2:])
head = head[:-2]
groups.insert(0, head)
digits = ",".join(groups) + "," + tail
sign = "-" if paise < 0 else ""
return f"{sign}{digits}.{part:02d}"
def split_line(price, diners, gst, tip):
"""(tax, extra, shares) of one item line, in paise (step 2)."""
tax = (2 * price * gst + 10000) // 20000
extra = (2 * price * tip + 10000) // 20000
line = price + tax + extra
weight = sum(w for _, w in diners)
shares = {name: line * w // weight for name, w in diners}
left = line - sum(shares.values())
for name in sorted(shares)[:left]:
shares[name] += 1
return tax, extra, shares
def split(text):
"""(stdout, stderr, status) of the specification for the text of a bill."""
gst, tip, items = 500, 0, []
for line in text.split("\n"):
words = line.split()
if words and words[0] == "item":
items.append((int(words[1]), [(name, 1) for name in words[2:]]))
totals = {}
for price, diners in items:
for name, share in split_line(price, diners, gst, tip)[2].items():
totals[name] = totals.get(name, 0) + share
return "".join(f"{name}: {rupees(total)}\n" for name, total in totals.items()), "", 0The sample tests · test_split.py
from split import split
# The twenty public vectors: (name, input, expected stdout, expected stderr, expected status).
VECTORS = [
('01-even', 'gst 5\nitem 20000 Asha Ravi\n', 'Asha: 105.00\nRavi: 105.00\nBill: items 200.00, gst 10.00, tip 0.00, total 210.00\n', '', 0),
('02-odd-paisa', 'gst 5\nitem 10001 Ravi Asha Meera\n', 'Asha: 35.01\nMeera: 35.00\nRavi: 35.00\nBill: items 100.01, gst 5.00, tip 0.00, total 105.01\n', '', 0),
('03-shares', 'gst 5\nitem 36000 Asha:2 Ravi Meera\n', 'Asha: 189.00\nMeera: 94.50\nRavi: 94.50\nBill: items 360.00, gst 18.00, tip 0.00, total 378.00\n', '', 0),
('04-tip', 'gst 5\ntip 10\nitem 24000 Asha Ravi\nitem 9000 Asha\n', 'Asha: 241.50\nRavi: 138.00\nBill: items 330.00, gst 16.50, tip 33.00, total 379.50\n', '', 0),
('05-decimal-rates', 'gst 2.5\ntip 7.5\nitem 12345 Asha Bilal\n', 'Asha: 67.90\nBilal: 67.90\nBill: items 123.45, gst 3.09, tip 9.26, total 135.80\n', '', 0),
('06-half-up', 'gst 5\nitem 10 Asha\nitem 30 Asha\nitem 50 Bilal\n', 'Asha: 0.43\nBilal: 0.53\nBill: items 0.90, gst 0.06, tip 0.00, total 0.96\n', '', 0),
('07-coupon', 'gst 5\nitem 30000 Asha Ravi Meera\nitem -1001 Ravi Meera\n', 'Asha: 105.00\nMeera: 99.75\nRavi: 99.74\nBill: items 289.99, gst 14.50, tip 0.00, total 304.49\n', '', 0),
('08-negative-half', 'gst 5\nitem 100 Asha\nitem -10 Asha\nitem -30 Bilal\nitem 100 Bilal\n', 'Asha: 0.95\nBilal: 0.74\nBill: items 1.60, gst 0.09, tip 0.00, total 1.69\n', '', 0),
('09-name-order', 'gst 0\nitem 100 asha Zoya Bilal\n', 'Bilal: 0.34\nZoya: 0.33\nasha: 0.33\nBill: items 1.00, gst 0.00, tip 0.00, total 1.00\n', '', 0),
('10-grouping', 'gst 0\nitem 99999 Asha\nitem 100000 Bilal\nitem 9999999 Chetan\nitem 10000000 Divya\n', 'Asha: 999.99\nBilal: 1,000.00\nChetan: 99,999.99\nDivya: 1,00,000.00\nBill: items 2,01,999.98, gst 0.00, tip 0.00, total 2,01,999.98\n', '', 0),
('11-crore', 'gst 18\ntip 10\nitem 1000000000 Asha Ravi Meera\n', 'Asha: 42,66,666.67\nMeera: 42,66,666.67\nRavi: 42,66,666.66\nBill: items 1,00,00,000.00, gst 18,00,000.00, tip 10,00,000.00, total 1,28,00,000.00\n', '', 0),
('12-one-diner', 'gst 12\nitem 49999 Asha\n', 'Asha: 559.99\nBill: items 499.99, gst 60.00, tip 0.00, total 559.99\n', '', 0),
('13-zero-price', 'gst 5\nitem 0 Asha Ravi\nitem 500 Asha\n', 'Asha: 5.25\nRavi: 0.00\nBill: items 5.00, gst 0.25, tip 0.00, total 5.25\n', '', 0),
('14-seven-diners', 'gst 5\ntip 5\nitem 1000 Gita Farah Esha Divya Chetan Bilal Asha\n', 'Asha: 1.58\nBilal: 1.57\nChetan: 1.57\nDivya: 1.57\nEsha: 1.57\nFarah: 1.57\nGita: 1.57\nBill: items 10.00, gst 0.50, tip 0.50, total 11.00\n', '', 0),
('15-small-negative', 'gst 5\nitem 1000 Asha\nitem -48 Ravi\n', 'Asha: 10.50\nRavi: -0.50\nBill: items 9.52, gst 0.48, tip 0.00, total 10.00\n', '', 0),
('16-comments', '# dinner on Friday\n\ngst 5\n item 500 Asha Ravi \n# the coffee\nitem 120 Ravi\n', 'Asha: 2.63\nRavi: 3.88\nBill: items 6.20, gst 0.31, tip 0.00, total 6.51\n', '', 0),
('17-tip-only', 'gst 0\ntip 12.5\nitem 8000 Asha Ravi:3\n', 'Asha: 22.50\nRavi: 67.50\nBill: items 80.00, gst 0.00, tip 10.00, total 90.00\n', '', 0),
('18-no-gst', 'tip 10\nitem 100 Asha\n', '', 'error: no gst line\n', 2),
('19-bad-price', 'gst 5\nitem 100 Asha\nitem 12.50 Ravi\n', '', 'error: line 3\n', 2),
('20-bad-share', 'gst 5\nitem 100 Asha:0 Ravi\n', '', 'error: line 2\n', 2),
]
def failing(names):
"""The vectors among names whose output, error or status differs from the expected one."""
return [n for n, text, out, err, status in VECTORS if n in names and split(text) != (out, err, status)]
def test_even_and_leftover():
"""the even split and the odd paisa"""
assert failing(['01-even', '02-odd-paisa', '03-shares', '14-seven-diners']) == []
def test_tip_and_rates():
"""a tip, and rates with decimals"""
assert failing(['04-tip', '05-decimal-rates', '17-tip-only']) == []
def test_rounding_halves():
"""halves round up, also below zero"""
assert failing(['06-half-up', '08-negative-half', '15-small-negative']) == []
def test_the_coupon():
"""a negative line shared by two"""
assert failing(['07-coupon']) == []
def test_names_and_grouping():
"""byte order of names and Indian grouping"""
assert failing(['09-name-order', '10-grouping', '11-crore']) == []
def test_odd_bills():
"""one diner, an item at 0 paise and comments"""
assert failing(['12-one-diner', '13-zero-price', '16-comments']) == []
def test_errors():
"""the three error messages"""
assert failing(['18-no-gst', '19-bad-price', '20-bad-share']) == []A hint
Read the bill line by line with its number, enumerate(text.split("\n"), 1), and line.split() to get the words. Check each rule of a line before you keep anything from it, so that a bad line gives error: line N at once, and check for the gst line and the items only after the last line.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Then take the specification to the atlas language you know best. Copy check.sh from this page, save the twenty
vectors of the last step’s sample tests as files in a folder named vectors, write the program, and run
sh check.sh with your program’s command; twenty of twenty is the goal, and every vector that differs names the rule
to read again. The self-check below asks one question at a time, starting where your answers
are weakest:
Practice that adapts to you
Practise this lesson
12 questions about 5 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
Warm-up (mid-level to senior): Why does the specification round half up with integers instead of calling the language’s round?
Because round means different things in different languages, and the specification must give the same paise in all
of them. Crystal’s round and Visual Basic’s CInt send a half to the even neighbour, Tcl’s and C’s take it away
from zero, Elm’s goes up towards plus infinity, and all of them work on floats, which hold most decimal fractions
only approximately. With integers, rounding a / b half up is (2a + b) divided by 2b with floor division, an
exact rule with no float and no mode: the coupon’s −50.05 paise becomes −50 in every language that floors. The
twenty vectors show why it matters: a Crystal version that used round failed exactly the two vectors whose taxes
fall on a half, 06 and 08, and passed the other eighteen.
Warm-up (fresher to mid-level): What is a test vector, and what can twenty public vectors prove?
A test vector is one input with the exact output it must give: here a bill, the report on standard output, the message on standard error and the exit status. A shared check such as check.sh runs any program on every vector and compares those three outputs byte for byte, so the same vectors grade every language. Passing all twenty proves that the implementation follows each rule the vectors pin, from floor division of a negative line to the order of names. It proves nothing about rules no vector pins, such as the limit of 50 % on rates or a name used twice on one line, so an implementer adds vectors of their own for those, and keeps the invariant that the diners’ totals add up to the bill.
Two longer questions, on an implementation that is one paisa off on some bills and on taking the specification to a new language:
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Fresher to senior
A teammate's implementation of the bill-splitting specification passes most vectors, but on some bills one diner is one paisa off and the totals no longer add up to the bill. Where do you look, in what order, and how do you prove the fix?
-
Mid to staff
You are asked to implement the bill-splitting specification in an atlas language you have never used. How do you go from zero to twenty of twenty vectors with the fewest wrong turns, and what do you check before you trust the result?
And the warm-up that the whole capstone rests on:
Warm-up (fresher to mid-level): What is floor division, and when does it differ from truncating division?
Both divide two whole numbers and drop the fraction, but in different directions. Floor division rounds down,
towards minus infinity; truncating division rounds towards zero. For a positive quotient they agree: 1051 divided by 2
is 525 either way. They differ only when the exact quotient is negative and not whole: -1051 divided by 2 is -525.5,
which floor division makes -526 and truncation -525. Crystal’s // and Tcl’s / floor; C’s and Objective-C’s /,
Visual Basic’s \ and Crystal’s tdiv truncate. The capstone needs floor division so that the paise left over after
rounding every share down are never negative.
Flashcards · 8 cards
Recall it, then check
Say the answer to yourself before you look: recalling it is what makes it stick.
-
Split −1,051 paise between two diners with each language's first integer division. What do the four languages give?
Crystal's // and Tcl's / floor, giving −526; Objective-C's / and Visual Basic's \ truncate, giving −525. A paisa per diner, decided by a default.
-
How does the capstone round a ÷ b half up using integers only?
(2a + b) div (2b) with floor division, below zero too. The coupon's tax of −50.05 paise becomes −50 in every language that floors.
-
How does the capstone hold a tax rate of 2.5 %, and why?
As 250 basis points; a basis point is a hundredth of one percent. The tax is then the price times 250, divided by 10,000, all in whole numbers.
-
Where do a line's leftover paise go?
One each to the line's first diners in byte order of their names, so that the shares add up exactly to the line total.
-
In which order are the diners reported, and why does Visual Basic's Array.Sort get it wrong?
Byte order: Bilal, Zoya, asha. Array.Sort follows the computer's language setting and gave asha Bilal Zoya; StringComparer.Ordinal sorts by bytes everywhere.
-
What is a test vector here, and what does check.sh compare?
A bill with the exact output it must give. check.sh runs a program on every vector and compares standard output, standard error and exit status byte for byte, so it grades any language.
-
Why did naive.cr, which rounded with Crystal's round, fail vectors 06 and 08 only?
Those are the two whose taxes land exactly on a half, and Crystal's round goes to the even neighbour: 0.5 paise became 0 and 2.5 became 2. The other eighteen passed.
-
Why does typeof(2 * 1_000_000_000_i64) print Int32 in Crystal?
The result takes the type of the left operand, Int32 here, so 2 * a may overflow while a * 2 is an Int64. half_up therefore puts the Int64 first.
Key takeaways
- The specification fixes everything a language would otherwise decide: paise as integers, rates as basis points, tax and tip half up per line, shares rounded down, leftover paise in byte order of names, and the report’s format.
- The twenty public vectors give each rule a bill that only a correct implementation gets right, and check.sh grades any language by its standard output, standard error and exit status.
- A Crystal version with
roundfailed exactly the two vectors whose taxes fall on a half; four careful implementations, in Crystal, Tcl, Objective-C and Visual Basic, passed all twenty. - The traps differ by language: truncating division in Objective-C and Visual Basic, rounding to even in Crystal and
CInt, 32-bit defaults in Crystal, Objective-C and Visual Basic, and culture-aware sorting inArray.Sort. - Each atlas mini-course recorded the rows of its own language, so a new implementation starts from the table, the vectors and the check.
Terms in this lesson
- basis point
- One hundredth of a percent. A rate of 2.5 % is 250 basis points and 18 % is 1800, so a specification can keep rates with two decimals as whole numbers and never needs a float for them.
- Indian digit grouping
- Writing the whole rupees of an amount with a comma before the last three digits and then before every two digits further left: 1,00,000.00 for one lakh and 1,00,00,000.00 for one crore.
- leftover paise
- The paise that remain when an amount is split into whole-paisa shares rounded down. With floor division they are never negative and always fewer than the sharers, and the capstone gives them one each in name order.
- ordinal comparison
- Comparing strings by the number of each character, as StringComparer.Ordinal and Crystal's sort do, instead of by the rules of a human language: every capital comes before every small letter, so Zoya sorts before asha.
References
- Int: floored and truncated division (Crystal 1.21.1 API) (Crystal)
- Int32: arithmetic with another integer type returns self (Crystal 1.21.1 API) (Crystal)
- Tcl 9.0 manual: expr (Tcl Core Team)
- Tcl 9.0 manual: lsort (Tcl Core Team)
- round, roundf, roundl: round to the nearest integer value (The Open Group)
- Clang language extensions: checked arithmetic builtins (LLVM Project)
- NSString compare(_:) (Apple)
- \ operator: integer division (Visual Basic) (Microsoft)
- Type conversion functions: CInt (Visual Basic) (Microsoft)
- StringComparer.Ordinal property (Microsoft)
- ABAP cheat sheet: numeric operations (SAP)
- Free Pascal reference guide: arithmetic operators (Free Pascal team)
- Free Pascal reference guide: ordinal types (Integer by mode) (Free Pascal team)
- Ada Reference Manual 4.5.5: multiplying operators (Ada Information Clearinghouse)
- The Apache Groovy programming language: operators (The Apache Software Foundation)
- D Language Specification: expressions (D Language Foundation)
- gleam/int (gleam_stdlib) (Gleam)
- Nim Manual (Nim)
- elm/core: Basics (Elm)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress