Wednesday, June 26, 2013

A gift at the supermarket

The other day I received a gift while shopping at our neighborhood grocery store.

It wasn't a gift from Key Market; it was a gift from God. Here's what it was: a sense of wonder and gratitude. I was heading over to the baking aisle, and I thought of how wonderful it was to be in a land of plenty, where flour and sugar and salt and baking powder and dozens of herbs and spices, are all on the shelf. And not just flour, but bags of the stuff in various sizes, "all-purpose" flour and bread flour and cake flour, whole wheat flour and organic flour and unbleached flour. And salt—which used to be so valuable that people were paid in it (thus our word salary)—plain salt and iodized salt, sea salt and kosher salt and ice cream salt, from various makers and in various sizes.

And milk! Whole milk and cream and half-and-half and reduced fat and nonfat and organic, soy "milk" in various flavors, almond "milk" and Mocha Mix® all right there with "sell by" dates stamped on them. Fresh eggs are nearby, too—white eggs and brown eggs by the dozen, organic and low-cholesterol eggs, eggs laid by cage-free hens. The grocery store is a marvel, and even if not everything is "health food," the store has a variety of food and drink (and housewares and personal-care products, not to mention pet food and stationery) not imaginable to people a century ago (or even a few decades), or to many people today born in, say, Mali.

Which reminds me of a time when Solomon "made silver and gold as common in Jerusalem as stones" (2 Chronicles 1:15). Solomon may have been richer than anyone else in history, but a middle-class resident of Jerusalem could not have imagined what you and I can see at the neighborhood market.

But here in the United States, and in particular in Silicon Valley, we do live in a sort of Solomon's Jerusalem. The wealth and consumption (and destruction) available to some folks at a whim—astonishing. And even those of us in the "middle-class" truly are rich, as in the richest 1% or 2% of people on the planet.

So that was my gift: a reminder that by any sane measure, I'm rich and fortunate beyond what anyone has a right to deserve. And so, for some time anyway, I complained a bit less than I usually do, I experienced a bit more joy than I usually do. And I hope I also spread a bit more joy, a bit less frustration and consternation than usual.

But this morning I found things to grumble to God about. Wretched man that I am! Thanks be to God that there is no condemnation for us in Christ. And that he will, according to his promise, sanctify us (1 Thessalonians 5:23f) and complete the work he began.

Thursday, June 20, 2013

But wait, Spot-It! has only 55 cards.

In a previous post and its follow-up I described the process by which I decided that Spot-It! likely used 57 symbols and that it could have up to 57 cards in its deck. But as mentioned earlier, the deck actually has only 55 cards. Did they just leave two cards out? Do they have more symbols, or fewer?

Yes, they just left two cards out; no, they use exactly 57 symbols. To figure this out, I created a file "cards.txt", with the name of each symbol on a single line. The symbols on a given card are grouped together in an eight-line stanza; an empty line separates stanzas.

yin-yang
paint
tree
lightning
zebra
clef
ladybug
Canada

bomb
dragon
carrot
paint
ghost
question
bang
clown

spider
…etc.
The excerpt at right signifies that:
  • one card contains the yin/yang sign, the paint dots, tree, lightning bolt, zebra, (treble) clef, ladybug, maple leaf;
  • another card has the bomb, dragon, carrot, paint, ghost, question mark, exclamation point…
you get the idea.

Alert readers may notice that "cards.txt" has names consisting of only one "word" (by which I mean a contiguous sequence of non-whitespace characters) each, and that some of them don't exctly match my summary. The one-"word" thing makes them easier for shell scripts to process, and I translate these internal names into less-cryptic (I hope) things like "maple leaf" (Canada) or "exclamation point" (bang).

