Impressive gaming: World of Goo

In order to fight off murderous tendencies while doing taxes, I play video games. This year, I played one game on my Android phone: The World of Goo.

Wikipedia claims that this is a physics-based puzzle game, but that is as accurate as describing chicken tikka as a dead bird. The World of Goo is a brilliant adventure game, told through many levels that involve tiny balls of Goo. The balls start out sticking together, and new levels add interesting capabilities. There is a single objective in every mission, usually collecting a fixed number of Goo balls towards a pipe. (To be fair, Wikipedia has a scary long page about the game. What they lack in humor, they make for in actual content and facts.)

A few years ago, I was saddened by the lack of inventiveness in new games. It seemed that every game was about the same boring plot: there were certain genres and everyone stuck to tried and tested mechanics. Walking through the aisles of a computer store, you could quickly categorize each game into a few genres: RPG, strategy, platform, with little that set the individual games apart. Compared to this, the early days of gaming were filled with creativity as programmers experimented with computers to create something fun and unique.

That wasn't the only problem. I use Linux and many games do not work on my system. Even when had the luxury to install Windows on one partition, games required registration codes and other fiddling just to get working.

In such unhappy times, I came across the demo for World of Goo. There was a Linux version, and I played one level or two and loved the idea behind the game. The game was refreshingly new, with goo balls sticking to one another and making cute sounds when they reached the destination.

For one reason or another, I put off the purchase and then promptly forgot about it. A few weeks ago, I finally bought the first Indie bundle on Android and downloaded my copy of World of Goo. It was as refreshing and enticing as I remembered it, and so I installed it on my Android phone.

Tax week was a whirlwind of administrative paperwork and an ill baby. In between copying numbers from one dull form to another, I was holding my child as he slept clinging to me. My hands were free, but I wasn't coherent enough to do anything productive. My phone was nearby, and the opportunity was perfect for the World of Goo. After a few hours over many days, I finally finished the last level. And I cried because I had no more goo world to conquer. That's how good the game is.

The game has exceptional level design. Most game developers fall in the trap of coming up with a single idea for a game: developing the engine and then churning out levels one after another. In such games, the fun dries up quickly after the first few levels. The game gets devilishly hard and the levels just get tougher. New levels are more challenging, but no more rewarding. Level two is level one, but with less time and fewer resources. That's not fun, that's a chore. In Goo, you go through different scenarios, changing weather and different kinds of goo balls. The game mechanic changes as you tackle new levels. This reminds me of Soul Bubbles for Nintendo DS, which had the same change of mechanic as the game proceeded. I'm glad the developers resisted the urge to copy-paste levels. I'm glad they spent as much time in innovative levels and level mechanics as they did on the creativity of the engine. The levels are inventive, they keep you eager to see what happens next.

As the game proceeds, the story of the goo balls unravels and takes the player through its strange and  humorous turns. World of Goo does a lot of things well, and is an instructive lesson to the cesspool of current-day gaming.

1. Creativity counts. Come up with something unique. Computer worlds are limitless, so don't package the same crap all over again.
2. Entertain in every level. Each level should be fun to play. Doing the same thing twice isn't fun.
3. Leave no player behind. Goo allows you to skip baffling levels rather than requiring your user to fight through tough levels. They can always come back for levels later. This makes the game more fun and accessible.
4. All the fun ideas, and nothing else. The game is small, but it is fun all along. That is far better than padding a game with mediocre content to increase the length.

The game is half a decade old, but is well worth playing.

What is inside electronic devices?

Not many people see the insides of electronic devices. Here is a picture of a Linksys E-1200 router:

If you compare this with electronic boards made a decade ago, the emptiness of the board would strike you immediately. Most of the board is empty space and two black chips dominate the real estate. The remaining components are minor: resistors and capacitors.

There are two big black chips in the center of the board. In order of appearance from left to right are:

1. Winbond W9425G6JH: That's memory, storage, or RAM.
2. Broadcom BCM5357B0: That's everything else: CPU, wireless, ethernet, router. Everything

The fat black things in the bottom look like chips but they are not. The FPE 2020 are tranformers for electrical isolation of the ethernet signal.

Everyone knows that computers getting faster, smaller, more durable and more cost efficient. The silent revolution is in the ubiquity of computers. Tiny computers are everywhere. The desktop was once the only computer in the house. Then came along the laptop, then the smart phone. Then your television set-top-box. Routers, ebook readers, the telephone box to give you cheap international calling. Deep inside, all these devices are empty boards like the one above. One powerful chip containing a computer to do everything.

