The Peak Traffic puzzle is easy to interpret. It is a graph problem to find all maximal cliques. Implementating it, like many graph problems, is quite difficult though. The possible combination is huge. And there is no simple ordering graph subset. It end up costed me several days to do it. Here is the outline of my solution:

1. Parse the input. Generate an undirected graph.
2. Generate a list of cliques using recursive algorithm.
3. Eliminate subsets from the result to find all maximal cliques.

After working on it for several days, I'm quite done. I haven't spent any more effort to optimize it and expain it. So here is my un-tidied code.

2010.03.03 [tech] - comments (0)

I was plotting a chart to visualize various development project in my area. The primary concern is in development density. But the project footprint itself is also a factor. We want to focus on big project that matters. We also want to identify outliers that has very high or very low density, but otherwise has small overall size and less relevance.

My solution is to use a variable with bar chart below. The height of each bar represents the density. The width represents the lot size. The area of each rectangle bar reflects the total number of units. The full article is posted in Potrero Boosters Neighborhood Association's website.

I thought everything that worth inventing has been invented. So I was frustrated that I cannot find a tool to generate this chart. Nothing in Excel (that I know) can generate a chart like this. I end up turning to matplotlib. But even matplotlib does not seem to have a function that support this directly. Fortunately a small twist to its histogram function does the job for me. See my (unpolished) source code here. In any case working with matplotlib is fun and the quality of the chart is excellent.

2010.02.26 [design] - comments (0)

Refrigerator Madness is the second Facebook programming puzzle I have tried. The problem description is complicated. I won't try to repeat it here but to suggest you to refer to the original facebook page.

To solve this problem it is necessary to see through the smokescreen. Instead of thinking how much Red Bull a Facebook engineer likes to drink, it is easier to map it to a problem known as Two-Sided Matching. A model with intuitive meaning is a marriage matchup between a group of man and woman. Each man has his list of preferred woman and each woman has her list of preferred man. The marriage is considered stable if there are no two people of opposite sex who were not married to each other but would both prefer to be.

For the Refrigerator Madness problem just map the engineer from the upper 50th percentile to "man" and lower 50th percentile to "woman" (or vice versa). The matching condition is equivalent to the stable marriage criteria.

At this point the problem can be solved by applying the Gale-Shapley algorithm. Write the code and it's done!

2010.02.22 [tech] - comments (5)

Facebook has published a number of programming puzzles to challenge software developers. Their problems are not trivial at all. This is my attempt on "Snack" level problem It's A Small World. Even this one take me sometimes to solve.

The idea is that there are n points on a 2-dimensional plane. For every point, we have to find the 3 nearest neighbors. The naive solution simply match all possible pairs, resulting in O(n²) complexity. The problem requires us to find a better solution than O(n²).

My idea is to divide the plane into a regular grid like below. For example, to find the neighbor of point A, we can focus on cell 2 in the center top and pretty much ignore the points in cell 9 in the lower right. This works very well if the points are randomly distributed. But if many points are clustered together like cell 9, it will work less well. We can recursively partition it into smaller region. But the basic plan should be suffice for this puzzle. The subdivision is a very simple O(n) process.

To search for the nearest neighbor, we start from points from the same cell. If this doesn't find the three nearest neighbors we extend into the neighboring cells. The pseudo code is shown below:

  result = None

  for step in 0...n

    cells = find cells "step" away from the source
    min_distance = minimum distance from source to the boundary of the cells

    for all point in cells
        insert distance(source, point) into result

    result = 3 closest points in result

    if there exists 3 points in result those distance < min_distance
        return result

  end for

Of course I'm not the first one to consider these algorithm. Wikipedia has some information on the Nearest neighbor search problem. My solution code is available here. (2010-02-21 Facebook's puzzle server is down. So the solution has not been validated.)

