Categories
Uncategorized

Solution to NPR puzzle using Raspberry Pi

Intro
Take a common five-letter word. If you add an “e” to the end you’ll get a common six-letter word. or add an ‘e” after the second letter to get a different six-letter word, or an “e” after the fourth letter. what word is it?

The technique
I used the strange dictionary built in to my Raspbery Pi, in /usr/share/dict/american-english.

Key command
$ egrep '^[a‐z]{5,6}$' jhwords > /tmp/five‐six

That leaves us with 11897 words (use wc command to learn this).

Now just look at the six-letter words containing an “e” at the end:

$ egrep '^[a‐z]{5}e$' five‐six > e‐at‐end

Down to 784 words.

Now strip off the terminal “e”.

(steps skipped)

And then…

Candidate word list

ameba
ampul
aorta
avers
blond
brows
cloth
corps
demur
expos
fauna
final
flora
fondu
grill
hears
hydra
karat
larva
loath
local
madam
moral
pleas
psych
regal
scrap
sever
sooth
spars
strip
swath
teeth
tibia
uvula
vulva
zombi

You can scan by hand – the answer jumps out at you.

Conclusion
Another NPR Weekend Edition puzzle is solved by use of some simple linux commands.

References and related
Another NPR puzzle similarly solved.

Categories
Linux Raspberry Pi

Solution to this week’s NPR puzzle using simple Linux commands, again

Intro
As I understood it, this week’s NPR puzzle is as follows. Think of a figure from the Bible with five letters. Move each letter three back, e.g., an “e” becomes a “b.” Find the Biblical figure which becomes an ailment after doing this transformation.

Initial thoughts
I figured this would be eminently amenable to some simple linux commands like I’ve done with previous puzzles (most are not, by the way). I was having a hard time doing these transformations in my head while I was driving, and the first names I tried came up empty, such as Jesus or Moses.

So I figured I could write a program to do the character transformations on each and every word and I could probably find a downloadable text version of the Bible. I didn’t find a pure text version, but I did download an HTML version, which is close enough for our purposes.

Then I was going to just keep the five-letter words and do this transformation on all of them and match against dictionary words. Then I would have taken just those matches and scanned by hand to look for words that are ailments, hoping there wouldn’t be too many matched words to contend with.

Finally settled on a different approach
That looked like a bit of work so I thought about it and decided there had to be a resource for just the figures in the Bible, and voila, there is, in Wikipedia, see the references.

rot13
Rot13 is a famous cipher (encryption is too strong a word to describe this simple approach), where A becomes N, B becomes O, etc. I had a feeling the tr command in linux might be able to do this but didn’t know how. So I searched for linux, tr and rot13 and found an example online. It was easy to adapt.

We need what you could call a rot -3. Here is the command.

$ tr 'A‐Za‐z' 'X‐ZA‐Wx‐za‐w'

So I put the text of the Wikipedia page of Biblical figures into a text file on my linux server, into a file called list-of-biblical-figures. It looks like this:

Adam to David according to the Bible
Creation to Flood
 
    Adam Seth Enos Kenan Mahalalel Jared Enoch Methuselah Lamech Noah Shem
 
Cain line
 
    Adam Cain Enoch Irad Mehujael Methusael Lamech Tubal-cain
 
Patriarchs after Flood
 
    Arpachshad Cainan Shelah Eber Peleg Reu Serug Nahor Terah Abraham Isaac Jacob
 
Tribe of Judah to Kingdom
 
    Judah Perez Hezron Ram Amminadab Nahshon Salmon Boaz Obed Jesse David
...

I was going to tackle just pulling the figures with five-character names, but the whole list isn’t that long so I skipped even that step and just put the list through as is:

$ cat list-of-biblical-figures|tr 'A‐Za‐z' 'X‐ZA‐Wx‐za‐w'

comes back as

Xaxj ql Axsfa xzzloafkd ql qeb Yfyib
Zobxqflk ql Cilla
 
    Xaxj Pbqe Bklp Hbkxk Jxexixibi Gxoba Bklze Jbqerpbixe Ixjbze Klxe Pebj
 
