Yesterday, the daily programmer Subreddit had a post that mirrored a problem I’ve often seen before: the idea that if you follow first links ((With some caveats)) on Wikipedia, you eventually end with Philosophy. For example, if you follow the first links from Molecule, you get the following path:
Molecule → Atom → Matter → Rest Mass → Invariant Mass → Energy → Kinetic Energy → Physics → Natural Philosophy → Philosophy
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.
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.
One of the rites of passage for computer scientists it seems is to solve the Eight Queens Problem–where you must place 8 queens on a chessboard so that no pair of queens is attacking each other. Even better is when you can expand that to the n-queens problem with n queens on an n by n chessboard. After finding it again in older posts on both Programming Praxis and DataGenetics, I decided to go ahead and take a crack at it and I think the solution is pretty straight forward.