Alecs' Blog

You got root, you got everything.

Yeah, Palm Pre is hot these days. Now with the webos emulator and ssh available, you can have more fun out of it.

Once you ssh to the emulator, you can see there's /usr/bin/ipkg, by which you can list and install .ipk packages.

And all applications are in the /usr/palm/applications directory. Spaz is a twitter client for webos and whats more, it's open source! Just grab spaz-webos and spazcore. Put spaz-webos contents to /usr/palm/applications/com.funkatron.app.spaz and spazcore contents to /usr/palm/applications/com.funkatron.app.spaz/spazcore.

some screenshots

The Haskell Platform is a blessed library and tool suite for Haskell distilled from Hackage, along with installers for a wide variety of systems.

IOW, It's Haskell with Batteries Included.

ghc on jaunty is totally out of date. I recommend you grab the latest bin from the ghc official site. After that, just install Haskell Platform. It contains a variety of selected commonly useful lib and tools. You just dont need to install (and set up) 'em one by one.

Just a note for jaunty: install libedit-dev (not libeditline-dev) if you got a dep error for editline.

Just found iMT. It's the iphone / ipod touch interface for mt4. So now you can add/edit blog entries / comments on your favorite device using the familiar web ui. =) Just extract the tarball and no config at all. Just type your original mt admin path in safari on iphone and you'll see the slick UI. Sreenshots: entries view and add a new entry.

And also iPhone Template Set. By adopting it you can publish iphone-friendly pages. After extrating it, you can see here how to use a template set. Now if you are using iphone / ipod touch to view my blog, you should be auto directed to the mobile version. Check out this entry in your iphone. Should get auto directed to the mobile page. Screenshots: main page and a specific entry.

Project Euler continues to be fun. First reached 100% when there were 240 problems. And have successfully guarded that honor since =). (As of this writing, there are now 245 problems). Well, not that easy. Recent problems tend to be more difficult IMNSHO. In the process, you learn new stuff, refresh your old knowledge and gradually become a better problem-solver.

In the no-spoiler tradition of Project Euler (oh, they say "If you cant solve it, you cant solve it. Dont ask."), i would not disclose any direct answer or code. Instead, I'd love to share some of my experience and give some general advice for newcomers:

1. Learn maths. You dont have to be a mathematician to solve Project Euler problems but the more math knowledge you have, the easier it would be. And in fact, the math required is not that 'deep' since Project Euler is not a pure math puzzle. It's more like a programming challenge based on some math background. So other than depth, try broadening the breadth of your math knowledge. Get interested in more math topics and learn to appreciate the beauty of the diverse math world. What Is Mathematics is a very good book to read. And btw, seems Project Euler devs more like these 3 fields than others: Number Theory, Combinatorics and Probability.

2. Learn algorithms. If judged only by the algorithms required, Project Euler problems are not as difficult as ACM/ICPC problems. Dynamic Programming might be Project Euler's favorite algorithm. Graph algorithms like bfs, dfs or shortest path are also good to know. And whats more important, learn algorithm runtime-and-space analysis. IOW, have a good estimate on how long your code will run and how much memory it will consume.

3. Know your tools/langs and sharpen your coding skills. Some problems can be easier solved by using a particular lib or programming language than other. Some heavy brute force might need you to cut the cost as much as possible. Better some knowledge of a few different langs (procedure, object, functional, script, etc.) with 1 or 2 very-good-at.

4. Dont fear the problems. "Only Thing We Have to Fear Is Fear Itself". There's no fun if the problems are not difficult. And different ppl have different knowledge backgrounds and expertise. So a problem easy for others might look very difficult to you. Learn the new math on-the-road. Often than not, there's a mention of the needed math background in the problem description. You can search and study it. And sometimes, there is no such magic or elegant solution at all. Please dont be a perfectionist and never be shy to get your hands dirty to try on small cases. You'll find some patterns that'd enlighten you very much.

5. Think outside the box. If you get stuck, try thinking of another different approach, sometimes totally different. Try to view the problem in other perspective. Be open-minded and learn to be 'creative' and 'smart'. Hints: some geometry problems in fact turn out not to be geometric at all. Cut all tedious lines, circles, sine and cosine; think of abstract combinatoric items.

