In the past, I absolutely loved messing around with genetic algorithms. The idea of bringing the power of natural selection to bear to solve all manner of problems just appeals to me for some reason. So when I came across a puzzle on on Programming Praxis called flibs source code

The eventual goal will be–given a binary sequence–to evolve a finite state machine that will recognize the sequence and output the same, offset by one. So if we’re given the sequence 010011010011, the solution will output something like this: 001001101001.

read more...

Today we get away from the word games for a little while and get back to talking about random number generators (previous posts here and here). Or rather one random number generator in specific: a Rule 30 psuedo-random number generator (PRNG). (Here’s the motivating post from Programming Praxis.)

Remember the previous post I made about cellular automaton? The basic idea is to turn those into a random number generator. If you go back to the linked post in particular and give it Rule 30 with a random initial state, you can see how chaotic the rows seem to be. Perfect for a PRNG.

read more...

One more challenge from Programming Praxis’ Word Games today (there are only a few left!). This time we have the challenge of cutting off bits of words, one letter at a time, such that each step is still a word.

The example given in their post is planet → plane → plan → pan → an → a, although surely many such examples exist.

read more...

Today we have doublets source code, dictionary source code, queue source code.

Using the same source code as the previous two posts (here and here, described originally here) for the dictionary, the code is a pretty straight forward case of using recursion to do backtracking. Basically, try all of the possible next words one letter different. Whenever you find a dead end, back up and try a different path. Something like this:

; find the path between two words, changing one letters at a time
; use call/cc to bail out when we find an answer
(define (direct-doublet dict src dst)
  (call/cc
   (λ (exit)
     (let ([src (string-upcase src)]
           [dst (string-upcase dst)])
       ; loop down possible solutions
       (let loop ([current src] [words (list src)])
         ; when we find one, bail out entirely
         (if (equal? current dst)
             (exit (reverse words))
             ; try all possible values
             (for*/list ([i (string-length src)]
                         [c "ABCDEFGHIJKLMNOPQRSTUVWXYZ"])
               (let ([next (string-set current i c)])
                 (when (and (not (member next words))
                            (contains? dict next))
                   (loop next (cons next words))))))))
     (exit #f))))

Basically, I’m using a neat trick I last used on the post about 4SUM where call/cc lets us bail out of the depths of the code as soon as we find a solution. Other than that, it’s a simple matter of using for* to loop over each position and each character, generating all possible words. Whenever a word is valid (and not one we’ve seen before in this path), keep going. Eventually, we’ll find a solution and can bail out. On the off chance that we don’t, return #f.

read more...

Continuing in my recent set of word-cube source code. Like yesterday, it’s designed to work in Racket 5.3+.

Okay, this one was just neat. Based on word-squares source. I’ve only tested it in Racket 5.3+, but newer versions should work as well. Racket 5.2 won’t work without some tweaking as (at the very least) it’s missing a definition for string-trim.

For the next few posts, we’re going to need a way to represent a dictionary. You could go with just a flat list containing all of the words in the dictionary, but the runtime doesn’t seem optimal. Instead, we want a data structure that lets you easily get all possible words that start with a given prefix. We want a trie.

Another day, another post from Programming Praxis. Today they posted a word game that seems simple enough: first find all words in a given dictionary that contain all five vowels (a, e, i, o, u) in ascending order and then find any words (at least six letters long) where the letters are all in ascending alphabetical order.

read more...

There’s been a bit of hubbub in the in the math world the last few weeks with Shinichi Mochizuki’s 500 page proof that of the ABC conjecture. Basically, the conjecture states that given three positive coprime integers a, b, and c such that a + b = c, the product of the distinct prime factors of a, b, and c is rarely much smaller than c. While this may sound strange, there are a number of interesting consequences that you can read about here.

To make a long story shorter, there was a challenge on Programming Praxis that intrigued me, which was to write code that given a upper bound on c would generate a list of all of the triples (a, b, c) such that the product is larger.

read more...

Recently I’ve been watching a lot of find-in-pi source code

(require racket/generator)

(define (make-pi-spigot)
  (generator ()
    (let loop ([q 1] [r 0] [t 1] [k 1] [n 3] [l 3])
      (if (< (- (+ (* 4 q) r) t) (* n t))
          (begin
            (yield n)
            (loop (* 10 q)
                  (* 10 (- r (* n t)))
                  t
                  k
                  (- (quotient (* 10 (+ (* 3 q) r)) t) (* 10 n))
                  l))
          (loop (* q k)
                (* (+ (* 2 q) r) l)
                (* t l)
                (+ k 1)
                (quotient (+ (* q (+ (* 7 k) 2)) (* r l)) (* t l))
                (+ l 2))))))

Simple enough to use, we can use Racket’s for to generate a list of n digits of pi or to convert the same to a string:

read more...