First you learn to code, then you code to learn

Great Python Challenge

Just like "The Great Giraffe Challenge", let us take  the Great Python Challenge.

The answer will be a piece of very short, one-liner like Python code. So it won't take too much of your time.

As usual, if you failed, changed your profile to a python related picture until, say, you find out the answer.

Are you ready?

The reflect package of Go 1.1 adds functions SliceOf, ChanOf，and MakeFunc.
With the help of these new functions, we can do things similar to Python's map, list, iterator comprehension, and decorator in Go.
The followings is a simple demonstration of functionality similar to Python's map function and list comprehension.

Math Proofs of Google Code Jam Qualification Round 2013 Problems

Problems of Google Code Jam Qualification Round 2013 can be found at http://code.google.com/codejam/contest/2270488/dashboard

$\newcommand{\lyxlock}{}$

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use $0,i,1,-1$ to represent “ “, T, O, X. So if$\left\Vert \sum_{i=1}^{4}a_{i,i}\right\Vert >3$ , then some one won.

2 Problem B. Lawnmower

Theorem.$\left(a_{i,j}\right)$ is a possible pattern if $$a_{i,j}=\min\left(\max\left(\left\{ a_{i,k}\right\} \right),\max\left(\left\{ a_{k,j}\right\} \right)\right)$$ for every $i,j$ .

Proof.

Can be easily proved by induction on $N=\sum_{i,j}M-a_{i,j}$ , where $M=\max\left(\left\{ a_{i,j}\right\} \right)$ .

         

     

3 Problem C. Fair and Square

Let $$N=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{1}10+a_{0}$$ , where $a_{i}\in\left\{ 0,1,\ldots9\right\}$ and $a_{n}\neq0$ . Denote by $\delta_{k}\left(x\right)$ the $\left(n-k+1\right)$ -th digit of $x$ , then we have $\delta_{k}\left(x\right)=a_{k}$ .

Assume $N$ is a palindrome, i.e., $a_{i}=a_{n-1}$ for every $i$ .

Let $b_{k}$ be the coefficient of $x^{k}$ of $$\left(a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}+a_{0}\right)^{2},$$ that is, $$b_{k}=\sum_{i=\max\left(0,k-n\right)}^{\min\left(k,n\right)}a_{i}a_{k-i}.$$

Theorem. $N^{2}$ is also a palindrome iff $b_{k}\leq9$ for all $k$ .

Proof.

($\Leftarrow$ )

Trivial.

($\Rightarrow$ )

Observe that $b_{k}=b_{2n-k}$ for all $k$ . We prove the statement by mathematical induction on $k$ for $k\leq n$ .

Case $k=0$ :

Since $$a_{n}^{2}10^{2n}\leq N^{2}<\left(a_{n}+1\right)^{2}10^{2n}$$ and $$\delta_{0}\left(N^{2}\right)=\delta_{0}\left(a_{0}^{2}\right)=\delta_{0}\left(a_{n}^{2}\right),$$ it is easy to see that $a_{0}=a_{n}\in\left\{ 1,2,3\right\}$ . So $b_{0}=a_{0}^{2}\leq9$ .

Moreover, we also know that $N^{2}$ has $2n+1$ digits and hence $\delta_{2n-k}\left(N^{2}\right)=\delta_{k}\left(N^{2}\right)$ for all $k\leq2n$ .

Case $k>0$ :

Suppose $b_{i}\leq9$ for all $i<k$ , we want to show $b_{k}\leq9$ .

By the induction hypothesis, we know that $\delta_{2n-i}\left(N^{2}\right)=\delta_{i}\left(N^{2}\right)=b_{i}=b_{2n-i}$ for all $i<k$ . So

$$\begin{eqnarray*} 10^{2n-k-1}\cdot\left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \sum_{i=2n-k-1}^{2n}\delta_{i}\left(N^{2}\right)10^{i}\\ & = & \sum_{i=2n-k-1}^{2n}b_{i}10^{i} \end{eqnarray*}$$

On the other hand, $$\begin{eqnarray*} \left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \left\lfloor \frac{\sum_{i=0}^{2n}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor \\ & = & \frac{\sum_{i=2n-k-1}^{2n}b_{i}10^{i}}{10^{2n-k-1}}+\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor . \end{eqnarray*}$$ Therefore, $\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor =0$ , hence $$b_{k}=b_{2n-k}\leq\frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k}}<10.$$

  

  

