Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Dueling Flamingos: The Story of the Fonality Christmas Golf Challenge

by ambrus (Abbot)
on May 10, 2009 at 10:22 UTC ( #763124=note: print w/ replies, xml ) Need Help??


in reply to Dueling Flamingos: The Story of the Fonality Christmas Golf Challenge

By the way, given that Fonality's original site about the golf rules, solutions, and post-mortem solutions is down, is there a mirror of all this somewhere?

Update: maybe I should ask this in a top-level question.

Update 2011-05-13: I include here a copy of the challenge statement, retrieved from http://replay.web.archive.org/20080917043403/http://app.fonality.com/golf/.

The Challenge:

In a nutshell, this is a Roman Numeral Calculator.

The program will take a single line of input containing upper-case Roman Numerals with the words " plus " or " minus " between them. The challenge is to create a Perl program in as few characters as possible to perform the calculation and print out the answer in Roman Numerals back to the screen.

The program is a filter: it must read from STDIN, and send output to STDOUT.

  • Input will consist of a single line, which will match /\A[IVXLCDM]+( (plus|minus) [IVXLCDM]+){1,3}\n\z/. This means that the input will consist of three to seven words separated by single spaces.
  • The input will be between two and four upper-case Roman Numerals between I and MMMCMXCIX (1 to 3999) joined by plus or minus, all separated by a single space. Your program need not test the input for validity, and its behavior on invalid input is not important.
  • The output should be a single line, matching /\A[IVXLCDM]+\n\z/, and be the Roman Numeral representation of the calculation. The output will be between I (1) and MMMCMXCIX (3999).
  • Roman Numerals will always be in upper-case and in short-hand form. For example, you will always receive an input of "IV" rather than "IIII". You must also always output "IV" rather than "IIII".
  • At no time during the various math operations will a number be less than I (1) or greater than MMMCMXCIX (3999). That means you will never have a calculation such as "I minus V plus X". Even though the output is >= I (1) and <= MMMCMXCIX (3999), during the process (I minus V) becomes < I (1) which is not allowed.
  • You may not use any Perl modules.
  • Anyone, anywhere is able to play and win!
  • More information on Roman Numerals can be found at Wolfram MathWorld.

All additional rules that apply to this challenge can be found here.

Roman Numerals
I = 1C = 100
V = 5D = 500
X = 10M = 1000
L = 50

A test program to test output of your program is provided here.

Tiebreaker:

The tiebreaker will favor programs with fewer alphanumeric, whitespace and underscore characters.

Examples:

$ perl romancalc.pl
in:I plus I
out:II
$ perl romancalc.pl
in:MDCCCXXIV plus DCCVI
out:MMDXXX
$ perl romancalc.pl
in:MCCXIII minus LXIV plus MMDXXX
out:MMMDCLXXIX
$ perl romancalc.pl
in:MMXIX plus MCCCXCVI minus DCXCV plus CI
out:MMDCCCXXI

Here is a copy of the extra rules, retrieved from http://replay.web.archive.org/20080927143500/http://app.fonality.com/golf/rules.htm.

Fonality Perl Golf Rules

based off of the Generic perl golf rules (Version 1.01)

  1. Rules are subject to change at any time.
  2. The contest is open to everyone, everywhere.
  3. Entrants have to supply a valid, up-to-date email address, location, and phone number to qualify for a prize.
  4. Entrants agree to accept a phone call from Fonality's Recruiter after the contest ends.
  5. A player may only claim one prize.
  6. The program must be written as one or more lines. The score for each hole is the total number of bytes you need (smaller is better). If your program is more than one line, you must count the newlines in between as one byte each. The #! line is not counted. If you use options on the #! line, the options themselves are counted, including the leading whitespace, the - and any trailing whitespace (but not the newline). Get the count program if you have any doubts.
  7. The program is expected to finish in a reasonable time. This means that even for your program's worst case input (whether that case is in the testset or not). For any valid input, the program should run in five minutes or less of CPU time on a 600 MHz Celeron. The program also has to be valid only during the period that the challenge runs.
  8. The program return code does not matter.
  9. You must not write to STDERR.
  10. The program is assumed to run on a perfect computer that never makes mistakes, and when the program finishes, the result should always be correct.
  11. You can submit as often as you want to until the deadline, no reason to wait until the last minute. In fact, other people want to see the score to beat on the leaderboard. So don't be a spoilsport by hoarding your score. Submit early and often.
  12. The program may only use the perl executable, no other executables on the system are allowed (in particular, you must not use the programs implementing any other holes. The program may use itself though). Your solution must be portable in the sense that it should work on all official unpatched versions of perl 5.8.5 everywhere. It's perfectly fine to abuse perl 5.8.5 bugs.
  13. Some golfs are played with the rule that you are not allowed to use any modules, even the standard core ones. However, there are some perl statements like the unicode regex /\pM/ that implicitly load a number of modules. You are still allowed to use code like that, but in a "no modules" contest you are not allowed to use the extra symbols that became available this way (like Carp::croak). Notice that perl also has builtin functions like utf8::downgrade that are available even if you don't load the utf8 module. These are always valid to use.
  14. The program should be self-contained (except for any I/O mentioned in the challenge). In particular, you may not do things like fetching extra data from a remote site.
  15. You may assume ASCII as character set and you may use perl's unicode semantics.
  16. Any bytes may be used in the sourcecode, including things like binary 0.
  17. At least 55% of the sourcecode must consist of normal ASCII characters matching /[ -~\t\n]/.
  18. All input and output will have a total size that will comfortably fit in memory (without swapping) and still allow you ample memory to play with.
  19. Your program should not introduce arbitrary limits not specifically mentioned in the challenge. In particular, your program should not need changes depending on the amount of free memory it runs with. E.g. doing @a = (1) x (10**8) (trying to create an array bigger than every valid inputsize) is wrong. It will fail miserably unless the machines has about 2 Gigabytes of free memory. You may however always assume enough base memory to make datastructures of a few million entries (or strings of a few million characters), so something like @a = (1) x (10**6) is just fine. Using the rule that the input fits in memory you can also see that @a = (1) x $input_size is OK (if the input is 10**8 bytes, that rule ensures that in that case you in fact have</c> these Gigabytes of free memory).

    This rule is intentionally not formulated in terms of real memory, since that is too variable. But as a (non official) rule of the thumb: if your program uses more than a few tens of megabytes of memory, start thinking whether you can justify that.

  20. Since your program should work on all official versions of perl 5.8.5, it should work on both the 32-bit and 64-bit versions. This has a number of implications. Among them:
    • Using 2**32 bytes of memory is an absolute maximum. This does however not imply the amount of memory you may assume available is even close to this number. It could be a lot less. See the previous rule for guarantees on the minimum amount of memory you can safely use.
    • Input and output sizes will be < 2**32 bytes.
    • Sizes of structures will fit in plain 32-bit integers.

    Still, for most things the difference between 32-bit and 64-bit won't matter. You don't directly have to try to install both.

  21. The program will be called as
    some_perl_5.8.5_binary -- programname {args}

    The file programname will be non-executable, but readable and writable (in fact, on unix it will have permissions 644). You do not get to choose the programname, but it will match /^[a-zA-Z][\w.-]*\z/ and will be the initial value of $0. You also don't get to choose the name of the perl binary.

  22. If you have no options, you may leave out the #! line. If there is one, it will start with #!, and you may decide to follow that with an optional space or tab and a /. For the rest you only know that the part before any options will match m#^[\w/.-]+\z#, but you do not get to choose the exact path.
  23. STDIN, STDOUT and STDERR may or may not be files.
  24. If a read on a perl handle gives EOF (End Of File), you may assume later reads on the same handle will again EOF.
  25. The sort operator is stable in perl 5.8.5 (which means that elements that compare as equal among each other will appear in the output in the same order as in the input).
  26. Several things are not so much determined by perl itself, but by the environment in which it runs. But in real perls some things still tend to be true. Here are a number of assumptions you may make until someone finds a real perl (not specifically built to break them) that breaks them. Some of them may be even further restricted.
    • There will be a crypt operator that behaves like old-style unix crypt if the salt matches /^[.\/0-9A-Za-z]{2}/ and the password matches /^[ -~]{0,7}\z/ or /^[ -~]{8}/.
    • 10**9 < $^T < 10**10 when the program starts.
    • You can use perl to get addresses of objects with constructs like this:
      perl -wle 'print []+0'

      You may assume that such an address will be > 100000 (At least one machine is known where the number is 156000) You may assume the address is a multiple of 4.

    • The output of rand() is assumed to be uniformly distributed and completely independent of previous calls to rand() (even if you know the underlying implementation and know it can't be). You may not assume it will never return the exact same value twice. The exact sequence you get after srand with a given value is not portable.
    • Shifts are done modulo some wordsize, so: 1 << 64 == 1 and 1 >> 64 == 1 (you don't know what 1 << 32 is since you don't know if your program will get tested on a 32-bit or a 64-bit perl). At least one system (powerpc mac) is known where the result is basically 2**($n % 64) & (2**32-1). <il>The result of $? after an empty `` is unportable (0 on windows with activestate perl, 256 on linux). All known perls set $! to dualvar(0,"").
    • -0.0 and -undef (and therefore also things like -$a on an undefined variable $a) are unportable. These will normally result in IEEE value -0.0 (negative zero). This value is false for perl and numerically equal to 0. But it stringifies to "0" (false for perl) on some systems and to "-0" (true for perl) on others. -0 and -"" are 0 everywhere.

The submissions (including post mortem ones) can be downloaded from http://replay.web.archive.org/20080927143456/http://app.fonality.com/golf/post_mortem.cgi?id=1. I don't include a copy of that here.


Comment on Re: Dueling Flamingos: The Story of the Fonality Christmas Golf Challenge
Select or Download Code
Re^2: Dueling Flamingos: The Story of the Fonality Christmas Golf Challenge
by eyepopslikeamosquito (Canon) on Jun 11, 2009 at 10:49 UTC

    I happen to have an old text file copy of the post mortem lying around on my local hard disk. Better upload it here for safe keeping before I have a hard disk crash. :) Actually, the whole post mortem is too big for a Perl Monks node, so I've just uploaded all of the post mortem up to 200 strokes.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://763124]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (6)
As of 2014-12-22 04:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (110 votes), past polls