Zxfk ifkb
 
    Xaxj Zxfk Bklze Foxa Jbergxbi Jbqerpxbi Ixjbze Qryxi-zxfk
 
Mxqofxozep xcqbo Cilla
 
    Xomxzepexa Zxfkxk Pebixe Bybo Mbibd Obr Pbord Kxelo Qboxe Xyoxexj Fpxxz Gxzly
 
Qofyb lc Graxe ql Hfkdalj
 
    Graxe Mbobw Ebwolk Oxj Xjjfkxaxy Kxepelk Pxijlk Ylxw Lyba Gbppb Axsfa
...
    Ebola
...

So it’s all gibberish as you might hope. Then towards the end you come across this one thing and it just pops out at you. As is my custom I won’t give it away before the deadline. [update] OK. Submission deadline has passed. Ebola just really popped out. Going back to the original text, you see it lines up with Herod. So there you have it.

I double-checked and confirmed this also works on a Raspberry Pi. I’ve come to realize that most people don’t have their own server, but hundreds of thousands or perhaps millions have a Raspberry Pi, which is a linux server, which makes techiques like this accessible. And fun.

Conclusion
I show a technique for using a linux server such as a Raspberry Pi to solve this week’s NPR puzzle. A very simple approach worked. In fact I was able to solve the puzzle and write this post in about an hour!

References and related
HTML version of Bible: https://ebible.org/Scriptures/eng-web_html.zip
Biblical figures: https://en.wikipedia.org/wiki/List_of_major_biblical_figures
An earlier NPR puzzle solved with linux command line techniques

Categories
Linux Raspberry Pi

Solution to this week’s NPR puzzle using simple Linux commands

Intro
Every now and then the weekend puzzle is particularly amenable to partial solution by use of simple Linux commands. I suspected such was the case for this week’s, and I was right.

The challenge for this week
Take a seven letter word of one syllable, add the consecutive letters “it” somewhere in the middle to create a nine letter word of four syllables.

The Linux command-line method of solution
On a CentOS system there is a file with words, lots of words. It’s /usr/share/dict/linux.words:

$ cd /usr/share/dict; wc linux.words

479829  479829 4953699 linux.words

So, 479829 words! A lot of them are junk words however, but it has the real ones in there too. This file comes from the RPM package words-3.0-17.el6.noarch.

So here’s a sort of stream-of-consciousness of a Unix person solving the puzzle without doing too much work or too much thinking:

How many seven-letter words are there? First what’s an expression that can answer that? I think this is it but let’s check:

$ egrep '^[a‐z]{7}$' linux.words|more

aaronic
aarrghh
abacate
abacaxi
abacist
abactor
abaculi
abaddon
abadejo
abaised
abaiser
abaisse
abalone
abandon
abandum
abasers
abashed
abashes
abasias
abasing
abatage
abaters
abating
abators
abattis
abattue
abature
abaxial
...

OK, that egrep expresison is right. So the seven-letter word count is then:

$ egrep '^[a‐z]{7}$' linux.words|wc ‐l

40230

That’s a lot – too many to eyeball. OK, so how many nine-letter words are there?

$ egrep '^[a‐z]{9}$' linux.words|wc ‐l

50748

Wow, even more.

OK, we have an idea, based not on what may be the best approach, but based on which Linux commands we know inside and out. The idea is to start from the nine-letter words which contain “it”, remove the “it” and then match the resulting seven-letter character strings against our dictionary to see which are actually words. We know how to do that. The hope is the resulting list will be small enough we can review by hand.

How many nine-letter words contain the consecutive characters “it”?

$ egrep '^[a‐z]{9}$' linux.words|grep it|wc ‐l

3245

They look like this:

abilities
abnormity
aboiteaus
aboiteaux
abolition
abrazitic
absurdity
academite
acanthite
accipiter
acclivity
accredits
accubitum
accubitus
acetosity
acidities
acinacity
aconitine
aconitums
acquisita
...

so it would take forever to go through. If we had a dictionary with the syllable count we coul really narrow it down. I think I’ve seen that, but I’d have to dig that up. We introduce the sed operator to remove the “it” from these words:

$ egrep '^[a‐z]{9}$' linux.words|grep it|sed 's/it//'|more