Corollary. $N^{2}$ is also a palindrome iff $\sum_{i=0}^{n}a_{i}^{2}\leq9$ .

Proof.

$b_{n}=\sum_{i=0}^{n}a_{i}a_{n-i}=\sum_{i=0}^{n}a_{i}^{2}$ .

($\Leftarrow$ )

$b_{n}\geq b_{k}$ for every $k$ by Cauchy-Schwarz inequility.

($\Rightarrow$ )

Trivial.

In particular, if $N\neq3$ , then $a_{i}\in\left\{ 0,1,2\right\}$ .

4 Problem D. Treasure

Let $T\subseteq\mathbb{N}$ be the set of all key types. Assume $0\notin T$ .

Construct a directed graph $G=\left(V,E\right)$ as following:

• $V=T\cup\left\{ 0\right\}$
• $\left(0,j\right)\in E$ iff we starts with at least one key of type $j$ .
• If $i\neq0$ , then $\left(i,j\right)\in E$ iff there is a key of type $j$ in a box of type $i$ .$b_{n}\geq b_{k}$ for every palidrone $N$ by Cauchy-Schwarz inequility.

Denote by $B\left(i\right)$ the number of boxes of type $i$ and $K\left(i\right)$ the total number of keys of type $i$ (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Proof.

($\Rightarrow$ )

If $B\left(j\right)>K\left(j\right)$ , then we don’t have enough keys of type $j$ to open all boxes of type $j$ .

If there is no path from $0$ to $j$ , then it means we are unable to get any key of type $j$ .

($\Leftarrow$ )

We prove this by induction on the number of boxes. Denote by $N$ the number of boxes.

Assume for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Case $N=1$ :

Then all vertices in $G$ are leaves except $0$ and the type of the only box. So there must be an edge from 0 to the type of the box.

Case $N>1$ :

Suppose the theorem holds for the case with $N-1$ boxes.

There are at least one $\left(0,i\right)\in E$ . Consider we open a box of type $i$ (that contains a key of type $i$ if possible). Assume we destroy the key and the box just opened, then we have a setting of $N-1$ boxes. In this setting, we still have $B\left(j\right)\leq K\left(j\right)$ for all $j$ . Let $G'=\left(V',E'\right)$ be the directed graph of this $\left(N-1\right)$ -box setting.

If $B\left(i\right)=1$ , then all children of $j$ in $G$ become children of $0$ , $0$ can still reach all other types in $G'$ .

Assume $B\left(i\right)>1$ .

If $\left(i,i\right)\in E$ , then we can open a box of type $i$ that contains a key of type $i$ .

Otherwise, because $K\left(i\right)\geq B\left(i\right)>1$ , we still hold at least one key of type $i$ after we open a box of type $i$ (and destroy the key).

Either way, $\left(0,i\right)\in E'$ . Therefore, for every child $j$ of $i$ in $G$ , either

1. $\left(0,j\right)\in E'$ (if a key of type $j$ is in the box we just opened), or

2. $\left(i,j\right)\in E'$ and so there is a path from $0$ to $i$ and then to $j$ .

So $0$ can still reach very vertex in $G'$ .

By induction hypothesis, the remaining $N-1$ can also be opened.

  

  

By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.

However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.

The solve the problem, you should open the box with smallest number such that either this box is the last one of type $i$ or there is still a way to get a type $i$ key.

---

Document generated by eLyXer 1.2.5 (2013-03-10) on 2013-04-16T11:23:46.409386

Py Girl 3rd try

Py Girl  impersonate (or perhaps it counts as cosplay) Haruhi Suzumiya.

 Anime style.

Black white manga style.

Blender renderd and edited in gimp

Project Euler Problem 198

Original post in Chinese: 2008/06/project-euler-198.html

Project Euler Problem 198 asek you to find all ambiguous numbers between 0~0.01 with denominator no more than 10^8, where by definition, a real number x ambiguous, if there is at least one denominator bound m for which x possesses two best rational approximations. For example, let x=9/40 and m=6, then 1/5 and 1/4 are both best rational approximation of x with denominator no more than 6. Clearly, an ambiguous number is necessarily rational.
This seems to be difficult if you don't have certain number theory background knowledge. On the other hand, if you do have the certain knowledge, you may think 10^8 is kind of too small for a Euler project problem. IIRC, you can find a nice algorithm in Knuth's The Art of Computer Programming.
However, it is pretty straightforward to solve it by recursion using Haskell:

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)

