As a Brain teazers lover, code sometimes can be a fun toy for me. From last year, I started to play around with python challenge occasionally and reached level 13 (with cheating). The famous python challenge seems quite difficult for me. Because the answers are easily to be found online, I could not help looking for hints when I felt I was stuck. Recently I came across a similar web puzzle provided by Chen Hao on coolshell (He is an influential programmer), the puzzle was release last Saturday, fresh new. It is quite concise that do not require too much time to solve. Yet it is informative and very smart! I went through the puzzle by coding for every required steps. Later I realized there are actually plenty of resources available, as long as you know what you are looking for. Google/Wikipedia solves problem better than my code. But I am glad that I tried, with great effort and really learned something as concrete knowledge rather than information that can only be considered to be known to me. Here I note down the process.

Level 0 Brainfuck

With the first sight, I did feel that my brain had been fucked. What the hell was that? Hopelessly I googled the only words on the page, and surprisingly found that there is a programming language called brainfuck. The language consists of only eight simple commands and an instruction pointer. It is designed for fun. The operators > < + - . , [ ] are corresponded to some operations on a pointer. Interpreted it using a piece of python code.

#! /usr/bin/python

interpret = "#include <stdlib.h> \n" + \
"int main(){ \n" + \
"char array[1000000]; char *ptr = array;"

fuckbrain = "++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>+++++++++>++++++++++>+++++++++++>++++++++++++>+++++++++++++>++++++++++++++>+++++++++++++++>++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>-.+<<<<<<<<<<<<<<<>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>>>>>>>>>>>+++.---<<<<<<<<<<<<>>>>>>>>>>>>>>-.+<<<<<<<<<<<<<<>>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<<>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<>>>>>>--.++<<<<<<>>>>>>>>>>>>>.<<<<<<<<<<<<<>>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<<>>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<."

for s in fuckbrain:
        if s == ">":
                interpret += "++ptr;"
        elif s == "<":
                interpret += "--ptr;"
        elif s == "+":
                interpret += "++*ptr;"
        elif s == "-":
                interpret += "--*ptr;"
        elif s == ".":
                interpret += "putchar(*ptr);"
        elif s == ",":
                interpret += "*ptr=getchar();"
        elif s == "[":
                interpret += "while(*ptr){"
        elif s == "]":
                interpret += "}"

interpret += "}"


with open("fuck.c", "w") as textfile:
        textfile.write(interpret)

Compile the c code and run, I got the answer welcome.html for next level

$gcc fuck.c -o fuck
$./fuck
$welcome.html

Level 1 Answer to Life

There are two numbers to be figured out. One is from the series 2, 3 ,6, 18, 108. It is obvious that the next number is always the product of the previous two numbers. Therefore one of the number is 18 * 108 = 1944. The other number is the “answer” to the ultimate question of life, the universe and everything, 42. Finally got 1944 * 42 = 81648, which led me to the next level.

Level 2 Keyboard

There is a strange keyboard and a string below. It was easy to come up with the idea that the string is the output from this strange keyboard, which corresponds to the one from a normal keyboard. So I manually built up the corresponds between the letters from these two keyboard and encode the string.

#! /usr/bin/python

n_k = "-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>?"

s_k = "[]',.pyfgcrl/=\\aoeuidhtns-;qjkxbmwvz{}\"<>PYFGCRL?+|AOEUIDHTNS_:QJKXBMWVZ"

inp = "macb() ? lpcbyu(&gbcq/_\\021%ocq\\012\\0_=w(gbcq)/_dak._=}_ugb_[0q60)s+"
result = ""

for n in inp:
        key = s_k.find(n)
        if not key == -1:
                result += n_k[key]
        else:
                result += n

with open("key.c", "w") as textfile:
        textfile.write(result)

It looks life c code, so I saved it as c program, compile and run.

main() { printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);}

$gcc key.c -o key
$./key
$unix

Later I knew that this keyboard layout is called Dvorak Simplified Keyboard. There is a type of encoding based on the differences in layout of a QWERTY keyboard and a Dvorak keyboard. The piece of the key.c code is famous. This program won a “Best One Line Program” award in 1987. But I could not quite understand it - yes, it is exactly that my code runs, and I don’t know why

Use unix to enter the next level.

Level 3 QR Code

There is a QR code, scan to get encoding information like

[abcdefghijklmnopqrstuvwxyz] <=> [pvwdgazxubqfsnrhocitlkeymj].

Decoding the line of letters below:

#! /usr/bin/python

d = "abcdefghijklmnopqrstuvwxyz"
e = "pvwdgazxubqfsnrhocitlkeymj"

i="Wxgcg txgcg ui p ixgff, txgcg ui p epm. I gyhgwt mrl lig txg ixgff wrsspnd tr irfkg txui hcrvfgs, nre, hfgpig tcm liunz txg crt13 ra \"ixgff\" tr gntgc ngyt fgkgf."

result = ""

for n in i:
        key = e.find(n)
        if not key == -1:
                result += d[key]
        else:
                result += n

print result

Decode the information, we are told:

“Where there is a shell, there is a way. I expect you use the shell command to solve this problem, now, please try using the rot13 of “shell” to enter next level.”

Use ROT13 to encode “shell”to get “furyy”. ROT13 cipher is to replace a letter with the one 13 letters after it in the alphabet. The interesting property is that encode and decode is using the same algorithms for ROT13. So encode “furyy” again, we get back to “shell”.

$ rot13
shell
furyy

Use furyy to get to the next level.

Level 4 Cat

The idea is similar to a level in Python Challenge, so I quickly got started. One of the tricks is that the hints are in the html source code. However I was also constrained by the idea of solving that similar Python Challenge problem and stuck in this problem for a very long time! Finally I got the correct idea, which is to match the pattern using Regular Expression.

#! /usr/bin/python

import re

with open("./data.txt", "r") as rfile:
        page_source = rfile.read()

p = re.compile(r'([A-Z])([0-9])[a-z](\2)(\1)|([0-9])([A-Z])[a-z](\6)(\5)')
m = p.finditer(page_source)

for s in m:
        print s.group()

Previously I did not use regular expression (coz I really didn’t know about regular expression!) I searched through all the text for 5-letter arrays and checked its pattern manually. I then went through one chapter talking about regular expression in the book The Linux Command Line, an excellent book I am reading for month, talking about fundamentals on Linux command line and shell. Here () is used to define a marked subexpression, later can be recalled for matching. That is how the RE checks the equality between the leading and ending letters, and between the second and the second last letters.

Using shell command

$ cat data.txt | grep -E "([A-Z])([0-9])[a-z](\2)(\1)|([0-9])([A-Z])[a-z](\6)(\5)" -o
E1v1E
4FaF4
9XrX9
O3i3O
0MaM0
4GbG4
M5l5M
0WeW0
Y0s0Y

The answer is the center letters in the Palindromes: variables

Level 5 Keep Going

This is very similar to one of the puzzles in Python Challenge. The hint is found by clicking the image. A number shows - 32722. Replace the number 2014 in the url with this number, a new page was shown with a new number. Keeping doing this led me to the answer!

#! /usr/bin/python
import urllib2

def check_url_2(url, params, method="GET"):
        if method == "POST":
                return urllib2.urlopen(url, data=urllib.urlencode(params))
        else:
                print "get "+url+"?"+urllib.urlencode(params)
                return urllib2.urlopen(url + "?" + urllib.urlencode(params))

path = "http://fun.coolshell.cn/n/"
s = "32722"
while s is not None:
        res = urllib2.urlopen(path + s)
        s = res.read()
        print s

At last I got tree

Level 6 Binary Tree

This is a test on the classic binary tree algorithms - Binary tree reconstruction from in-order traversal and post-order traversal. The main idea is to use the information that the last node in the post-order array is the root of the tree. That root value can be found in the in-order array which divides the array into two, each indicates the left branch and right branch from that root. By counting the number of nodes in each branch, the post-order can also be divided into two branches, which corresponds to the ones in the in-order array. In this case, in-order and post-order array for the left and right sub-trees are found and the problem can be solved recursively.

public class Tree {
    private Node mRoot;
    private char[] inOrder;
    private char[] postOrder;

    private class Node {
        char value;
        Node left;
        Node right;
    }

    public Tree(char[] i, char[] p) {
        //restore the tree from in-order traversal array and post-order traversal array
        inOrder = i;
        postOrder = p;
        mRoot = restore(0, i.length-1, 0, p.length-1);
    }

    private Node restore(int ios, int ioe, int pos, int poe) {
        //check termination condition
        if(ios > ioe || pos > poe) {
            return null;
        }

        //find the root value from post-order array
        char r = postOrder[poe];

        //find the position of r in in-order array
        int ridx = -1;
        for(int i = ios; i <= ioe; i++) {
            if(r == inOrder[i])
                ridx = i;
        }

        //count the number of nodes in left and right branch
        int left_size = ridx - ios; 
        int right_size = ioe - ridx;

        Node root = new Node();
        root.value = r;
        root.left = restore(ios, ios + left_size - 1, pos, pos + left_size -1 );
        root.right = restore(ridx + 1, ioe, poe - right_size, poe-1);

        return root;
    }

    public int height(Node n) {
        if (n == null)
            return 0;

        return max(height(n.left), height(n.right)) + 1;
    }

    private int max(int a, int b) {
        return a >= b ? a:b;
    }

