Monday, October 13, 2003

Making Problems Interesting

by Asim Jalis

What makes things interesting for me. This might not work for everyone. I am hoping to meditate on what makes things interesting to me and then to go from there. Hopefully in the process I can identify software problems that engage me deeply. 1. Byte algorithms are interesting, because they are hard. Easy things are boring, and hard things are interesting. Byte arrays are also so primitive. I like primitivity. I like command lines over GUI. I like bytes of more complex data structures. Bytes are so real, so concrete. Everything beyond bytes is a big fat lie, in a manner of speaking. It is make-believe. It is not real in the same intense immediate way that bytes are real. 2. Here are some algorithms I have found interesting: (a) How to do byte arithmetic. (b) How to implement dynamic arrays using tree structures. The tree makes it easy for the data structure to grow but at the same time it is relatively easy to get to any single point. (c) Implement N queues (enq, deq, newq, delq) in 2048 bytes. This is the problem that Marshall found on (d) How to find a pattern in a potentially very long byte stream with fixed small memory. (e) Storing XML as a byte array. 3. What is in common between these problems. What are some other problems that would be equally interesting? 4. Is it the problems that are interesting? Or is it that the way I look at them that is interesting? Perhaps there is a particular way of looking at byte array problems that engages me, and I might be able to apply the same idea to other problem domains too, I mean I might be able to apply the same way of looking to other problem domains. 5. Second, I have to find a way to make these algorithms commercially viable. 6. Applications of this kind of stuff will be similar to applications of mathematics and number theory and algebra in general. For example, cryptography might be an application. What other applications are there of finite number theory? 7. Note: I also really enjoyed working on permutation problems: Generate all possible permutations of the numbers 1 through N. That's a neat problem. 8. Note also: it is not interesting to implement existing algorithms. The joy the fun comes from actually solving novel problems. The quality of a problem that is fun to work on is that it should be easy to understand but hard to solve. It should provide a rich structure or space in which to play. Marshall's queue problem had all of these characteristics. The problem of pattern matching in a byte stream with fixed memory also had these characteristics. It was easy to understand, but required some real thought to implement. 9. I don't like problems which go on and on with special cases, most of which are one-off hacks. For example, implementing regular expressions, or implementing printf does not sound like fun. Printf seems too easy. Regex has too many special cases and too many one-off weirdnesses. After a point it just becomes drudgery. 10. Another problem I found interesting, which is relatively trivial to implement, is the algorithm for an LCD calculator screen for printing numbers. Why is this? The screen is full of nuances and the same kind of irrational rules that I dislike in regexes. 11. Perhaps the reason is that the screen is really fundamental and primitive. 12. Another problem I find enjoyable is implementing the screen of tic-tac-toe. I am talking now about simple pixel based graphics. These are fun in a way. 13. Perhaps the key ingredient is concreteness. Primitive concreteness. Byte arrays have this concrete quality. So do pixels on a screen. Pixels are fun to play with if I am implementing something fundamental like calculator screens. 14. I feel I am missing something but I am not sure what it is. 15. Also it feels weird to write all these thoughts in public. Hopefully it is not too distracting for me. Hopefully, the distraction will go away after a while. 16. Simulations might also be fun. For example, a simulation of people moving through a building in an elevator would be quite interesting. 17. Next, some thoughts on the marketability of these ideas. Bytes are marketable as encryption algorithms. Simulations might have a market too. I am not sure what. Perhaps through simulation you can measure the performance scenarios of a grid network. 18. Here is a simple way to find other interesting projects that are similar in flavor to the byte algorithms that I like so much: Find shareware sites that are selling byte algorithm components, and see what else they are selling. If they are successful they must be selling things that are easy and fun for them to do. Companies which veer too far from what is interesting usually die. So if a company is still around chances are that it is feasting on some interesting problems. 19. Searching for byte array algorithms yields companies such as ChilKat Soft. 20. Let see what this probing turns up. 21. Another set of problems with a similar flavor: Base64 conversion and its close relative the MIME format. 22. Other companies: (a) Gives away free Base64. (b) Sells Base64, FTP, SMTP, WAV utilities. 23. One approach might be to just publish interesting byte array algorithms on a website dedicated to byte array fun. 24. Yet another thought: There might be algorithms out there that work okay if you have lots of memory, or whose performance is not very good. Rewriting the same existing libraries with memory and timing restrictions might be fun too. 25. For example, how optimal are Java strings anyway? The problem with implementing anything natively for Java is that there is an unspoken rule against going outside the virtual machine. No one wants to recompile the virtual machine just to use your nifty little library. 26. The other market for this might be C/C++ dlls. The .NET market might be too immature. And .NET might also have issues with integrating into a native unmanaged library. 27. Here is another question then, that might be relevant at this point: What kinds of managed problems do you like? I mean what kinds of problems do you like which make sense in the managed world of C# and Java? Clearly, byte algorithms are in some ways underkill here. Is there anything in the matrix that is interesting? Or is this bright and shiny reality just a thin cloak over a hideous ugly reality which refuses to become interesting? 28. Here are some more thoughts: (a) Target Palm, because it is primitive and low-level. This will make it fun to work on. (b) Is there a market for libraries for the Palm? (c) Find other platforms that are still using C (that consider C++ too advanced). For example X-Box or PS2 might be other targets. Or Game Boy Advanced. (d) Or target Nokia and programmable cell phones. 29. The goal in all of this is not to deliver complete applications, but rather to deliver small elegantly written C libraries that other developers can use to deliver complete applications. 30. Writing a small virtual machine in C for regular platforms might also be interesting. C programming is interesting period. Another interesting problem: Date calculations. 31. Coding up the suckerpunch queue problem should be a lot of fun whether someone wants it or not. There must be problems like this which people actually want. Hmm. 32. Another company FlagShip sells an API that lets you read a dbase file.