Categories
computer science Math Origami Protocols

Origami crease-patterns are NP-complete

After talking about it with someone I met, I looked it up, and it does seem to be so. There is of-course a lot of research on the subject that I didn’t yet get the chance to read, but I think this is the general picture.

In any case, this shows that my suggestion of using origami as a hash function is valid! Really cool stuff… I wonder if it could actually be useful somewhere.

Categories
Humour Programming

Misunderstood humour – and NP-Completeness

One of the good xkcd comics that I liked. I tried showing it to other people, but almost nobody got it…

Categories
C Design Programming Python

Exception handling policy – use module exception hierarchies

While programming some bigger projects, and not some home-brew script, I used to wonder what to do with exceptions coming from lower level and library modules. The ‘home script’ approach to exceptions is “let it rise” – usually because it indicates an error anyway, and the script needs to shut-down. If there is any cleanup to be done, it will happen in the __del__ functions and finally clause as required.

After getting some experience with handling problems and writing applications that continue to work despite exceptions, I’ve come to the conclusion that the best practice approach is that each of the project’s module must raise its own type of exception. That way, in higher level modules that catch the exception you can set a concrete policy about ‘what to do’.

An example: I have some low level module named “worker”. Let’s say this module’s job is to copy files around efficiently. The higher level module, “manager” decides on ‘policy’ about what to do with files (copy them, delete them, etc…). Now, the “worker” module raised an exception. If this exception is an IndexError, the higher level module can’t really decide – was this because of a programming error, or an OS error? Even if “worker” did define an interface that allowed for throwing IndexError’s in some cases, if there is a real programming error in the module, it will be missed. The correct way to go about it is to create an exception hierarchy for each module, which will be the ‘communication channel’ for errors. This way, any unexpected programming error will percolate up as such, and not get missed – and any exception handling mechanism on the way can decide what do to about it (log, die, ignore, etc…).

Every exception handling rule has exceptions: when writing ‘low-level’ library modules yourself, such as a dict-like class, it makes sense to use IndexError. Don’t get confused with other library modules though – If you are writing some communication library, it should follow the same rules described above for a module.

Categories
C Programming Programming Philosophy Python Teaching Programming

"Fnord" or "The evil empire cheerfuly striked back at the merry-colored pretty princess"

One of my favorite exercises for young programmers is the following (widely known program):

Write a program that will read lists of words from the following files:

  • verbs.txt – contains verb, the others are respectively –
  • nouns.txt,
  • adverbs.txt,
  • and adjectives.txt.

After reading the words, the program will construct sentences of the form:

The <adj> <noun> <adv> <verb> the <adj> <adj> <noun>.

You could of course allow for different sentence structures, or more types of words (prepositions). This site made me remember that. This exercise is really handy, and it also allows for great variations of difficulty (at least in C). If you tell the programmer that he or she must support variable number of words, or just a maximum, or how to define the files… the options are endless. The interesting thing about this exercise, is that in C, it is much more effort to write then in Python (with all the built-in modules). This makes the exercise even more effective: After letting the new programmer painfully implement it in C, I let the guy (or girl) implement it in Python. Really fun to watch. Especially after he or she discovers the meaning of ‘one-liner’ :)

Categories
Math Programming Python

Computation over Zp in Python

Lately I’ve been working a lot on my Algebric Structures homework. One of the reasons I don’t blog as much as I should. While working on my homework, I had to factor some polynomials over Z5 – the field containing the numbers {0,1,2,3,4}. The trick was that given a 4th degree polynomial without any roots, you could only factor it to two 2nd degree polynomials.

That turns out not to be that hard, but a bit of work – especially if you dislike just computing values. So I wrote a simple script to solve this little problem for me. While writing that script, I saw that it could be really fun to write a general Zp class. So naturally, I fired Google up, and tried looking for existing implementations. I didn’t find any (except some python implementations of many number thoery algorithms). Being quite a small amount of work, I hacked up something. After finishing with it, I wrote a polynomial class that can accept any given “number class”. There is actually a public implementation of real valued polynomials in SciPy, but not for integer valued or Zp-valued polynomials. After some more work my polynomial class was also finished. I actually used that class for some computations later on.

I added polynomial division, just for the heck of it, even though I didn’t use it. I hope this little script will be useful to someone.