Solve the Global Debt, the Code Golf way

The leaders of the world have met and have finally admitted that the best (and only) way of resolving global economic woes is to take stock of how much they owe each other and just pay each other off with huge cheques. They have hired you (ironically, at the lowest contract rate possible) to work out the best means of doing so.

After much deliberation, and asking someone to draw a simple example they've come up with the following spec.

Each country is represented by their ISO 3166-1 alpha-2 code: US for the USA, AU for Australia, JP for Japan, CN for China and so on...

1. A ledger is drawn up as a series of country entries and the amounts owing to each country.
2. Each country's entry starts off with their domain ID a colon, and how much they have in surplus/deficit (in billions of Euro), followed by a semicolon, then a coloned comma-separated list of the countries and how much (in billions of Euro) they owe.
3. If a country owes nothing to another country, no mention of that country is entered after that semicolon separator.
4. Deficits are indicated as negative numbers, surplus is indicated as a positive number.
5. Values can also be floats.
6. The ledger must be taken from STDIN. The end of the ledger is indicated by a carriage return on a blank line. The tally must be delivered to STDOUT.

An example of a ledger:

Input:
AU:8;US:10,CN:15,JP:3
US:14;AU:12,CN:27,JP:14
CN:12;AU:8,US:17,JP:4
JP:10;AU:6,US:7,CN:10

The system then works out how much each country owes and is owed and determines their surplus/deficit, for example, for AU:

AU = 8 (current surplus) -10 (to US) -15 (to CN) -3 (to JP) +12 (from US) +8 (from CN) +6 (from JP) = 6

When all the computing is done, a tally must be shown:

Output:
AU:6
US:-5
CN:35
JP:8

Your job is to create this system, capable of taking any number of ledger entries for any number of countries and capable of determining how much each country has in deficit/surplus when everything is paid out.

The ultimate test is for you to use your code to resolve the debt owed between the following countries in the test case below. These figures were taken from BBC News as of June 2011. (http://www.bbc.com/news/business-15748696)

For the purposes of the exercise, I have used their respective GDP as their current surplus... Please bear in mind that this is strictly an exercise in code quality assurance... there will be no talk of global economic resolution here in this question... If you want to talk economics I'm sure there's another subdomain in SE that handles it...

US:10800;FR:440.2,ES:170.5,JP:835.2,DE:414.5,UK:834.5
FR:1800;IT:37.6,JP:79.8,DE:123.5,UK:227,US:202.1
ES:700;PT:19.7,IT:22.3,JP:20,DE:131.7,UK:74.9,US:49.6,FR:112
PT:200;IT:2.9,DE:26.6,UK:18.9,US:3.9,FR:19.1,ES:65.7
IT:1200;JP:32.8,DE:120,UK:54.7,US:34.8,FR:309,ES:29.5
IE:200;JP:15.4,DE:82,UK:104.5,US:39.8,FR:23.8
GR:200;DE:15.9,UK:9.4,US:6.2,FR:41.4,PT:7.5,IT:2.8
JP:4100;DE:42.5,UK:101.8,US:244.8,FR:107.7
DE:2400;UK:141.1,US:174.4,FR:205.8,IT:202.7,JP:108.3
UK:1700;US:578.6,FR:209.9,ES:316.6,IE:113.5,JP:122.7,DE:379.3

Now, be the economic savior of the world!

Rules:

1. Shortest code wins... this is code-golf after all...
2. Please provide your output of the major test case with your code answer...
• In the "ultimate test", shouldn't there be a semicolon after JP:4100? – Mathieu Rodic Mar 27 '14 at 8:53
• I can't help but wonder if this is a very clever way of having a homework assignment completed for you. If so, you deserve it. – mkingston Mar 27 '14 at 11:30
• Yeah, if you did this will real numbers you'd notice an astonishing contradiction. The sum of all surpluses and deficits will be negative. – Cruncher Mar 27 '14 at 12:57
• Actually, it's not homework in disguise... It was inspired from my weekly poker tournament with my friends... Trying to figure out a quicker way of working out the winnings for each player ;) – WallyWest Mar 27 '14 at 20:31
• @WallyWest LOL ;) btw, apologies for the OT comments, but it's a matter I'm quite passionate about. Now let's get back to some fun coding and forget the woes of the world... – Tobia Mar 27 '14 at 20:33

