Who brings the croissants?

Question

This question is inspired by a similar question first asked on StackOverflow by Florian Margaine, then asked in variant forms on CS by Gilles and on Programmers by GlenH7.

This time, it's a code golf, with specific metrics for success!

In an office of ten people, it's someone's turn to buy croissants every morning. The goal is to produce a schedule that lists whose turn it is on any given day, subject to the following constraints:

1. Presence. Each person is away from the office on business or vacation on average ~20% of the time. Each time you schedule a person who is away, lose one point per person who didn't get to eat croissants. For simplicity, generate the away-schedule with the random number generator seed = (seed*3877 + 29573) % 139968, starting with 42*(10*i + 1) as the initial (unused) seed, where i is the zero-indexed number of the employee; whenever seed is below 27994, that person will be away. Note that if everyone is away, you can assign anyone and not lose points.
2. Fairness. Each person will keep track of whether they have bought more or fewer croissants than the average. A person who never buys more than 10 more than the average will give you one point (they understand that someone has to buy first, and they'll of course go above the average). Otherwise, let k be the farthest above the average that a person has gotten in n days of buying; that person will give you 1 - (k-10)/100 points. (Yes, this may be negative.)
3. Randomness. The employees get bored if they can predict the sequence. Gain ten times the number of bits of information revealed a typical choice; assume that the employees can search for repetitive patterns and know the order of how long it's been since each of them bought croissants.
4. Non-repetitiveness. Employees hate buying croissants two days in a row. Each time this happens, lose a point.
5. Brevity. if b is the number of bytes of the gzipped* version of your solution, reduce your score by b/50.

The solution should be an output of letters or numbers (0-9 or A-J) indicating who should buy croissants on each day. Run the algorithm for five hundred days (two years of work); give yourself a point if the output is in 10 rows of 50.

You only need to produce the sequence, not calculate the score. Here is a reference program in Matlab (or Octave) that picks people completely at random except for avoiding people who are away:

function b = away(i)
b=zeros(500,1); seed=42*(10*i+1);
for j=1:500
  seed=mod((seed*3877+29573),139968);
  b(j)=seed<27994;
end
end

A=zeros(500,10);
for i=1:10
  A(:,i)=away(i-1);
end
for i=1:10
  who = zeros(1,50);
  for j=1:50
    k = 50*(i-1)+j;
    who(j)=floor(rand(1,1)*10);
    if (sum(A(k,:)) < 10)
      while (A(k,who(j)+1)==1)
        who(j)=floor(rand(1,1)*10);
      end
    end
  end
  fprintf(1,'%s\n',char(who+'A'));
end

Here is a sample run:

HHEADIBJHCBFBGBIDHFFFHHGGHBEGCDGCIDIAEHEHAJBDFIHFI
JFADGHCGIFHBDFHHJCFDDAEDACJJEDCGCBHGCHGADCHBFICAGA
AJAFBFACJHHBCHDDEBEEDDGJHCCAFDCHBBCGACACFBEJHBEJCI
JJJJJBCCAHBIBDJFFFHCCABIEAGIIDADBEGIEBIIJCHAEFDHEG
HBFDABDEFEBCICFGAGEDBDAIDDJJBAJFFHCGFBGEAICEEEBHAB
AEHAAEEAJDDJHAHGBEGFHJDBEGFJJFBDJGIAJCDCBACHJIJCDF
DIJBHJDADJCFFBGBCCEBEJJBAHFEDABIHHHBDGDBDGDDBDIJEG
GABJCEFIFGJHGAFEBHCADHDHJCBHIFFHHFCBAHCGGCBEJDHFAG
IIGHGCAGDJIGGJFIJGFBAHFCBHCHAJGAJHADEABAABHFEADHJC
CFCEHEDDJCHIHGBDAFEBEJHBIJDEGGDGJFHFGFJAIJHIJHGEBC

which gives a total score of -15.7:

presence:    0    (Nobody scheduled while away)
fairness:    6.6  (~340 croissants bought "unfairly")
randomness: 33.2  (maximum score--uniformly random)
no-repeat: -51.0  (people had to bring twice 51 times)
size:       -5.5  (275 bytes gzipped)
format:      1    (50 wide output)

Here is the reference Scala method I'm using to compute the score

def score(output: String, sz: Either[Int,String], days: Int = 500) = {
  val time = (0 until days)
  def away(i: Int) =
    Iterator.iterate(42*(10*i+1))(x => (x*3877+29573)%139968).map(_<27994)
  val everyone = (0 to 9).toSet
  val aways =
    (0 to 9).map(i => away(i).drop(1).take(days).toArray)
  val here = time.map(j => everyone.filter(i => !aways(i)(j)))
  val who = output.collect{
    case x if x>='0' && x<='9' => x-'0'
    case x if x>='A' && x<='J' => x-'A'
  }.padTo(days,0).to[Vector]
  val bought =
    time.map(j => if (here(j) contains who(j)) here(j).size else 0)
  val last = Iterator.iterate((0 to 10).map(_ -> -1).toMap){ m =>
    val j = 1 + m.map(_._2).max
    if (bought(j)==0) m + (10 -> j) else m + (who(j) -> j)
  }.take(days).toArray

  def log2(d: Double) = math.log(d)/math.log(2)
  def delayEntropy(j0: Int) = {
    val n = (j0 until days).count(j => who(j)==who(j-j0))
    val p = n.toDouble/(days-j0)
    val q = (1-p)/9
    -p*log2(p) - 9*q*log2(q)
  }
  def oldestEntropy = {
    val ages = last.map{ m =>
      val order =  m.filter(_._1<10).toList.sortBy(- _._2)
      order.zipWithIndex.map{ case ((w,_),i) => w -> i }.toMap
    }
    val k = last.indexWhere(_.forall{ case (k,v) => k == 10 || v >= 0 })
    (k until days).map{ j => ages(j)(who(j)) }.
      groupBy(identity).values.map(_.length / (days-k).toDouble).
      map(p => - p * log2(p)).sum
  }

  def presence =
    time.map(j => if (here(j) contains who(j)) 0 else -here(j).size).sum
  def fairness = {
    val ibought = (0 to 9).map{ i =>
      time.map(j => if (i==who(j)) bought(j) else 0).
        scan(0)(_ + _).drop(1)
    }
    val avg = bought.scan(0)(_ + _).drop(1).map(_*0.1)
    val relative = ibought.map(x => (x,avg).zipped.map(_ - _))
    val worst = relative.map(x => math.max(0, x.max-10))
    worst.map(k => 1- k*0.01).sum
  }
  def randomness =
    ((1 to 20).map(delayEntropy) :+ oldestEntropy).min*10
  def norepeat = {
    val actual = (who zip bought).collect{ case (w,b) if b > 0 => w }
    (actual, actual.tail).zipped.map{ (a,b) => if (a==b) -1.0 else 0 }.sum
  }
  def brevity = -(1/50.0)*sz.fold(n => n, { code =>
    val b = code.getBytes
    val ba = new java.io.ByteArrayOutputStream
    val gz = new java.util.zip.GZIPOutputStream(ba)
    gz.write(b, 0, b.length); gz.close
    ba.toByteArray.length + 9 // Very close approximation to gzip size
  })
  def columns =
    if (output.split("\\s+").filter(_.length==50).length == 10) 1.0 else 0

  val s = Seq(presence, fairness, randomness, norepeat, brevity, columns)
  (s.sum, s)
}

(there is a usage note^).

The winner is the one with the highest score! Actually, there will be two winners: a globally optimizing winner and a short-notice winner for algorithms where earlier selections do not depend vacations that will happen in the future. (Real office situations are in between these two.) One entry may of course win both (i.e. it is short-notice but still outperforms other entries). I'll mark the short-notice winner as the "correct" winner, but will list the globally optimizing winner first on the scoreboard.

Scoreboard:

Who            What                   Score   Short-notice?
============== ====================== ======= ===
primo          python-miniRNG          37.640  Y
Peter          Golfscript-precomputed  36.656  N
Rex            Scala-lottery           36.002  Y
Rex            Matlab-reference       -15.7    Y

*^{I'm using gzip 1.3.12 with no options; if there are multiple files, I cat them together first.}

**^{A list prepared in advance is not considered short-notice unless it would be swapped out for a better list if an away-day appeared the day before; if this is a major issue (e.g. an unanticipated away day causes reversion to an algorithm that performs horribly) I'll define precise criteria.}

^ ^{If you use gzip, pass in the size as Left(287); otherwise if your code is in code (val code="""<paste>""" is useful here), use Right(code))}

Answer 1

Python (37.640 points)

i=61
r=[420*n+42for n in range(10)]
for n in r:
 o=''
 for n in r*5:
    r=[(n*3877+29573)%139968for n in r]
    f=[n<27994for n in r]
    l=i
    while~-all(f)*f[i%10]or(i-l)%10<1:i=i**3%1699
    o+=str(i%10)
 print o

The second level of indentation is with literal tab characters.

Score breakdown:

presence:    0.0
fairness:    8.618
randomness:  31.502
no-repeat:   0.0
size:       -3.48
format:      1.0

The PRNG i'm using is a simplified version of Keith Randall's solution to the Diehard challenge, which despite its extreme brevity, passes all 15 tests. The solution is short notice: the absentee list is calculated on the day of, and all previous attendance is forgotten. The only thing which is recorded is who bought on the previous day, so that repetition may be avoided.

I suspect that the fairness score could be improved by keeping a queue of individuals who should have bought, but didn't, and adding them into the rotation as soon as possible. I'm not sure if this would lead to an overall improvement, though, due to a lower score for size.

About the randomness upper-bound, it is certainly higher than 32. Replacing line 7 with i=i**3%1699 (removing the attendance and repetition constraints) results in a randomness score of 32.966.

Update:
Most of the improvement comes from better zip compression, by renaming variables, and reusing constructs such as for n in r numerous times.

Answer 2

GolfScript (36.656 points)

presence:    0
fairness:    9.498
randomness: 31.778
no-repeat:   0
size:       -5.62*
format:      1

* The Lempel-Ziv step is actually bad for this program: it would only be 5.46 (including the 9-character "penalty" from the Scala code) if strategy HUFFMAN_ONLY where used. (By my Huffman tree calculations, it should be 1839 bits, which suggests that there are 34 bytes of overhead - more than I remember from the last time I read the gzip file format spec, but my memory could be off).

'45274749890953461384092895296161282397696128454780712395638361237579450740141057012045098236468567830463395138297694808909654367173131250582012342078481734627820869476489062315253101230346792585956785940285674601914907495382306749019845658361271737890123953439852610678507814707530469358317402346278901984267190129362162512915678681507567831843423709082970928201432569730525454784512915686709218065814323413439817345681607567947860143456038712392671909236989193072045789650183645701325105856402426275'50/n*

Answer 3

Scala (36.002 points)

Code (run in REPL):

val (p,d,s)=(0 to 9,0 to 499,Array.fill(10)(0d))
val h=p.map{i=>var s=42*(i*10+1);d.map{_=>s=(s*3877+29573)%139968;s>27993}}
val n=d.map{j=>h.count(_(j))}
var q=0
d.map{j=>val t=s.map(_+util.Random.nextGaussian);t(q)+=9;p.map{i=>if(h(i)(j))t(i)-=9};val k=t.indexWhere(_==t.min);q=k;s(k)+=0.3;k}.mkString.grouped(50).foreach(println)

Example output (for which score was calculated):

71756902145841391934765437292035652843760984098583
86397265015640974915628232730106147281529836713094
08565240287124932136398520876027407943071218763914
50987680167146425903575318020863656749795382985435
07941018246493815719641937560694585402820150738727
13126926431856275181072676938295301345412807480484
81839634956059251426350709373902682797204746548906
16175895303731651486209495295428383160620710851569
74013482373647246513814672019837413985207414790529
39206976935168020524260381937139452108673574826406

Score breakdown:

presence:    0
fairness:    9.094
randomness: 31.448
no-repeat:   0
size:       -5.54
format:      1

Short-notice: yes, here-list h is used on the day of selection only.