abilies
abnormy
aboeaus
aboeaux
abolion
abrazic
absurdy
academe
acanthe
acciper
acclivy
accreds
accubum
accubus
acetosy
acidies
acinacy
aconine
aconums
acquisa
...

There are more efficient ways to loop through these results using xargs, but I’m old school and have memorized this older construct which I use:

$ egrep '^[a‐z]{9}$' linux.words|grep it|sed 's/it//'|while read line; do
> grep $line linux.words >> /tmp/lw
> done

We look at the resulting file and found we made a little goof – we didn’t limit the resulting matches to seven characters:

$ more /tmp/lw

academe
academes
Pleuracanthea
vacanthearted
vacantheartedness
aconine
japaconine
pseudaconine
adderspit
affidavit
affidavits
affidavy
preaffidavit
divagating
extravagating
indagating
propagating
self-propagating
...

But that’s easily corrected:

$ cd /tmp; egrep '^[a‐z]{7}$' lw > lw2
$ wc -l lw2

376 lw2

Now that’s a number we can review by hand. Very few of these have only one syllable:

$ more lw2

academe
aconine
alumine
alveole
ammonic
barbary
barbone
basting
bauxite
berline
bethank
boraces
bullion
capella
carbone
carmele
carmine
cascade
catline
cavated
celeste
ceruses
chloric
chondre
chromes
cations
claries
cockney
coenobe
compose
...

I quickly reviewed the list and the answer popped out, somewhere towards the end – you can’t miss it.

Friday update – the solution
The 7-letter word that pops out at you? Reigned, which you immediately see becomes reignited – nine letters and four syllables!

Want to do this on your Raspberry Pi?
The dictionary file there is /usr/share/dictd/wn.index, but you probably don’t have it by default so you’ll need to install a few packages to get it which is simple enough. This post about Words with Friends explains the packages I used to provide that dictionary. Aside from the location of the dictionary, and that it contains fewer(?) words, everything else should be the same.

Conclusion
We have solved this week’s NPR puzzle without any complex programming just by using some simple Linux commands.

References and related
This link is nice because it has a transcription of the puzzle so you don’t have to waste time listening to the whole six-minute segment.
Another NPR puzzle we solved in a similar way.

Categories
Linux Perl

Solution to NPR puzzle: capitals and cities

Problem statement
Take a US state capital. Drop a letter. Re-arrange the remaining letters to get the name of a US city. There are two answers.

I know Wlll Shortz says he makes up problems that are not programmable, but he goofed up this time, big time. This one is eminently programmable. I am not even a programmer, more a scripter. I don’t want to have an unfair advantage so I’m sharing my Perl scripts that solve this problem.

The setup
Find a Linux machine. A Raspberry Pi makes a great economical choice if you don’t have anything like that.

Scrape the 50 state capitals from a web page after arriving at a page (I used Wikipedia) that lists them. By scrape I mean copy-and-paste into a file in a terminal window of your Linux server.

Same for US cities. I went to a more obscure listing and picked up the 666 of the largest cities from a listing of the top 1000.

Cleaning up the Capitals
Here’s a script for processing those capital cities. The input file contains lines like these first two:

Alabama         AL      1819    Montgomery      1846    155.4   2       205,764         374,536         Birmingham is the s
tate's largest city
Alaska  AK      1959    Juneau  1906    2716.7  3       31,275          Juneau is the largest capital by land area. Anchora
ge is the state's largest city.
...

I called it cap-fltr.pl

#!/usr/bin/perl
while(<STDIN>) {
  ($cap) = /\d{4}\s+(\D+)\s+\d{4}/;
  $cap = lc $cap;
  $cap =~ s/\s//g;
  print "$cap\n";
}

Create a clean listing of capitals like this:

$ ./cap-fltr.pl < capitals.orig > capitals

assuming, that is, that you dumped your paste buffer of scraped capitals and related information into a file called capitals.orig. So that creates a file called capitals looking like this:

montgomery
juneau
phoenix
littlerock
sacramento
denver
...

Cleaning our cities
My scraped cities file morecities.orig looks like this:

