BWInf 2011, question 5: Twin towns

Question

This is a challenge that was originally a tas for the German Bundeswettbewerb Informatik (federal competition of computer science [?]), a competition for highschool students. As opposed to the original question, where you have to find a good solution and write some documentation, I want you to golf this. I try to replicate the question as good as possible:

Challenge

Many towns in Europe have so-called twin towns. This year, there is a special Jubilee where each pair of twin-towns in the EU organizes a festival to celebrate their partnership. To ensure that no city has to organize too many festivals, each city has a limit of festivals it can organize. Is it possible to distribute the festivals among the twin-towns in a way, such that each pair of twin-towns organizes one festival in one the two towns and no town organizes more festivals than it is allowed to? If yes, explain how.

This is a map of some towns, their partnerships and their limits of festivals.

partnerships http://dl.dropbox.com/u/1869832/partnerships.png

Requirements

• Your program must terminate the problem in one minute each for both testcases. (See below)

• Refer to the testcases for the input format.

• The output should be empty iff no solution exists and should have the following format otherwise: One line for each pair of twin towns, a if city1 organizes the festival, b otherwise.

    <city1>, <city2>, <a/b>
  

• The solution with the least number of characters that satisfies the requirements wins. In case of a tie, the program that was submitted first wins.

• Usual code-golf rules apply.

Testcases

The original task had two testcases. I have uploaded them on github.

Answer 1

Python, 380 chars

import sys
N={};H={};X={}
for L in open(sys.argv[1]):n,x,y=L.split('"');N[x]=int(n);H[x]=0;X[x]=[]
for L in open(sys.argv[2]):s,t=eval(L);X[s]+=[t]
p=1
while p:
 p=0
 for x in N:
  if len(X[x])>N[x]:
   p=1;S=[y for y in X[x]if H[y]<H[x]]
   if S:X[x].remove(S[0]);X[S[0]]+=[x]
   else:H[x]+=1
   if H[x]>2*len(N):sys.exit(0)
for x in N:
 for y in X[x]:print'"%s", "%s", a'%(x,y)

This code uses a push-relabel-style maximum flow algorithm. N[x] is the number of parties allowed at x, X[x] is the list of partner cities currently scheduled to host at x (which may be longer than N[x] during the algorithm), and H[x] is the labelled height of x. For any oversubscribed city, we either push one of its scheduled parties to a lower partner city, or raise its height.

Answer 2

C#, 1016 992 916 chars

Takes 4 seconds for me on the large test set; performance can easily be improved a lot by making X a HashSet<s> rather than a List<s>.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D<T>:Dictionary<s,T>{}class E:D<int>{static void Main(s[]x){s
S="",T=">",l;s[]b;D<E>R=new D<E>(),P=new D<E>();R[S]=new E();R[T]=new E();foreach(s L in
File.ReadAllLines(x[0])){b=L.Split('"');s f=b[1];R[T][f]=0;R[f]=new E();P[f]=new
E();R[f][T]=int.Parse(b[0].Trim());}foreach(s L in File.ReadAllLines(x[1])){b=L.Split('"');s
f=b[1],t=b[3],v=f+t;R[v]=new
E();R[v][S]=R[f][v]=R[t][v]=0;P[f][t]=R[S][v]=R[v][f]=R[v][t]=1;}for(;;){List<s>X=new
s[]{S}.ToList(),A=X.ToList();w:while((l=A.Last())!=T){foreach(s t in
R[l].Keys){if(!X.Contains(t)&R[l][t]>0){X.Add(t);A.Add(t);goto
w;}}A.RemoveAt(A.Count-1);if(!A.Any())goto q;}l=S;foreach(s n in
A.Skip(1)){R[l][n]--;R[n][l]++;l=n;}}q:if(R[S].Values.Contains(1))return;foreach(s
f in P.Keys)foreach(s t in P[f].Keys)Console.WriteLine(f+", "+t+", "+"ba"[R[f][f+t]]);}}

This uses the reduction to max flow which I hinted at earlier in comments. The vertices are

1. A newly generated source S and sink T.
2. The partnerships.
3. The cities.

The edges are

1. From the source to each partnership with flow capacity 1.
2. From each partnership to each city in the partnership with flow capacity 1.
3. From each city to the sink with flow capacity equal to that city's budget.

The algorithm is Ford-Fulkerson with DFS. It is obvious a priori that each augmenting path will increase the flow by 1, so the golfing optimisation of removing the computation of the path's flow has no negative effect on performance.

There are other possible optimisations by making assumptions such as "The names of the input files will never be the same as the names of the cities", but that's a bit iffy IMO.