Archive for the ‘puzzles & games’ Category.

Programming challenge: anagrams in PCRE

(inspired by a question a student asked me in the course I TA)

In the language of your choice, write a function that takes a string argument and returns a string representing the PCRE pattern that matches all anagrams of the input word. For example, if the argument to the function is “retrains”, it should return a regex pattern that matches “restrain”, “retrains”, “strainer”, “terrains”, and “trainers” as well as a bunch of strings that aren’t real words. You can assume that all characters in the input string are English letters. The length of the output string should be polynomial in the length of the input (i.e., just enumerating all possible anagrams doesn’t count, since that takes exponential space).

Also, if you haven’t seen this chestnut: write a POSIX-compliant regex pattern that matches strings of the form a* (i.e., “”, “a”, “aa”, “aaa”, etc) which have composite (non-prime) length.

…and people claim that regular expressions are only as powerful as DFAs are. :-P

Word Games, part 3

What do you mean I haven’t posted in 3 months!? …oh, I guess I’ve made a bunch of half-written drafts, but never finished any of them. I should get on that.

In the meantime, here’s a word game for you. How many words can you name in 10 minutes that contain all 5 vowels? Y’s are optional but stylish. It’s okay if the words contain some vowels multiple times, or if the vowels are out of order. My word list is in the first comment.

Logic Puzzles vs. Hat Problem II

This is closer to the unsolved hat problem I have previously discussed than the solved hat problem I discussed. It made the rounds on a “Math Enthusiasts” mailing list I’m on today.

There are n people who have been given a challenge: tomorrow, a hat will be placed on each of their heads. There are n different colors of hats, and colors can be repeated (or not used at all). Everyone will be able to see the hats on everyone else’s head but not their own. No one is allowed to communicate in any way while looking at each others’ hats. Then everyone is lead away into separate rooms and each person is asked the color of their own hat. If at least one person answers correctly, the group as a whole wins (unlike the unsolved hat problem mentioned above, no one is penalized for an incorrect guess). The people can discuss strategy amongst themselves before the challenge starts, but cannot communicate in any way once anyone gets a hat.

What strategy can they use to guarantee that the group wins?

and for the pedants out there: all participants are told all possible hat colors before the challenge starts (no need to guess what the unseen colors might be), and n is small enough that all colors can be distinguished on sight (it uses less than a million different shades of blue, for instance).

The photograph lies at my feet, falls from my fingers, is in my hand.

Dearest Internet, I write you today to share a discovery that excited my very being. I have found a wonderful connection between two ideas in which I merely dabble, and the way they complement each other so perfectly has given me new insight into both. The phrase “strawberries and cream” comes to mind. I am, of course, referring to quantum electrodynamics and video games.

If the complementarity is not immediately obvious, let me direct your attention to a particular video game, Braid. Oh, Internet, it is a marvelous game, full of challenge and fun! In the way that Portal is a puzzle game wherein you must manipulate space to solve the puzzles, Braid is a puzzle game wherein you manipulate time. Braid is also an homage to Super Mario Brothers, which gives it a nostalgic feel. But on top of the usual “go left,” “go right,” and “jump” commands, you have at your disposal a “rewind time” button that is your main tool throughout the game. You control a character named Tim, whose goal is to go from the door on the left of the level to the door on the right side, while solving any puzzles preventing this (yes, I am simplifying, but that’s the important part for now).

Although the connection to QED may already be coming into focus, I should like to take a moment to remind you about the discipline. As you may recall, Internet, a man named Richard Feynman worked many a year on QED. He invented something called Feynman Diagrams, which are a very simple way to visually represent interactions between particles. He drew them as graphs with time along one axis and space along another, such as this:

In this image, the horizontal axis is time and the vertical axis is space. Depicted is one possible interaction between an electron and a photon. If one views time as monotonically moving forward (in the intuitive sense by which one normally perceives it), the photon coming down from the top spontaneously degenerates into an electron-positron pair (note that the positron is an anti-electron), and then the positron encounters the electron near the bottom of the diagram, and the two annihilate each other and turn into another photon.

However, there is another way to view this event. Anti-particles behave just like their (non-anti) counterparts moving backwards in time, since they have opposite charge and opposite spin but are otherwise identical. In other words, my good Internet, we could just as easily view this diagram as depicting an electron moving along the bottom of the diagram, then spontaneously “turning around” and moving backwards in time, while shooting off a photon as it reverses direction. It continues to move up the diagram, traveling backwards through time, and then spontaneously reverses its direction once more to travel forwards through time, sending out another photon as it does so. Although this photon gets sent backwards in time, we would perceive it normally because the photon is its own antiparticle (because it has no charge).

This reminded me quite strongly of certain levels in Braid, wherein time goes forwards as Tim moves to the right and backwards as he moves to the left. Here is an example, though it contains spoilers if you have not yet played the game. To give a better illustration of their similarity, consider the following diagram. Living things are in blue, photons are in red, and objects and platforms are in black.