I have decided to put the algorithm into good use. I used it to generate a map of all sizable cities in the world and their nearest neighbors. With 20,000 cities a naive algorithm will need 400 million pairing. Using this algorithm only 10 million pairing are need. It is far from optimal, but good enough to handle Facebook's problem. Also I am curious to use it to find the loneliest city in the world, that is a city those nearest neighbor is the furthest away. Check the map to find out which city is the loneliest city in the world!

2010.02.21 [tech] - comments (1)

Last month the IT world is jolted by the news of a security breach of Google's system by Chinese hackers and the subsequence response by Google threatening to pull out their China operation altogether. Many in the west see this as a courageous resistance to China's Internet censorship and a righteous response to the assault on some human right activists. Other observers noted that Google's market share in China is trailing far behind the local competitor, that they may using this incident to give themselves a graceful excuse to exit.

All of them could have learned something from anthropologist Tricia Wang's insightful observation of Google's uses or non-use in China. Tricia is a research scholar working in China to study how youths and migrants are using ICT to manage their inter-personal communication networks. She come up with her observation from the angle of grassroot youngsters.

Among her observations are

• Google is mostly irrelevant to Chinese users. While elite, educated Chinese depend on Google as much as others do, young people has a very different usage pattern. They mostly use Internet with IM or mobile devices to connect to their friends. They have never found Google to be useful.
• Google has a huge branding issue in China. Most Chinese cannot spell the word 'Google'! I was amused to find that Google is known by its colloquial name GouGou (狗狗doggy) more than its official name Gu-Ge (谷歌). Here in the west, especially within the IT industry, Google's brand name stands for leadership in innovation and intelligent services. There in the back street of China, Google's name is associated with the lowly doggy. What a satire!

Tricia has an excellent piece of analysis that should be on most reader's radar screen.

2010.02.11 [tech] - comments (0)

Your walk in a cafe. You see everyone is working alone with their laptop. Nobody is talking to each other. Even the most ardent Internet junkie would admit they should have spent more time personally with other people rather than glue to the computer screen all day long. These cafe owner even try to setup rules asking patrons to log off and talk.

These moves are no doubt well intentioned. It will probably inspire many supporters. But why is so many people stick to their computer in the first place? It would be easy if we can determine that too much Internet is for sure a bad behavior, like watching too much TV. But what if it is true, that your second life is actually better than your first life?

2010.02.06 [philosophy] - comments (0)

Last month I've upgraded my first generation Mac Mini to Intel Core Duo. I have been bother by its wireless network issues ever since. It is a late 2009 model with Snow Leopard. It is connected to a Linksys WRT110 router. The problem is its poor reliability. Packets are dropped frequently. Sometimes it disconnects from the access point altogether. This means a very frustrating experience for some applications. VNC session are dropped frequently to the point it is unusable. Directory browsing and file transfer with Samba is a hit or miss. It unreliable and often incurs lengthy delay.

It seems mine is not an isolated problem. Wireless issue is a frequent topic on Apple support forum. I find many message like this one:

Topic : New Mac Mini Wireless Internet - Slow, Disconnects frequently

I use ping to test its connectivity. Pinging the gateway from the Mac gets result like below. There are plenty of missing packets.

64 bytes from 192.168.1.1: icmp_seq=7 ttl=64 time=1.219 ms
64 bytes from 192.168.1.1: icmp_seq=8 ttl=64 time=3.698 ms
64 bytes from 192.168.1.1: icmp_seq=9 ttl=64 time=3.862 ms
Request timeout for icmp_seq 10
Request timeout for icmp_seq 11
64 bytes from 192.168.1.1: icmp_seq=12 ttl=64 time=3.671 ms
64 bytes from 192.168.1.1: icmp_seq=13 ttl=64 time=3.766 ms
Request timeout for icmp_seq 14
64 bytes from 192.168.1.1: icmp_seq=15 ttl=64 time=3.997 ms
64 bytes from 192.168.1.1: icmp_seq=16 ttl=64 time=5.394 ms

Pinging the Mac from a PC, both are connected wirelessly, is even worst. Besides loss packets, the response time is pathetic. Sometimes it takes hundreds of millisecond.

