2011-01-15 front | Hacker News

Minecraft’s story is even more impressive than the article makes it seem. The game was not developed by a few people, it was developed by one guy (“Notch”). He hired six people only recently and they started working together around Winter 2010/2011.

He now gets help with the business and support side of running a company but only one of the developers he hired is working on the game with him together. The other developer is getting their next game up and running.

What’s also interesting is that Notch does not want to run the business, at least not at the scale at which it is now. He hired people to do that for him.

edw519 on Jan 15, 2011 | parent | context | on: Programmers think differently than non-programmers

Programmer's Aptitude Test (Don't scroll down until you're done.)

  1. You push your cart through the supermarket
     a. In a pre-defined manner
     b. Randomly
     
  2. When watching football on TV, you focus on
     a. the quarterback
     b. the defensive linemen
     
  3. You drive to work
     a. the same route every day
     b. with a different route every once in a while
     
  4. Which card game do you prefer?
     a. bridge
     b. poker
     
  5. To plan for tomorrow's weather
     a. You check the TV or internet.
     b. You go outside, looking for signals.
     
  6. Who do you prefer?
     a. Andrew Carnegie
     b. Marie Curie
     
  7. You prefer
     a. your keyboard
     b. your mouse
  
  8. Which subject do you prefer?
     a. history
     b. literature
     
  9. Which would you rather do?
     a. take a walk in the woods
     b. a crossword puzzle
     
  10. Which is more important to you?
      a. time
      b. space

Answer: If you tried to figure out (game) the test as you took it, you have a programmer's aptitude. If not, you don't, and probably don't even understand this answer.

ximeng on Jan 15, 2011 | parent | context | on: Why pi?

It gets going after the first 2 minutes, not many digressions, pretty much pure maths lecture. Summary below of the first hour or so if you want it, might be hard to follow, but it shows the depth of the lecture pretty well.

He will establish a link between Pi and factorials, as well as trees, using generally simple maths.

---

The number of (ordered) forests with n nodes:

n=2 - 2 forests [o, o; o (o)], where , separates trees within forests, ; separates forests, () indicates child node

n=3 - 5 forests [o, o, o; o, o (o); o (o), o; o (o) (o); o (o (o))]

In general the number of forests with n nodes is Cn where Cn is the nth catalan number. For n=0..4, Cn=[1, 1, 2, 5, 14].

The nth catalan number is C(n):=((2n)!/n!(n+1)!). E.g. for n=3, 6!/(3!4!)=5.

It turns out that:

C(n) approx= Exp(4,n)/(Sqrt(npi)(n+1))

For n=1000, the first 4 significant figures match in a number with 598 digits.

Johan Wästlund published a result explaining the link between Pi and trees in Dec 2007.

---

Problem inspiring JW's investigation is biasing two dice (changing their probability) so that 2..12 are all equally likely.

To do this set the probability of two 1s to x. This is the probability of rolling a total of 2.

Now the probability of a total of 3 is the probability of a 1 and a 2, times two. So we want the chance of rolling a 2 to be half the probability of rolling a 1.

Similarly the probability of rolling a total of 4 is the probability of a 1 plus a 3 times two, plus the chance of two 2s.

If we set p1 = probability of a 1, p2 = probability of a 2, ...

(1) p1p1 = p1p2 + p2p1 (since a total of 2 is as likely as a total of 3) => p2 = p1/2

(2) p1p1 = p1p3 + p2p2 + p3p1 = p1p3 + p1p1/4 + p3p1 => p3 = 3p1/8

(3) ... p4 = 15p1/16

(4) ... p5 = 35p1/128

(5) ... p6 = 63p1/256

This set of probabilities satisfies the original problem up until a total of 6.

( ^ ) Note the constants are: 1/2, 1/2 3/4, 1/2 * 3/4 * 5/6, 1/2 * 3/4 * 5/6 * 7/8.

( ^^ ) Proof of this: Let pj=a(j-1)p1. We have a0=1, a1=1/2.

Form an infinite series, A(z)=a0+a1z+a2Exp(z,2)+a3Exp(z,3)+... Square it: Exp(A(z),2)=a0a0+(a0a1+a1a0)z+(a0a2+a1a1+a2a0)Exp(z,2)+... This equals 1+z+Exp(z,2)+Exp(z,3)+... (by hypothesis, ajp1=p1 for all aj), which is just a geometric series with total 1/(1-z).

(+) So A(z) = 1/(sqrt(1-z)) = Exp(1-z,-1/2). Using binomial theorem, this equals

Sum(n=0..infinity) of (-1/2 choose n [binomial coefficient])Exp(-z,n).

an=(-1/2 choose n)Exp(-1,n)

E.g. a3= (-1/2 - 3/2 - 5/2)/(3 2 * 1) * Exp(-1,n) = (1+3+5) / (2 * 3!), which is the result we had above at ( ^ ).

( ^^^ ) We know p1+p2+p3+p4+p5+p6=1 as the dice are six-sided. This gives p1p1(a0+a1+...+a5) = 1 (see ( ^^ )). So what's a0+a1+...+a5?

