RegExp Master

Sphere Online Judge (SPOJ) is an ongoing automated online programming contest site. They are presently running Open Contest 2008, which Dion and I have done some problems in. In order to compare our results, and so that we overdo one problem set rather than actually trying many, I have written a python script to allow us to compare our scores on the RegExp Master problem.

The answer set consists of 10 regular expressions, one per line, or — if no answer is provided for that task. The script assumes that answers are correct, and calculates the score of 1 + 1/length of pattern. — lines score 0 points, as expected.

#!/usr/bin/env python
 
import sys
 
def analyze(fname):
    lines = open(fname, "r").readlines()
    i = 1
    total = 0
    for l in lines:
        l = l.rstrip()
 
        if l == "---":
            score = 0
        else:
            score = 1.0 + 1.0/len(l)
 
        print "%d:\t%d\t%f" % (i, len(l), score)
        i += 1
        total += score
    print "Total score:\t%f" % (total)
 
if __name__ == "__main__":
    analyze(sys.argv[1])

My (updated) results:

1:      29      1.034483
2:      104     1.009615
3:      36      1.027778
4:      54      1.018519
5:      17      1.058824
6:      187     1.005348
7:      3       0.000000
8:      95      1.010526
9:      3       0.000000
10:     15      1.066667
Total score:    8.231759

Update: Added more columns to score output, increased my score.

Tags: , ,

7 Responses to “RegExp Master”

  1. Dion Says:

    I have yet to optimize any (heavily) but #8, which I just did.

    1:      1.034483
    2:      1.009174
    3:      1.027778
    4:      1.018519
    5:      1.058824
    6:      1.004673
    7:      0.000000
    8:      1.011765
    9:      0.000000
    10:     1.066667
  2. Jonathan Says:

    8: 1.010526

    Still not as good as yours.

  3. Jonathan Says:

    Woot.

    8:      83      1.012048
    
  4. Dion Says:
    My latest:
    1:      1.034483
    2:      1.009615
    3:      1.027778
    4:      1.018519
    5:      1.058824
    6:      1.005000
    7:      1.025641
    8:      1.012346
    9:      1.000165
    10:     1.066667
    Total: 10.259036
  5. Jonathan Says:
    1:      29      1.034483
    2:      104     1.009615
    3:      36      1.027778
    4:      54      1.018519
    5:      17      1.058824
    6:      187     1.005348
    7:      41      1.024390
    8:      83      1.012048
    9:      3       0.000000
    10:     15      1.066667
    Total score:    9.257671
  6. Jonathan Says:
    1:      29      1.034483
    2:      104     1.009615
    3:      36      1.027778
    4:      54      1.018519
    5:      17      1.058824
    6:      187     1.005348
    7:      41      1.024390
    8:      79      1.012658
    9:      3       0.000000
    10:     15      1.066667
    Total score:    9.258281

    Ha. Beating you on 6 and 8. Guess I need to make a generator for 9 now.

  7. Dion Says:
    1:      29      1.034483
    2:      104     1.009615
    3:      36      1.027778
    4:      54      1.018519
    5:      17      1.058824
    6:      200     1.005000
    7:      39      1.025641
    8:      73      1.013699
    9:      6057    1.000165
    10:     15      1.066667
    Total score:    10.260389