Project Euler problem is a mixture of math, algo and coding. Solving them is a mixture of joy and pain, trail and fail, fun and frustration, love and hate.

Here are all my solutions to Project Euler. Of course, I wont spoil the real fun and you have to solve the problem yourself thus know the answer to see my code, not vice versa. The site is on top of Google app engine and currently very primitive (poor ui but please dont say 'ugly'). I'm not into web dev very much. You can see the code on github.

More puzzles, more fun.

Besides acm oj and projecteuler, i also like to solve the puzzles on spoj. The ACM/ICPC rules are rather limited -- you have to submit the src code (only one file) in java or c/c++. ProjectEuler is much more free: it just accepts the final answer -- you are free to use any tools/langs as you like. Spoj stands kinda in between: it still accepts a one-file-src but you can use a lot of languages (just to name a few: bash, perl, lua, lisp, python, haskell, c, asm, etc.). In other words, it's hard to not to find your favorite language there. But you cannot use any external src or libs (only standard feature or lib of the langauge is allowed).

Among many interesteting puzzles, spoj has some challenge problems. These problems are not simply checked right-or-wrong. Instead it makes the rank based on its problem-specific scoring: usually precision, sometimes code-length. Take the following three for example:

• Digits of e
• Digits of sqrt(2)
• Digits of pi

The rules are same: given limited time and code-length, calculate the value in as many decimal digits as possible.

All three problems involve arbitrary-precision computations -- you either implement your own FFT or use those languages that have bignum built in (like java, python or haskell).

• Digits of e -- just use the Taylor expansion with Binary-Splitting.
• Digits of sqrt(2) -- Newton iteration (note that each iteration doubles the precision).
• Digits of pi -- use Chudnovsky series with Binary-Splitting.

For the underlying magic algorithms, see the those wonderful papers/docs. Here's a reference implementation for pi digits using gmp -- claims to be the world's fastest -- for as many as billion digits. Also, mpmath has some interesting implementations as well.

I myself dont bother to implement a FFT in c/c++ (and i doubt i could write a fast enough version in 4K code). Python is really slow for this (sorry, sad, but true) . Haskell's Integer is using the fast(est) gmp. Not only it's fast, it's very convenient and leads to (much) shorter and cleaner code. You can see the ranks. Also specific ranks in your favorite languages.

Other interesting ones might be:

• Make the src as short as possible. Perl is the ruler for this. But you can try to be the top 1 on a specific language ranking.
• Compress and uncompress in one file. The hard part is how to dump the compressed data in src file.
• Magic Markov. Write code to generate code, with special craft.

I've listed some math tools and libraries before. A lot of math tools have their own DSL (domain-specific language) for quick & easy access to their various math functions with some primitive control flows. DSL is better in the sense that it's relatively convenient and it gets hooked more tightly to the underlying base (i.e. shorter code, more inner-involving). A general programming language has its own strength: it's powerful, elegant, much more mature and more easy to access the 'outer' world. DSL for the math tools (like the 3 big Ms) sometimes looks kinda awkward from a 'programming' point of view. Besides, people tend to like doing work in their own favorite languages.

Python is rather popular nowadays. It's been used in various fields -- sys admin, net utility, web, prototyping, unit testing, etc. -- and of course, in mathematics, science, and engineering. One of the well-known tool chains is: scipy + numpy + matplotlib + ipython aka the PyLab. scipy/numpy is tremendously good for numeric computation and matplotlib can generate high-quality 2D plots -- in your favorite language.

Another tool chain i'd like to share is for symbolic manipulation: gmpy + mpmath + sympy. gmpy provides the python binding for gmp, mpmath provides some high-level arbitrary-precision computing functions while sympy is really good at symbolic processing with great 2D/3D plotting support and a convenient interactive 'isympy'. Your distro may have these pkgs but please check if they are outdated. I recommend you use the latest version built from their own repos. (sympy has included mpmath, btw). Newer versions are way faster -- Try calculating 1M digits of Pi.

And here's a big all-in-one math tool called sage, which is using python as the primary programming language and can be regarded as a free alternative to the 3 big Ms.

