A puzzle like the one shown (left) played a role in my first date with my wife Margie. I'll get to the puzzle in a bit. In last week's blog entry, I described how we were introduced by a computer dating service called Data-Mate.
Margie was on a list I received on January 7, 1969, in my fifth year of using these computerized dating services. I'd met many nice women in those years, but none of those introductions had grown into a lasting relationship, although a few were of reasonably long duration.
Why was Margie the one I proposed to on February 7, 1970, a year to the day after we met? In an earlier blog entry about Margie, I noted that, "It turned out that we each had close relatives in Roslyn Heights, New York who lived next door to each other, and were good friends. We only found this out some time after we started dating. They had never gotten us together. Actually, had they done so much earlier in our lives, we might not have been ready for each other."
So step one was that I had to be psychologically ready for the possibility of marriage. Despite the fact that most of my college friends had already married, that was a point which it had taken me a long time to get to. I was 27 when I met Margie. I think if I had met her a few years earlier, I wouldn't have been ready.
As a graduate student in Electrical Engineering at MIT, working on a thesis in the field of Computer Science, I knew a lot of people who might have been described as "computer nerds", and I was a bit of one myself. These were people who were fascinated by the relatively new art of computer programming, and immersed themselves in it, sometimes to the exclusion of almost everything else in their lives (I wasn't quite as caught up as that).
But while this phenomenon is well known to the general public these days, it was not widely recognized back in 1969. Computers were mostly large "mainframes", minicomputers were just coming along, and "personal" computers didn't exist at all. Members of the general public tended to look upon anyone working with computers not as a little bit strange, but rather as probably a genius. This might have helped me to make a good impression on Margie.
I also showed up for my date rather well dressed, and there's a tale behind that. I hate shopping for clothes, but wanted to upgrade my appearance nevertheless. I requested the assistance of Julia Beckreck, wife of my friend and MIT classmate Larry Beckreck. Julia was happy to oblige, and led me on a shopping spree that hit Boston stores such as Louis. The resulting wardrobe was a major improvement over my earlier "whatever" attitude towards clothing. Note 1
Margie was not the first person I called from the list (fragment to the right), but some time during the week of February 2, we had a reasonably lengthy phone conversation. My note "See Fri" (Friday, February 7) can be seen on the list. I also wrote "Sat 2/22", making a note that her twenty-fifth birthday was coming up soon.
Margie mentioned a puzzle she had come across, the triangular puzzle seen at the top of this entry. The version in that picture is one that's handed out by the restaurant chain Cracker Barrel, to amuse patrons while they're waiting there for their food to be prepared. Note 2
The puzzle intrigued me. The rules allow you to remove any peg you can jump over with another (in a straight line of three contiguous pegs, like a jump in Checkers). The objective is to eliminate all the pegs but one by a series of 13 such jumps. I tried to solve it myself, without success.
Ah, but I had a computer in my lab - a half-million-dollar PDP-10 mainframe. And being always willing to procrastinate on my thesis work, I decided to write a computer program to solve the puzzle by an exhaustive search, which I proceeded to do. Note 3
Margie and her roommate Sue Saaz greeted me when I arrived that evening, and I seem to recall a brief moment before Margie identified herself when I was unsure which one was my date for the evening. I took her to the Blue Parrot Café in Cambridge. Going out to a café or coffee shop was typical on a blind date, as it wasn't a major commitment for either party if it didn't work out.
I don't remember what we talked about in any detail, but I no doubt tried to impress her with my having used a computer to solve the puzzle she had told me about. We clicked pretty quickly over the next few weeks, and it wasn't long before we were seeing each other exclusively.
In Daniel Slater's book, Love in the Time of Algorithms: What Technology Does to Meeting and Mating, he quoted Margie as saying that she thought "We were matched [by the computer program] because we were both short, educated, and Jewish." On the questionnaires I had submitted to Operation Match and Data-Mate, I had been asked to specify my religion, and I responded with "Jewish". I was also asked whether I would date women of a different religion, and I said I would.
But having listed myself as Jewish, I found that I was matched only with Jewish women. The matches, after all, had to work both ways, and perhaps many Jewish women were asking to be matched only with Jewish men (Margie doesn't remember how she answered that question). In order to get more diversity in my matches, I was thinking about submitting another questionnaire and leaving my religion unspecified. Who knows, one questionnaire later, and I might have missed Margie.
Clearly there was a lot of happenstance in my connecting with Margie. At any one of a number of points, we each could have taken another path. After my last blog entry, Data-Mate, my daughter Sara posted a link to it on her Facebook page, which quickly attracted over sixty "Likes". In it, Sara commented, "For those of you who didn't know, I am alive because of 1960s computer dating." Note 4
But of course, every new baby is the result of a shuffling of the genetic deck. If Sara had been conceived a day later, she would have been a different person, and maybe even a different sex.
Obviously, all the events described above were only the prelude to a year of gradually getting to know one another. We discovered what we had in common (particularly our common values), and learned about our differences. We began building a strong relationship, a process that continued even after marriage. Here's to the last 45 happy years with Margie, and here's hoping for many more to come.
Note 1: Louis still exists, as you can see from its web page, but it's become so outrageously expensive that I no longer shop there. I don't see any prices on the web page. Shopping at Louis is a bit like buying a yacht: if you have to ask the price, you can't afford it.
Julia brought her son Seth along in a stroller. At one point, the salesman complimented me on my beautiful child. I didn't disabuse him of the notion. [return to text]
Note 3: In order to specify a solution, and to describe my computer program, let's start by numbering the holes as shown below:
A solution that gets you to the state shown to the left is 4-1, 6-4, 1-6, 7-2, 13-4, 2-7, 10-8, 15-13, 12-14, 7-9. From that point, the jumps 6-13, 14-12, 11-13 will solve the puzzle, leaving only a single peg in position 13 (the middle of the bottom row). Click the next link for a YouTube animation of the left-right reversed solution.
How did I solve it with a computer program?
This is the technical part of this blog entry - you will need some familiarity with computer programming to understand it. Otherwise, feel free to skip it.
Having numbered the holes in the puzzle as shown, I used 15 bits in a computer "word" to specify the state of the puzzle (0 in the corresponding bit position = no peg in the hole, 1 in the corresponding bit position = peg in the hole).
I then listed all possible jumps (consult the image while reading these). The 12 possible jumps parallel to the base are: left-to-right jumps 4-6 (removing peg 5), 7-9, 8-10, 11-13, 12-14, and 13-15. The corresponding right-to-left jumps are the reverse, 6-4, 9-7, 10-8, 13-11, 14-12, and 15-13.
By symmetry, there are also 12 possible jumps parallel to the 1-11 side (6-13, 3-8, 5-12, 1-4, and so on), and 12 possible jumps parallel to the 1-15 side. That gives a total of 36 potential jumps.
From any given starting point, a jump can be taken if its first and center positions are filled, and its final position is empty. As an example, look again at the sample position given in the picture. Given that position, in the word representing the board position, bits 6, 9, 11, and 14 would contain 1, and all other positions would be zero. Since bits 6 and 9 are 1, and bit 13 is zero, the 6-13 jump can be taken. Similarly, the 14-5 jump can be taken, but no other jumps are possible.
The main program started from the initial position, the one shown way up at the top of this blog entry, with all positions filled except position 1. It fed the word representing that position (all bits set except for bit 1) to an evaluation subroutine. That subroutine pushed the board position onto the stack, and then scanned through all 36 potential jumps. For any jump that could be taken, the subroutine "took" the jump (that is, computed the new position that taking the jump would yield), and called itself recursively to evaluate that new position.
If no jumps were possible, the evaluation subroutine just popped its input off the stack and returned. But if the position to be evaluated had only a single bit set to 1, the program halted. When it in fact did so, I used a debugger to look at the stack to read out the sequence of positions the program had gone through to get to that point. I was thus able to quickly get the result of an exhaustive search without bothering to write any output routines at all. I wrote the whole thing in PDP-10 assembly language, and it ran to completion in a second or two.
The only languages we had available on our machine were assembly (using the MIDAS assembler), and the high-level language LISP. Given how easy it was to save a board position in only 15 bits, which fit into a PDP-10's 18-bit half-word, assembly seemed the better choice. It didn't take me very long to write.
By the way, it's very easy to tell if a computer word has only a single bit set. Call the contents of the word N. If N is non-zero, and the value N AND (N-1) is zero (where AND represents the bit-by-bit logical-AND operation), then the binary representation of N has only a single 1 in it. N AND (N-1) is the same as N, except with the right-most 1 reset to a 0. This is the sort of trick we used back when we programmed in assembly language. We needed such tricks - the machines weren't very fast (by today's standards). [return to text]
Note 4: Sara's thoughts and this entry call to mind a spoof published yesterday by the ONION called, Parents Reminisce To Children About Dating Algorithm That Brought Them Together. [return to text]
This photo was taken in Montréal in August, 1969, on a trip that I described in my blog entry Mont-Tremblant. You find out a lot about another person when you travel together. [return to text]