As easy as 7 lines of code, yet the code is a pretty straightforward translation of the mathematics behind it. However, using Python to solve it is a totally different story. The above recursion exceeds the limit of numbers of function calls in python. The following is a loop based solution:

def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2

The code is directly copy from the code I gave on Project Euler website, so it does not look good.
With the help of psyco, it is fairly fast, but is not very readable by human and can not be considered as a straightforward interpretation of the mathematics behind the problem.
On the contrary, doing some easy tasks in Haskell is not so elegant. For example, suppose we want to find the integer part of the square root of an integer n, and then print it on the screen. Doing this task in python is as simple as you can imagine.

print int(x**0.5).

To do this in Haskell, you will have to convert the integer n to a float point number, then take square root, then take floor, then covert it to an integer, and then convert it to a text before it is ready to print on screen.

putStrLn.show $ (floor . sqrt) (fromIntegral n)

If there are a lot of float point numbers and integers involved, then you probably need to do the coversion every here and there in your code. I know that those conversions exist for a good reason, however, sometimes you just fell like to do a quick and simple computation.
Sure Haskell can make complicate tasks simple and make simple tasks complicate.

Py Girl, 2nd try

Looks a bit better than the first try, but still not quite there. 

 It is created using blender + freestyle like before. I also use gimp to auto balance the color. The original blender rendered image can be found below.

The basic idea of this image is inspired by Nüwa and Zhao Ling'er, as suggested by Jenny JS Liang.
The background image features a landscape painting of Fan Kuan.

The .blend  file can be downloaded at  Blend Swap.

Blender Renderting Time (On computers available to me)

This a simple test of  of the rendering time of  blender internal render.
I was curious how Xoom or Azure compares to my desktops and laptops. However, running blender in the chrooted ubuntu of  my xoom causes a segment fault ( for both the ubuntu blender and a 2.66 blender compiled by me).

The test .blend file is my Python Girl video.  The video has 800 blender rendered frames (frame 600 - frame 1400). But in this test, only one of every 4 frames between frame 1250 and frame 1346 are rendered. We measure the difference between the modified time of 1250.png and 1346.png.

The blender used in this test is freestyle branch. On windows,  a 32bit executable is used. 64 bit binaries are used on linux and OSX.
The followings are the results：

• Core i7-2700 Ubuntu 12.10: 19min 16sec
• Azure extra large 8 core Ubuntu 12.10:  32min 45sec
• Core 2 Quads Q9500 Win7: 53min 8 sec
• Macbook Air Core i5-3317u: 60min
• Win8 Core 2 Duo T5600: about 3 hours (I had a train to catch, so unable to finish the rendering)

The segment fault on  Xoom could be caused by kernel incompatibility or because Xoom does not have enough RAM. But compiling blender on Xoom took like 10 hours while compiling on my Core i7 desktop took only 10-20 minutes.
If possible, it would be interesting to run the same test on an ipad, iphone, EC2,  raspberry Pi, or high end android phone like HTC One, Butterfly, or may padfone infinity, S4.

The Life of Py : Girl Py Debut

 

Girl Py or Python Girl is an anthropomorphic character of Python programming language. The original purpose of this character is to promote PyCon Taiwan.

Most tools used to create Girl Py are python related.

The main tool is Blender with freestyle, which is no doubt a python related 3d rendering and modeling tools.

The body of the character is created using Makehuman. Makehuman contains a lot of Python code, in fact, the version I used is the pure python branch. Makehuman is designed for modeling realistic human bodies instead of manga style ones. Fotunately, makehuman support customized skin and target. I made a manga skin and manga target for it. The result of first draft looks like the following.

The hair color is actually black, but the light was too strong, so it looks very pink.

The face generated by my manga target is kind of ugly and scary, but does not look that bad with smooth modifer.

After playing with makehuman and blender awhile, I was getting more familier with these tools and improve the target a bit.

It looks less scary and more smooth now but still ugly.

After adding some manga style material, it looks like the following

Still not good. Because of the time constraint, I decided to model the face by blender directly instead. Using the models list at the end of the video as reference and inspiration, the result is the following:

It looks like this in Blender's opengl view

The python code featured in the video is PyLottery of PyCon Taiwan 2012, which generates an animated snake to fetch random lottery balls.

Other software used in this project are OpenShot and gimp, all python related.

The next image is the credit at the end of the video

PyCon Taiwan 2013 is Calling for proposals, you are welcome to submit your proposals.