The other important fact is that these are a full, general-purpose computers. You can run browsers, games, and email programs on these computers. Manufacturers make a board with a general computer and then write router software for it. This method is cheaper than creating a specialized router-only computer. A router is very similar to a television set-top box: they both contain roughly the same parts. The only difference is in the software.

We are getting better at manufacturing these full computer chips: they cost less, last long, and fail less frequently. It is not unusual to run these computers constantly for years. This astonishing reliability is one reason why the repair industry is dying. The other reason is that there isn't much left to repair. Boards contain few parts, and if a CPU or RAM chip goes bad due to overheating or electrical surges, it is nearly impossible to repair it.  And capacitors and connectors fail much more often than CPU and RAM chips. Since there is nothing mechanical left to fail, and the failure rate of silicon components is low, electronic boards provide decades of service.

Another trend to notice is that many of these devices run Linux. Linux has many benefits: it is free, it has support for a wide variety of these new computers, and it is easy to modify.

(Image courtesy Wikia.com)

Book Review: The Continent of Circe by Nirad Chaudhuri

Want to read a possible theory about Hindus and Hindu behavior? Read the confusing book, "The Continent of Circe", by Nirad Chaudhuri.

"The Continent of Circe" is a book published in 1966 by Nirad Chaudhuri. He grew up in Bengal and writes about the Indian freedom struggle. His views are very different from mainstream views about India. He differs from both Western authors and Indian authors, which makes his writing unique. Some of the arguments made in this book are

1. There is no religion called Hinduism. This is a name given to a group of people from a specific region.
2. The Muslims and Hindus in India are completely different people. Conversions and intermarriages have done little to change the stock and behavior of the people. The two groups distrust one another and the relations are deteriorating over time.
3. The Hindu caste system was the Aryan way of assimilating the local groups. It was never a barrier to professions, and that it might have done some good in maintaining social order and regulating competition between the competing groups: priets and warriers at the top were Aryan and the lower classes were local merchants.
4. Hindus live among contradiction: (a) they espouse non-violence while their history is replete with butchery (b) they have a grand view of themselves while also professing humility (c) they hold a view of their unity while being deeply fragmented and divisive.
5. The Indian weather molds Indian (specifically Hindu) behavior.
6. Hindu thought is rather simple, and written analysis of Hindu thought makes it more profound that it really is.

That's as far as I made it through the book. As you can tell, some of the arguments are correct and obvious while others are strange and need explaining. Explanations are provided, though the language in the book is bizarre and complex. For one, the essays appear unedited. The language is complex, sentences are long and winding. The author rambles on, and paragraphs are disconnected and dry. Every other paragraph has some foreign phrase which makes it doubly hard to understand the intent. Here is a typical sentence:

Today, as an old man I would say that I have seen so much of this feckless tragedy of Hindu life on this green earth and under the blue sky, that the moment I see any sign of the Hindu dementia in me, I shall cry out, "Nunc dimittis..."

Entire passages from foreign languages are quoted. I gather there is some French, German, Latin involved, and I'm glad the typesetter did not have Cyrillic or Japanese or Chinese characters. I don't know what to make of the strange writing style and the profusion of Latin. I'm sure the words "De rerum indicarum natura: exempla gentium et seditionum" appeal to learned people. An illiterate villager like me has no idea what the hell just happened.

Is it pretentious writing? Did everyone write like this in 1960? Or am I too dumb to understand it?

One thing is certain. Nirad Chudhuri was original. He sees the vast difference between Indian and Western behavior and tries to explain the difference. He isn't pandering to either group: his observations are brutally honest and his analysis is equally impartial. The standard Indian reaction to him is to call him prejudiced and bitter. I don't agree with that. His brutal honesty hurts Indian sentiment. Indians prefer objectivity to be coated with lots of warm love about Indian greatness. Nirad Chudhuri also points out the poor aspects of Western behavior. His praise and condemnation is showered on both groups equally.

Read him, if only to see how honest and unabashed an Indian author can be.