K, 66

{(((!)."SF"$+":"\:'*+a)-+/'d)+/d:"F"$(!).'"S:,"0:/:last'a:";"\:'x}

.

k)input:0::ledg.txt
k){(((!)."SF"$+":"\:'*+a)-+/'d)+/d:"F"$(!).'"S:,"0:/:last'a:";"\:'x} input
US| 9439.3
FR| 2598.9
ES| 852.1
PT| 90.1
IT| 887.5
IE| 48
GR| 116.8
JP| 4817.4
DE| 2903.7
UK| 1546.2
• Incredibly impressed with this one... any chance you can provide a link to the K programming paradigm? – WallyWest Mar 31 '14 at 22:25
• @WallyWest code.kx.com provides lots of information on q, which is the syntactic sugar that sits on top of k. q, moreso thank k, is what you'll find in production systems but for golfing k has the edge. Also check out Kona (github.com/kevinlawler/kona) which is an open source implementation of an older version of k – tmartin Apr 1 '14 at 12:05

Perl, 139137134119 112

Here's another working piece of code... I will document it later.

Golfed code

With dictionary (112):

for(<>){~/:(.+);/g;$d{$c=$}+=$1;$l=$';$d{$1}+=$2,$d{$c}-=$2while$l=~/(..):([^,]+)/g}print"$_:$d{$_}
"for keys%d

Without dictionary (137):

for($T=$t.=$_ for<>;$t=~/(..:)(.+);(.+)/g;print"$c$s\n"){$c=$1;$l=$3;$s=$2;$s-=$&while$l=~/[\d.]+/g;$s+=$1while$T=~/$c([\d.]+)(?!;|\d)/g} Output US:9439.3 FR:2598.9 ES:852.1 PT:90.1 IT:887.5 IE:48 GR:116.8 JP:4817.4 DE:2903.7 UK:1546.2 See it in action! http://ideone.com/4iwyEP • The definition of "short" should be judged by amount of tokens, not characters. Readability 4 life! – Domi Mar 28 '14 at 6:57 • @Domi - you're new here, aren't you ;-) – jimbobmcgee Mar 28 '14 at 12:27 • @jimbobmcgee: I also have a feeling this website is not much about readability... – Mathieu Rodic Mar 28 '14 at 12:28 Python, 211185 183 import sys,re;t,R,F=sys.stdin.read(),re.findall,float;S=lambda e,s:sum(map(F,R(e,s))) for m in R('(..:)(.+);(.+)',t):print m+F(m)+S(m+'([\d.]+)(?!;|\d)',t)-S('[\d.]+',m) Output with major test case: US:9439.300000000001 FR:2598.9 ES:852.0999999999999 PT:90.09999999999997 IT:887.5 IE:48.0 GR:116.8 JP:4817.4 DE:2903.7 UK:1546.2000000000003 (test it here: http://ideone.com/CjWG7v) C - 257 253 if no CR at end of line Depends on sizeof(short)==2. No check for buffer overflow. #define C(c) x[*(short*)c] main(i){double x={0},d;char*q,b,*(*s)()=strtok;for(;gets(b);)for(s(b,":"),C(b)+=atof(s(0,";"));q=s(0,":");C(b)-=d=(atof(s(0,","))),C(q)+=d);for(i=b=0;i<23131;memcpy(b,&i,2),x[i]?printf("%s:%f\n",b,x[i++]):++i);} Output: DE:2903.700000 IE:48.000000 UK:1546.200000 JP:4817.400000 FR:2598.900000 GR:116.800000 ES:852.100000 US:9439.300000 IT:887.500000 PT:90.100000 Less golfed: #define C(c) x[*(short*)c] main(i) { double x={0}, d; char *q, b, *(*s)()=strtok; for(;gets(b);) for(s(b, ":"),C(b)+=atof(s(0, ";")); q=s(0, ":"); C(b)-=d=(atof(s(0, ","))), C(q)+=d) ; for(i=b=0; i<23131; memcpy(b, &i, 2), x[i]?printf("%s:%f\n", b, x[i++]):++i) ; } PHP - 338, 280 Should work with any version of PHP 5. Golfed: while(preg_match("#(..):(.+);(.*)#",fgets(STDIN),$m)){$l[$m]=(float)$m;foreach(explode(",",$m)as$x){$_=explode(":",$x);$l[$m][$_]=(float)$_;}}foreach($l as$c=>$d)foreach($das$_=>$o){$l[$_]+=$o;$l[$c]-=$o;}foreach($l as$c=>$d)echo$c,":",$d,"\n";

Un-golfed:

<?php

while( preg_match( "#(..):(\d+);(.*)#", fgets( STDIN ), $m ) ) {$l[$m] = (float)$m;

foreach( explode( ",", $m ) as$x )
{
$_ = explode( ":",$x );
$l[$m][$_] = (float)$_;
}
}

foreach( $l as$c => $d ) foreach($d as $_ =>$o )
{
$l[$_] += $o;$l[$c] -=$o;
}

Output

UK:1546.2
DE:2903.7
IT:887.5
FR:2598.9
PT:90.1
US:9439.3
JP:4817.4
ES:852.1
IE:48
GR:116.8

Perl - 116114 112

for(<>){($n,$m,@l)=split/[:;,]/;$h{$n}+=$m;$h{$n}-=$p,$h{$o}+=$p while($o,$p,@l)=@l}print"$_:$h{$_}\n"for keys%h

GR:116.8
UK:1546.2
DE:2903.7
IE:48
IT:887.5
US:9439.3
PT:90.1
ES:852.1
FR:2598.9
JP:4817.4

Ungolfed:

for(<>) {
($n,$m, @l)=split(/[:;,]/);
$h{$n}+=$m;$h{$n}-=$p, $h{$o}+=$p while ($o,$p,@l)=@l } print "$_:$h{$_}\n" for keys%h
• Nice! I like your approach :) – Mathieu Rodic Mar 28 '14 at 12:30

C++ - 1254

#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cstdlib>
using namespace std;int main(){vector<string>input,countries,output;vector<double>results;string last_val;int j,k,i=0;cout<<"Input\n";do{getline(cin,last_val);if(last_val!=""){input.push_back(last_val);countries.push_back(last_val.substr(0,2));}}while(last_val!="");for(j=0;j<countries.size();j++){results.push_back(0);for(k=0;k<input.size();k++)input[k].substr(0, 2)==countries[j]?results[j]+=atof(input[k].substr((input[k].find(countries[j])+3),(input[k].find(',',input[k].find(countries[j]))-input[k].find(countries[j]))).c_str()):results[j]+=atof(input[k].substr((input[k].find(countries[j],3)+3),(input[k].find(',',input[k].find(countries[j]))-input[k].find(countries[j]))).c_str());}for(j=0;j<input.size();j++){for(k=0;k<countries.size();k++){if(input[j].substr(0,2)!=countries[k]){results[j]-=atof(input[j].substr((input[j].find(countries[k])+ 3),(input[j].find(',',input[k].find(countries[k]))-input[j].find(countries[j]))).c_str());}}}for(i=0;i<countries.size();i++){stringstream strstream;strstream<<countries[i]<<":"<<results[i];output.push_back(strstream.str().c_str());}cout<<"Output:\n";for(i=0;i<output.size();i++){cout<<output[i]<<'\n';}return 0;}

I realize the code is very long, but enjoyed the good fun. This is my first time code golfing, and I am new to C++, so suggestions for improving my code are much appreciated.

Output:
US:9439.3
FR:2598.9
ES:852.1
PT:90.1
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7
UK:1546.2

Ungolfed Code

#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cstdlib>

using namespace std;

int main() {
vector<string> input, countries, output;
vector<double> results;
string last_val;
int i, j, k;

cout << "Input\n";
do {
getline(cin, last_val);
if(last_val != "") {
input.push_back(last_val);
countries.push_back(last_val.substr(0, 2));
}
} while(last_val != "");

for(j = 0; j < countries.size(); j++) {
results.push_back(0);
for(k = 0; k < input.size(); k++) {
if(input[k].substr(0, 2) == countries[j]) {
results[j] += atof(input[k].substr((input[k].find(countries[j]) + 3),
(input[k].find(',', input[k].find(countries[j])) -
input[k].find(countries[j]))).c_str());
} else {
results[j] += atof(input[k].substr((input[k].find(countries[j], 3) + 3),
(input[k].find(',', input[k].find(countries[j])) -
input[k].find(countries[j]))).c_str());
}
}
}

for(j = 0; j < input.size(); j++) {
for(k = 0; k < countries.size(); k++) {
if(input[j].substr(0, 2) != countries[k]) {
results[j] -= atof(input[j].substr((input[j].find(countries[k]) + 3),
(input[j].find(',', input[k].find(countries[k])) -
input[j].find(countries[j]))).c_str());
}
}
}

for(i = 0; i < countries.size(); i++) {
stringstream strstream;
strstream << countries[i] << ":" << results[i];
output.push_back(strstream.str().c_str());
}

cout << "Output:\n";
for(i = 0; i < output.size(); i++) {
cout << output[i] << '\n';
}

return 0;
}
• Hi, Nice to see an example in C++. You could reduce number of characters by using one-letter identifiers in stead of descriptive names, i.e. use i for input, c for countries and so on. – ahy1 Mar 31 '14 at 18:11
• Agreed with @ahy1 here... If you reduce your variables to 1 letter you can cut a fair bit of this... You may also find this of interest for future golf challenges: codegolf.stackexchange.com/questions/132/tips-for-golfing-in-c – WallyWest Mar 31 '14 at 22:28
• Oh, and you won't need cout << "Output:\n"; either... That's a 20 byte saving there... – WallyWest Mar 31 '14 at 22:29

AWK - 138 120

{l=split($0,h,"[:,;]");t[h]+=h;for(i=3;i<l;i+=2){t[h]-=h[i+1];t[h[i]]+=h[i+1]}}END{for(v in t){print v":"t[v]}} And the results$ cat data.withoutInputHeadline |awk -f codegolf.awk
IT:887.5
UK:1546.2
DE:2903.7
PT:90.1
ES:852.1
FR:2598.9
GR:116.8
Input:0
JP:4817.4
IE:48
US:9439.3

{
l=split($0,h,"[:,;]"); t[h]+=h; for(i=3;i<l;i+=2){ t[h]-=h[i+1] t[h[i]]+=h[i+1] } } END{ for(v in t){ print v":"t[v] } } (test it here: http://ideone.com/pxqc07) • Why even put those headers in? You'll save more bytes without them... they weren't even part of the spec I set... ;) – WallyWest Mar 31 '14 at 12:03 • @WallyWest: Ok, so I didn't understood that, because they are displayed in your first example of Input and Output e.g.: (..)a tally must be shown: Output: (..) No worry about that, I remove my first example right now. – Doomsday Mar 31 '14 at 12:33 Ruby - 225 First try in a challenge like this, sure it could be a lot better... R=Hash.new(0) def pd(s,o=nil);s.split(':').tap{|c,a|R[c]+=a.to_f;o&&R[o]-=a.to_f};end STDIN.read.split("\n").each{|l|c,d=l.split(';');pd(c);d.split(',').each{|s|pd(s,c.split(':'))}} puts R.map{|k,v|"#{k}: #{v}"}.join("\n") And the results$ cat data|ruby codegolf.rb
US: 9439.299999999997
FR: 2598.8999999999996
ES: 852.1
JP: 4817.4
DE: 2903.7
UK: 1546.2000000000003
IT: 887.5
PT: 90.09999999999998
IE: 48.0
GR: 116.8

JS, 254240 245

z='replace';r={};p=eval(('[{'+prompt()+'}]')[z](/\n/g,'},{')[z](/;/g,','));for(i in p){l=p[i];c=0;for(k in l){if(!c){c=k;r[c]=0;}else{r[c]-=l[k];}};for(j in p){w=p[j][c];if(w!=null)r[c]+=w}};alert(JSON.stringify(r)[z](/"|{|}/g,'')[z](/,/g,'\n'))

Well..I know it is quite long but this is my second code golf.

Suggestions are welcome!

BTW, Interesting Javascript preserves the order of elements in hashmaps, so, even if p contains an array of dictionaries, I can iterate each dictionary as an array and I'm sure that the first element of a dict is the first inserted. (the name of the country referred to the current line)

Ungolfed:

z='replace';
r={};
p=eval(('[{'+prompt()+'}]')[z](/\n/g,'},{')[z](/;/g,',')); // make the string JSONable and then evaluate it in a structure
for(i in p){
l=p[i];
c=0;
for(k in l){
if(!c){ // if c is not still defined, this is the country we are parsing.
c=k;
r[c]=0;
}
else r[c]-=l[k];
};
for(j in p){
w=p[j][c];
if(!w)  r[c]+=w
}
};
alert(JSON.stringify(r)[z](/"|{|}/g,'')[z](/,/g,'\n')) # Stringify the structure, makes it new-line separated.

Note: the input is a prompt() which should be a single line. But if you copy/paste a multi line text (like the proposed input) in a prompt() window then JS read it all.

Output:

US:9439.3
FR:2598.9
ES:852.1
PT:90.09999999999998
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7000000000003
UK:1546.2
• You use the word "replace" four times in your code. How about shortening it like this: z='replace';r={};p=eval(('[{'+prompt()+'}]')[z](/\n/g,'},{')[z](/;/g,','));for(i in p){l=p[i];c=0;for(k in l){if(!c){c=k;r[c]=0;}else{r[c]-=l[k];}};for(j in p){w=p[j][c];if(w!=null)r[c]+=w}};alert(JSON.stringify(r)[z](/"|{|}/g,'')[z](/,/g,'\n'))? – user2428118 Mar 28 '14 at 13:35
• Woah this saved me 7*4-(3*4+11) characters! (I also put (w!=null) as (!w) – Antonio Ragagnin Mar 28 '14 at 13:43
• @AntonioRagagnin Could you please show your output? – WallyWest Mar 31 '14 at 3:48
• Thanks for your message @WallyWest. Turns out !w was not a good idea to check w!=null and the script wasn't working anymore :p. Now I'll update it with the results – Antonio Ragagnin Mar 31 '14 at 6:29
• Try using: z="replace";r={};p=eval(("[{"+prompt()+"}]")[z](/\n/g,"},{")[z](/;/g,","));for(i in p){l=p[i];c=0;for(k in l)c?r[c]-=l[k]:(c=k,r[c]=0);for(j in p)w=p[j][c],null!=w&&(r[c]+=w)}alert(JSON.stringify(r)[z](/"|{|}/g,"")[z](/,/g,"\n")) for 229 bytes... What I've done here is reduced the if(!c) sequence to a single ternary operator, and I've also incorporated it in its parent for loop... I've also done something similar with the other for loop... comma operators can work wonderfully to join multiple statements within a loop... – WallyWest Mar 31 '14 at 11:56

JavaScript(ES6) 175,166, 161, 156, 153147

Golfed

R={};prompt().split(/\s/).map(l=>{a=l.split(/[;,:]/);c=b=a;a.map(v=>b=!+v?v:(R[b]=(R[b]||0)+ +v c==b?b:R[c]-=+v))});for(x in R)alert(x+':'+R[x])

Ungolfed

R = {};
prompt().split(/\s/).map(l => {
a = l.split(/[;,:]/);       // Split them all!!
// Now in a we have big array with Country/Value items
c = b = a;               // c - is first country, b - current country
a.map(v =>
b = !+v ? v                 // If v is country (not a number), simply update b to it's value
: (R[b] = (R[b] ||0) + +v   // Safely Add value to current country
c == b ? c : R[c] -= +v)  // If current country is not first one, remove debth
)
});
for (x in R) alert(x + ':' + R[x])

Output

US:9439.299999999997
FR:2598.8999999999996
ES:852.1
JP:4817.4
DE:2903.7
UK:1546.2000000000003
IT:887.5
PT:90.09999999999998
IE:48
GR:116.8
• Not sure that ungolfed variant will be working correctly because in golfed variant i'm using one-line operators – tt.Kilew Mar 31 '14 at 9:27
• can you please show your output? – WallyWest Mar 31 '14 at 12:04
• Replaced R[b] ? R[b] += +v : R[b] = +v to R[b]=R[b]||0+ +v – tt.Kilew Mar 31 '14 at 13:06
• Removed index i=0;i++%2==0?b=v to b=isNaN(+v)?v: – tt.Kilew Mar 31 '14 at 13:21
• isNaN(+v) -> !+v – tt.Kilew Mar 31 '14 at 13:28

Groovy 315

def f(i){t=[:];i.eachLine(){l=it.split(/;|,/);s=l.split(/:/);if(!z(s))t.put(s,0);t.put(s,x(z(s))+x(s));(1..<l.size()).each(){n=l[it].split(/:/);t.put(s,x(z(s))-x(n));if(!z(n))t.put(n,0);t.put(n,x(z(n))+x(n))}};t.each(){println it}};def x(j){j.toDouble()};def z(j){t.get(j)}

Output:
US=9439.299999999997
FR=2598.8999999999996
ES=852.1
JP=4817.4
DE=2903.7
UK=1546.2000000000003
IT=887.5
PT=90.09999999999998
IE=48.0
GR=116.8

Ungolfed:

input = """US:10800;FR:440.2,ES:170.5,JP:835.2,DE:414.5,UK:834.5
FR:1800;IT:37.6,JP:79.8,DE:123.5,UK:227,US:202.1
ES:700;PT:19.7,IT:22.3,JP:20,DE:131.7,UK:74.9,US:49.6,FR:112
PT:200;IT:2.9,DE:26.6,UK:18.9,US:3.9,FR:19.1,ES:65.7
IT:1200;JP:32.8,DE:120,UK:54.7,US:34.8,FR:309,ES:29.5
IE:200;JP:15.4,DE:82,UK:104.5,US:39.8,FR:23.8
GR:200;DE:15.9,UK:9.4,US:6.2,FR:41.4,PT:7.5,IT:2.8
JP:4100;DE:42.5,UK:101.8,US:244.8,FR:107.7
DE:2400;UK:141.1,US:174.4,FR:205.8,IT:202.7,JP:108.3
UK:1700;US:578.6,FR:209.9,ES:316.6,IE:113.5,JP:122.7,DE:379.3"""

ungolfed(input)

def ungolfed(i){
def tallyMap = [:]
i.eachLine(){
def lineList = it.split(/;|,/)
def target = lineList.split(/:/)

if(!tallyMap.get(target)){tallyMap.put(target,0)}
tallyMap.put(target,tallyMap.get(target).toDouble() + target.toDouble())
(1..lineList.size()-1).each(){ e ->
def nextTarget = lineList[e].split(/:/)
//subtract the debt
tallyMap.put(target, (tallyMap.get(target).toDouble() - nextTarget.toDouble()))
if(!tallyMap.get(nextTarget)){ tallyMap.put(nextTarget, 0) }
tallyMap.put(nextTarget, (tallyMap.get(nextTarget).toDouble() + nextTarget.toDouble()))
}
}
tallyMap.each(){
println it
}
}
• Do you happen to have a link to where I can find more info on Groovy? – WallyWest Mar 31 '14 at 3:46
• @WallyWest: I have this book, and learned tons from it. I feel that this is one of those languages that it is good to have a reference on the shelf. link, Also tons of info here: link – md_rasler Apr 1 '14 at 3:00

PHP, 333

$a='';while(($l=trim(fgets(STDIN)))!='')$a.=$l.'\n';$a=rtrim($a,'\n');$p=explode('\n',$a);foreach($p as$q){preg_match('/^([A-Z]+)/',$q,$b);preg_match_all('/'.$b.':(\d+(?:\.\d+)?)/',$a,$c);$e=ltrim(strstr($q,';'),';');preg_match_all('/([A-Z]+)\:(\d+(?:\.\d+)?)/',$e,$d);echo$b.':'.(array_sum($c)-array_sum($d)).PHP_EOL;}

Ungolfed version :

$a=''; while(($l=trim(fgets(STDIN)))!='')
$a .=$l.'\n';
$a = rtrim($a,'\n');
$p = explode('\n',$a);
foreach($p as$q){
preg_match('/^([A-Z]+)/',$q,$b);
preg_match_all('/'.$b.':(\d+(?:\.\d+)?)/',$a,$c);$e = ltrim(strstr($q,';'),';'); preg_match_all('/([A-Z]+)\:(\d+(?:\.\d+)?)/',$e, $d); echo$b.':'.(array_sum($c)-array_sum($d)).PHP_EOL;
}