The format of "cards.txt" made for easy error checking, which as it turned out was necessary. (If you're thinking at this point, "How anal!" all I can say is "guilty as charged, yer honor.") It also made for some easy analysis. For example, we learn that although most of the symbols appear on 8 cards each, some don't:

% grep -v '^$' cards.txt | sort | uniq -c | sort -n | head -n16
   6 snowman
   7 Canada
   7 bang
   7 cactus
   7 daisy
   7 dinosaur
   7 dog
   7 eye
   7 ice
   7 ladybug
   7 light-bulb
   7 man
   7 question
   7 skull
   7 stop
   8 anchor
% grep -v '^$' cards.txt | sort | uniq -c | sort -n | tail -n3
   8 web
   8 yin-yang
   8 zebra
% 
The (American) English translation of the above is: only six cards have a snowman. Fourteen symbols (maple leaf, exclamation point, cactus, daisy, etc.) appear on only 7 cards each; the rest appear on 8 cards each. This suggests that two cards could be added to the deck. Each card would have a snowman and 7 of the other symbols. Which symbols? Well, any symbol that would appear with the maple leaf (aka "Canada") on a new card must not already appear with the maple leaf on another card. How to decide that?

It takes a few steps. First, a shell script converts "cards.txt" into another file, "cards-sorted.txt":

% L1=1; while [[ $L1 -lt 490 ]] ; do 
    ((L2=L1+7)); sed -n $L1,${L2}p cards.txt | sort | fmt -w222; 
    ((L1=L1+9)); done | 
    sort > cards-sorted.txt
% 
This takes, e.g., lines 1-8 of "cards.txt", sorts them, and combines them into a single line. Then it takes lines 10-17 (that's eight lines) and does the same with them. Then lines 19-26, and so on.

Each line in "cards-sorted.txt" thus corresponds to a single card, and contains the card's one-word symbol names in alphabetical order. Consequently, cards-sorted.txt starts off like this:

% head cards-sorted.txt 
Canada anchor carrot cheese clock knight stop web
Canada apple bang igloo moon scissors snowflake spider
Canada art balloon bomb drop fire lips skull
Canada bottle candle ghost light-bulb lock pencil sunglasses
Canada car cat clover clown dog ok sun
Canada clef ladybug lightning paint tree yin-yang zebra
Canada dolphin dragon eye hand heart key target
anchor apple art dinosaur dolphin ghost ladybug ok
anchor balloon clown lightning snowman spider sunglasses target
anchor bang car clef daisy key lips lock
% 
Now I'll use "cards-sorted.txt" to see which of those fourteen symbols appear together with "Canada" (maple leaf) on any card:
% f() { grep Canada.*$1 cards-sorted.txt; }
% C=; D=; grep -v '^$' cards.txt |sort | uniq -c | sort -n | grep 7 | 
    while read A B; do 
       echo === $B ===
       if f $B; then C="$C $B"; else D="$D $B"; fi 
       echo C=$C
       echo D=$D
    done
… [much output deleted]
C= bang dog eye ladybug light-bulb skull stop
D= Canada cactus daisy dinosaur ice man question
% 
The "C=" symbols already appear together with "Canada" (maple leaf), so we won't put them on the same card as a maple leaf again. Therefore, I think that the following cards, if added, would "complete" a set of 57 cards:
  • snowman, exclamation point, dog, eye, ladybug, light bulb, skull, STOP!
  • snowman, maple leaf, cactus, daisy, dinosaur, ice cube, man, question mark
I wasn't quite confident in this, so I wrote this brief shell script to check it.
% cat checkit.sh 
#!/bin/sh
# Ensure that for any pair of symbols within $C [or $D], no single card 
# contains both members of the pair.

C="bang dog eye ladybug light-bulb skull stop"
D="Canada cactus daisy dinosaur ice man question"

all_combos() {
    while [[ $# -ge 2 ]] ; do
        first=$1
        shift
        for it in $*; do
            echo checking $first $it ...
            if grep $first cards-sorted.txt | grep $it; then 
                echo ERROR $first $it 
            fi
        done
    done
}

all_combos $C
all_combos $D
% 
A visual inspection of the output revealed that we were indeed checking for "bang" and "dog" together, then "bang" and "eye"... and so on. It did all that without ever printing "ERROR", so I think the list is good.

That sure was fun! But let me check one more time. I'll add the above two cards to the list of sorted cards:

% diff cards-sorted.txt  cards-complete.txt 
55a56,57
> snowman bang dog eye ladybug light-bulb skull stop
> snowman Canada cactus daisy dinosaur ice man question
% 
Then let me ensure that given any pair of symbols on a given card, that that card is the only one containing that pair:
% cat check-complete.sh 
#!/bin/sh
# based on checkit.sh -- for every card in the 
# hypothetical "complete" Spot-It! deck (in "cards-complete.txt"),
# extract every pair of symbols. If both members of the pair appear
# on any other card in the complete deck, then print "ERROR"...
TEMPFILE=/tmp/spot-tmp.$$
all_combos() {
    while [[ $# -ge 2 ]] ; do
        first=$1
        shift
        for it in $*; do
            echo checking $first $it ...
            if grep " $first " $TEMPFILE | grep " $it "; then 
                echo ERROR $first $it 
            fi
        done
    done
}
C=cards-complete.txt 
cat $C | while read X; do
    grep -v "$X" $C | sed -e 's/^/ /' -e 's/$/ /' > $TEMPFILE
    all_combos $X
done
rm -f /tmp/spot-tmp*
% 
The above script, "check-complete.sh", completed without ever saying "ERROR".
% ./check-complete.sh > x
% grep -m5 ERROR x
ERROR Canada igloo
ERROR igloo question
ERROR igloo man
ERROR ice igloo
ERROR cactus igloo
% 
To make sure that it actually works, though, I changed the last card to say "igloo Canada…" rather than the correct "snowman Canada…". The script did in fact catch the error, as you can see at right.

Am I satisfied now? I refer you to the "anal" comment above. (In other words, No.) One more thing: the above check-complete.sh verified that we didn't have any PAIR of symbols in common between any pair of cards. What it didn't do is verify that there was in fact any symbol in common between any pair of cards. That's done by this script:

% cat overlaps.sh
#!/bin/sh
# Confirm that at least one symbol overlaps every card vs every other card.
TEMPFILE=/tmp/spot-tmp.$$

check() {
    # Given two cards ($1, $2), ensure exactly one word is in common.
    if [[ $# -ne 2 ]] ; then
        echo "check() called with wrong # of args"
        exit 1;
    fi
    ACARD="$1"
    BCARD="$2"
    NUM=0
    for asym in $ACARD; do
        for bsym in $BCARD; do
            if [[ $asym == $bsym ]] ; then
                ((NUM=NUM+1))
            fi
        done
    done
    if [[ $NUM -ne 1 ]] ; then
        echo ERROR: card1=$ACARD
        echo ERROR: card2=$BCARD
    fi
}

verify_one() {
    # Handle one card's syms (args) vs the rest of the deck ($TEMPFILE)
    ONE="$*"
    cat $TEMPFILE | while read IT; do
        echo checking $ONE ==vs== $IT
        check "$ONE" "$IT"
    done
}
C=cards-complete.txt 
cat $C | while read X; do
    grep -v "$X" $C | sed -e 's/^/ /' -e 's/$/ /' > $TEMPFILE
    verify_one $X
done
rm -f /tmp/spot-tmp*
% 
This completed without error, but just to make sure, I modified the last card to use nonexistent symbol "snowman2" and re-ran it, yielding:
% ./overlaps.sh > x; grep -m6 ERROR x
ERROR: card1=anchor balloon clown lightning snowman spider sunglasses target
ERROR: card2=snowman2 Canada cactus daisy dinosaur ice man question
ERROR: card1=apple bomb cat hand lock snowman tree web
ERROR: card2=snowman2 Canada cactus daisy dinosaur ice man question
ERROR: card1=art candle carrot key moon snowman sun yin-yang
ERROR: card2=snowman2 Canada cactus daisy dinosaur ice man question
% 
Of course, each pair of cards shown (there are lots more) should have the "snowman" in common. By tweaking the last card, I removed that sharing. So the script works, and the hypothetical deck is correct.

Wednesday, June 19, 2013

More Spot-It! Math

In a previous post, I mentioned some work with pencil and paper that led me to a certain formula. This post adds a some detail, and I hope it'll be easier to follow. As you may recall from that previous post, I use M to refer to the number of symbols on a given card, and N to refer to the number of distinct symbols (or "alphabet") from which the symbols are drawn. So, continuing on, here's my exploration of the puzzle starting with M=3.
1|ABC
2|A
D
F
E
G
3|A
4|B
DF
5|BEG
6|CDG
7|CEF
To approach the problem I decided to list each card's symbols in increasing alphabetical order. Please refer to the table at left. The progression A-B-C, A-D-E, A-F-G is perhaps obvious. What of the B-x-x cards?

After each "B", we take vertical slices of the dotted blue square, the first slice being the D F in the thin black border. The thing to note with the "B"s is that the "F" is directly below the "D" (i.e., it's down one row and zero symbols to the right).

Similarly on card 5, B-E-G, the "G" is directly below the "E" in the dotted-blue square.

Regarding the "C"s: note on card 6, C-D-G, that the G is below and to the right of the D in the dotted blue square. Card 7 (C-E-F) shows the principle (we'll expand on this later) that when "below and to the right" runs off the right-hand edge of the dotted blue square, we simply resume counting from the left-most symbol in the same row within the dotted blue square. Thus card 7's C-E-F.

So for cards matching the pattern B-x-x, the 2nd "x" is directly below (i.e., displaced zero symbols to the right) of the 1st "x". For C-x-x, the 2nd "x" is displaced one symbol to the right of the 1st "x". How did I arrive at this? Trial and error and eventual "success."

This solution is symmetric in that each of the 7 symbols appears on 4 cards; any given pair of symbols appears upon one and only one card. (Wait, does every possible pair of symbols appear on a card? Yes.)

Suppose we have M=4, N=13? Does the pattern above generalize? What will we do with cards D-x-x-x—would each subsequent "x" be one row below and two symbols to the right of its predecessor "x"?

1|ABCD
2|A
E
H
K
FG
I J
L M
3|A
4|A
5|B
EHK
6|BFIL
7|BGJM
8|CEIM
9|CFJK
10|CGHL
11|D E J L
12|DFHM
13|DGIK
In a word, "Yes." As the table at right shows, the B-x-x-x cards take vertical slices (a subsequent "x" is directly below the preceding "x"). The 3rd (4th) symbol in a C-x-x-x card is one symbol down and to the right of the 2nd (3rd) symbol within the dotted blue square, as C-E-I-M. Again, if you'd run off the right-hand end of a row, continue counting from the left, staying within the dotted blue box, as in card 9, C-F-J-K.

In the D-x-x-x cards, symbols are one down and two to the right of their predecessors within the dotted blue square, again resuming counting from the left when we run off the right-hand side of a row: thus D-E-J-L, D-F-H-M, D-G-I-K.

As in the M=3,N=7 case, we have each of the N symbols appearing on M cards each; every possible pair of symbols appearing on one card; every pair of cards having one and only one symbol in common. At least so far, then, the solution generalizes thus:

  1. one card with the first M symbols (e.g., A-B-C-D in the table at right)
  2. M-1 cards, which include the (M-1)×(M-1) blue-dotted square region
  3. (M-1)2 cards (in the table at right, three B-x-x-x cards, three C-x-x-x cards, three D-x-x-x cards). Each set of M-1 cards takes one symbol from each row of the blue-dotted square:
    • the B-x-x-x cards take vertical slices, i.e., each subsequent symbol is zero columns to the right of its predecessor in the previous row;
    • in the C-x-x-x cards, each subsequent "x" comes from one column to the right of its predecessor in the previous row (and if you're about to run off the end, resume counting at the far left of the same row);
    • in the D-x-x-x cards, each subsequent "x" comes from two columns to the right of its predecessor in the previous row (and if you're about to run off the end, resume counting at the far left of the same row);
    • … and so on
    If (M-1) is a prime number, then the above procedure yields M-1 sets of M-1 symbols in the blue-dotted square. Each set of M-1 symbols has one from each row in the blue-dotted square. And each set has at most one symbol in common with any other set. For example, E-H-K and E-I-M have only the "E" in common. And either set has only the "E" in common with E-J-L.
    Exercise: What if the (M-1)×(M-1) square is 4×4? Would the D-x-x-x-x cards run into some kind of trouble? (Answer: Yes. And I haven't figured my way out of it.)
This yields (M(M-1)+1) cards total, and the same number of symbols. As suggested in my snarky "Exercise:" comment, the above solution works unaltered only when M-1 is a prime number—which, fortunately for me, is true when M is 8.

And that is true for Spot-It!—each card has eight symbols (M=8), and the "optimum" value of N is 8*7+1=57 symbols, which allows for a deck of 57 cards. In my "ideal" (symmetric) deck, each of the 57 symbols would appear eight times (i.e., once on each of eight cards).

How does this relate to the actual Spot-It! cards? More on that in a subsequent post.

Saturday, June 15, 2013

A "Spot It!" puzzle

The game of “Spot It!” (blueorangegames.com) provided an entertaining mathematical and programming puzzle, which I have mostly (I think) figured out.

In case you haven't seen it, there's a deck of some 55 cards; on each card are eight stylized figures of various creatures or things: man, dragon, dog, cat, car, daisy, maple leaf, and so on. Any two cards in the deck have one and only one figure in common: cards 1 and 2 might both have a man, cards 2 and 3 might both have a dragon, but then card 1 won't have a dragon; card 3 won't have a man.

This strikes some people as odd. “Really?” they say. “Any two cards have exactly one thing in common?” It is indeed true. Which of course made me wonder: How does that work? If each card has M figures out of an alphabet of N, how many cards can you have?

Naturally, I started with M=2 and came upon this rather simple set of 3 cards with N=3 symbols:

A B  
A   C
  B C
If we have N=4 then one could imagine cards (A,B), (A,C), (A,D), but then what? You can't go (B,C) because that has nothing in common with (A,D). So bumping N from 3→4 actually reduces the number of cards with M=2.

Thus with M=2 there's a sort of optimum value of N, namely 3. What's the optimum value of N for M=3 or M=4? The number of cards might have something to do with the number of combinations of N things taken M at a time, but it doesn't say much about the optimum N for a given M.

After many stabs at this with pencil and paper, I came up with the following lists for M=3 and M=4:

1 |A B C        
2 |A     D E    
3 |A         F G
4 |  B   D   F  
5 |  B     E   G
6 |    C D     G
7 |    C   E F  
 
1 |A B C D                  
2 |A       E F G            
3 |A             H I J      
4 |A                   K L M
5 |  B     E     H     K    
6 |  B       F     I     L  
7 |  B         G     J     M
8 |    C   E       I       M
9 |    C     F       J K    
10 |    C       G H       L  
11 |      D E         J   L  
12 |      D   F   H         M
13 |      D     G   I   K    
The pattern that seems to emerge from this is that we have
1. card with figures {1..M}
2. card with figures {1, M+1..2M-1} (M-1) cards M sets of (M-1) cards
M. card with figures {1, (M-1)(M-1)+2..M(M-1)+1}
(M-1)(M-1)+2. card with figures {M,M+1} and (M-2) figures from the set {2M..M(M-1)+1} (M-1) cards
M(M-1)+1. card with figures {M,2M-1} and (M-2) figures from the set {2M..M(M-1)+1}
…the total being M(M-1)+1 figures in the alphabet, and M(M-1)+1 cards.

I believe the optimal N for a given M is M(M-1)+1; this gives a symmetric (I think) set of cards, with each symbol appearing on M cards. I haven't proven any of this, but I have (of course) written some code that generates a set of these things for the case where M-1 is prime—which is the case for the real Spot It! game (M=8). In particular if M=8 then the optimum N would be 8*7+1=57, and the deck could have 57 cards. Why does the real Spot It! card game have only 55 cards in the deck? You got me.

I'll add a link to the code one of these days but right now I think it's time for bed.
Update: Code is here

Sunday, June 09, 2013

The Aussie Cure For Tired Old… Bathtubs!

Short version: Accident leads to astonishing discovery: Aussie shampoo cleaned up stains on our old bathtub that scrubbing never did. Details follow.
Our bathtub is old—maybe older than I am. On its floor was (I thought) a permanent layer of dirt, maybe some sort of stain. I tried the usual chemical helps (Bon Ami, X-14®, Formula 409®) including a lot of elbow grease, all to no avail. So I gave up years ago on ever seeing the original finish. But one day, we had a happy accident: somebody stood up a bottle of Aussie shampoo, upside-down, without first securing the lid. It was a big spill.

The bottle was mostly empty, but where the pool of shampoo had been, the stains were gone, like the old gospel song: My stains were washed away / And my night was turned to day (or maybe that was "My sins were…").

In any case, I used a lot more shampoo on the bathtub floor, toward the top and right of the photo you see at right. I tried a couple of other brands, which I won't mention here. The Aussie outperformed them.

Yesterday morning I decided to take care of the remaining 40% or so of the tub. The surface was mostly dry (this is important). I squirted liberally from the giant bottle. The stuff sorta piles up, as you can see in the photo below/left.

I kept squirting, and eventually ended up with a layer over the entire stained region. This requires a dry tub surface, lest the shampoo slide off the stain and toward the drain end of the tub. When I said "liberally" I mean I might have used half the bottle. I uploaded a high-resolution photo of the result (click on the photo below/right).

The shampoo sat for maybe eight hours; after that, it was, well, shiny. I shot a photo where you can see the reflection of the camera:

How did it work? Well, I stepped into the shower (ugh! my feet were dirty!) and rinsed the shampoo away. It took a lot of rinsing, but no scrubbing. Here's what it looked like at the end:
The 50-year-old stains are gone, and the tub looks better than it has in years. I should have cleaned up the footprints before taking the picture. Next time.

Saturday, June 08, 2013

When Thunderbird Uses Too Much Memory

So I run Thunderbird on Linux, and the other day at work I noticed thunderbird taking up way too much memory—both virtual and physical, as top(1) showed:
top - 10:57:52 up  2:48,  2 users,  load average: 0.09, 0.08, 0.04
Tasks: 117 total,   2 running, 115 sleeping,   0 stopped,   0 zombie
Cpu(s): 14.3%us,  2.5%sy,  0.0%ni, 83.3%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:    998152k total,   827696k used,   170456k free,    14308k buffers
Swap:  4192252k total,    11084k used,  4181168k free,   398176k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
 4144 collin    20   0  760m 218m  32m R   23 22.5   7:31.57 firefox
 4097 collin    20   0  502m 185m  28m S    0 19.0   4:47.57 thunderbird
 1888 root      20   0 55352  17m 3960 S    8  1.8   2:11.66 Xorg
 4905 collin    20   0 38620  12m  10m S    0  1.2   0:00.88 notification-da
…
The above is from mh home computer, but at work thunderbird was showing something like 1680m virtual size, and the %MEM was something like 70.0. Way, way too high. Of course, it also made the computer run slower than molasses in January.

A web search led me to "Daifne"’s advice on http://forums.mozillazine.org/viewtopic.php?f=39&t=530263#p2794923—the short version of which is to

  • quit Thunderbird (probably kill(1) it to be sure), then
  • cd into the profile directory and
  • remove all files matching *.msf; then
  • restart thunderbird and
  • compact all folders (this last is optional if you've already got tbird configured to automagically compact folders frequently)
After doing all that, the memory numbers dropped dramatically, to about 1/3 their former values.

Amazing, really, how much easier some things are with the web. Of course the web is partly the cause of so much complexity. Is that dialectical?