• The Monthly Course: Factorials and Binary Trees
  • Hole 1: Factorial
  • Hole 2: Postorder
• Tiebreaker
• General rules
• Deadline
• Test program
• Submitting
• Leaderboard
• Feedback
• Referees

The Monthly Course: Ciphers and Letters

This month we play a two hole course again, one about numbers and one about strings.

Hole 1: Factorial

As n grows large, n factorial (n!) begins to accumulate a string of trailing zeroes. Your job is to determine the last non-zero digit of n! for n in the range 0..9999.

Examples

0! is 1 by definition, and the last non-zero digit is 1.

1! = 1 * 0! = 1 *   1 =   1, last non-zero digit is 1
2! = 2 * 1! = 2 *   1 =   2, last non-zero digit is 2
3! = 3 * 2! = 3 *   2 =   6, last non-zero digit is 6
4! = 4 * 3! = 4 *   6 =  24, last non-zero digit is 4
5! = 5 * 4! = 5 *  24 = 120, last non-zero digit is 2
6! = 6 * 5! = 6 * 120 = 720, last non-zero digit is 2

The number n will be given as the only commandline argument, and it will match either /^[1-9]\d{0,3}\z/ or /^0\z/. On STDOUT you must print the last non-zero digit of n! followed by a newline. Nothing should appear on STDERR. The program's return code will be ignored. For once you may not use any modules.

Hole 2: Trees by postorder

When traversing a binary tree depth-first from left to right, and writing down the nodes, there are three major ways to do this:

1. Preorder: Write down the topnode, then write down the left subtree in preorder, followed by the right subtree in preorder.
2. Inorder: Write down the left subtree in inorder, write down the top node, write down the right subtree in inorder.
3. Postorder: Write down the left subtree in postorder, then the right subtree in postorder, finally followed by the top node.

Example

                 B             preorder:  BCQSTAZDE
                / \            inorder:   SQTCBZAED
               /   \           postorder: STQCZEDAB
              C     A
             /     / \
            /     /   \
           Q     Z     D
          / \         /
         /   \       /
        S     T     E

When given such a string, it's generally not possible to reconstruct the original binary tree. However, if you are given preorder and inorder or inorder and postorder, the tree can be reconstructed (assuming all nodes had a different name).

The program will receive two strings as command line arguments: the preorder and inorder traversals of a binary tree. Given this input, the program must print the postorder traversal of the binary tree followed by a newline to STDOUT. You may assume the command line arguments to be in any order, either the preorder string first or the inorder string first. However, the interpretation must be consistent. If you assume one order for one input pair, you must asume that order for all pairs. Nothing should appear on STDERR. The program's return code will be ignored.

It is possible to specify a preorder and inorder string such that no binary tree can satisfy both traversals. You do not need to worry about this possibility; the command line arguments are guaranteed to represent a valid binary tree (binary here means that each node has at most 2 subtrees and never has two left subtrees or two right subtrees).

The nodes of the tree will be named using different uppercase letters (so the tree will have at most 26 nodes). The strings won't be empty (so you don't have to handle the empty tree). As you can see, the commandline arguments will match /^[A-Z]{1,26}\z/.

Tiebreaker

The tiebreaker favors characters with high ASCII values below 127. The tiebreaker is basically determined by:

General rules

• 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 inbetween as one byte each. The #! line is not counted. If you use options on the #! line, the options themselves are counted, including the leading space and -.
• 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). You may use any of the perl 5.6.1 standard core modules on the Postorder hole, but you may not use any modules on the Factorial hole. Your solution must be portable in the sense that it should work on all official versions of perl 5.6.1 everywhere. It's perfectly fine to abuse perl 5.6.1 bugs. For perl golf the executable (not the documentation) defines the language.
• 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.
• If two (or more) golfers have the same score for the hole, the golfer with the lowest tie break score wins.
• You may assume ASCII as character set and you may use perl's unicode semantics.
• Any bytes may be used in the sourcecode, including things like binary 0.
• All input will have a total size that will comfortably fit in memory (without swapping) and still allow you ample memory to play with.
• You may assume total memory is < 2**32 bytes (with the previous rule this e.g. implies sizes of arbitrary datastructures can be represented in a plain integer, and that you must not try to generate arbitrarily big datastructures).
• 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 GigaByte of free memory. You may however always assume enough base memory to make datastructures of a few million entries, 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 these GigaBytes of free memory).
• The program will be called as

  some_perl_5.6.1_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.
• The program file shall start with #!perl.
• The program is expected to finish in a reasonable time, e.g. if it gets started when the challenge opens, it's expected to be finished by the time the challenge closes even on a somewhat slow computer. The program has to be valid during the period that the challenge runs.
• 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.
• If you play as a team, you must enter in the team section, not as an individual player. You may play in one team only and not at the same time play as an individual. Teams may be extended during play, but not with people already playing.

Deadline

The game starts August 1st (05:00 UTC) and ends August 8th (05:00 UTC).

Test program

A test program (version 4) is provided to help screen entries.

Any program that passes the test program can be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help us identify bugs in the test program.

Name your scripts factorial.pl and postorder.pl respectively, and place them in the same directory as your test program. Then verify and score your attempt using:

    $ perl tpr04c.pl

    $ perl tpr04c.pl --help

Passing the test program does not assure your solution is valid. The referees have the final say.

Submitting

Follow the links to submit your solutions for Factorial and Postorder (you'll notice it's the same page as the Leaderboard).

Do not publish your solutions anywhere. That will spoil the game, as your solutions are meant to be secret. All solutions will be published at the end of the game.

Prizes (provided by O'Reilly and ActiveState) will be awarded to veteran and beginner winners. A prize may also be awarded to any especially fascinating solution(s).

Leaderboard

You can track your ranking through the leaderboard here. Beginners are encouraged to enter and there is a separate leaderboard for them.

There is also a special leaderboard for teams. There will be no prizes awarded to the best team, other than the admiration of your fellow golfers. If you are in a team, you can't also play individually.

Feedback

We encourage you to send feedback as well as your ideas for future holes and tiebreakers to golf@theperlreview.com.

Referees

• Ton Hospel < perl-golf at ton dot iguana dot be >

• Michael Thelen < thelenm at cs dot utah dot edu >

• F. Xavier Noria < fxn at retemail dot es >

• David Lowe < dlowe at saturn5 dot com >

If you want to be a referee next month, drop us a note: golf@theperlreview.com