Also, two tools not specifically for math: psyco and parallel python (via bones). psyco is kind of a python JIT. If you do a lot of cpu-bound instructions in python, it is your lovely friend. pp is for parallel computing (multi-core or even network cluster). It can split computation at the function level.

Finally, for speed-lovers, there's a language called wirbel. It has very similar syntax to python (almost equal). The key difference is that it can compile src to native bin, thus it's very fast. But limited: not all python code can be easily changed and compiled by it of course, at least not now. Still an interesting alternative anyway. You might want to have a look.

Installing linux is much more easier these days. LiveCD is now becoming a de facto standard. Some distro even provides a LiveUSB. If not, here's a great tool that can help you make a liveusb from a livecd image, automatically: unetbootin.

Besides the usblive feature, it also supports install-from-net, install-from-windoze, install-from-disk, etc. If you like to try installing different distros and dont have a CD drive (or dont like to burn CDs), unetbootin is your friend.

Big distros nowadays are all trying hard to make the booting fast: kernel-mode-setting, init-ng, readahead, parallel loading, etc. Here's a great tool that can monitor and visualize the booting process: bootchart. I upgraded to Intrepid weeks ago. And here's a bootchart shot.

35 seconds: a cold start, from boot to xorg/gdm running with all common services and wireless network up. I'm very pleased with this, considering its a ubuntu default kernel, default initrd with default settings. If you customize your kernel building all needed drivers in with no module or initrd, and use a slimmed down DE/WM without many startup services, it may reduce about 10 seconds i guess.

And speaking of wireless network, i've been using network-manager for a long time (since edgy?) It works fine (well, though not as half good as AirPort). But not for me in intrepid. Authentication goes well but it fails requesting an ip address. I dunno why. Maybe the kernel, the iwl driver, the wireless router or the nm itself. Dont bother to figure it out or use the cmd line (iwconfig, wpa_supplicant, etc.). Bad me, I am a typical desktop linux user now. Here's a replacement: wicd. It works well. No bloat. Kool.

And finally, here's a tool called smolt which can gather your hardware information and submit it to its central database. You can see some stats and devices information. Maybe not directly good for you but it helps the community in the long run.

Cabal is a system for building and packaging Haskell libraries and programs. Put it another way: its Setup.lhs is like Makefile.pl for perl or setup.py for python. Well, you've got the idea. See the user guide for details.

And cabal-install is like perl's cpan (the command) which can automatically download/install/update haskell package off from Hackages. It's still a work in process. Occasionally it cant resolve the dep right or miss out one or two packages. You might have to manually install them. So be warned.

BTW, I dont think many ppl are still using the 'cpan' cmd to install perl modules these days. At least not for most linux distros. CPAN perl modules are very mature and most distro vendors have made their own pkg/ports already for you. But not for haskell, because far few ppl are using/developing haskell pkg. Either there are no pkg built or if there is, the pkg is usually outdated. So if you need to install cutting-edge haskell pkg, i recommend cabal-install. I used it to install lambdabot. Almost went fine except a dead dep loop. Manually fixed it anyway.

Solving project euler problems continued to be fun. Now i have solved 200 out of 213 problems. There have been some relatively easier ones recently added as well as some hard-and-fun ones. Just to name a few:

• laser beam reflecting on mirrors
• paranoid flea jumping on a chess board
• secret ambiguous numbers

And as always, i like to use haskell to solve them if possible. And the more you use haskell the more you love it. Here are some (new) haskell resources:

• Learn You a Haskell, great tutorial, very enjoyable.
• Real World Haskell, soon to be published by O'Reilly.

Two search engines for haskell (API, library, types, etc.):

• Hoogle, Haskell's Google
• Hayoo!, Haskell's Yahoo! 2.0

I've been using awn for quite a while. It's normally ok but sometimes it just has one glitch or another: not very stable. Also the feel is not quite like Mac's Dock. Now here's a new one: Cairo Dock. It looks great and feels snappy. The icon magnification is just neat.

And for the input method, i got fed up with scim and its crappy dict. Now i start using ibus. It's written by the same author of scim-python. It looks very promising (Dbus based, native theme, etc.) and hopefully has a bright future (i guess). You can give it a try.