(Image courtesy ManasTech's blog.)

Project Euler in R: Problem 26

I have been posting R solutions to Project Euler problems as a way of polishing my R skills. Here is the next problem in the series, problem 26. The problem is stated as follows:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle. Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

The first task is to define a function that returns the cycle length of 1/n for any input n. The function logic is pretty simple.  We compute all the remainders in the long division of 1 by n. The moment we encounter a remainder that has been seen before, we know that the fraction has a recurring cycle and can compute its length.

recur.length <- function (n) {
  x = 1                             # Starting with the numerator 1
  remainders = c(x)
 
  repeat {
    x = (x*10) %% n                   # Find the remainder
    if (x == 0) { return (0) }        # Fraction terminates, so cycle length is 0.
    if ((x %in% remainders)) {break}  # Repeating remainder is found. Break from loop.
    remainders <- c(remainders, x)    # Else add remainder to list.
  }
  return (length(remainders) - which(remainders == x) + 1)  # Exclude non-repeating part of the decimal
}

The above code demonstrates the use of the less common but simple repeat loop.  R doesn't have a do-while, so repeat with a break is a perfect way to imitate such a construct.  You can read more about R control-flows here.

Using the recur.length function we find d < 1000 with the largest recurring cycle. The following insights that make our search pretty efficient

• A number d can have a recurring cycle of at most d - 1.  This is because modulo division by d can have only d unique remainders (0, 1, ..., d-1), after which we will necessarily find a remainder that repeats. One of these remainders is zero, and if we get this, no recurrence is possible. 
• Due to the first observation, larger values of d will possibly have larger cycle lengths.  So it is faster to searching from 1000 down to 2, rather than from 2 up to 1000.
• Searching down from 1000, say we find a recurring cycle of length k.  Now we know that the smallest number that we need to check is k + 1.  This is because the numbers smaller than k + 1 (that is 2 to k) can only have cycle lengths of k - 1 or less.

Based on the above, here's a function to find the d with the largest recurring cycle. 

longest <- function (n) {
  maxlength = 0       # Maximum recurring cycle
  maxd = 0            # d with the maximum recurring cycle
 
  # Check all numbers between low and i for a longer cycle length
  low = 2
  i = n
 
  while (i > low) {
    ilength = recur.length(i)
    if (ilength > maxlength) {
      maxlength = ilength
      maxd = i
      low = maxlength + 1           # The candidate must be > = low
    }
    i = i - 1
  }
  maxd
}

The search is efficient and takes only 0.15s on my Intel Core 2 Duo 1.6Ghz laptop running Linux.  Discussion threads suggest limiting the search to prime numbers, but I'm not sure if this would be much more efficient.  The gains in the reduced number of candidates would probably be offset by primality tests. It is amazing how small this code is. R handles most of the array handling and searching through a vector.

Code formatted by Pretty R at inside-R.org

Project Euler in R: Problem 25

Solutions in R to Project Euler problems are generally hard to find, so I've recently started posting R solutions on this site.  Here are the previous problems: problem 22, problem 23 and problem 24

Now let's look at Problem 25 from Project Euler.  Here is the problem statement:

The Fibonacci sequence is defined by the recurrence relation: Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
...
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits. What is the first term in the Fibonacci sequence to contain 1000 digits?

This is an easy problem to solve for a small number of digits. It gets interesting once we increase the required number of digits to 1000. The R integer type can hold 10 digits at most, and the type double can hold 309 digits.  There is no Big Integer class in R that can hold larger numbers, so to compute the 1000 digit Fibonacci number we will have to be creative.

Computing Fibonacci numbers iteratively

Here is a basic iterative Fibonacci function, that works for Fibonacci numbers with 309 or fewer digits.

fib <- function(n) {
  a = 0
  b = 1
  for (i in 1:n) {
    tmp = b
    b = a
    a = a + tmp
  }
  return (a)
}

The version that works with larger numbers is similar, with the following changes

• Integer vectors are used to store each Fibonacci number.
• Each element of the vector is at most nine digits long.  
• Once all the nine digits are used, a new element is added to the vector and the Fibonacci number computation is carried over to the new element.
• The variable numberDigits counts the number of digits in the latest Fibonacci number.  When numberDigits exceeds 999, the function exits, returning the Fibonacci number index.

fib.bigint <- function(lim) {
  a = c(0)
  b = c(1)
  n = 0           # Fibonacci number index
  integerSize <- 1000000000  ## How big is each integer
  while (1) {
    n = n + 1     # Compute next Fibonacci number
    tmp = c(rep(0,length(a)-length(b)), b)  # Pad beginning with zero
    b = a
 
    # Add a and tmp
    carry = 0
    for (i in length(a):1) {
      sum.i = tmp[i] + a[i] + carry
      a[i] = sum.i %% integerSize
      carry = floor (sum.i / integerSize)
    }
    if (carry > 0) {a <- c(carry, a)}
    numberDigits <- (length(a) - 1) * 9 + countDigits(a[1])
    if (numberDigits > (lim - 1)) { return (n) }
  }
}

countDigits <- function(n) {
  count <- 1
  for (i in 1:9){
    if ((n/10) > 1) {
      count <- count + 1
      n = n / 10
    } else {
      return (count)
    }
  }
}

On my Intel Core 2 Duo 1.6Ghz laptop running Linux, this function less than 4 seconds to find the Fibonacci number with 1000 digits.

The analytical solution
Fibonacci numbers have a closed form solution, which leads to a simpler approximation by rounding (from Wikipedia),

F_n = the closest integer to (golden ratio)^n / sqrt(5) 

We need the first Fibonacci number with 1000 digits.  This number will be greater than or equal to 10^999.

F_n = the closest integer to (golden ratio)^n / sqrt(5) >= 10^999

We can drop the closest integer function because if F_n rounds off to the floor of the ratio, the resulting Fibonacci number will have less than the required digits.  So we need smallest n satisfying

(golden ratio)^n / sqrt(5) >= 10^999 

Or, n >= (999 log(10) + log(sqrt(5)))/log(golden ratio) 

Or, n >= 4781.86

So we need the 4782nd Fibonacci number to get the required 1000 digits.

This problem was particularly interesting to R users because it runs into an R-specific limitation. Many other languages don't have this problem and can just use a simple Fibonacci generator to get the answer. For example, in Scheme (or other Lisp variants), a naive Fibonacci implementation produces all the digits.

Aside: Having started writing about R, I have found an excellent online resource, R-bloggers -  an aggregator of content from various blogs about R. You can search for other R Project Euler solutions here.  Be sure to check out the top articles box on R-bloggers landing page if you're looking for new and interesting applications of R.

Project Euler in R: Problem 24

I had previously posted solutions in R to Project Euler problem 23 and problem 22.  This is the next problem from Project Euler. The statement of problem 24 is as follows.

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This is a very interesting problem and it can be solved analytically. The key insight is that n distinct digits can be arranged in n! permutations.

Here's the logic you could use. If the permutations of the numbers 0 through 9 are arranged in lexicographic order,

• The first 9! permutations, #1 to #362,880 are numbers starting with 0, in order from 0123456789 to 0987654321
• The next 9! permutations, #362,881 to #725,760, are numbers from 1023456789 to 1987654320
• The next 9! permutations, #725,761 to #1,088,640  are numbers from 2013456789 to 2987654310.  The millionth permutation is contained in this set.  Thus we know that the millionth number must start with a 2.  In fact, it is the 274,240th = (1000000 - 725760) number contained in this set.
• Our problem has now reduced to finding the 274,240th lexicographic permutation of the numbers 0, 1, 3, 4, 5, 6, 7, 8 and 9 - the nine digits excluding 2.  We can repeat the above process to get each successive digit.

Essentially we're writing one million as the following sum

1000000 = (a1 x 9!) + (a2 x 8!) + ... + (a10 x 1)

As shown above, the index a1 is 2.  That is, only two times 9! numbers fit perfectly within 1,000,000.  So the first digit of the millionth number is the third digit in 0123456789.  The index a2 is 6, so the second digit of the millionth number is the seventh digit of the remaining numbers 013456789, which is 7.  The remaining digits can be found similarly. While finding the digits you have to be careful to ignore the digits that have been previously used. This is a permutation, so each digit appears exactly once.

The process is tedious, so here is some R code that will make it easier.  This generalizes the solution to find the nth permutation of the numbers 0 to 9.

findperm <- function (n) {
  # Find the indices a1 - a10
  indices = c()
  for (i in 9:0) {
    index = 0
    while (factorial (i) < n) {
      n = n - factorial (i)
      index = index + 1
    }
    indices = c(indices, index)
  }
 
  # Use the indices to find the nth permutation
  input = 0:9                         # The list of numbers to permute
  output = c()
  for (j in 1:10) {
    output[j] = input[indices[j] + 1] # Move digit to output
    input = input[-(indices[j] + 1)]  # Remove the assigned digits from input
  }
  return (output)
}

That was straight-forward and a fun illustration of R's capabilities.

But you can do better. The strength of R lies in the wealth of user defined libraries and functions that can ease the implementation of tricky computation.  For a simpler solution, try the lexicographicPermutation function in the library R.basic. Here is the entire solution.

library(R.basic)
lexicographicPermutation(c(0,1,2,3,4,5,6,7,8,9),999999)

The first solution illustrates that even tricky computation can be coded easily in R and the code is pretty readable.  The second solution suggests that before writing your own code, it is a good idea to look for existing libraries that can help. Statistical computations can get complex and tricky. You can write your own k-means clustering algorithm but it is difficult getting all the edge cases correct. Rather than writing your own routine, look around and see if it has been written already. An expert does a better job writing such routines. And you can leverage their code and their expertise.