Ender's Game

A while ago, a friend of mine recommended the book Ender's Game to me. Intrigued by his description and enthusiam for the plot, I ordered a copy. Suffice to say, it was an amazing and fast read. I've always loved science fiction, and although this book was written in the mid-80s, its depiction of future technology is still very advance from modern day.

In the story, Earth is preparing for a third alien invasion. Time is running out quickly, and the International Fleet must find the most brilliant commander to lead the war against the insect-like aliens referred to as the "buggers". Insanely smart children were given head-monitors since they turn 3, and those who showed true genius and promise were then lead to battle school located on a ship in outer space. 

The wiggin family has 3 children, which is an exception to the law as over-population limits the number of children per household to only 2. However, because the first 2 children of the Wiggen family were so incredibly gifted (though they have weaknesses that render them unfit to train in battle school), the government commanded the family to produce another child. Hence, the third child Ender Wiggin was born. At age 6, Ender was sent to Battle School away from his evil brother, his sister who is the only one to truly loves him, and his parents who were ashamed to have him as the third child. What Ender didn't know is that he is the chosen one to help save mankind from the buggers. 

----

Happy Reading! On another note... only exactly 2 more months until the Hunger Games Movie comes out!!

Also, today is Lunar New Year. Happy New Year! 

Chúc các anh chị em và bạn bè năm mới vui vẻ!

New Year Resolutions

The New Year is about new beginnings, a new chance to start over. What I love about this time of year is that everyone becomes their best self. People make goals and resolutions for self improvement and to enhance the quality of their lives. We can all feel the positive and hopeful energy buzzing through the air, and it is infectious.

The winter break has given me time to reflect on the previous year and make a new list of resolutions for this year. Granted, 2011 was an amazing year with lots of accomplishments and high moments, but if there was anything I could change, it was the amount of stress that came with it. With that being said, my resolutions for 2012 are as follows.

New Year Resolutions

1. read at least a book a month
2. learn to cook more dishes
3. stick to my low carb and low sugar diet
4. run 3 mornings a week on my treadmill for 20 minutes 
5. review and go over 150 interview coding problems
6. develop a fun software product

Crossword Puzzle Solution Generator

     In my artificial intelligence graduate course this semester, we had a term project to create a LISP crossword puzzle game. The game has two modes, an automatic and a manual mode. In automatic mode, the computer is programmed to automatically fill in the grid, whereas the user may choose to play manually through manual mode. In automatic mode, the program generates as many solutions to the crossword puzzle as it can in the limited time span of 30 CPU seconds or until it reaches a maximum of 100 solutions. The program was given a wordlist of over 100,000 English words contained in the text file wordsEn.txt and an arbitrary grid data file as input.

Technical Approach and Intelligence

     My program uses a depth-first search backtracking algorithm to fill in the grid with words from the wordlist until the puzzle is solved while backtracking if no solution for an entry is found. An entry is defined as the horizontal or vertical lines of empty cells that are to be written. The depth-first search approach starts with an empty entry (root node), writes to it, and moves to its first neighbor (first child node). The same process trickles down for all neighbors’ neighbors. If a neighbor is already written to, it will then move to its second neighbor and so on until all neighbors are filled and we move back up to the entry that calls it. If there is no solution for an entry, we retrace back to the calling entry, find a different solution for that entry, and repeat the process until all entries are filled and the puzzle is solved.

     In order to speed up search time and reduce the chances of the program searching through dead end solutions, I applied a couple of heuristic to minimize the number of backtracks and improve performance.

     The problem was approached with the “First Fail principle: try first where you are more likely to fail”. One heuristic that was used was the least constraining variable heuristic where the crossword puzzle is solved by first filling in entries with the greatest number of constraints. The constraints that is of the most interest, is the number of intersections of letters a word entry has with other entries of different directions. In other words, an entry with 3 neighbors will have a constraint of 3. However, because we are using a depth-first search approach, it is important to also sort each entry’s neighbors by greatest number of constraints. This allows us to visit neighbors that have more intersecting positions first. Another way of looking at this heuristic is that it looks at one additional level of constraints, and permits us to starting writing at a position in the grid that is of the highest degree of complexity in terms of constraints and limits the number of backtracks. 

     To break ties between entries with the same constraints, the entry with the smaller domain size will be chosen to maximize choices for the remaining entries.

letter frequency of text

    Another heuristic that was employed was to check if the letters at each intersection begins with an e, t, a, o, i, n, s, h, or r. These letters have the highest frequency of appearance in the English dictionary as portrayed by the figure below. This approach was taken so that intersecting letters that have low frequency won’t be chosen and hence lead to a dead end which would cause more backtracking. Admittedly, as with other greedy heuristics, this heuristic might have an adverse effect where the only possible intersecting letters for two entries are one of the letters that were not allowed. In this sense, we are omitting search sensitivity for speed.

     Finally, words in the same domain were not shuffled and were instead sorted in alphabetical order. This is another strategy to limit the searches for words to fill an entry because words at the beginning of the alphabet have a higher frequency of appearing.

Results

     The algorithm was tested using 14 test grids with varying degree of complexity. Mostly, the program was able to generate 100 solutions for each test grid with an average run time of 0.3 second per grid. For extremely cluttered grid with high solving difficulty, the program was unable to generate a solution within the 30 second time frame permitted. Out of the 77 class projects, my algorithm ranked 8th in speed and completeness which I thought was pretty impressive. 

     Overall, this was a challenging but fun project. I especially enjoy finding new and creative ways to improve my algorithmic efficiency. It was also my first time programming in LISP, and boy was it a major battle. Debugging and finding documentations on the language prove to be quite difficult. However, there are many benefits that I've discovered upon using the language such as the "nth" function and the straightforwardness of the code.

The French Press

The french press coffee maker is officially my favorite investment this fall! The coffee it yields is so much more flavorful and aromatic than a regular drip-brewed coffee maker. Why? Because the direct contact of coffee and water traps the essential oils and flavor that is otherwise lost in the paper filters of regular coffee makers. 

To brew the coffee, I start off by stirring the ground coffee and boiling water together in the beaker, let it brew/steep for 4-5 minutes, then press the plunger to trap the coffee grounds towards the bottom of the beaker. I use my favorite standard coffee which is Starbucks Expresso Roast whole beans. To prepare it, I add to the coffee a tbsp of condense milk and a tbsp of milk in a medium sized mug or tumbler. Topped with some whipped cream or milk froth and you have a yummy concoction!

So what are you waiting for? Join the bandwagon, get it at Amazon.com for $19, and enjoy!

Smart List

Smart List was an idea my friend and I came up with for our senior project. We wanted to take advantage of the Google Places API that was recently released to the public as of May 2011, and create a unique and useful Android app. Hence, we decided on the idea of a task managing system/to-do list which would voice alert  (proximity alert) you whenever you're near your errands' locations. You need only to enter the name of a place such as Wholes Food and it would return a list of all Wholes Food in the area which you can pick from and view on the map to do a task such as Groceries. Additional features include displaying a map of where all the tasks are located, an alarm system to set when the errands are due, and the option to email the list of all errands. 

After 3 months of careful design, implementation, and user testing, we finally have a finished and working product! It has been an amazing experience getting to work with Android. We definitely faced some problems with how often to poll for the GPS location so as not to overload the battery consumption. Our solution was to set different polling rates based on whether the users' position (longitude and latitude) changes over time. If the user is at home, the GPS will poll every 10 minutes whereas if the user's location changes rapidly (perhaps he/she is in a car driving), we would poll it every 5 seconds. It manages to work pretty well, I would say.

Some Views of Smart List

Add Task Activity

Home Activity

Proximity Alert

Map of all Tasks

RIP Dennis Ritchie

Only days after Steve Jobs' death, we also lost the inventor of the C programming language and the Unix operating system, Dennis Ritchie. Not many has heard of him and certainly no biography has been released only 2 weeks after his death, but let us pay a tribute to the genius whose shoulders we all stood on. RIP Dennis Ritchie, the king of the invisible world.

"Ritchie was under the radar. His name was not a household name at all, but . . . if you had a microscope and could look in a computer, you'd see his work everywhere inside." - Paul E. Ceruzzi

Philosophical Musing

I've always been an idealistic person, always intrigued by things, feelings, and situations that are sensational, captivating. I like reading books with an exemplary hero, an element of magic, adventure, or flights of fantasy. I like associating love with those rare magnetic moments that envelope your entire being. More wildly, I like imagining the fate of the universe and mankind resting on our own creation. That is, I’m speaking of sentient machines. Artificial intelligence has always been a fascinating subject to me. Of course we are decades, possibly centuries away from true AI. But, if we are to create sentient beings in the image of our likeness, as it is the only way we know how, we must first reverse engineer the human brain and decipher our own intelligence, which in itself is another phenomenon.

The other day in AI class, my professor brought up something very interesting. He asked us to tell him the phone number of the White House. We immediate acknowledge that we do not know. And that, quite frankly, is the genius of the human brain. We did not have to search our memory bank to come up or not come up with an answer. We instantly know that we do not have that information; whereas, computer systems must have a searching process in their database. If we are able to understand how our human brain can bypass this search method, perhaps we can shift the paradigm of how knowledge can be attained.

RJ and I often discuss about living forever by preserving our brain and reconstructing our memories onto another stronger body/host. He believes that if something has all the same memories as you, then it is essentially you. I, on the other hand, believe that just because a host has all of your memories does not make it you. It’s like cloning a person, you’re missing an important element and that is the human consciousness. If my conscious no longer exists, it is just someone else with my memories. Perhaps if we were born in the next century, we would have the answer to this puzzle. I often question if it is a blessing to be born in my age for the reason that I do not have to witness some sort of Apocalypse that would end my race, or that it is a curse not to be able to witness the ultimate advancement of my species.

Emo Philips: “I used to think that the brain was the most wonderful organ in my body. Then I realized who was telling me this.”