8/28/13

work notes:

problem: how do we get a timestamp for the most recent sunday at midnight?
solution:
var x = new Date(new Date().toDateString())
var lastSundayAtMight = x.getTime() - (1000 * 60 * 60 * 24 * x.getDay())

...
I had a pleasant walk into work today.
I saw some colleges from work on the way.
They had gelato.
They offered me some.
It was surprisingly flavorful — mint that reminded me of my mother's mint garden.

[spoiler alert]

I came up with a solution to that problem involving soldiers coordinating when to fire — I solved it first on paper, but I wasn't certain it would work, so I implemented it in javascript

the problem turns out to be the firing squad synchronization problem

my solution is messier, but essentially the same as the simple/slow one depicted on wikipedia — apparently it can be done faster using black magic

8/27/13

I said before that my roommate told me a cool puzzle,
involving soldiers coordinating when to fire their guns,

and I came up with a solution that seemed optimal,
I could prove it couldn't be faster,
which involved sending a signal all the way down the line,
and then back to the front,

but,

he says the soldiers are only allowed to have finite state machines for brains..
so they can't count..

the thought crossed my mind,
of some lobsters in a pot,
pulling each other down,
as they try to climb out,
screaming: please give us a policy to save us from ourselves!

8/26/13

I love people,

but,

there's this feeling of reverie I get,
where I feel in tune with my thoughts,
and I feel on top of things,

and it pops like a bubble when I need to open my mouth and talk

hooray!

I generated an xkcd style password,
for a service that I use on my phone,

and it was easy to type into the phone,
as opposed to being hard,

that is all.

I'm excited for Soylent. I thought they were funded on Kickstarter, but they weren't — apparently it doesn't meat Kickstarter's criterion for projects.

-1 for Kickstarter.

my roommate told me a cool puzzle:

there are a large number of soldiers standing in a line,
so many that we don't know how many there are,
and we can't just count with our eyes,

and we want them to all fire their guns simultaneously,
and there's a drum that they can all hear and count the beats of,

but we can only talk to the soldier on one end,
and each soldier can only talk to the soldiers next to them,
so what's the most efficient way to get them all to fire at the same time?

he didn't tell me the solution.. though I'm sure it's online.. but I love having a puzzle :)
oh wolfram|alpha, I want to kiss you: simplify: ((n-1) choose (k-1)) / (n choose k) .. I just made up that syntax, but it understood, and it did it

successful lucid dream!

my success rate so far is about 5% — about 5 successes over 100 attempts over the past month and a half

the strongest correlate with success for me seems to be reading something new about lucid dreaming before making an attempt.. not sure how to sustain that..

8/23/13

A friend and I walked 18.4 miles today, from my apartment near the caltrain to the other side of the golden gate bridge, and back.

It didn't seem that long though, because the company was good — and we stopped for ice cream.

8/20/13

I almost had a lucid dream.. it's like flying a jet, which requires a long runway (relaxing a lot), and when it's going fast enough, and the wheels finally lift off the ground, the lucid dream starts.. but this jet is very fast and unstable and I quickly crashed it into the ground (woke up).

decision by committee

proto-thought: maybe decisions by committee are bad because committees are steered by the strongest voices, and maybe the strongest voices are the stupidest ones, drowning out the smart but shy voices

as a committee discusses its agenda, it makes many small decisions, eventually ending up somewhere.. perhaps these decisions could be called to a vote — a real-time anonymous vote using some smartphone app that probably exists for that

8/15/13

youtube video editing

I wanted to crop a video and post it on YouTube. My first thought was to use iMovie, since it's on my machine. But it didn't support the format of the video I wanted to crop, and the cropping interface was not straightforward.

I asked a friend how they would do it, and they suggested uploading it to YouTube first, and editing it online. I didn't know I could edit it online. A few more things surprised me. First, YouTube supported the format that iMovie didn't. Second, it seemed faster to upload a video to YouTube than to open it in iMovie. Third, the interface for cropping videos on YouTube was easier to use than iMovie.

So, +1 for YouTube, and cloud-based interfaces, and asking experts for advise when doing tasks.

8/13/13

I was talking to a taxi driver. He was an engineer. He had worked at Airbus for 9 years. When he came to the US, he got a job at United, but they told him he had two weeks of vacation a year. And he said fuck that. Apparently it's easier to take long vacations as a taxi driver.

8/12/13

I currently know about two styles of meditation that seem different to me:

  • following the breath, and trying to remove all other thoughts
  • observing thoughts, as if from afar, without becoming involved with them

I've been trying the technique of following the breath, and I can do it fairly well for 5 minutes, but it is somehow frustrating to me.

Today I spent my 5 minutes observing thoughts as if from afar, and this felt more productive.

Of course, maybe meditation is meant to feel frustrating and unproductive.

However, when my uncle suggested that I run for exercise (which he often does), and I retorted that I find running boring, he suggested that I meditate as I run, in the "following the breath and removing thoughts style", which sounds like a good thing to try — if I'm going to be frustrated following my breath and trying not to think, why not increase that frustration by also physically exerting myself?

8/11/13

battlecode

I spent six years in grad school at MIT. Every year, the thing I looked forward to most was 6.370 "Battlecode" — a programming competition held in January during IAP (independent activities period).

I never won. I never placed in the top 8. I'm pretty sure I always placed in the top 16. I talked to some of the winners, and I think I played Battlecode wrong. The way to win was refinement — lots of tests and tweaks. But I just wanted to find some simple elegant hack that could win without too much code.

I failed. But here are some hacks I was proud of:



*

2006: The Drop

Robots mined energy by sitting on a green square. Each player started by a green square, and most maps didn't have any other green squares available. It was very difficult to attack the opponents green square, since they could regenerate units, and the attacking force couldn't, so the battle was generally waged over some hills in the middle of the map — whoever controlled the hills the most after some time limit would win.

But I figured the opponent's green square could be killed, with a StarCraft "drop". I built a bunch of mortars (very slow long range tank type things), loaded them into two transports, flew around the edge of the map, one going left, and the other right, arriving simultaneously, unloading just in range of their green square, and firing continuously. The mortars couldn't even see the green square — the transports had to tell them where it was before being shot down.

I didn't test this trick in the scrimmage matches — I uploaded it at the last possible moment. The next day, before the tournament matches started, someone told me they were impressed and scared of my drop. I asked how they saw it, and apparently one of our scrimmage matches was delayed in the queue, and when it finally ran, it ran with my latest code, but the deadline for the other team had already passed to upload new code.

Anyway, it did well, but it didn't win. I seem to recall in my final match killing the opponent's green square, but that map had alternate green squares, and their team managed to take one.

Still, I was flattered to win the vote for best strategy, which was a prize of a PSP.



2007: Regular Expression Pathfinding

This year had upgrades scattered around the map. Navigating to the upgrades required path finding, and although everyone knew about A*, the issue was implementing it efficiently. The world of Battlecode provides relatively few bytecodes per time-step — so few, in fact, that most people didn't use A*, and those that did faced a tradeoff between thinking time and moving time.

To make things easier on people, the Battlecode engine would discount the bytecodes involved with various standard library methods, counting them as a predetermined fixed number of bytecodes regardless of what happened inside the function. For instance, Arrays.hashCode would count as maybe 100 bytecodes, regardless of the length of the array being hashed.

Battlecode excluded certain standard libraries, including java.util.regex. However, they didn't exclude String, and String has a couple regular expression methods build into it: matches and replaceAll. And these functions could be called for a fixed bytecode cost, regardless of the size of the string being matched against.

This gave me an idea about how to do path finding — a method that would be extremely inefficient in terms of actual computation time, but counted as fast by the Battlecode engine:

Step 1: Encode the entire map as a giant string. Mark traversable squares with a ' ', mark myself with an 'x', mark upgrades with a 'u'.

Step 2: To find the shortest step toward a 'u' from 'x', replace blanks next to u's with u's, until there's a u next to an x. If the u is north of the x, go north, etc.

Here's an excerpt of the code (full code here) with highlighted regular expressions:

for (int t = 0; t < 40; t++) {
if (s.matches(regex(".*(x(?=.{A,C}u)|(?<=u.{A})x|(?<=u.{B})x|(?<=u.{C})x|x(?=u)|(?<=u)x).*"))) {
...
if (s.matches(regex(".*x(?=.{B}u).*"))) {
... = SOUTH;
} else if (s.matches(regex(".*(?<=u.{B})x.*"))) {
... = NORTH;
} else if (s.matches(regex(".*x(?=u).*"))) {
... = EAST;
} else if (s.matches(regex(".*(?<=u)x.*"))) {
... = WEST;
}
...
return ...;
}

String ss = s.replaceAll(regex(" (?=.{A,C}u)|(?<=u.{A}) |(?<=u.{B}) |(?<=u.{C}) | (?=u)|(?<=u) "), "u");
if (s.equals(ss)) break;
s = ss;
}

Note that the regex function is replacing the A's, B's and C's with numbers having to do with the size of the map.

Now normally a robot wouldn't have enough time to iterate over a small portion of the map within a single time-step, which made even A* difficult, but my robots would iterate over every square of the entire map 40 times within a single time-step and have computation to spare.

Of course, this strategy was so inefficient that it slowed down the Battlecode engine itself, and for fear of triggering some red flags amongst the dev team hosting the competition, I restricted this path finding to only certain robots (the other robots would just follow them).

This team did extremely well, and was at the top of the scrimmage server for most of the time leading up to the final tournament, but near the end, another team rose above me with a team making efficient use of a robot type that I wasn't using — they were using a weak-fast unit, while I was using a strong-slow unit.

So, wanting to win first place, and knowing I would lose to this particular team with my current strategy, I made a last-minute change, which turned out to be bad. I started using the weak-fast unit myself, which required making more of them, but they were harder to navigate through narrow passages (since they were all crowded around the special path-finding unit), and in my final match, my robots literally got stuck trying to navigate through a small hole in a wall.

Still, the devs were impressed with my regular expression path-finding hack, and I got some sort of prize for it :)



2008: Attempted Genetic Algorithm

I had a teammate this year, and he had access to a 16-core machine which we tried to use to genetically evolve the parameters for a robot player. We actually did get all the infrastructure set up to do it, and ran a few generations, but we ended up thinking of strategies that existed outside the parameter space of the player we were evolving. I was sad that the genetic algorithm strategy didn't work out. I was so hopeful.

I do feel proud of our team logo though. I had been calling my team "little" from previous years, and that name had earned some cred in the community, so I wanted to keep it. My teammate was fine with that, but I felt bad anyway. So, since his name was "yang", I made this our logo:



2009: Communication Warfare

Battlecode robots can't talk to each other directly. They need to send messages. The thing is, the enemy team can hear the messages too, if they are in range. Not only that, but there's no way to know for sure who sent a message. So there's some possibility of communication warfare, by trying to send fraudulent message to the other team, usually by re-broadcasting messages received from them earlier, after corrupting them with random modifications.

Most teams don't worry about this since communication warfare is hard (it's hard enough to get the robots to do anything at all), meaning that most teams don't bother to do it, meaning that defending against it is usually worthless. However, the top teams generally do worry about it, since they don't want to lose against a team that actually does modify and re-broadcasts their own messages.

So how does one protect against someone modifying a string? Usually by hashing it, and sending the hash as well. Of course, the bytecode restrictions are pretty severe, so hashing the message can be costly, but it's cheap to use the Arrays.hashCode function, since that one is discounted (as mentioned above).

However, it turns out that Arrays.hashCode is not cryptographically secure. I took at look at the sourcecode for it, and devised a way to modify an array, without affecting the hash of the array. Here's the way Java hashes an array of ints from Arrays.hashCode:

public static int hashCode(int a[]) {
    if (a == null)
        return 0;
    int result = 1;
    for (int element : a)
        result = 31 * result + element;
    return result;
}

Here's a snippet from my robot's code:

public static void corruptMessage(Message m) {
    ...
    int i = r.nextInt(m.ints.length - 1);
    int x = r.nextInt();
    m.ints[i] += x;
    m.ints[i + 1] -= 31 * x;
    ...
}

It would pick two sequential elements of the array to corrupt. It would then add a random value x to the first element, and to preserve the previous hash value, it would then subtract 31*x from the next element.

One of the top teams was in fact affected by this, and told me about it. As I understood it, they were sending map coordinates, and they would resize an array to hold coordinates that fell outside their current map data structure (since the robots don't know the extents of the map when the game starts). However, when they received corrupted coordinates from me, they would often resize the array to be gigantic, and throw an out-of-memory exception and die.

I believe they fixed this before the final tournament — I think I included the message corruption in my scrimmage player and they noticed their robots mysteriously exploding in some scrimmage matches. However, I recall getting some sort of "message warfare" award.



2010: Teleportation

It wasn't much, but I did get a prize for some teleportation code. There was a teleportation tower unit that could teleport units near it to other teleportation towers. And I had a bit of path planning code that factored in the possibility of teleportation — though not with regular expressions.



2011: 6.470-staff

While competing in 6.370, I was helping run 6.470, a web programming competition. In fact, four of the 6.470 organizers were interested in competing in 6.370, and so we pooled our resources under the Battlecode team 6.470-staff. This year was perhaps the most complicated Battlecode environment to date, with robots that could be customized with components, and I spent some time writing code to simulate duels between robots with various components in order to know what configurations to use in response to enemy configurations.

Appendix

* Note that the 2006 shirt says RoboCraft. This was the original name, but to avoid angering Blizzard, it was changed to Battlecode, and in fact Blizzard became a sponsor of Battlecode in 2008.

Here are the fronts and backs of all my Battlecode shirts.

Here's all my Battlecode sourcecode.. well, most of it. I don't know where my code is from 2006.

phonegap, you're so amazing!

I just built my first non-hello-world app: https://github.com/dglittle/phonegap-timer

you can download it here: https://build.phonegap.com/apps/505560/builds

"phonegap build" compiles the app for all the phones in the cloud, I didn't install any software on my own machine. To test it locally, I just loaded my html file in chrome — of course, there was one line chrome couldn't run: navigator.notification.vibrate(1000), which is meant to vibrate the phone for one second, but other than that, the app is literally a single html file, with some standard includes like jquery and bootstrap and phonegap's own api (oh, and a small config.xml file)

8/6/13

I just spat into a 23andme tube

8/5/13

ahh.. a little more of that sweet, exhilarating feeling of freedom as I move the last remaining stuff out of S3. TalentCourt was storing images there, but now it stores them inside it's own MongoDB :)

done! nothing in S3! nothing in EC2!

now I love these services, and I actually do have a lot of stuff in S3 (if Dropbox still uses it), and EC2 (used by heroku).
just received my second cell phone alert ever.. the previous one was a flash flood warning that made a lot of sense given where I was..

so this time I'm in San Francisco, and my first thought was, earthquake..

but it was an amber alert. apparently those are on phones now. and if you search for "amber alert" or even just "alert" on google it's there too. impressive.

ahh..
it feels so sweet..
I just shut down an EC2 machine that had been running a node.js server for months..
I moved all the apps onto free heroku servers that I don't need to maintain,
and I pointed the domain that used to point at the EC2 machine to a github gh-pages stub instead, which has redirects to all the heroku apps

another step toward the freedom of not being responsible for anything

so.. my flatmate has a friend staying here for a month as a "butler" (read: personal assistant), strange, I know..

I've had him do a few physical things:
- get rid of some hard-drives, including wiping them and properly disposing of them
- dispose of a mercury-containing bulb
- change the address on my driver's license (not super physical except that I was able to hand him my license)

I plan to have him take some clothes to good will and mail away some books that I've borrowed

I have also benefited from him cleaning and taking out the trash and keeping the dishes washed and clearing out old food from the fridge..

verdict: pretty amazing. physicality helps a lot.

"overstimulation"

in a previous post, I mentioned a post about 10 myths about introverts, and one of those myths is:
Myth #9 – Introverts don’t know how to relax and have fun.
Introverts typically relax at home or in nature, not in busy public places. Introverts are not thrill seekers and adrenaline junkies. If there is too much talking and noise going on, they shut down. Their brains are too sensitive to the neurotransmitter called Dopamine. Introverts and Extroverts have different dominant neuro-pathways. Just look it up.
..which paints this picture of an introvert going into a club and saying "oh no! it's too exciting and fun in here! I want to go read a book which is slower and simpler!"

and it defends this picture by saying that introverts' brains are "too sensitive" to dopamine to handle such high energy situations, "just look it up."

well, a friend found the reference: http://psycnet.apa.org/journals/epp/3/1/37/

now mind you, I didn't read it — I couldn't be bothered to pay for what is probably tax funded research — but I read the publicly available abstract, which indeed suggests that introverts are more susceptible to dopamine than extraverts..

however, it doesn't say that lots of talking and noise produce dopamine.

here's an alternative model:
kids like to bang pots and pans together. adults find it annoying.
extraverts like lots of people packed together with loud noise. introverts find it annoying.

they don't find it annoying because there is too much information to process.
they find it annoying because there is very little information at all — the information is just really loud.

note to self: you can double-click the files in the sidebar of Sublime to open them in their own tab (single clicking opens them in the viewer, but without a tab, so clicking another tab essentially closes them)

Introverts vs Extroverts

there's a meme going around, something like "introverts aren't so bad".
here are some examples I've seen:

from TED: Susan Cain: The power of introverts

from some web comic: How to Live with Introverts (featuring a hamster ball)

and a friend just pointed me to a list of: "Top ten myths about introverts"

one issue though,
I feel like people start with the premise that socializing is good,
and try to say that introverts do socialize,
just in different ways,
or different amounts.

but I don't think socializing is good,
anymore than sex is good.

It's fun,
for some people,
sometimes,
but the activity itself isn't inherently valuable — it doesn't push humanity along — except to the extent to which it keeps people undepressed enough to do truly valuable things

communication is valuable.
reproduction is valuable.
socializing and sex often have these valuable side effects

but both of these side effects can be achieved without socializing or sex,
through the marvel of technology

so,
extroverts,
if you like socializing,
go for it.

First Kickstarter Pledge

I just pledged money toward this device.

I thought at first: why pledge money? I could just buy it when it comes out.

But then I thought, this is how I think products should be made. Rather than someone going to venture capitalists to get money, who expect to make 10x on their investment, causing weird incentives, since many cool ideas are really cool, but aren't going to take over the world, entrepreneurs can just ask for money in advance. If enough people like what they plan to build, then they can buy the product before it exists, and cause it to be created. And the entrepreneurs don't need to sell their souls. They just need to build the thing they said they'd build — no five year exponential growth plan, no pivoting, no desperation to sell the dying company. And if it turns out that the thing does explode into exponential goodness, the entrepreneur retains full control.

So, as an experiment, and somewhat against my nature, I'm being an activist, hoping against reason to nudge humanity microscopically closer to the direction I think it should be headed in.

moved the "near" and "bayesian truth serum" apps to heroku (and into their own github repos, here and here).

I almost have everything off of apps.glittle.org..

8/4/13

I've moved TalentCourt from EC2 to Heroku, and from my own crazy in-memory "database" to MongoDB.

The transition to MongoDB was pretty seamless. +1 to MongoDB.

8/3/13

Tennis Court

so.. I was working on Talent Court, and wanted to make sure I was spelling "court" correctly, so I typed "Tennis Court" into Google, and I saw this video as the second result.. and I watched it.. and, it was pretty great: