Few weeks ago I've translated "How Browsers Work: Behind the Scenes of Modern Web Browsers", the document which describes internal mechanism of modern browsers, to Japanese.

"How Browsers Work - Behind the Scenes of Modern Web Browsers — Translation of "How Browsers Work" v0.1 documentation"

The document is originally written by Tali Garsiel - she is a Web Developer from Israel - on her site and re-publish on HTML5Rocks by Paul Irish. This is a great useful resource for web authors, web developers, browser extension developers and anyone who hacks around web browser. I've thought more people should read this content so I've translated it to Japanese for whom can understand Japanese ( and also for me ;) ). The original document is licensed under the Creative Commons Attribution 3.0 License (text content), and under the Apache 2.0 License (code sample). My translation is same to it.

The translation is on GitHub. If you find some mistakes, typo, etc., please tell me with twitter or make issue on GitHub.

PS. I'm glad since paul menthond about my translation and will link from html5rock to my doc, wow!

I’m friendly with Emacs so I’d like to write python with Emacs. In this article I introduce you how to setup python environment on emacs.

Before this, I need to note is that configuring emacs for python have been so complex and painful for me. Thet’s why:

• It’s hard to find appropriate and updated information on the web.
• It requires several file to introcude.
• And emacs configuration becomes large.

You might be happy to choose vim or IDE to write python. In fact, Expert Python Programming describes how to setup vim with several pages but not deal with emacs setup.

python.el vs python-mode.el

Several page on the web says that python.el (default emacs python major mode) and python-mode.el (maitained by Python community) are different. And they also say you should install python-mode.el instead of python.el. But I thnink I should keep setting file smaller and simpler, so I decide to use default python.el with some small configuration.

.emacs file becomes larger easily. So keep it simple is good practice.

Some configurations

Additionaly add these two confs:

• Add closing ), ]… when type opening (, [… and set cursor at middle of these.
• Insert property indent when you type RET

Write these lines to .emacs for above setting.

;; Electric Pairs for python-mode
(add-hook 'python-mode-hook
          (lambda ()
            (define-key python-mode-map "\"" 'electric-pair)
            (define-key python-mode-map "\'" 'electric-pair)
            (define-key python-mode-map "(" 'electric-pair)
            (define-key python-mode-map "[" 'electric-pair)
            (define-key python-mode-map "{" 'electric-pair)))
(defun electric-pair ()
  "Insert character pair without sournding spaces"
  (interactive)
  (let (parens-require-spaces)
    (insert-pair)))
;; bind RET to py-newline-and-indent
(add-hook 'python-mode-hook '(lambda ()
     (define-key python-mode-map "\C-m" 'newline-and-indent)))

Flymake setting

Flymake (on-the-fly make) is neccessary for coding on emacs this time. In python, use pyflakes and pep8 module as make file.

Setting up these modules first of all. In my case I’m using vritualenv. Install these in virtualenv environment via pip.

pip install pyflakes pep8

My virtual environment are ~/share/pyenv. In this case installed bins are located at /Users/kosei/share/pyenv/bin/pyflakes and /Users/kosei/share/pyenv/bin/pep8.

Prepare a shell script which invokes these scripts. Supporse that name of the script is ‘pycheckers’, the body of the script is like this:

#!/bin/bash

/Users/kosei/share/pyenv/bin/pyflakes "$1"
/Users/kosei/share/pyenv/bin/pep8 --ignore=E221,E701,E202 --repeat "$1"
true

Put pycheckers script somewhere in $PATH. Then add this configuration to .emacs.

;;; flymake for python
(add-hook 'find-file-hook 'flymake-find-file-hook)
(when (load "flymake" t)
  (defun flymake-pyflakes-init ()
    (let* ((temp-file (flymake-init-create-temp-buffer-copy
                       'flymake-create-temp-inplace))
           (local-file (file-relative-name
                        temp-file
                        (file-name-directory buffer-file-name))))
      (list "pycheckers"  (list local-file))))
  (add-to-list 'flymake-allowed-file-name-masks
               '("\\.py\\'" flymake-pyflakes-init)))
(load-library "flymake-cursor")
(global-set-key [f10] 'flymake-goto-prev-error)
(global-set-key [f11] 'flymake-goto-next-error)

After restart (or re-eval .emacs buffer) you can use flymake in python-mode. If some line violates syntax / pep8 style, the line mark as red. Also you put cursor on the red line, error/warning message appears mini buffer.

Conclusion

In this article I’ve described how to set up python environment on Emacs, especially these topics. – Use letest stable emacs binary – Add () or [] compilation and auto indent – Flymake setting Enjoy python coding :)

Solved A, B and C. All of these has been passed the system test. Got 70pt so I could advance to Round 1.

This year I’ve been using Python instead of C++.

Repository on GitHub

A. Bot Trust

Easy problem. Just simulate. There are only a hundred buttons for each bot, so it’s fast enough for both small and large input.

T = int(raw_input())

for test_num in range(1, T + 1):
    ret = 0
    line = raw_input().split()
    N = int(line[0])
    seq = []

    for i in range(1, len(line), 2):
        seq.append((line[i], int(line[i+1])))

    cur_pos = {'O': 1, 'B': 1}
    others_duration = 0
    others_color = seq[0][0]

    for i in seq:
        color = i[0]
        dst = i[1]
        time = abs(cur_pos[color] - dst) + 1

        if others_color == color:
            ret += time
            others_duration += time
        else:
            if time > others_duration:
                diff = time - others_duration
                ret += diff
                others_duration = diff
            else:
                ret += 1
                others_duration = 1

        others_color = color
        cur_pos[color] = dst

    print "Case #{0}: {1}".format(test_num, ret)

B. Magicka

Very complex problem statement and poor example. And since number of combines and opposes of small input are at most 1, we should carefully read problem and write code to run with multiple combines/opposes.

If once we could understand the problem accurately, the problem is not so hard. Just simulate the changing of spells. Computational complexity doesn’t become the problem for both small and large input.

def check_comb(last, seq):
    for i in seq:
        if last == i[0]:
            return i[1]
    return False

def check_oppos(target, seq):
    for i in seq:
        if target.count(i) > 0:
            return True
    return False

T = int(raw_input())

for test_num in range(1, T + 1):
    line = raw_input().split()
    combs = {}
    oppos = {}
    spells = ""
    ret = []

    # parse
    idx = 0
    C = int(line[idx])

    i = 0
    while i < C:
        i += 1
        idx += 1
        seq = line[idx]
        if combs.has_key(seq[0]):
            combs[seq[0]].append((seq[1], seq[2]))
        else:
            combs[seq[0]] = [(seq[1], seq[2])]
        if combs.has_key(seq[1]):
            combs[seq[1]].append((seq[0], seq[2]))
        else:
            combs[seq[1]] = [(seq[0], seq[2])]

    idx += 1
    D = int(line[idx])

    i = 0
    while i < D:
        i += 1
        idx += 1
        seq = line[idx]
        if oppos.has_key(seq[0]):
            oppos[seq[0]].append(seq[1])
        else:
            oppos[seq[0]] = [seq[1]]
        if oppos.has_key(seq[1]):
            oppos[seq[1]].append(seq[0])
        else:
            oppos[seq[1]] = [seq[0]]

    idx += 1
    N = int(line[idx])
    spells = line[idx + 1]

    # proccess spells
    for s in spells:
        if len(ret) < 1:
            ret.append(s)
        else:
            cur = s
            # check combine
            last = ret[-1]
            if combs.has_key(cur):
                res = check_comb(last, combs[cur])
                if res:
                    cur = res
                    ret.pop()

            # check opposite
            if oppos.has_key(cur) and check_oppos(ret, oppos[cur]):
                ret = []
            else:
                ret.append(cur)

    print "Case #{0}: [{1}]".format(test_num, ", ".join(ret))

C. Candy Splitting

First I’ve wrote a brute-force for small input. Use bit to walk around all combinations.

import math

T = int(raw_input())
seq = []
ret = -1

def calc(pat1, pat2, sum, n):
    global seq
    global ret

    if n >= len(seq):
        if pat1 == pat2:
            ret = max(ret, max(sum, reduce(lambda x, y: x + y, seq) - sum))
        return

    calc(pat1 ^ seq[n], pat2, sum + seq[n], n + 1)
    calc(pat1, pat2 ^ seq[n], sum, n + 1)

for test_num in range(1, T + 1):
    ret = -1
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)

    for i in range(1, 2 ** N - 1):
        pat1 = 0
        pat2 = 0
        sum = 0

        for j in xrange(N):
            if i >> j & 1:
                pat1 ^= seq[j]
                sum += seq[j]
            else:
                pat2 ^= seq[j]

        if pat1 == pat2:
            ret = max(ret, max(sum, total - sum))

    ret = ret if ret != -1 else 'NO'
    print "Case #{0}: {1}".format(test_num, ret)

This solution is obviously too slow for large input because it takes 2 ^ N times for largest case. In the beginning I’ve considerd DP solition. However I couldn’t figure it out.

After a while I’ve noticed the pattern of the problem.

• Patrick’s adding is equal to xor.
• A xor B = 0 is same to A = B because of difinition of xor.

According to these facts, if all xor of input sequence are equal to zero, the answer is total sum of sequence without a smallest element.

T = int(raw_input())

for test_num in range(1, T + 1):
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)
    patrick_total = reduce(lambda x,y: x^y, seq)
    mini = min(seq)

    if patrick_total != 0:
        ret = 'NO'
    else:
        ret = total - mini

    print "Case #{0}: {1}".format(test_num, ret)

D. Goro Sort

Cannot solve. See Contest analytics.

Just started my blog on posterous. I’ll write here about mainly technology following my interests.

I’ve wrote on WrodPress.com previously but changed the service because:

• Posterous is simple. Just email to write entry.
• Can use markdown. I’m a one of markdown fan.
• There are many cool default free design.

I’ve migrated part of entries which I’ve wrote on wordpress blog. Entries blow this are all old one which is moved.

When importing the data from wrodpress to posterous, I’ve simply replace the part of data to fit it to posterous style/syntax. So there might be odd appearance.

Submitted 250 problem but challenged. The result was 0pt and rating was 1257. The rating slightly gained but I’m not satisfied the result. Also the result of the SRM had been 0pt in which recent 3 matches.

Easy – AgeEncoding

The algorithm for this problem is not so hard, this is just a problem for searching the solution with binary search. However, the most difficult point is consideration for corner cases. According to problem statement, we should return -1 if there is no solution and -2 if there are multiple solution. And it was very hard to notice all cases of such conditions. Many coders had been challenged or failed system test. It seems that almost of them hadn’t noticed the case whose input are, for instance, age = 1 and candlesLine = “11111”. In this case the correct answer is -1, not 0, since return value must be “strictly positive”.

class AgeEncoding {
public:
  double getRadix(int age, string candlesLine) {
    double ret = 0;
    int i, j;
    int n = candlesLine.size();
    int one_num = count(candlesLine.begin(), candlesLine.end(), '1');

    if (one_num == 0) return -1;
    if (candlesLine[n-1] == '1')
      if (age == 1)
        if (one_num == 1) return -2;
        else return -1;
      else
        if (one_num == 1) return -1;

    double left = 0, right = 100;
    for (i=0; i<1000; i++) {
      ret = (left + right) * 0.5;
      double ans = 0;
      double B = 1;

      for (j=n-1; j>=0; j--) {
        ans += (candlesLine[j] - '0') * B;
        B *= ret;
      }

      if (ans > age)
        right = ret;
      else
        left = ret;
    }

    return ret;
  }
};

TZTester is one of a great plugin for TopCoder SRM. It adds sample test cases of problem statements into the local code automatically (which is generated by CodeProcessor plugin, normally). This function encourages us to write the code as test-first, this is quite helpful to find bugs and fix it quickly. How to introduce these plugins is described here:

How to install The Arena plug-ins – TopCoder Wiki

However, I had little two dissatisfaction about generated test cases of TZTester.

1. There are no enough new lines in test cases. This makes little hard to add new own test cases.
2. I’d like to put more two cases into the tail of test cases. This intends that it enforce me to think about another tests for considering corner cases or worst cases.

So I’ve tried to modify my TZTester.

How to modify

TZTester is written in Java. I’ve had a little experience for java development. So I’ve confused several times for modification. Because of this, this section is maybe so dully for java programmer.

Step 1: Extract .jar file

TZTester is distributed as .jar file format. “.jar” file is just a zip file. I don’t know about the difference between jar and zip. So don’t be afraid.If Java development environment has been set up on your system, perhaps there are “jar” command. In my case (Mac OSX), the command seems to be bundled. You can extract and compress jar file by this command. The interface of jar command is quite similar to tar command:

// extracting
% jar -xvf foo.jar

// compressing
% jar -cvf foo.jar foo bar baz/

If you don’t have a jar command, try unzip command since jar file is just a zip file, again.Now let’s extract a TZTester.jar. If you type this command:

% jar -xvf TZTester.jar

Then you will get these files:

• tangentz/
  • TZTester.java
  • TZTester.class
  • TZTester.html
• META-INF/

The only important file is TZTester.java. This is a source code of TZTester. TZTester.class is a compiled file of TZTester.java, and TZTester.html is just a manual file.

Step 2: Editting TZTester.java

Now we could get a source code of TZTester. So only you have to do is editing this code. For instance, you’d like to modify test cases, these are generated by generate_test_case() or generate_parameter() method.

Step 3: Compiling TZTester.java, and make TZTester.jar

Before compiling, TZTester requires ContestApplet.jar file, so you need to get this jar. ContestApplet.jar could be downloaded from here. And then put the downloaded ContestApplet.jar file to same directory with tangentz/. ContestApplet.jar contains classes, which is used by TZTester. Also you need to pay attention to the directories, put the source code in tangetz/ directory, ContestApplet.jar and Makefile (describe later) in same directory with tangentz/ itself.

your_working_dir/
| -- ContestApplet.jar
| -- Makefile
` -- tangentz/
     |-- TZTester.java
     `-- (TZTester.class)

For compiling, firstly just type this commands in “your_working_dir”:

% javac -classpath ContestApplet.jar tangentz/TZTester.java

Then TZTester.class is generated. Next step, make jar file from .class file.

% jar cvf TZTester.jar tangentz/TZTester.class

It’s convenient to make such Makefile and put it in “yoru_working_dir”:

jar: class
        jar cvf TZTester.jar tangentz/TZTester.class
class:
        javac -classpath ContestApplet.jar tangentz/TZTester.java

The final step is just replacing your existing TZTester.jar by this new modified one.

My modification

I’ve pushed my TZTester.java code to my github repository.

plugin/modify_TZTester/build/tangentz/TZTester.java at master from cou929’s topcoder – GitHub

I’ve modified these two points. * Add new lines to test cases. Append “ ” to argument of Code.appen() in generate_test_code(), generate_test_case() and generate_parameter() * Append additional two test cases which contents are same to test case #0. Call generate_test_case() method two times more.

Other modifications

There are another modifications. Petr displays his TZTester:

Algorithm problems for dummies: Petr Mitrichev’s blog: Screencast and challenging

The TZTester.jar file itself is here. This is modified for C# code generation.

cafelier also shows his modification (in Japanese).

TZTester をどうにかする – cafelier@SRM – TopCoder部

The zipped file itself is here. He did a lot of changes such as put the test codes in global, measure processing time and so on.

Easy – FallingFactorialPower

For implementing quickly, consider conditions (k 0), and calculate the answer respectively using the for loop.

class FallingFactorialPower {
public:
  double compute(int n, int k) {
    double ret = 1;

    if (k < 0)
      for (int i=1; i<=abs(k); i++)
        ret /= (double)(n + i);
    else if (k > 0)
      for (int i=0; i<k; i++)
        ret *= (double)(n - i);

    return ret;
  }
};

Medium – RelativePath

Took a quick string processing-like approach. First of all, divide the two strings by “/” and store into two vectors. Check the vectors simultaneously to find an index that the first time two element of vectors are differ. Then append “../” to reach such index, and also append paths behind from such index.

class RelativePath {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  string makeRelative(string path, string currentDir) {
    string ret;

    vector <string> p = split(path, "/");
    vector <string> c = split(currentDir, "/");

    int i = 0, n = min(p.size(), c.size());
    for (i=0; i<n; i++)
      if (p[i] != c[i]) break;

    for (int j=0; j<c.size() - i; j++)
      ret += "../";
    for (int j=i; j<p.size(); j++)
      ret += p[j] + "/";

    ret.erase(ret.end()-1);

    return ret;
  }
};

Easy – LaserShooting

Calculate expected numbers for each obstacles, and then sum up these numbers. The way to calculate the expected number for the obstacle is that (the angle of laser to hit the obstacle) / (pi). In this problem the position (x, y) of obstacle is given, so we can calculate the angle using arc tangent.

class LaserShooting {
public:
  double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2) {
    double ret = 0;

    for (int i=0; i<x.size(); i++) {
      double ang1 = atan((double)y1[i] / (double)x[i]);
      double ang2 = atan((double)y2[i] / (double)x[i]);
      ret += abs(ang1 - ang2) / M_PI;
    }

    return ret;
  }
};

Easy – MagicWords

According to “Constrains”, S contains up to 8 element and maximum length of each elements are 20. So there is 8! * 20 * 8 = 6451200 steps in the largest input case. This is seems that we can solve this problem simply searching all permutations. I’ve coded as such, but in the largest case (such as test case #6), it has took too long time, therefore introduced memorization using std::map. Then the code is optimized, passed system test.

class MagicWords {
public:
  map <string, int> memo;

  bool isMagic(string &str, int pos) {
    int len = str.size();
    for (int i=0; i<len; i++)
      if (str[i] != str[(i+pos)%len])
        return false;
    return true;
  }

  int count(vector <string> S, int K) {
    int ret = 0;
    vector <int> pos;
    for (int i=0; i<S.size(); i++) pos.push_back(i);

    do {
      string str;
      int magic = 0;
      for (int i=0; i<S.size(); i++) str += S[pos[i]];
      if (memo.find(str) != memo.end()) 
        magic = memo[str];
      else
        for (int i=0; i<str.size(); i++) if (isMagic(str, i)) magic++;
      memo[str] = magic;
      if (magic == K) ret++;
    } while (next_permutation(pos.begin(), pos.end()));

    return ret;
  }
};

Easy – CellRemoval

Easy problem. First of all, find leaf nodes from array ‘parent’. Leaf node is the node that no element refer it. And then traverse a tree from each leaf node to root node. During traversing, stop traverse if encounters ‘deletedCell’. If the leaf node can reach root node, count up return value.

The size of parent array is up to 50. This is very small tree. So you need not to implement memorization or other techniques. Number of nodes is small enough for execution time.

class CellRemoval {
public:
  int ret;
  vector <int> parent;
  int deletedCell;

  int r(int pos) {
    if (pos == -1) {
      ret++;
      return 0;
    } else if (pos == deletedCell) {
      return 0;
    }

    r(parent[pos]);
    return 0;
  }

  int cellsLeft(vector <int> _parent, int _deletedCell) {
    ret = 0;
    parent = _parent;
    deletedCell = _deletedCell;
    int leafs[parent.size()];
    memset(leafs, 0, sizeof(leafs));

    for (int i=0; i<parent.size(); i++)
      if (parent[i] != -1)
        leafs[parent[i]]++;

    for (int i=0; i<parent.size(); i++)
      if (leafs[i] == 0)
        r(i);

    return ret;
  }
};