Log in

No account? Create an account
Perturbation theory - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Perturbation theory [Jul. 3rd, 2008|12:46 pm]
Lindsey Kuper

A perturbation of a string is a permutation, but with one m removed and one r and one b added. For example, perturbation is a perturbation of permutation.

Challenge!: I'll bake cookies for the first person who can generate a list of all the words in your words file that have at least one valid perturbation. (In this case, a "valid perturbation" is one that also appears in words. Perturbation is undefined for strings that don't have an m to begin with.)

Update, eleven hours later: Thank you for playing! Jesse jes5199 wins the cookies with his Ruby implementation. Peter pmb was hot on his heels with Python. Further versions welcome.

Without looking at Jes or Peter's code, Alex oniugnip and I each tried it ourselves. Alex had it in Python in 20 minutes or so (although he says Peter's is more concise). (Alex is working on a Scheme version now; I'm looking over his shoulder as we speak, and one of the things I see is:

(define test-words
  '("yarmulke" "parmalat" "aardvark" "chutzpah" "intersperse" 
    "permute" "parmalat" "perturb"))

This is perhaps the best thing ever.)

Here's my Perl version (which took a couple of hours, because I'm a slow programmer) and output. My results match Alex's, but differ from Jesse's; it looks like we have different words. In mine, 2070 words have perturbations (wow; I was expecting maybe a hundred). There are 2735 perturbations in all. imitatively -> veritability is one of my favorites!

And I'm more and more envious of you Python kids. I like that you can print anything. And that you can .append to an array.


[User Picture]From: lindseykuper
2009-01-08 10:23 pm (UTC)

import antigravity

Okay, so half a year later, I finally wrote my own Python version, and I suddenly have things to say about all of this. [letter for letter in word]: I think that that's a list comprehension! Man, people are excited about those! And I didn't think to use one. I didn't know about sorted(), either, and ended up writing my own sort_str(). It also took me a little while to get the hang of the in-place sorting. (reverse() is in place, too, it turns out.) setdefault may be ugly but it's nicer than my long-winded "if there's nothing in so-and-so, stick an empty list in there". I didn't want to put that in because it was so Perly, and it's nice to realize now that I don't have to.
(Reply) (Parent) (Thread)