Problems from Project Euler

Langton's Ant

This is a start toward solving problem 349 from Project Euler:

An ant moves on a regular grid of squares that are coloured either black or white. The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves from square to adjacent square according to the following rules:

  • if it is on a black square, it flips the color of the square to white, rotates 90 degrees counterclockwise and moves forward one square.

  • if it is on a white square, it flips the color of the square to black, rotates 90 degrees clockwise and moves forward one square.

Starting with a grid that is entirely white, how many squares are black after $10^{18}$ moves of the ant?

I made a Mathematica simulation to find the point around which the motion of the ant stops being random and enters a "highway."

After spending a lot of time at the beginning going through seemingly random configurations, the ant reaches a configuration that makes it "repeat" the same sequence and launch into a highway.

Continue reading...

Plasma current reconstruction

Tokamaks are donut-shaped containers for hydrogen plasmas that we heat to ludicrous temperatures so that charged particles overcome their mutual repulsion and fuse, releasing energy that could be used to turn a steam turbine and power the lights in your house. To keep the plasma at such enormous temperatures and to protect the Tokamak's interior, the plasma is suspended in midair using magnetic fields. Tokamaks are surrounded by electromagnetic coils that generate powerful magnetic fields, but they also rely on an electric current going through the plasma itself to create the perfect confining magnetic field. This plasma current is induced by a transformer coil at the center of the torus:

I'm working on a Python program that uses magnetic sensor measurements to reconstruct the plasma current profile on Columbia's High-beta Tokamak.

It can calculate the magnetic field at any location resulting from current in a circular coil:

$$B = G(r, z, r_{coil}, z_{coil})\cdot I_{coil}$$

where G is a Green's function of their positions in cylindrical coordinates. For each magnetic sensor, we subtract the coil fields from the sensor's readings to get the field of the plasma current alone. Then we do the linear algebra version of $I = G^{-1}B$ to calculate the plasma current over a grid of different positions.

Continue reading...

Notes on ordinary differential equations

A cheat sheet under construction.

Integrating factor

Any linear first-order ODE can be rearranged into the form

$$\mu(t)=e^{-\int p(t)dt}$$
$$y = \frac1{\mu(t)}\left[\int_{t_0}^t\mu(s)g(s)\,\mathrm ds+c\right]$$

Continue reading...

The volume and surface area of n-spheres

What follows was an extra credit assignment to figure out formulas for the volume and surface area of higher-dimensional spheres. This might seem pretty abstract, but it has a cool real-world application: optimizing error-correcting codes has to do with finding the densest way to pack spheres in higher dimensions.

Volume of a 4-sphere

To find the area $v(B^2)R^2$ of a disk $x^2 + y^2 \leq R^2$, we integrate the height $y = \sqrt{R^2-x^2}$ along the diameter to find the area of the upper half. This is not trivial, but we'll save our strength for the 4-sphere. The full area of the disk is

$$v(B^2)R^2 = \int_{-R}^R 2\sqrt{R^2-x^2}\,dx = \pi R^2$$

Continue reading...

Tempofy: rhythm-matching shuffle

This is a project I worked on with a team at PennApps in winter 2015. It finds random songs on Spotify matching the tempo of your movements according to the iPhone's accelerometer.

I did the iOS programming, but it currently requires a backend Flask server to be running to calculate bpm and use the Echonest API.

Continue reading...

Stratus: bluetooth chat

Wouldn't it be cool if you could chat with strangers around you in a coffee shop, or even around an entire campus? A couple friends and I thought so, and we made a bluetooth chat app for Android phones during Columbia's ADI hackathon.

It's a fun proof of concept, and hopefully in the future we'll figure out some decentralized protocol like Bittorrent for phones to communicate over. This could be useful for people in disaster areas when cell towers get damaged, or in very crowded places where networks get overloaded.

Continue reading...

Tracking space usage at Columbia

During the last finals week of my junior year, an interesting website came online at It tracks the number of devices connected to WiFi access points at many places on campus, and translates these numbers into a crowdedness metric (100% := full, 0% := empty). The website, however, only shows the crowdedness at the instant you access it. ρ(t) is a tool I made while procrastinating during finals week that scrapes data from the website every 15 minutes and shows it using a D3 plot. It's not a smart solution now since there's an API, but it can show you how to scrape a website.

Above is what ρ(t) recorded during finals at Columbia. The largest fluctuations are between daytime and nighttime (although a fair number of people stay active at Butler, the 24-hour library). We can also see on most days a swell in activity after lunchtime. In my experience, finding a spot in the library was impossible just after lunch.

And we also see the beautiful, gradual death of finals week over three days.

Continue reading...

Spacecraft inspection robot

As we contemplate long-term manned missions to Mars and beyond, we need a convenient way to inspect and repair the damage to spacecraft caused by micrometeorites, space debris, and radiation. I designed a robot for this purpose with a team of fellow students in the excellent Human Spaceflight class taught by former astronaut Mike Massimino. The robot is designed to be a companion for spacecraft and space habitats like the International Space Station, and can be deployed to inspect the exterior of any structure in microgravity.

The robot is cube-shaped with thrusters at the center of each face and an omnidirectional antenna. It also has a camera at the center of each face, and their video feeds are stitched together to form an immersive view of every direction surrounding the robot. Piloting the robot is supposed to be very easy to learn, and would consist of setting a direction in the immersive view and pressing go/reverse at different speeds. Finally, one face also has precision and infrared cameras, a trace gas analyzer, and a flashlight, to closely inspect damaged areas. When the robot is not being used, it can rest and recharge in the airlock.

I created a simulation of the robot in the ISS environment to train prospective pilots. Interestingly, it runs pretty well on iPhones (20 MB download), but collision detection is slow even on desktops.

Continue reading...