Take A(z)(1+z+Exp(z,2)+...) = a0+(a0+a1)z+(a0+a1+a2)Exp(z,2)+... . Let's call this S1 + S2z + S3z + ... . Then we want to find S6 = a0 + ... + a5. Remember that p1p1s6=1 from ( ^^^ ).

Well by (+) A(z)(1+z+Exp(z,2)+...)=Exp(1-z,-1/2) (1+z+Exp(z,2)=Exp(1-z,-1/2) Exp(1-z,-1). This is just Exp(1-z,-3/2).

Expanding that, we have Sum(n=0..infinity) of (-3/2 choose n)Exp(-z,n). The - signs cancel out again.

Let's work out the values of Sn: S1=1, S2=a0+a1=3/2, S3=a0+a1+a2=15/8=3/2 * 5/4 ... and S6=3/2 * 5/4 * 7/6 * 9/8 * 11/10.

Picture here:

  6zzzzzz
  5""""""zzzzz
  4oooooo"""""zzzz
   xxxxxxooooo""""zz
  3xxxxxxooooo""""zz
   ######xxxxxoooo""zz
  2######xxxxxoooo""zz
   ######xxxxxoooo""zz
   ......#####xxxxoo""z
   ......#####xxxxoo""z
  1......#####xxxxoo""z
   ......#####xxxxoo""z
     1      2   3  4 56 (each number j has width / height a(j-1)), total width = S6)

This is meant to be symmetric around x=y. Each different character represents a different total. All these areas are the ones we've been trying to make the same: "." is the probability of getting a total of two on two dice. "#" is the probability of a 3 total, and so on. It gets closer and closer to a circle.

So this is the link to the circle. If n is the area shown in the diagram above, we have n approx= (pi/4) Exp(Sn,2), since this is a quarter of a circle with radius Sn. We want to prove the circle goes through the rectangles just outside the edge, if so we can show that n - 1 < (pi/4) Exp(Sn,2) < n + 1 (!) . This is because we are setting the area of each total (i.e 2..7) to be 1, so adding an extra total (which looks more and more like a circle as n gets bigger) will just add one to the total, and we are going to prove an ideal circle would go through the outer rim (e.g. the "z"s in the diagram above).

Let's look at some examples.

Exp(S6,2) = Exp(3/2,2) * Exp(5/4,2) * Exp(7/6,2) * Exp(9/8,2) * Exp(11/10,2) from above.

Exp(S9,2) = Exp(s6,2) * Exp(13/12,2) * Exp(15/14,2) * Exp(17,16,2)

Note Exp(1+1/2k,2)=1+ 1/k + 1/(4Exp(k,2)) > 1 + 1/k

So Exp(S9,2) > Exp(S6,2) (1+1/6)(1+1/7)(1+1/8) = Exp(S6,2)(7/6)(8/7)(9/8)=Exp(S6,2)(9/6) by cancelling. He also proves that Exp(S9,2) < Exp(S6,2)(8/5).

In general Exp(Sa,2)(a+b)/a < Exp(s(a+b),2) < Exp(Sa,2)((a+b-1)/(a-1)). From this inequality (ineq), he can prove his result on the approximate value of Sn, (!) above.

He wants the circle of radius S6 to go outside the inner most notches in the diagram (between " and z in the diagram above). Note that these coordinates (S5,S1), (S4,S2), ... . By Pythagoras we want Exp(Sk,2) + Exp(S(n-k),2) < Exp(Sn,2) < Exp(Sk, 2) + Exp(S(n+1-k),2), this follows from his inequality (ineq) above.

(Incidentally you can do the same construction with 3 dice forming a ball, there is a picture at 56:00 which I won't try to reproduce in ascii.)

---

So we now have a relationship between Sn and Pi, Sn approx= 4n/Pi. Also Sn is a sum of values of an, which are just (1/2) (3/4) ... (2n-1/2n). Finally Sn=2nan (not quite sure why??). From all this we can get an=1/(Sqrt(Pin).

The number an is famous in connection with a random walk of length n. The probability of flipping a coin 2n times and getting equal number of heads and tails is an. This probability is (2n choose n)/Exp(2,2n). But (2n choose n) is just ((2n) (2n-1) ... 1) / (n! n!), which is just an an above.

Rather than a coin, he takes the binary digits of pi/4 as heads and tails:

   .11001001...

This looks like this (- marks 0)

     x
    x x x
   x---x-x-x- etc.
          x x
             x
              x

We know Sum(ak, a(n-k))=1.

This is equivalent to (apparently!) Sum((2k choose k) * (2n-2k choose n-k)=Exp(n,4)

(A digression here on "balanced random walks" and the links to 2d barcodes like QR-codes. You decompose a finite random sequence of bits like the bits of pi, into two parts. The first part is the sequence up to the last point the sequence crosses the origin, this part is balanced. The second part diverges from zero and needs to be balanced by flipping some bits according to a "Christmas tree pattern".)

--- c. 1h15m in at this point.

It gets a bit sketchy from here, but he goes to the Stirling formula from here, which uses the Catalan numbers.