If one were playing the game, one would see Tim come out of the door at the bottom left of the image, travel to the right (going forwards through time) until time E, then shoot out a photon, turn around, and jump up onto the platform (going backwards in time), jump over the Goomba at time B (Goombas can only be killed when going forwards through time). Tim would then turn around at time A (shooting a photon to the left in the process), jump forwards through time and land on the Goomba to kill it, then jump at time D to get to the platform with the door and exit the level.

If, instead, we needed to watch these events as time monotonically increased, we would observe a photon on the platform and a Tim on the floor. At time A, the photon spontaneously decays into a Tim-antiTim pair. The Tim jumps immediately, while a moment later the antiTim unjumps. At time B, a Goomba comes into existence and is killed by the descending Tim. The antiTim, meanwhile, is high above and dodges the event. At time C, the Tim and antiTim collide, annihilate each other and become a photon again, though this photon decays into another Tim-antiTim pair at time D. The Tim jumps and the antiTim unjumps. Then the platform winks out of existence, and the antiTim falls through the space where it used to be. At time E, the antiTim encounters the Tim from the floor, the two annihilate each other and become a photon. The platform materializes above, the remaining Tim lands on it and encounters the final door, finishing the level. When I first realized this, it was a very exciting connection for me. I imagine, dear Internet, that you now share my spark of insight.

If you desire to play Braid for yourself, it is available for download on XBox, Windows, and Mac. The demo is free, and the entire game is $15.

Logic Puzzles vs. Gambler’s Paradox

I got this one from Alasdair months ago, and it’s a doozy. However, it’s really only intended for the mathematically minded, so feel free to skip if you’re not comfortable with introductory probability. It’s a multi-part question, but the first parts are intended to be easy, so don’t second-guess yourself too much on those.

  1. A guy is repeatedly rolling an unbiased six-sided die in a room when you enter the room and start watching him. How many rolls do you expect to watch before he rolls a 1?
  2. On further inspection, you notice that he has written down his previous rolls in a list. How far back in the list do you expect to have to look before seeing the previous 1? You can assume that the guy has been doing this for long enough that he rolled a 1 at some point in the past.
  3. Define a “drought of 1’s” as the die rolls between successive 1’s (including the bounding 1’s). For instance, the rolls 1-4-2-1-5-1 would constitute a drought of length 4 followed by a drought of length 3. What is the expected length of a drought of 1’s?

The typical answers to the above questions are six, six, and seven (since we’re including both the starting 1 and the ending 1). However, this implies that on average droughts will have length seven, but when you walk into the room the average drought will have length twelve: you’d expect to be six rolls into the drought already, and you’d expect six more once you start watching. What’s going on here? How should this discrepancy be resolved?

Logic Puzzles vs. Prisoner’s Dilemma

Also courtesy of Steamboat Steven. That guy has all kinds of neat puzzles!

There are n prisoners on a train being taken to a prison. Once they arrive there, they will each be put in separate sensory deprivation chambers. They will have no conception of how long they have been in there. However, sometimes a guard will take one of them into a room with two switches on the wall, make the prisoner flip one of the switches, and send him back to his sensory deprivation chamber. If you wait long enough, every prisoner will go to the switch room an arbitrarily large number of times (i.e., none of them will be “starved” of visits to the switch room). At any time, any prisoner may make the claim that all prisoners have been in the switch room at least once. If he is right when making this claim, they will all be set free. If he is wrong, they will all be killed.

The prisoners can discuss and agree on a strategy for the switches right now, but once they reach the prison they won’t see each other again. They don’t know the initial configuration of the switches. No prisoner will know how many other prisoners have visited the switch room before him; the person who goes to the switch room first won’t know he’s the first. They won’t know how often the guards take people to the switch room, and even if they did they wouldn’t know how much time has passed between their own visits.

How can they be guaranteed to eventually go free?

Logic Puzzles vs. Hat Problem

Steamboat Steven gave me this gem. Unlike my previous discussion of a hat problem, this one can be solved in a reasonably short amount of time.

There are n people on a staircase facing downstairs when a hat is placed on each person’s head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.

The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?

One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?

Liar’s Poker: a tricky problem, part 3

I’ve been working off and on to find the optimal strategy for the final round of a game of liar’s poker. I’ve gotten a bit farther on it, and it now looks solveable. I’ve now solved the 12-card deck version (i.e. if the deck only contains aces, kings, and queens), and I suspect I’ve got an algorithm that will solve the whole problem in a reasonable amount of time.

A few more lemmata →

Liar’s Poker: a tricky problem, part 2

I recently wrote about a card game called Liar’s Poker and my endeavours to find an optimal strategy for the final round. Some extra progress has been made, but it’s still a long ways off. Despite what I wrote when I edited my previous post, I’m no longer convinced that we can adapt Simplex or a gradient descent algorithm to solve this. It turns out that although the gradient function is piecewise linear, there are an exponential number of different linear regions in it, and I’m not convinced we can do something like Simplex without enumerating them all. but here’s some other stuff Reid and I have done on the problem:

More strategies and proofs and stuff →

Liar’s Poker: a tricky problem

Liar’s Poker is a card game we sometimes play around the office. It’s a pretty simple game to learn if you’re already familiar with poker hands: the rules to Liar's Poker, followed by some work figuring out the strategy for the final round →