    public void printLongestPath() {
        Node n = mRoot;
        while(n != null ) {
            System.out.print(n.value);
            if (height(n.left) > height(n.right))
                n = n.left;
            else
                n = n.right;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String in = "T, b, H, V, h, 3, o, g, P, W, F, L, u, A, f, G, r, m, 1, x, J, 7, w, e, 0, i, Q, Y, n, Z, 8, K, v, q, k, 9, y, 5, C, N, B, D, 2, 4, U, l, c, p, I, E, M, a, j, 6, S, R, O, X, s, d, z, t";
        String po = "T, V, H, o, 3, h, P, g, b, F, f, A, u, m, r, 7, J, x, e, w, 1, Y, Q, i, 0, Z, n, G, L, K, y, 9, k, q, v, N, D, B, C, 5, 4, c, l, U, 2, 8, E, I, R, S, 6, j, d, s, X, O, a, M, p, W, t, z";

        in = in.replace(", ", "");
        char[] inorder = in.toCharArray();
        po = po.replace(", ", "");
        char[] postorder = po.toCharArray();

        Tree tree = new Tree(inorder, postorder);
        tree.printLongestPath();
    }
}

Use the string found from the longest path of the binary tree to decode the information given, I got a word nqueens

$ java Tree
zWp8LGn01wxJ7
$ openssl enc -aes-128-cbc -a -d -in code.txt
enter aes-128-cbc decryption password:
nqueens

Level 7 NQueens

A classic algorithm question again. Nqueens problem is to place n queens on an n by n chessboard, where solutions exist for all natural numbers n with the exception of n = 2 and n = 3. NQueens problem is a good example for backtracking algorithm practice. The java code to solve 9 queens problem:

public class NQueens {

    public static void main(String args[]) {
        int[] board = new int[9]; 
        placeQueenOnBoard(0, board);
    }

    private static void placeQueenOnBoard(int Qi, int[] board) {
        int n = board.length;
        //base case
        if (Qi == n) {
            for(int i = 0; i < 9; i++)
                System.out.print(board[i]+1);
            System.out.println();
        } else {
            //try to put the ith Queen (Qi) in all of the columns
            for (int column = 0; column < n; column++) {
                if (isSafePlace(column, Qi, board)) {
                    board[Qi] = column;

                    //then place remaining queens.
                    placeQueenOnBoard(Qi + 1, board);

                    //backtracing
                    board[Qi] = -1;
                }
            }
        }
    }

    //check if the column is safe place to put Qi (ith Queen)
    private static boolean isSafePlace(int column, int Qi, int[] board) {
        //check for all previously placed queens
        for (int i = 0; i < Qi; i++) {
            if (board[i] == column) { // the ith Queen(previous) is in same column
                return false;
            }
            //the ith Queen is in diagonal
            //(r1, c1) - (r2, c1). if |r1-r2| == |c1-c2| then they are in diagonal
            if (Math.abs(board[i] - column) == Math.abs(i - Qi)) {
                return false;
            }
        }
        return true;
    }
}

There are totally 352 solutions, traverse all to find the one whose sha hash equals to the given encoded information

#! /usr/bin/python 
import hashlib

r = "e48d316ed573d3273931e19f9ac9f9e6039a4242"

i = "zWp8LGn01wxJ7" 
code =[]

with open("./nqueen_result.txt", "r") as rfile:
        for l in rfile.readlines():
                code.append(l)

for s in code:
        h = hashlib.sha1(i+s).hexdigest()
        if h == r:
                print s

Found the answer 953172864

Level 8 Excel Number

It is easy to notice that this is a base26 to decimal conversion. Using the code below:

#! /usr/bin/python
from math import log, floor

alp = "abcdefghijklmnopqrstuvwxyz"
a = "coolshell"
b = "shell"

def base26todecimal(a):
        size = len(a)
        s = 0
        for i in a:
                index = alp.find(i)+1
                s += index*26**(size-1)
                size -= 1
        return s

def decimaltobase26(a):
        n = int(floor(log(a, 26))) #highest 
        s =""

        while n >= 0:
                d = a/26**n
                r = a%26**n
                s += alp[int(d-1)]
                a = r
                n -= 1
        return s

d = base26todecimal(a)/base26todecimal(b)
print decimaltobase26(d)

The output is duyo

Level 9 Pigpen

Finally got to the last level! There seemed to be no relations between the given two images. Looking around for a while and with some useless search, the hints showed up when I googled one of the pictures - pigpen. There is a cipher, called pigpen or Freemason’s cipher, which is a geometric simple substitution cipher which exchanges letters for symbols. The graphs below can be easily decoded as helloworld using the diagram below

pigman

Get to the page using helloworld. Finally get to the end. It is really an incredible journey to work through all the problems. Along the way I learned a lot funny topics and fundamental knowledge about computer science which I lack of. Most of the problems can be easily solved by searching online, but I coded from sketch as a coding practice. I feel lucky and grateful that I stepped into this wonderful world 4 year ago, although it’s a bit late. I would choose to stay in this field for my career.

Hidden Level

Wait! I was told it is not the end! Here is hidden information. View the html source at the helloworld page, I can find a line below the shutdown image

“Did you even think vi an image file?”

Interesting! Well, let’s vi the image file. Save the shutdown.png and open it with vi. There is a line

“This Image actually is a RAR file as well.”

Save it as an rar file and unzip

$cp shutdown.png shutdown.rar
$unrar e shutdown.rar

Here we get a text file helloworld.txt, open it. There are some information about hello world program, c language, and the father of c programming language - Dennis Ritchie. The keyword to next level: DennisRitchie.html

In Memoriam - Dennis Ritchie Hello world, the world full of imagination, creativity and joy, that brought to us by those great scientists.