Shallow Thoughts : tags : puzzles

Using grep to solve another Cartalk puzzler

It's another episode of "How to use Linux to figure out CarTalk puzzlers"! This time you don't even need any programming.

Last week's puzzler was A Seven-Letter Vacation Curiosity. Basically, one couple hiking in Northern California and another couple carousing in Florida both see something described by a seven-letter word containing all five vowels -- but the two things they saw were very different. What's the word?

That's an easy one to solve using basic Linux command-line skills -- assuming the word is in the standard dictionary. If it's some esoteric word, all bets are off. But let's try it and see. It's a good beginning exercise in regular expressions and how to use the command line.

There's a handy word list in /usr/share/dict/words, one word per line. Depending on what packages you have installed, you may have bigger dictionaries handy, but you can usually count on /usr/share/dict/words being there on any Linux system. Some older Unix systems may have it in /usr/dict/words instead.

We need a way to choose all seven letter words. That's easy. In a regular expression, . (a dot) matches one letter. So ....... (seven dots) matches any seven letters.

(There's a more direct way to do that: the expression .\{7\} will also match 7 letters, and is really a better way. But personally, I find it harder both to remember and to type than the seven dots. Still, if you ever need to match 43 characters, or 114, it's good to know the "right" syntax.)

Fine, but if you grep ....... /usr/share/dict/words you get a list of words with seven or more letters. See why? It's because grep prints any line where it finds a match -- and a word with nine letters certainly contains seven letters within it.

The pattern you need to search for is '^.......$' -- the up-caret ^ matches the beginning of a line, and the dollar sign $ matches the end. Put single quotes around the pattern so the shell won't try to interpret the caret or dollar sign as special characters. (When in doubt, it's always safest to put single quotes around grep patterns.)

So now we can view all seven-letter words: grep '^.......$' /usr/share/dict/words
How do we choose only the ones that contain all the letters a e i o and u?

That's easy enough to build up using pipelines, using the pipe character | to pipe the output of one grep into a different grep. grep '^.......$' /usr/share/dict/words | grep a sends that list of 7-letter words through another grep command to make sure you only see words containing an a.

Now tack a grep for each of the other letters on the end, the same way:
grep '^.......$' /usr/share/dict/words | grep a | grep e | grep i | grep o | grep u

Voilà! I won't spoil the puzzler, but there are two words that match, and one of them is obviously the answer.

The power of the Unix command line to the rescue!

Tags: cmdline, regexp, linux, shell, pipelines, puzzles
[ 11:00 Mar 15, 2011    More linux/cmdline | permalink to this entry | ]

Python for (Cartalk) Puzzlers

Last week's Car Talk had a fun puzzler called "Three Pieces of Paper":

Three different numbers are chosen at random, and one is written on each of three slips of paper. The slips are then placed face down on the table. The objective is to choose the slip upon which is written the largest number.

Here are the rules: You can turn over any slip of paper and look at the amount written on it. If for any reason you think this is the largest, you're done; you keep it. Otherwise you discard it and turn over a second slip. Again, if you think this is the one with the biggest number, you keep that one and the game is over. If you don't, you discard that one too.

What are the odds of winning? The obvious answer is one in three, but you can do better than that. After thinking about it a little I figured out the strategy pretty quickly (I won't spoil it here; follow the link above to see the answer). But the question was: how often does the correct strategy give you the answer?

It made for a good "things to think about when trying to fall asleep" insomnia game. And I mostly convinced myself that the answer was 50%. But probability problems are tricky beasts (witness the Monty Hall Problem, which even professional mathematicians got wrong) and I wasn't confident about it. Even after hearing Click and Clack describe the answer on this week's show, asserting that the answer was 50%, I still wanted to prove it to myself.

Why not write a simple program? That way I could run lots of trials and see if the strategy wins 50% of the time.

So here's my silly Python program:

#! /usr/bin/env python

# Cartalk puzzler Feb 2011

import random, time

random.seed()

tot = 0
wins = 0

while True:
    # pick 3 numbers:
    n1 = random.randint(0, 100)
    n2 = random.randint(0, 100)
    n3 = random.randint(0, 100)

    # Always look at but discard the first number.
    # If the second number is greater than the first, stick with it;
    # otherwise choose the third number.
    if n2 > n1 :
        final = n2
    else :
        final = n3

    biggest = max(n1, n2, n3)
    win = (final == biggest)
    tot += 1
    if win :
        wins += 1
    print "%4d %4d %4d %10d %10s %6d/%-6d = %10d%%" % (n1, n2, n3, final,
                                                       str(win),
                                                       wins, tot,
                                                       int(wins*100/tot))
    if tot % 1000 == 0:
        print "(%d ...)" % tot
        time.sleep(1)

It chooses numbers between 0 and 100, for no particular reason; I could randomize that, but it wouldn't matter to the result. I made it print out all the outcomes, but pause for a second after every thousand trials ... otherwise the text scrolls too fast to read.

And indeed, the answer converges very rapidly to 50%. Hurray!

After I wrote the script, I checked Car Talk's website. They have a good breakdown of all the possible outcomes and how they map to a probability. Of course, I could have checked that first, before writing the program. But I was thinking about this in the car while driving home, with no access to the web ... and besides, isn't it always more fun to prove something to yourself than to take someone else's word for it?

Tags: python, programming, probability, puzzles
[ 21:17 Feb 22, 2011    More programming | permalink to this entry | ]