City Puzzle

I thought of a fun puzzle while I was at a conference in Downtown LA. You and I are in a city with a grid layout. All pedestrian signals alternate which direction is allowed to walk, and last exactly the same amount of time. To simplify, we are only allowed to cross one road at each intersection and we can never jaywalk.



We're trying to meet a friend at a restaurant one block north and two blocks east. We come to an intersection. We've got a walk signal going north, and a don't walk signal going east, with a big red timer counting down. The timer says one second. What do we do? Maybe you're thinking it doesn't matter?



Foolishly, you go north. Already, your fate is sealed. At the next intersection you can only go east, so you have no choice but to wait three seconds for the light to change. The intersection after that, you need to go east again. You wait an excruciating five seconds.

I go east. I lost one second waiting for the light to chance, but I'm not worried. As I arrive at the next intersection, I smile to myself and immediately walk whichever way the light allows, east in this case. At the next intersection, I wait a modest four seconds for the light to allow me to go north. One block later, I arrive at the intersection three precious seconds before you do. I high-five our mutual friend. You miss out.



What happened here? The only signal you know about is the one you're standing at. We know that you can go north immediately, but you have to wait one second to go east so, \( \tau_{north} = 0\text{ s} \) and \( \tau_{east} = 1\text{ s} \). We don't know anything about the other lights, but we can try to figure out some average behavior.



To find the average wait time, let's plot out the system. Say each walk signal lasts a time \(T\). The x-axis on the plot below is the time you arrive at the light, marked with the moments when the signals change. The y-axis is the resulting wait time to go in each direction. If you know nothing about the state of an intersection and you want to go east, you could get lucky and arrive when the light allows you to go east. You could also arrive and have to wait \(T\) seconds. One in two chance of catching a walk signal. Average wait time of \(T/2\) if you catch a don't walk signal. Overall, the average time you expect to wait is \( \left < t \right > = \frac{T}{4} \).



We can apply this to the intersections in question. At the intersection (1,0), we must go east. We could get lucky and be able to go immediately, but we expect to wait an average of \(\frac{T}{4}\). We'll write \( \left < t_{(1,0)} \right > = \frac{T}{4} \). The situation at (0,1) is the same, \( \left < t_{(0,1)} \right > = \frac{T}{4} \). At (2,0), you have to wait the same average time as at (1,0) twice, for a total wait time of \( \left < t_{(2,0)} \right > =2 \frac{T}{4} \) from (2,0) to the finish line.

Things are different at (1,1). Here, you get to make a decision. You can immediately go to either (0,1) or (1,0), whichever the light allows. Because you get to choose, the intersection at (1,1) is free. That means a total wait time of only \( \left < t_{(1,1)} \right > = \frac{T}{4} \) from here. That's the value of having multiple options.



The problem is almost solved. At (2,1), we know our options now. We can immediately go north to (2,0), where we expect to wait \(T/2\), or we can wait one second and go to (1,1), where we expect to wait \(T/4\). In other words, \(\left < t_{north}\right > = \frac{T}{2}\) and \(\left < t_{east} \right > = \frac{T}{4} + 1\text{ s}\). As long as T is longer than 4 seconds, you should go east. In general, you should go east unless \(\tau_{east} > \frac{T}{4}\).

It's more complicated for other intersections, but I wrote some code to figure it out. If you're walking in an idealized city and you have Mathematica on your phone, feel free to use it to save time.

tS[t_]:= Piecewise[{{T-t,0<=t<=T},{0,T<=t<=2T}}]/.{T->1}
tE[t_]:= Piecewise[{{0,0<=t<=T},{2T-t,T<=t<=2T}}]/.{T->1}

expectation[fn_]:=Integrate[fn[t]/2,{t,0,2}]

expectation[0,0]:= 0
expectation[0,dy_]:= expectation[dy,0]
expectation[dx_,0] :=(1/2) +expectation[dx-1,0]
expectation[dx_,dy_]:=expectation[Min[tE[#]+expectation[dx-1,dy],tS[#]+expectation[dx,dy-1]]&]

goEast[dx_,dy_,t_]:=(expectation[dx,dy-1] >= t + expectation[dx-1,dy])

»


The Ha Giang Loop

I just got back from an amazing trip to Vietnam. Declan has been traveling in South East Asia for the last few months, so Liz, Phil, and I met up with him in Hanoi. There was a lot to love about this trip, but I think everyone's highlight was the Ha Giang Loop, a three day motorbiking adventure in the northern mountains of Vietnam. If you google this term, you'll find travel blogs claiming that driving the loop is the best thing you can do in Vietnam, all of South East Asia, or all the world. I'll just say, if you find yourself in northern Vietnam with a few days on your hands, you should grab a motorbike and drive the Ha Giang loop.



I found the prospect of illegally riding motorbikes in a very foreign country on very foreign roads intimidating. Declan insisted that there was nothing to worry about. This didn't comfort me much at the time, but I think he was right. The illegality seems to be a non-issue. From what we read, it is illegal to ride a motorbike in Vietnam without a Vietnamese license. However, we passed several policemen and none of them seemed to care about us. Apparently, even if they do stop you, they'll just fine you. Vietnam generally seemed to have a live-and-let-live approach to personal safety. As for the foreign roads, Google Maps and Maps.me worked well, and we seemed to have mobile internet everywhere. Driving in Vietnam looks hectic but you get used to it quickly. I had never even touched a motorbike before this, but I felt comfortable on the road very quickly.



From Hanoi, we grabbed an eight hour sleeper bus to Ha Giang. This was an interesting one. We had trouble finding the My Dinh bus station, and ended up being about ten minutes late. Tough luck, this was our first bus in Vietnam to leave on time. Once the mob of taxi drivers found out that we had missed our bus, one of them offered to "drive us to the bus". Huh? We were desperate and flustered and we agreed. He rushed us into his cab and took off through Hanoi. Twenty minutes later, we've cleared the city limits and we're racing north on the highway. With time to think, this plan doesn't really make sense. How are we going to find the bus? Are we meeting them at the next stop? Did the bus stop already, or will it stop when we reach it? The taxi driver is confusing to talk to, definitely not clearing any of this up. At this point, we were all wondering what kind of scam we had been wrapped up in. Then, we come around a curve and the bus is waiting for us on the side of the highway. It worked! We pulled into Ha Giang at 4 AM and crouched on a stoop until the sun came up.

In Ha Giang, it was no problem to rent bikes. We picked up four of them for about two million dong, something like $100. We fueled up and headed north for Tam Son. Leaving Ha Giang, we passed through a long valley. The road was flat, but we could see mountains start to rise on either side of us.



Pretty soon, we were ascending steeply and looking back down at the valley floor.



At the top of this climb was the Dong Van Karst Plateau. We stopped for some tea and wondered if we were dressed warmly enough for the elevation. We were. We all had wind breakers and gloves. This turned out to be the coldest part of our ride. We descended into Tam Son for lunch, and continued north toward Yen Minh.



We found a great hostel in Yen Minh and stayed for the night. If you're looking for a place to stay, check out the A2 Coffee an Hostel.


Day two was spectacular. We left the hostel early, knowing we had a lot of riding to do. Our plan was to ride north to Dong Van, then south to Meo Vac, then back to Yen Minh via Mau Due.



We stopped in Dong Van for lunch. Phil wasn't feeling too hot and, unrelatedly, we saw a cow being ripped apart in the street.



Between Dong Van and Meo Vac is the Ma Pi Leng pass. This is the most spectacular part of the loop. Don't skip it.



You get it.



After about eight hours of driving, we made it back to Yen Minh before the sun went down. Phil was feeling a bit better



The next day we back tracked to Ha Giang. It was sad leaving.



Back in Ha Giang, we used our remaining daylight to climb to the shrine at the top of the hill. Instead of asking for a few thousand dong to visit, they asked us to carry bricks to a construction site at the top!



We returned our bikes and headed to the bus station where we saw a very sad pig and caught our bus uneventfully. A great trip!



»


Bench

Matt and I made a fancy new bench out of red oak. In case you can't tell it has subtly curved legs and stretchers, with mortice and tenon joints connecting them. The legs attach to the top with some neato through-tenons, exposing the end grain of the wood.



The design was based on images from this Wood Wisperer post. Below are some adapted plans, with the dimensions we ended up using.


Here are some plans of the individual pieces: the seat, the two long stretchers, the two short stretchers, and the four legs. All the parts except for the seat have gentle curves cut into one edge.


We started by making the seat. We edge joined two 40" pieces of 2x8" red oak. We read that you need a jointer to make edge joining work. It would probably help, but we just glued together the factory edges from the lumber yard. There was a visable glue seam in some places, but it was good enough for us.

Speaking of the lumber yard, we went to L. Sweet Lumber in Providence. They were helpful and the wood was beautiful.


Next, we cut the legs and stretchers to length. The legs were made from 2x6" and the stretchers from 1x4".


Next, we cut the mortices. We decided to go with uniform 1/8" shoulders for all of our tenons. This left us with ~1/2" wide mortices for the stretchers and ~1 1/2" for the legs. We used Phil's drill press with some forstner bits to remove most of the wood, then finished the mortices with the chisels.


This was time consuming and difficult, especially for the larger mortices on the seat. These were for through-tenons, so the result would be on display on the seat of the bench. We made some gnarly edges in some places.


Next, the tenons. We did this on the table saw, using a dado. We threw together a table saw sled for this part, and it was very helpful. I can't believe we didn't have a sled before this. We put together a 1/2" dado stack and clamped a stop for the tenon length. We ran the ends of the stretchers and legs over the dado for a few passes, until we reached the stop. The length was 3/4" for the stretcher tenons and just over 1 3/4" for the legs, so that they would barely emerge from the top of the seat. After sanding them to fit, they were looking pretty handsome.


We weren't exactly sure how we would cut the curves into the stretchers and legs. We marked the curves very approximately according to the plan. We traced the small stretcher curves with a 24" drum head. Luckily it had exactly the right radius for our design. For the long stretchers and legs, we didn't have any enormous circles on hand so we just bent a thin piece of wood and clamped it in place.

We didn't have access to a band saw, and we were worried that we'd mess it up with the jig saw. There was no other option, though. The curves looked only a little horrible immediately after cutting, and way better after some fine tuning with the palm sander. Now we had all the pieces ready.

Gluing everything together was almost a disaster. We carefully fit every tenon to its matching mortice with chisels and sand paper, but when we started gluing we realized we had done it wrong and commited to an impossible orientation. We pressed ahead, hoping everything would fit, but the glue started setting and some of the tenons felt stuck half way in. I thought we were doomed. There were some moments of "Oh god, what do we...?! Just hit it! Is it fitting? Just hit it keep hitting it!". After five minutes of terror and dozens of strikes with the mallet, the bench made it together. Somehow, it was square everywhere.

We filled the shameful gaps between the mortices and tenon ends on the top of the seat with a mixture of saw dust and wood glue. This seemed to work.


The next morning, we removed the clamps, and sanded away all the glue. On the seat, we sanded almost 1/8" of the ends of the tenons to make them flush. We worked our way to 400 grit on every surface. We tried some weird fine sanding disks called SandNet from the Home Depot, because they looked fun. It's some kind mesh material made from ancient elven fibers. The pack says it lasts longer because you can wash the sawdust out of it. Instead, they seemed to get ripped up immediately by the sander. I don't know.


Finally, we applied two coats of finishing wax.


Here's the finished product. It turned out to be very heavy and sturdy. Hopefully no one ever has to move it.


»


Programmatic Sol LeWitt Wall Drawing

I visited MASS MoCA with some friends recently. There was a whole building there filled with the work of Sol LeWitt, a contemporary artist famous for minimalist geometric art. We spent a while looking at Wall Drawing #797.



Helen Harrison

This drawing was made in an interesting way. One person drew a starting wavy line at the top. Then artists took turns following the bottom of the line with another line. This was repeated for the whole wall. The result has some complicated behavior. Concave parts produced ridges propagating downward and combining into larger ridges. It reminded us of caustic shapes produced by the complex surface of disturbed water. Phil pointed out that the connection with waves isn't an accident, since this procedure effectively applies Huygens' Principle. He blogged about this too, but my post is better.

We all thought it would be cool to reproduce this idea in a computer. I found a way to do it with a few lines of Mathematica.


Not a perfect match, but it has most of the features we noticed. The heart of it is the overloaded function, requiredY. The points that make up the lines are confined to discrete positiosn in x. With two arguments, it finds the new y value required to put a new point at in the column at index i based on being a distance r from the last point in the row at index j. With one argument, it finds the minimum y required by all other rows. Maybe that makes sense. The rest of the code is just defining the starting curve, repeatedly applying the function that generates a new line, and displaying the results.

xs = Range[200];
ys = 10 + 5 (Sin[xs/10.] + Sin[xs/6.] + Sin[xs/16.]) +
   Last /@ Normal[
      RandomFunction[WienerProcess[0, .75], {0, 199, 1}]][[1]];
next[xs_, ys_, r_] := Module[{requiredY, newYs},
  requiredY[i_, j_] := ys[[j]] - Sqrt[r^2 - Abs[i - j]^2];
  requiredY[i_] :=
   Min[requiredY[i, #] & /@ Range[Max[i - r, 1], Min[i + r, 200]]];
  newYs = requiredY /@ xs;
  newYs
  ]
ListPlot[NestList[next[xs, #, 2] &, ys, 50], Joined -> True,
 Axes -> False, PlotStyle -> {Thickness[0.005]}]
I stumbled on some other neat looking results by accident too.
»


Q Learning Maze Game

I've been learning about reinforcement learning. The simplest version I've heard of is called Q learning. The key to this method is maintaing a Q matrix, which stores information about the quality each state-action pair. Once trained, a player can simply look up their state and take the action with the highest value.

The goal is obviously to train this Q matrix to accurately reflect the game. This can be done by taking moves and updating Q each time in the following way:

As you can see below, when my QLearner is training, it takes random moves every time. I think the more common way to do it is to sometimes take random moves and sometimes take moves according to the current version of Q. That kind of weights the learner toward moves that seem better. It doesn't matter in this case, though. The maze problem is so easy that anything would work.

Here, the reward is simply zero unless the player reaches the goal. At first I set the discount factor, gamma, to be 1. This did not work. Since the random player will always eventually finish the maze, this resulted in every square eventually getting a value of 1. The discount factor means that faster routes to the goal are favored.

import numpy as np
from random import randint

class Maze:
    def __init__(self):
        self.w = 5
        self.h = 5
        p = Tile.player
        b = Tile.block
        e = Tile.empty
        g = Tile.goal
        self.map = [
            [e, e, e, b, g],
            [e, b, e, b, e],
            [e, b, e, e, e],
            [e, b, b, b, b],
            [e, e, e, e, e],
        ]
        self.reset()
    def __repr__(self):
        returnStr = ""
        for i in range(self.h):
            for j in range(self.w):
                if (j, i) == self.playerPos:
                    returnStr += str(Tile.player)
                else:
                    returnStr += str(self.map[i][j])
            returnStr += "\n"
        return returnStr
    def tileAt(self, (x, y)):
        return self.map[y][x]
    def isValidPos(self, (x, y)):
        return all([x >= 0, y >= 0, x < self.w, y < self.h])
    def reset(self):
        self.playerPos = (0, 4)
        self.gameWon = False
    def move(self, dir):
        movePos = addTuple(self.playerPos, dir)
        if self.isValidPos(movePos):
            if self.tileAt(movePos) == Tile.empty:
                self.playerPos = movePos
                return 0
            elif self.tileAt(movePos) == Tile.goal:
                self.playerPos = movePos
                self.gameWon = True
                return 1
            else:
                return 0
        else:
            return 0

class QLearner:
    def __init__(self, maze):
        self.maze = maze
        self.Q = np.zeros((self.maze.w, self.maze.h, 4))
        self.alpha = 0.1
        self.gamma = 0.9
    def learn(self, n):
        for r in range(n):
            while self.maze.gameWon == False:
                i = randint(0,3)
                self.updateQ(i)
            self.maze.reset()
    def updateQ(self, i):
        x0, y0 = self.maze.playerPos
        moveDir = Dir.moveOptions[i]
        reward = self.maze.move(moveDir)
        x, y = self.maze.playerPos

        maxQ = max(self.Q[x, y, [0,1,2,3]])

        self.Q[x0, y0, i] = self.Q[x0, y0, i] + (self.alpha * (reward + (self.gamma * maxQ) - self.Q[x0, y0, i]))
    def getBestMove(self, (x, y)):
        bestMove = Dir.moveOptions[np.argmax(self.Q[x, y, [0,1,2,3]])]
        return bestMove


def addTuple((a1, a2), (b1, b2)):
    return (a1 + b1, a2 + b2)

class Dir:
    UP = (0,-1)
    DOWN = (0, 1)
    LEFT = (-1, 0)
    RIGHT = (1, 0)
    moveOptions = [UP, RIGHT, DOWN, LEFT]

class Tile:
    player = 'p'
    goal = 'g'
    block = 'X'
    empty = ' '

maze = Maze()
learner = QLearner(maze)
learner.learn(1000)

print learner.Q

maze.reset()
while maze.gameWon == False:
    maze.move(learner.getBestMove(maze.playerPos))
    print maze
»