Reply from 192.168.1.120: bytes=32 time=609ms TTL=64
Reply from 192.168.1.120: bytes=32 time=632ms TTL=64
Reply from 192.168.1.120: bytes=32 time=655ms TTL=64
Request timed out.
Reply from 192.168.1.120: bytes=32 time=97ms TTL=64
Reply from 192.168.1.120: bytes=32 time=1ms TTL=64
Reply from 192.168.1.120: bytes=32 time=93ms TTL=64
Request timed out.
Reply from 192.168.1.120: bytes=32 time=640ms TTL=64
Request timed out.

Note that this is not a wireless signal problem. I have moved the access point to only 15 feet away from the Mac with a direct line of sight. The test does marginally better at best. Besides, none of other wireless devices on the network have any connectivity problem.

After several false start using different suggestions from the Internet, I have found a config that dramatically improve the Mac's connectivity. I set the router to use Wireless-G only. The default of Linksys WRT110 is in "Mixed" mode. It includes some proprietary Linksys enhancement that none of my device can take advantage anyway. And it is not even Wireless-N. Setting it to Wireless-G only improve the Mac's connectivity with no loss of performance for other devices.

2010.01.26 [tech] - comments (0)

SF Appeal has published the Muni onboard video recording of the collision between a Muni #19 bus and a pickup truck on Jan 5th morning. The intersection is controlled by four way stop sign. Question has been brought about who's at fault. I have reviewed the video frame by frame. I come to a clear conclusion that the truck driver was at fault. While the bus driver technically did not made a complete stop, it has the right of way. The accident was caused by the truck running the stop sign at a high speed.

The four frames below captured the action during a span of 2.8 s until the moment they collided.

• Frame 1 - 00:02:34.22
• Frame 2 - 00:02:35.02
• Frame 3 - 00:02:36.02
• Frame 4 - 00:02:37.02

At frame 1, using the trash can as a reference point, it shows the bus was right at the intersection. The truck was about half a block away. It should be immediately obvious that the bus has the right of way.

At frame 2, the bus rolled forward. The truck was still some distance away.

At frame 3, the bus proceeded across the intersection slowly. The truck still have not arrive at the intersection. It should stop and yield to the bus.

At frame 4, truck ran the stop sign at high speed and caused the collision.

Base on the video frames, I plotted the estimated position and the movement of the vehicles during this 2.8 s on a map. I estimated the bus has rolled through the stop at 8 mph. In contrast, the truck has flown through the intersection from half a block away at 32 mph.

The verdict is clear, the truck driver was driving recklessly and caused the accident.

San Francisco Chronicle has published an article with the release video titled "Crash video shows bus, pickup ran stop signs". It implies they are equally at fault. I think this is wholly a mischaracterization by failing to unambiguously call out it was the truck's fault. The bus had the right of way. Actually had the bus made a complete stop the same accident could still happen.

2010.01.07 [San Francisco] - comments (3)

My niece was visiting us from Peru. So we had an active holiday week showing them around in San Francisco. She brought her 1 year old baby daughter along. I setup some old infant gear for her. It all worked out quite well. [more...]

2010.01.02 [personal] - comments (0)

I have a phone call with my dad this evening. We talked about some issues in handling of family properties. At the end of the conversation my father mentioned sometimes he feels he is counting days. He is in his mid-80s so it is not a complete surprise. Since my mother passed away last year my father is living alone. Actually this is something already on my mind, perhaps subconsciously. But we have seldom talked openly about it. [more...]

2009.12.28 [personal] - comments (0)

Monday is Tatchee's preschool's day off. I brought him to my office for a few hours so that I can work there. I brought the Totoro DVD to entertain him. And I also brought along some toy cars. One of them is his favorite police. I was worrying about its siren and the sound it can make. I warned Tatchee not to make noise it in the office. Once he was there he understood that noise is not appropriate and voluntary put this car away. Finally, I bring him along to an hour long meeting. He played quietly in the meeting room the whole time. People are fairly impressed by him. I'm happy that the day turned out quite well and he wasn't too bored. [more...]

