A quick programming post, since it’s been a while, inspired by this video:
I’m not going to go quite as far as that, but I thought it would be interesting to write up some quick code to generate portmanteaus1.
A quick programming post, since it’s been a while, inspired by this video:
I’m not going to go quite as far as that, but I thought it would be interesting to write up some quick code to generate portmanteaus1.
Today’s five minute post brought to you via Programming Praxis / Career Cup:
Given a positive integer, return all the ways that the integer can be represented by letters using the mapping 1 -> A, 2 -> B, …, 26 -> Z. For instance, the number 1234 can be represented by the words ABCD, AWD and LCD.
So far this week we’ve had a pair of related posts at the DailyProgrammer subreddit1:
Basically, if you’re given a string with vowels, take them out. If you’re given one without vowels, put them back in. One of the two is certainly easier than the other2. :)
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
Yesterday’s puzzle from Programming Praxis asks us to solve a Sunday Puzzle from NPR:
Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?
It’s another in a long history of word games, my favorite sort of puzzle.
Today’s intermediate challenge on Reddit’s /r/dailyprogrammer intrigued me somewhat, so I decided to take a crack at it. The basic idea is if you are given a number, try converting it to all bases from 2 to 64 (with a special encoding). Print out any of those that are words.
For example, if you interpret the number 44,269 as a base 16 (Hexadecimal) number, you get the word “aced”. So just how many of these words are there out there?
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
.
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
.