1       New York - city         New York        8,491,079       5.9%
2       Los Angeles - city      California      3,928,864       6.0%
3       Chicago - city  Illinois        2,722,389       -5.9%
4       Houston - city  Texas   2,239,558       13.2%
5       Philadelphia - city     Pennsylvania    1,560,297       3.0%
6       Phoenix - city  Arizona         1,537,058       15.8%
...

These can be cleaned up with this script, which I call morecities-fltr.pl:

#!/usr/bin/perl
while(<STDIN>) {
  ($city) = /^\d+\s+([^-]+)\s-/;
  $city = lc $city;
  $city =~ s/\s//g;
  if ($city =~ /st\./) {
    $form1 = $city;
    $form1 =~ s/\.//g;
    print "$form1\n";
  }
  $city =~ s/st\./saint/;
  print "$city\n";
}

Note in this and the capitals filter I get rid of space, lowercase everything and here I consider st and saint as alternate forms, just in case. Those puzzle-masters can be tricky!

So the cleanup goes into a cities file with a command like this:

$ ./morecities-fltr.pl < morecities.orig > cities

Finally the program that solves the puzzle…
The solution script, which I called sol2.pl, isn’t too bad if you know a tiny bit of Perl. It is this:

#!/usr/bin/perl
$DEBUG = 0;
open(CAPITALS,"capitals");
open(CITIES,"cities");
@cities = <CITIES>;
@capitals = <CAPITALS>;
foreach $capital (@capitals) {
  chomp($capital);
  print "capital: $capital\n" if $DEBUG;
  $lenCap = length $capital;
  foreach $city (@cities) {
    chomp($city);
    print "city: $city\n" if $DEBUG;
    $lenCity = length $city;
    next unless $lenCap == $lenCity + 1;
# put the individual letters of the city into an array
    @citychars = split //, $city;
    $capitalcopy = $capital;
# the following would be a more crude way to do it, leaving us results to be picked over by hand
    #$capitalcopy =~ s/[$city]//g;
# this is the heart of it - eat the characters of the capital away, one-by-one, with the characters of the city
# this provides for an exact, no-thinking solution
    foreach $citychar (@citychars) {
      $capitalcopy =~ s/$citychar//;
    }
    print "capitalcopy: $capitalcopy\n" if $DEBUG;
# solution occurs when the copy of the capital is left with excatly one character
    print "capital, city: $capital, $city\n" if $capitalcopy =~ /^\w$/;
  }
}

With the comments it’s pretty self-documenting.

I’ll publish my answer after the deadline. you have to do some work after all!

Python approach
This hasn’t been thoroughly tested yet. A friend has suggested the following python code might work.

current_city = ""
current_capital = ""
missed_letters = 0
 
 
for count, capital in enumerate(capitals):
    missed_letters = 0
    current_capital = capital
    print current_capital, "current capital"
 
    for count, city in enumerate(cities):
        current_city = city
        print current_city, "current city"
 
        for count, letter in enumerate(capital):
            while missed_letters <2:
                if missed_letters <2 and len(city)== count+1:
                    print current_capital, "Take one letter from this capital"
                    print current_city, "Rearrange the letters in the capital to get this city"
 
                elif letter in city:
                    pass
                    print "letter in the capital matched the city"
 
                elif letter not in city:
                    missed_letters+=1
                    print "letters didn't match any in the word"

My answer
$ ./sol2.pl

capital, city: trenton, renton
capital, city: salem, mesa
capital, city: salem, ames

Actual answer
salem -> mesa
st paul -> tulsa

This illustrates a good lesson. Program, yes, but don’t turn off your brain. I was aware of possible saint/st spelling pitfalls, but I only applied it to the cities list. For some reason I overlooked applying this ambiguity to the capitals list! If add stpaul to my capitals list the program finds tulsa instantly – I just tried it.

If there’s any satisfaction, very, very few people got the correct answer.

References and related
Audio clip of the puzzle
Another NPR puzzle amenable to simple computer tools, in this case shell commands, is documented here: puzzle
Raspberry Pis. Here we describe building a four-monitor display with Raspberry Pis.
A good python tutorial: https://docs.python.org/2/tutorial/