2009.11.30 [personal] - comments (0)

I am off to a vacation to Perú shortly. I was hit by flu in the last few days. So my preparation is somewhat interrupted. I hope the trip will be smooth from now on.[more...]

2009.10.31 comments (0)

Last Saturday I have joined WalkSF in their annual Peak to Peak Walk. We gathered the starting point at West Portal. It was sunny when I took off from the east side. Who would have expected it was actually drizzling in West Portal! We headed out to the wood in Mount Davidson and then Twin Peaks and over a series of hills in San Francisco. When we have arrived on Twin Peaks, we were right at the edge of the morning fog. The scenery change from instance to instance. One moment we saw the Sutro Tower floating in the air, a moment later it was hidden by fog. I find such scenery magical. I have also visited the beautiful campus of USF for the first time. The walk ended in Coit tower where we have a small picnic. [more...]

2009.10.27 comments (0)

Jean de Florette / Manon des Sources (1986)
Director: Claude Berri [more...]

2009.10.18 [movie] - comments (0)

Yesterday's storm has caused quite a bit of havoc for me. It wasn't the first time we were out of power during a storm. But this time I saw the electric pole in front of my house exploded in a blindingly lightning. It continues 4-5 more times in the span of half an hour. Firemen has closed off our street because live wires were still dangling from the pole. We went out to the street with trepidation because we have to pick up our son from pre-school. I found there was a one foot deep flooded pond to wade through in order for us to go out. We are stopped from returned home for another hour until the PG&E people have arrived. The good things is PG&E restored the power by 9 pm. Also there seems to be no injury other than the damaged equipment. [more...]

2009.10.14 comments (0)

Last night I was in this unfortunate incident. I was walking in Mission when a young man behind me suddenly fell down, knocked himself unconscious and was bleeding on the street. I called 911 for an ambulance. This was perhaps the first time I use the emergency service. I gave the dispatcher my location. It was an small alley, those name I only come to know for the first time despite having walked by it many times. Nevertheless, the dispatcher immediately identified the street. This is all more impressive because I have mispronounced the street name. She sent an ambulance to the scene. It takes less than 5 minutes from the time I picked up the phone to the arrival of the ambulance. I saw the young man was getting help. I hope he was only drunk and suffer no more than a bruise on his face. [more...]

2009.10.07 comments (0)

The title of this precentation Data and Capital Markets in Money:Tech 2008 is not very obvious. It is actually an excellent presentation on the state-of-art of database design. Dr. Michael Stonebraker is behind a series of database innovation for several decades from INGRES and Postgres up to his current work on StreamBase Systems. In this talk he has criticized the traditional RDBMS as something woefully outdated. He has presented several new directions in database design that he think will soon upstage the current generation of RDBMS systems. [more...]

2009.09.28 [tech] - comments (0)

I've mentioned that I'm reading Richard Florida's Who's Your City. It explores the finding that innovation and creativity are often concentrated in certain region. The location a person lives has a great impact on one's life but people have often overlook this factor. I'm so interested in the topic that I have pick up some other related books as well as some book I've read in the past. I plan to do a summary on all of them shortly. [more...]

2009.09.23 [book] - comments (0)

You may have aware of the media buzz around the British government has made an posthumous apology to the mathematician and computer scientist Alan Turing, who despite of his contribution in World War II, was dishonored by the conviction of being gay in 1952. The government's apology is perceived as fair an uncontroversial, given Turing's monumental contribution to computer science and that gay is not longer considered a crime today. [more...]

2009.09.22 comments (0)

I'm reading Richard Florida's 2008 book "Who's Your City". In this book he asserts that the location where one lives has significant impact on every aspect of one's life. Therefore one should give it major consideration and choose it consciously. [more...]

2009.09.14 comments (0)