?

Log in

Give me not speed nor certainty

> Recent Entries
> Archive
> Friends
> Profile
> previous 10 entries

October 30th, 2009


01:27 am
Shown here is a split-flap single-digit display in action. The display is designed in sketchup, printed using a laser cutter on birch, and made of absolutely nothing but glued wood. The motor is a three-wire switched reluctance motor, which I control by energizing the three coils independently using an RBBB Arduino-like microcontroller and a handful of transistors. In this video I'm using the laptop to talk over a serial cable with the microcontroller, sending it digits to print. Eventually, this will be part of a metro bus real-time arrival board I'm going to convince some store owner to put in their window for the benefit of passers-by. This was built at Metrix Create:Space. Matt took the video on his cracked iPhone.



For a portion of the video I'm typing out pi, but I'm so excited that it's working that I miss a few digits in the middle.

You can make one if you want. The design is on thingiverse.

(11 comments | Leave a comment)

September 4th, 2009


10:49 am
Now that the qualifying round for Google Code Jam is over, I'd like to share my solution to the third problem.

Imagine you're sailing a ship in choppy seas towards a faraway shore. Every second, a bit of choppy wave slaps he side of your boat, jogging your boat a little bit to the left or to the right. Because of the choppy seas, it's not certain where you'll make landfall. You could make landfall in the middle of the shore, or you could make landfall significantly to the left or to the right. The chance that you'll land at any given stretch of beach is not uniform - it's small at the edges and large in the middle. We can figure out the relative chances of making landfall at any particular point on the beach by drawing a picture. A very simple diagram depicts us in three successive moments before making landfall:
1 2 3 .
      x|
    x  |
  x   x|
x   x  |
  x   x|
    x  |
      x|

At Moment 1 you have an equal chance of being slapped left or right, so your chances of being at any position at Moment 1 are equal:
1 2 3 .
      x|
    x  |
  1   x|
1   x  |
  1   x|
    x  |
      x|

At Moment 2 you could be on he left and get slapped left, or you could be on the left and slapped right, or you could be on the right and slapped left, or you could be on the right and slapped right. There is one way to get to the leftmost. There are two equally likely ways to get to the middle. There is only one way to get to the right:
1 2 3 .
      x|
    1  |
  1   x|
1   2  |
  1   x|
    1  |
      x|

The reasoning is the same for Moment 3. We could write it out in longhand, or realize that to determine the number of equally likely paths to a particular place all you need to do is sum up he number of equally likely paths leading to upward adjacent cells:
1 2 3 .
      1|
    1  |
  1   3|
1   2  |
  1   3|
    1  |
      1|

This is called a "random walk", and the structure shown is called a "Pascal's Triangle". The resulting distribution is the ever famous "normal distribution" or "bell curve". Ever wonder why the bell curve distribution pops up again and again in nature? Because the thing measured to fall in bell curve distribution was arrived at through a random walk. The height of a person in a population, for example, is arrived at by a genetic random walk.

I didn't really grok this concept until a few months back when I read it in Feynman's "Lectures on Physics" and then a week or so later in a pop sci book I bought hastily in an airport. One interesting thing about this approach is the absolutely astronomical numbers it arrives at fairly quickly. The value at any triangle cell is determined by the combinatorial operation "n choose k" which expressed in a closed form is:

n!/(k!(n-k!)

where n is is the row and k is the entry. The middle of the 50th row is 126410606437752 - there are 126410606437752 different random paths from the hapless ship's origin slapping around in the ocean to it's destination 50 slaps later. A fascinating and convenient property of pascal's triangle is that it returns such magnificent numbers using a small number of additions. One way to find the number of random paths in choppy seas to a point 50 Moments later would be to literally count them. If you did that a rate of one path counted for every millisecond you'd be working for 4008 years. If you use Pascal's Triangle to count up the number of paths, one millisecond for every successive moment, it takes 0.05 seconds.

--==--

The third question in this round of Google Code Jam was:


So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.


I didn't really have any idea how to solve the problem. How could they have gotten 400263727 "welcome to code jam" combinations out of the first paragraph? There was a warning there - if you tried to count paths on any nontrivial chunk of code it would take you several centuries. My first inkling was to sketch this:

    w e l c o m i n g _ e m a i l _ t o _ w e l c o m e _ y o u _ t o _ c o d e _ j a m

w   +-------------------------------------+
e     +-----------------+-------------------+
l       +-----------------------+-------------+
c         +-------------------------------------+
o           +-------------------------+-----------+
m             +-----------+-------------------------+
e                       +-------------------+---------+
_                                 +-----+---------------+-------+
t                                   +-----------------------------+
o                                     +-----------+---------+-------+
_                                       +---------------+-------+-----+
c                                               +-----------------------+
o                                                 +---------+-------+-----+
d                                                                           +
e                                                                             +
_                                                                               +
j                                                                                 +
a                                                                                   +
m                                                                                     +


The first entry in a line was the first "chance" to use that letter to make the phrase. The last entry on a line was the "last chance". You could construct the target phrase out of the origin phrase by picking any of your "chances" from one line, and then any of the "chances" further up the line on the next line, and so on.

The problem was if I actually counted the number of paths to the solution I would run out of centuries. I remembered something...about counting the number of paths in a combinatorially large problem...from a book I read on an airplane. I continued sketching:

    w e l c o m i n g _ e m a i l _ t o _ w e l c o m e _ y o u _ t o _ c o d e _ j a m

w   1-------------------------------------1
e     1-----------------1-------------------2
l       1-----------------------2-------------4
c         1-------------------------------------7
o           1-------------------------1-----------8
m             1-----------1-------------------------10
e                       1-------------------2---------12
_                                 1-----1---------------15------15
t                                   1-----------------------------32
o                                     1-----------1---------1-------33
_                                       1---------------2-------3-----36
c                                               1-----------------------42
o                                                 1---------1-------1-----43
d                                                                           46
e                                                                             46
_                                                                               46
j                                                                                 46
a                                                                                   46
m                                                                                     46


So, there are 46 different ways to make "welcome to code jam" out of "welcoming email to welcome you to code jam". I coded up the algorithm (noticing during programming that I don't actually have to figure out which character is the "first chance" and the "last chance" - you can make a number entry for any occurrence of a character on a line and the number comes out the same) and ran it on the first paragraph of the problem statement. The solution: 400263727. With a small number of additions.

(Leave a comment)

March 16th, 2009


09:47 pm
Never thought I'd see the day when suits talk amongst themselves about some stuff I made:

Property Portal Watch on Transit Maps - A website all about real estate websites.
AIM Group on Transit Maps - Site is bar-graph themed, includes tabs for "Real Estate" and "Automotive".

--==--

Aimee and I just returned from a weekend trip to Oregon, WHEREIN we had breakfast with Ellen Range in Eugene, and danced to the world's largest contra band in Portland. Now for some Q&A:

Q: When will The Singularity occur?
A: Ray Kurzweil, in his 2006 book "The Singularity Is Near", based on order-of-magnitude estimates of the capacity of the human brain (~10^15 instructions/second) and the steady exponential increase in non-biological computing power (doubles about once every two years), estimates The Singularity should occur some time around 2025.

Q: Bacon Maple Bar?
A: Yes.

--==--

I've reimplemented Workstack. It's here:

http://workstack.appspot.com/task/b445c84c0f3411deb48b090a5f4ffd46

blah blah blahCollapse )

(2 comments | Leave a comment)

February 26th, 2009


09:00 pm
This afternoon I tidied up and released something I'd made a little while ago, a way of driving the Processing renderer from inside Python. Here it is:

PRender

PRender was made as a map renderer. So I made some of those:

Here's a map of my trip from my house to PCC, with the width of the line proportional to slowness:

trip_to_pcc

You can see where I stopped, and where I had to slow down for stop lights and signs.

This map I find especially stunning - it shows everywhere that Lee rode for a year:

newlee-seattle

(2 comments | Leave a comment)

February 18th, 2009


11:04 pm
This evening I made specifiable at runtime some of the parameters previously built-in to the transit trip planner - for instance, the speed the transit rider is able to move along the street, to transfer between stops or walk to the origin or destination stops. Here's the transit reachability map for the same origin at the same time of day, for different street speeds.

Each graphic shows 15, 30, and 45-minute reachability intervals.

1 mph - slow walking speed
1 mph

2 mph - average walking speed
2 mph

4.5 mph - slow biking speed
4.5 mph

9 mph - average biking speed
9 mph
Some contouring artifacts showing up - pay no attention to the man behind the curtain. At a fairly slow biking speed, the contour intervals are losing their ragged appearance, meaning that, interestingly, the bike is doing most of the traveling.

15 mph - brisk biking speed
15 mph
Contouring artifacts get fairly bad. Within 45 minutes the entire metropolitan area is within reach.

(1 comment | Leave a comment)

December 29th, 2008


03:05 pm
Visualization of the shortest path tree on a weighted directional graph representing a social network, with respect to Michelle. The weight of a "friendship" is 1/((number of mutual friends + 1) / number of frinds) - basically, the strength of your friendship is assumed to be proportional to the number of mutual friends you have with that person normalized against the number of friends you have. Since smaller edge weights mean you're closer, the edge weight is inversely proportional to the strength of your friendship. You then find the shortest path tree with respect to a given node (that is to say, a person), to find the path of least resistance to all people in your social graph. I tried this for two reasons - first, whereas a social graph is very difficult to visualize, a tree is fairly easy to visualize. Second, this illustrates that sometimes the path that you would take to reach an acquaintance goes through a person well known to both of you. For example, if you want your friend's girlfriend to show up at a party you may not invite her directly, but you would invite her indirectly through your friend. Along similar lines there are a number of people you are not acquainted with who are relatively nearby you in the social graph - they are very socially accessible to you through a common person who both of you know very well. If this is a person you fancy, knowing the path of least resistance to them might be useful.

Your close friends make a number of other people accessible to you. That is what it means to "have connections". This is shown in the visualization with the blue lines - the blue circles show how well you know a person directly, and the blue lines connecting to the red circle show how much closer they get to you by virtue of the common friend. In other words, this image is an esoteric illustration of the value of friendship.

It is interesting to note, I made this graph using Graphserver, which I originally built to find trip plans in transit systems. Other subtasks of this project: coded Python bindings for Processing, and ported the Facebook python client library to Python-3000.

The full size is desktop background size. It's not as pretty as it could be - I could use some help on design. I can't pay any money, but I'll give you credit when this thing goes live on Facebook.

social_spt_background_widescreen

(Leave a comment)

July 7th, 2008


01:51 am
I valgrinded the hell out of Graphserver today, completely shoring up the remaining memory leaks I was getting on street-based shortest path trees. It continues to return city-sized SPTs in about a tenth of a second, which is heartening. I'll need to figure something out for truly large, state-sized road networks, though. But that's for later. Presently it's ready to be ponied around with some neat-looking demo-type things. For example, here's a Processing rendering of a growing shortest path tree, where the width of a branch is proportional to the square root of the "burden" of the branch - the amount of road network behind the branch. The road network is pulled from the Open Street Map. Bike paths are set to 3 times more desirable than a road, walking paths 2 times, and freeways are 1000 times less desirable than a normal road. The two thickest branches you see there are actually the Burke-Gilman trail, and the I-90 trail. Basically, this is an image of the mental evaluation a cyclist has of the city when setting out from downtown. I've made things like this before, but this one is a bit larger. And animated.



Graphserver isn't really a server anymore - it's a C library with a set of wrappers in both Ruby and Python. I'm thinking of redubbing it "openitin" and letting a real server take care of the network layer.

(3 comments | Leave a comment)

July 5th, 2008


01:25 pm - Valgrind Hello World
I've said this before, but Valgrind is cool. Here's a basic example of how to use it to find memory leaks in a C program:

Here's a file, "vhelloworld.c"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

//This should leak memory
int main() {
    
    char* hiworld = (char*)malloc(15);
    memcpy(hiworld, "Hello, world!\n", 15);
    printf(hiworld);
    
    return 1;
}

(Remember, "Hello, world!" takes fifteen bytes with the newline and the null delimiter) Compile it like this, with the -g switch:
gcc -g vhelloworld.c -o helloworld
Then run valgrind like this:
valgrind --leak-check=yes ./helloworld
It returns this:
==10877== Memcheck, a memory error detector.
==10877== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10877== Using LibVEX rev 1804, a library for dynamic binary translation.
==10877== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10877== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10877== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10877== For more details, rerun with: -v
==10877== 
Hello, world!
==10877== 
==10877== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
==10877== malloc/free: in use at exit: 15 bytes in 1 blocks.
==10877== malloc/free: 1 allocs, 0 frees, 15 bytes allocated.
==10877== For counts of detected errors, rerun with: -v
==10877== searching for pointers to 1 not-freed blocks.
==10877== checked 60,348 bytes.
==10877== 
==10877== 15 bytes in 1 blocks are definitely lost in loss record 1 of 1
==10877==    at 0x4022AB8: malloc (vg_replace_malloc.c:207)
==10877==    by 0x80483F0: main (vhelloworld.c:8)
==10877== 
==10877== LEAK SUMMARY:
==10877==    definitely lost: 15 bytes in 1 blocks.
==10877==      possibly lost: 0 bytes in 0 blocks.
==10877==    still reachable: 0 bytes in 0 blocks.
==10877==         suppressed: 0 bytes in 0 blocks.
It says I'm losing 15 bytes, created at a call at vhelloworld.c:8 which is:
char* hiworld = (char*)malloc(15);
Yup. That's a problem. Fix the file:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

//This cleans up after itself
int main() {
    
    char* hiworld = (char*)malloc(15);
    memcpy(hiworld, "Hello, world!\n", 15);
    printf(hiworld);
    free(hiworld);
    
    return 1;
}

recompile and run valgrind, and it returns:
==10966== Memcheck, a memory error detector.
==10966== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10966== Using LibVEX rev 1804, a library for dynamic binary translation.
==10966== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10966== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10966== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10966== For more details, rerun with: -v
==10966== 
Hello, world!
==10966== 
==10966== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
==10966== malloc/free: in use at exit: 0 bytes in 0 blocks.
==10966== malloc/free: 1 allocs, 1 frees, 15 bytes allocated.
==10966== For counts of detected errors, rerun with: -v
==10966== All heap blocks were freed -- no leaks are possible.
Now we're sure we have no memory leaks. So rad!

(1 comment | Leave a comment)

July 3rd, 2008


02:04 pm


Growing shortest path tree from an intersection just south of the University Bridge in Seattle. Using Graphserver and OSM street data. Visualization using Processing. Nino Walker and I have made some great progress in writing a set of Python wrappers for the Graphserver library, making things like this relatively straightforward to implement. While pre and post-processing of the graph took several seconds, and the process of making this graphic is not completely automated, the Graph.shortest_path_tree() function that produced this graph returned in 0.03 seconds.

(Leave a comment)

June 30th, 2008


03:42 pm
WhatTheMetro has a post in Seattlest

Someone who is not me wrote python wrappers for Graphserver. I'm writing a unit testing framework for it right now, tracking down some segfaults.

(4 comments | Leave a comment)

> previous 10 entries
> Go to Top
LiveJournal.com