Sample Inputs

The judges have published some of the inputs they are using to test the programs at http://cristal.inria.fr/ICFP2001/prog-contest/inputs/. I ran my program on them to see how it would do.

The first thing I noticed was that their example 002-almost-empty.txt exposes a bug in my program. The output is still correct, but it is not optimal. The problem: if the input contains only tags, and no regular characters, the program runs 0 passes of its algorithm, producing no optimized versions of the input, and it prints out the input string (when it should print the empty string).

Times given below are on a 700 MHz Windows machine. (I had to tweak the program to use files instead of stdin/stdout to avoid problems with end-of-line characters under Windows.) "Work size" means the number of groups of characters sharing common (or compatible) contexts.

Results

000-example.txt
  Work size: 321
  original       13942 bytes
  3 minutes      13058 bytes    62 passes       2:54
  final          13058 bytes   321 passes      29:58

001-null.txt
  Work size: 0
  original           0 bytes
  final              0 bytes     0 passes       0:00

002-almost-empty.txt
  Work size: 0
  original           9 bytes
  final              9 bytes     0 passes       0:00

003-third-step.txt
  Work size: 355
  original        5548 bytes
  3 minutes       4368 bytes     4 passes       2:54
  10 minutes      4078 bytes    94 passes       9:54
  30 minutes      4073 bytes   236 passes      29:54
  final           4068 bytes   355 passes      37:10

004-random.txt
  Work size: 1211
  original       13020 bytes
  3 minutes      13020 bytes     2 passes       2:54   (22403 bytes)
  10 minutes     13020 bytes     2 passes       9:54   (22403 bytes)
  30 minutes     13020 bytes     2 passes      29:54   (22403 bytes)
  1 hour         13020 bytes     3 passes      59:54   (18452 bytes)
  6 hours        13020 bytes     6 passes    5:59:54   (14188 bytes)
  12 hours       13020 bytes     8 passes   11:59:53   (13196 bytes)
  final              ? bytes     ? passes      ??:??

005-icfp2000.txt
  Work size: 2673
  original       64936 bytes
  3 minutes      57449 bytes    17 passes       2:54
  10 minutes     57331 bytes    36 passes       9:54
  30 minutes     57281 bytes    65 passes      29:54
  1 hour         57269 bytes    93 passes      59:54
  12 hours       57219 bytes   338 passes   11:59:54
  final              ? bytes     ? passes      ??:??

006-exhaustive.txt
  Work size: 24330
  original     1269376 bytes
  3 minutes     899928 bytes     1 pass         2:54
  10 minutes    556954 bytes     2 passes       9:49
  30 minutes    556954 bytes     2 passes      29:49
  1 hour        556954 bytes     2 passes      59:48
  final              ? bytes     ? passes      ??:??

100-hand.txt
  Work size: 294
  original        4392 bytes
  3 minutes       3678 bytes     4 passes       2:54
  10 minutes      3388 bytes   105 passes       9:54
  final           3383 bytes   294 passes      23:56

101-validate-big.txt
  Work size: 6404
  original      134881 bytes
  3 minutes      99911 bytes     2 passes       2:54
  10 minutes     99911 bytes     2 passes       9:54
  30 minutes     99911 bytes     2 passes      29:54
  1 hour         91414 bytes     3 passes      59:54
  12 hours       82219 bytes     9 passes   11:59:54
  final              ? bytes     ? passes      ??:??

102-validate-small.txt
  Work size: 6404
  original       97483 bytes
  3 minutes      97483 bytes     2 passes       2:54   (99911 bytes)
  10 minutes     97483 bytes     2 passes       9:54   (99911 bytes)
  30 minutes     97483 bytes     2 passes      29:54   (99911 bytes)
  1 hour         91414 bytes     3 passes      59:54
  12 hours       82219 bytes     9 passes   11:59:54
  final              ? bytes     ? passes      ??:??

103-the-random-returns.txt
  Work size: 656
  original       11385 bytes
  3 minutes      11385 bytes     2 passes       2:54   (11542 bytes)
  10 minutes     11385 bytes     2 passes       9:54   (11542 bytes)
  30 minutes      9492 bytes     3 passes      29:54
  1 hour          9492 bytes     3 passes      59:54
  12 hours        6384 bytes    10 passes   11:59:54
  final              ? bytes     ? passes      ??:??

Jeremy Sawicki (jeremys AT mit DOT edu)