Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper
lindseykuper

Perturbation theory

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.

Tags: programming
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 38 comments