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.


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.


                 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/.


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

1 - (sum of character ASCII values (below 127))/(total number of characters * 126)

General rules


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 and respectively, and place them in the same directory as your test program. Then verify and score your attempt using:

    $ perl
It will auto-detect the order of arguments you assumed for To see some extra options of the test program, do:
    $ perl --help

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


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).


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.


We encourage you to send feedback as well as your ideas for future holes and tiebreakers to


If you want to be a referee next month, drop us a note: