Eric Zhang

Projects

I welcome collaborations. If you find anything below particularly interesting, let me know!

Table of Contents

Set with Friends January 2020

JavaScript Game React Firebase

An online, real-time multiplayer card game.

Set with Friends is a web implementation of a real-time pattern matching card game called Set. Originally, when I was at SPARC 2019, I wondered how I could bridge the 3000 mile gap between some of the friends I had made after we parted ways. Set with Friends lets you play Set online with minimal overhead (no login necessary); it's as simple as sharing a custom link and having fun!

During the design process, I learned about Firebase (a service offered by Google), so for me this became an introduction to serverless architectures, as well as an exercise in creating live interfaces. We completely overhauled the design in May and released version 2.0 in June. At the time of writing (July 2020), the website has over 40000 monthly active users and 5000 games played every day.

Links: GitHub, Website


Competitive Programming Workspace September 2019

JavaScript CP React Express

An online, cloud-synchronized workspace for competitive programmers.

If you're a top competitive programmer, you have a dedicated setup on your local machine that lets you quickly creating new programs from templates, generate input files, and run code on sets of test data. But what if you're working on a different computer, and you don't have all these tools installed?

This is a side-by-side problem viewer and code editor that allows you to run code online. It even has advanced features like autocompletion and automatically parses of test cases for each problem, so you don't need to manually copy-paste these yourself. This was inspired by CS Academy's interface.

To accomplish this, the web server lets you scrape problems from online judges at the click of a button. Your code is safe, as it's autosaved and synchronized with a MongoDB instance in the cloud, so it even persists across sessions and browsers. Try it below!

Links: GitHub, Website


Polygon Triangulation with Holes May 2019

C++ Algorithms Emscripten Graphics

Fast computational geometry algorithms in WebAssembly.

This was an experiment to implement the ear clipping algorithm from computational geometry for polygon triangulation. Although easy to describe, triangulation is a surprisingly difficult problem, as you can draw weird concave polygons that can pretty much approximate any 2D shape. My implementation works even for polygons with multiple holes and nested polygons, using some clever techniques.

Note that there is also a randomized O(N log* N) algorithm for this problem (Seidel 1991). However, for most practical applications, ear clipping is fast enough and produces more robust results, while having a lower constant-factor overhead from using simpler data structures.

I implemented the algorithm in C++ from scratch, then compiled it to WebAssembly using Emscripten to produce code that could be run in the browser at the link below.

Links: GitHub, Website


Procedural Harmony February 2019

Python Music Algorithms Flask

Dynamic programming applied to four-part harmony.

This is a Python program that takes as input a string containing keys and roman numerals representing a chord progression, and voices the resulting chords according to common practice four-part SATB voice leading conventions. This can be used to compose a chorale—or quickly solve exercises on homework for your music theory class.

Parsing and interpreting the roman numerals was done with Music21. To handle a very technical set of voice leading constraints, I chose to frame this as a combinatorial optimization problem. Although the set of possible chorale voicings is exponential in size, you can solve this quickly using dynamic programming on intermediate states for a relatively fast algorithm. See the website below for a web version deployed with Flask.

Links: GitHub, Website


Algorithm and Data Structure Library January 2019

C++ CP Algorithms Angular

A competitive programmer's library of algorithms and data structures in C++.

I maintain an open-source library of about thirty-five C++ templates for algorithms and data structures. These are not your typical algorithms from school; I focused on complex algorithms useful for advanced competitive programmers. These include fast implementations of FFT, Aho-Corasick, and Dinic, as well as data structures like Link-Cut Trees and Centroid Decomposition.

This is accessible on a website, which I developed using Angular and the GitHub API. The website also includes a searchable collection of more than 600 templates from other open-source competitive programming libraries.

Links: GitHub, Website


Canvas Hashlife December 2018

JavaScript Algorithms Graphics Vue

An ultra-fast simulation of Conway's Game of Life in the browser.

Ever wanted to simulate a 2100 × 2100 grid of cells over 250 generations? Well, now you can do that in just milliseconds without any specialized software, right in your browser!

How is it possible to simulate such a massive pattern? The wonderful secret is Bill Gosper's Hashlife algorithm, which combines quadtrees and memoization to "compress space and time". In the image, you can see the web application computing the 498,913,509,376th generation of a Turing machine pattern in Conway's Game of Life, in just under a millisecond. Try it yourself at the link below!

Links: GitHub, Website


Char-RNN Keras October 2018

Python Machine Learning Music

Character-level language models with recurrent neural networks in Keras.

Inspired by Andrej Karpathy's blog post, this is an implementation of a long short-term memory (LSTM) network in Keras, for learning and sampling from character-level patterns in text. This was trained to generate writing in the styles of historical authors, like Shakespeare, Hugo, and Caroll.

A really interesting application was training this network on a corpus of folk music, from which it could compose new music fairly well. See the web demo below to play with this yourself!

Links: GitHub, Demo


Handwriting Generator August 2018

Python Machine Learning Graphics

Variational autoencoder that learns latent features in handwriting.

This is a neural network that encodes 28×28 images of handwritten characters in a 6-dimensional latent space using unsupervised learning. It consists of two parts: an encoder network that puts the input through several convolutional and downsampling layers to extract latent variables, and a decoder network that takes latent variables and a label to reconstruct the original image, minimizing mean squared error. After adding some trained Gaussian noise to the latent space, the result is sometimes called a conditional variational autoencoder.

I implemented the model in Keras and trained it on a dataset of over 400,000 handwritten characters. You can see the results in the web demo below, which stitches the outputs together on a canvas. Without any prior knowledge, we can isolate the six most important distinguishing characteristics of a person's handwriting. You could use this to copy anyone's writing style given a sample!

Links: GitHub, Demo


Estimation Markets July 2018

JavaScript Game Angular Sails

Run interactive, simulated markets on estimation problems.

Inspired by online prediction markets like PredictIt, this website allows users to create real-time markets on math or Fermi estimation problems, then use their information on the trading floor to compete to earn the most money by the end of the game. I used this app to run estimation markets in classes at SPARC, AlphaStar Academy, and MIT Splash with great feedback from the participants.

Links: GitHub, Website


Julia Fractal Renderers April 2018

C++ Java Graphics TypeScript OpenGL

Fast, interactive fractal renderers in C++, Java, and WebGL.

This project started out as a multithreaded Julia fractal renderer in C++, and used it to create high-resolution static renders, as well as animations. This worked alright, but I also wanted to be able to interactively explore the fractals (zooming and panning), so I created a Java Swing app that did this with similar optimizations.

The performance of the Java version was a little disappointing though, so I finally implemented an OpenGL Shader that could render Julia fractals with blazing speed, fast enough to be explored interactively with almost no lag on my laptop. I deployed this with WebGL and connected it to mobile-friendly controls in TypeScript. You can play with this fractal explorer in the website linked below.

Links: GitHub, GitHub (Java), GitHub (WebGL), Website


Universal Gravity Simulator May 2016

JavaScript Graphics Physics

Control hundreds of tiny planets with gravity.

This was one of my first fun programming projects, a visual experiment of simulating gravity in a system with hundreds of interacting planets. The calculations are done with simple physics formulas, with a bit of tweaking and damping to make them more robust. Clicking adds an invisible mass that makes all objects move towards the cursor. Everything is rendered on a <canvas> element, and it's quite satisfying to move the colorful balls around!

Links: GitHub, Website