Missouri S&T

Between 2014 and 2018 I wrote a lot of code for school. Below are my favorite projects from my academic years.

This repository isn't just source files; it's a collection of memories. Ten years later, I can (and will) tell you where I was when I wrote each of them. I remember how late into the night I stayed at it. I remember how I wrote them, from the elegant one-liners to the nastiest regexes and bit manipulation you will ever see. I remember why I wrote them, because pain is temporary, but GPA is forever.

If you'd rather read the notes and problem sets themselves, they're collected in Academia Notes. The full source is on GitHub.

Notes

Projects

Senior Year:

1. Chess AI
2. Puzzle Solvers
3. Shape Packer
4. Linear Algebra Library
5. CFG Tracer
6. Splatoonio

Junior Year:

7. Space Invaders
8. Camelot

Sophomore Year:

9. CLC Tally
10. Grading Suite

1. Chess AI

A chess AI engine built from scratch using bitboards. Each position fits in a set of 64-bit integers, one bit per square, so move generation is pure bitwise operations: shifts for sliding pieces, masks to prevent wraparound at the edges of the board. On top of that, alpha-beta pruning, iterative deepening, and a custom evaluation function that considers piece position, king safety, and pawn structure.

This was my most memorable software project throughout all of college; with good reason, it was the most notorious within our computer science department. Part one of the project was generating a complete chess move engine with a simple search algorithm to explore the game space. This was one of the handful of assignments I ever turned in late. And I started it a week before it was assigned.

Bitboards were nasty; I never anticipated how complex they would make the engine. But it was a proper learning experience, and I came out much stronger at bit manipulation. While well structured, it was a large surface area for bugs to fester. I tested my move generator against a standard Python one to see if it was correct; after running through >50 test cases, I called it good. Except there's still one test case, on the desktop of a computer I no longer have, that I could never get to pass. And I never even knew why.

This and a few other engine bugs made me skip the class-wide chess AI competition, one of my big regrets of college. I contemplated submitting a build that inverted the fitness function, producing an agent that optimizes for losing, but chickened out, afraid it would error on an illegal move. The decision wasn't pride; with 18 credit hours and a part-time internship, my straight-As were hanging on for dear life.

Code

The moving function shifts bits to simulate piece movement, masking edge files to prevent wraparound. Each piece type builds on this primitive.

Bitboard MoveEngine::moving(const Bitboard& board, const Direction& direction) {
    const static Bitboard aFileInverse = 0xfefefefefefefefe;
    const static Bitboard hFileInverse = 0x7f7f7f7f7f7f7f7f;

    switch (direction) {
        case north:     return board << 8;
        case south:     return board >> 8;
        case east:      return (board << 1) & aFileInverse;
        case west:      return (board >> 1) & hFileInverse;
        case northeast: return (board << 9) & aFileInverse;
        case northwest: return (board << 7) & hFileInverse;
        case southeast: return (board >> 7) & aFileInverse;
        case southwest: return (board >> 9) & hFileInverse;
        default:        return Bitboard();
    }
}

Pawns are the worst: different moves per color, double-moves from the starting rank, diagonal captures only when an enemy is present.

Bitboard MoveEngine::pawnMoves(const Bitboard& pawn, Bitboard self,
                               Bitboard enemy, const Color& selfColor) {
    const Bitboard enemyOriginal = enemy;
    self = ~self;
    enemy = ~enemy;

    static Bitboard secondRank = 0xff00;
    static Bitboard seventhRank = 0xff000000000000;

    if (selfColor == white) {
        return (pawnNorthMovesWithBlockers(pawn, self & enemy)
              | pawnNorthNorthMovesWithBlockers(pawn & secondRank,
                                                self & enemy)
              | (moving(pawn, northeast) & enemyOriginal)
              | (moving(pawn, northwest) & enemyOriginal))
            ^ pawn;
    } else {
        return (pawnSouthMovesWithBlockers(pawn, self & enemy)
              | pawnSouthSouthMovesWithBlockers(pawn & seventhRank,
                                                self & enemy)
              | (moving(pawn, southeast) & enemyOriginal)
              | (moving(pawn, southwest) & enemyOriginal))
            ^ pawn;
    }
}

And FEN (Forsyth-Edwards Notation), the standard for serializing a chess position as a string. Parsing it requires a regex that looks like someone smashed their keyboard. The apology is warranted.

std::string FenParser::getToken(const FenToken& token) {
    // lol sorry
    const char* regexString =
        R"((([pPnNbBrRqQkK0-8]{1,8}/?){8})\s*(w|b)\s*)"
        R"(([KQkq-]{0,4})\s*([a-hA-H0-8\-]{1,2})\s*)"
        R"((\d+)\s*(\d+)*)";
    std::regex regexExpression(regexString);
    std::smatch match;

    if (std::regex_search(fenString, match, regexExpression)) {
        switch (token) {
            case board:       return match[1];
            // off by one, regex error; don't ask
            case colorAtPlay: return match[3];
            case castling:    return match[4];
            case enPassant:   return match[5];
            case halfTurns:   return match[6];
            case fullTurns:   return match[7];
            default:
                throw std::logic_error("Fen String is fucking broke");
        }
    } else {
        throw std::logic_error("Fen String is fucking broke");
    }
}

2. Puzzle Solvers

Four puzzle solvers built around different search algorithms. The standout is an A* implementation with custom heuristics that chews through state-space problems in milliseconds. Each puzzle forced careful thought about state representation and admissible heuristics. Watching the solver walk thousands of states to find an optimal path, faster than you can blink, was deeply satisfying.

The AI class had two programming projects: part two was the chess AI above. Part one, much simpler, was an AI engine that played a match-three clone. Reasonable project with sizeable scope, it was one of the projects that gave me real confidence as a programmer then. I remember comparing solutions with my friend Mark: his had a smaller code footprint, and he said mine was bloated. I remarked "your code is concise, but mine is poetic", then showed everyone my one-line move generator, like poetry.

Here's my desk setup at the time, editing this very code. I'm particularly proud of the new MacBook Pro; I bought it with my own internship money.

Code

Python generators let you build lazy sequences that compute on demand. Instead of materializing all moves upfront, the generator yields valid ones one at a time. Memory stays flat regardless of how many possible moves exist, because only the ones we actually touch get computed.

@staticmethod
def actions(state):
    # This is ugly, but by abusing list comprehension, I get lazy evaluation.
    # In turn, I actually do a linear search of the entire space, but only store
    # the states that are legal. Thank you, generators.

    row_max, column_max = MechanicalMatch.grid_size(state.grid)

    return [] if state.swaps >= state.max_swaps else (
        Action((row, column), direction)
        for row in range(0, row_max)
        for column in range(0, column_max)
        for direction in [Direction.UP, Direction.LEFT]
        if MechanicalMatch.swap_is_valid(state.grid, (row, column), direction)
    )

3. Shape Packer

An evolutionary algorithm for 2D shape packing. Given irregular shapes and a rectangular board, find the placement that maximizes coverage. The genome encodes position and orientation per piece; mutation perturbs placements, recombination swaps configurations between parents. Fitness proportional selection, k-tournament (with and without replacement), truncation for survival.

This was my first real test of writing performant Python, and boy was it full of lessons. In short, my code was slooowww. Not hours but days slow. Every submission felt like a grueling experience (this is when I fell in love with tmux). But there's a certain fun to watching the convergence in such tight packings. Optimization problems are fun.

4. Linear Algebra Library

A templated C++ linear algebra library. Matrices, vectors, and decompositions (LU, QR, Cholesky). Heavy use of operator overloading so matrix math reads naturally. The final project ties it all together to solve linear systems with different numerical methods.

This assignment taught me that our library was sometimes open until 3am; I found a spot in the basement next to the vending machines. It wasn't a mental test, it was an endurance one. The course wasn't just about numerical modeling in code, but about writing good numerical modeling code: fully templated, high test coverage, with proper documentation. Two weeks to deliver 2k lines of code and 57 test cases, and a self-imposed single night to ship 1.6k lines of comments.

This problem called for solving steepest descent, using the various matrix and vector types we'd built:

• vector
• banded matrix
• diagonal matrix
• rectangular matrix
• symmetric matrix

Code

An iterative linear system solver that follows the gradient downhill until it converges. The initial guess is just the b vector because "why not."

template <typename T>
Vector<T> SteepestDescentSolver<T>::operator()(const SymmetricMatrix<T>& A,
                                               const Vector<T> b) {
    Vector<T> x = b; // initial guess is the b vector, cause why not
    T alpha{};

    unsigned i = 0;
    Vector<T> residual = b - (A * x);

    if (!isDiagonallyDominant(A)) {
        throw NonDiagonallyDominantMatrixError();
    }

    while (norm(residual) > EPSILON && i++ < MAX_ITERATIONS) {
        residual = b - (A * x);
        alpha = (residual * residual) / ((A * residual) * residual);
        x += alpha * residual;
    }

    return x;
}

5. CFG Tracer

Undergraduate research project that instruments C++ code to trace control flow at runtime. A control flow graph represents all possible paths through a program: nodes are basic blocks, edges are jumps. This tool parses source, identifies basic blocks, and generates execution traces. Boost handled the regex. The goal was to understand how programs actually execute versus how we think they execute.

Even by my senior year, most of the bigger projects were codebases I developed or co-developed; this was my first notable exception. With a fellow researcher, our job was to pick up an existing codebase from a graduate student and get it running. I thought it would be a walk in the park, but it needed some massaging. I particularly liked this assignment because it was a semester-long, tag-team effort to push someone else's work forward.

6. Splatoonio

Capstone project, a multiplayer mobile game in Flutter/Dart. Went from concept to deployed app with a team. Real-time synchronization, touch controls, cross-platform deployment. The kind of project where you learn that 80% of software engineering is communication.

I hope Nintendo doesn't read this. We had a team vote on the project name, and Splatoonio won. We can change it.

This was my most "complete" software project in college: server, client, docs, pitch, you name it. And it was hardly my doing; it was a team project, and our team was the dream team. No, literally: our team name was "Dream Team", after we realized we averaged two internships per person and all of us were in the same AI and numerical modeling classes (the most demanding combination at our college).

Our last presentation of the year was naturally a live demo, and we couldn't disappoint. We wanted to showcase the rendering across campus because our classroom definitely wasn't big enough, and we only had a production build with no demo wiring. So I showed up on game day in running gear, introduced our team, and proceeded to run across most of campus with the game running. I even timed my return to the last minute of the demo to make a statement. We were unanimously the top project of the class, affirmed by one of the most memorable rounds of applause I got as a student.

7. Space Invaders

Space Invaders running on an 8051 microcontroller. Assembly and C, pressed against tight memory constraints. Every byte mattered. Implementing smooth sprite movement and collision detection on hardware this limited teaches you what efficiency really means.

Cold November nights, coding with How I Met Your Mother playing in the background (see Code, below). This one assignment made me appreciate video game logic: writing a screen rendering engine with nothing but ncurses is a tall order. Keeping track of not just bounding boxes but changing state, animations, player input, drawing, all of it.

Despite the complexity and having never done anything like it, I got something working. It had several bugs centered around the aliens: they never progressed down the screen, they never shot, you could never hit the one in the last row. But it was satisfying nonetheless. One snag: this was supposed to run on hardware with 4k of memory, and my first compile for the target platform came in at 15k. Yikes. I stripped essentially every library and wrote my own. 8k.

This is the part where I'd love to say I found a clever hack to squeeze under the limit, but there's no perfect ending. I hit my wits' end, talked to the professor, and made up for the failure by implementing another feature.

I did get to present my game to the whole class. And my adventures made for some great memes, which I attached to my homework and presented to the class too.

Code

The game loop is a switch inside a do { } while (true), with the render living in the default: branch. Instead of the usual tick → input → update → draw, this loop reads a key and only redraws when the player didn't press anything. Hold a key and the screen stops updating. Space Invaders with a frame rate inversely proportional to how panicked you are.

do {
    switch (getch()) {
        case KEY_LEFT:  /* ... move ... */  break;
        case KEY_RIGHT: /* ... move ... */  break;
        case ' ':       /* ... shoot ... */ break;
        case 'q':       endwin(); exit(0);  break;
        default:
            createHeader(&game, &header);
            createShooter(game.gunner.center, &game, &footer);
            createGameboard(&game, &gameboard,
                            stateOfAliens, stateOfShot);
            draw(&game, &header, &gameboard, &footer);
            break;
    }
    i++;
    if (i % STATE_CHANGE_ALIENS == 0) {
        stateOfAliens = stateOfAliens ? false : true;
    }
    stateOfShot = (i % 25 == 0);
} while (true);

The alien-selection logic is three branches of nested ternaries, picking which invader sprite to draw based on the row and animation frame.

if ((i / heightOfAverageAlien + 2) % 3 == 2) {
    (*aliens)[i][j] = stateOne
        ? smallInvaderOne[i % heightOfAverageAlien][j % smallWidth]
        : smallInvaderTwo[i % heightOfAverageAlien][j % smallWidth];
} else if ((i / heightOfAverageAlien + 2) % 3 == 0) {
    (*aliens)[i][j] = stateOne ? mediumInvaderOne[...]
                               : mediumInvaderTwo[...];
} else {
    (*aliens)[i][j] = stateOne ? largeInvaderOne[...]
                               : largeInvaderTwo[...];
}

The comment two lines above this block is the most honest sentence I ever wrote in a CS assignment:

// Then we mod by 3 because that's the number of aliens, and we
// compare to a number I put there because the returned numbers
// baffle me.

I had found an empirically-correct offset, and rather than figure out why, I shipped a comment saying so. Ten-years-later me is proud.

And then there's the HIMYM tax, paid in a split declaration so the comments land the punchline:

// It's gonna be legend..
void waitForIt(unsigned char seconds);
// ..ary! Legendary.

void waitForIt(unsigned char seconds) {
    unsigned int retTime = (unsigned int)time(0) + (unsigned int)seconds;
    while (time(0) < retTime);
}

8. Camelot

A team software engineering project with full documentation, UML diagrams, and Doxygen-generated API docs. Agile methodology, code reviews, collaborative development. The code itself is less interesting than the practice of building software with other people. An optional iOS chat client hooks into the server for real-time messaging. Swift, JSQMessagesViewController for the UI, SwiftSocket for TCP.

This class was pure joy. Not too difficult, not too easy. It was mostly just building useful software: an end-to-end chat interface. I got to make use of my iOS skills while the team built a fully-functioning message server. We put it together with flashy presentations.

Code

The server is exactly what you'd expect from a sophomore who just learned sockets: threaded TCP, a module-global SOCKET_LIST, and a broadcast loop that fans every message out to every connected client.

class ThreadedTCPRequestHandler(socketserver.BaseRequestHandler):
    def handle(self):
        my_socket = self.request
        SOCKET_LIST.append(my_socket)

        while True:
            data = str(my_socket.recv(1024), 'ascii')
            if not data:
                if my_socket in SOCKET_LIST:
                    SOCKET_LIST.remove(my_socket)
                return
            try:
                response = bytes(data, 'ascii')
            except Exception:
                response = bytes(json.dumps({
                    "error": "Something went wrong"
                }), 'ascii')
            for s in SOCKET_LIST:
                s.sendall(response)

The iOS side is sophomore-level in a different way: no push, no WebSockets, no long polling. Just a Timer that reads the TCP socket every second, decodes the bytes into a JSQMessage, and hops back to the main queue to render. Real-time by brute force.

switch client.connect(timeout: 1) {
case .success:
    self.timer = Timer.scheduledTimer(
        withTimeInterval: 1.0,
        repeats: true
    ) { _ in self.getNewMessage() }
    // ...
}

func getNewMessage() {
    DispatchQueue.global(qos: .background).async {
        let data = self.client.read(1024 * 10)
        guard data != nil else { return }

        if let string = String(bytes: data!, encoding: .utf8) {
            let message = JSQMessage(
                senderId: User.reciever.rawValue,
                displayName: getName(User.reciever),
                text: string)
            self.chatView.newMessage(message)
        } else {
            print("not a valid UTF-8 sequence")
        }

        DispatchQueue.main.async {
            self.chatView.finishReceivingMessage()
        }
    }
}

9. CLC Tally

iOS app for tracking student headcounts at Missouri S&T's Computer Learning Center (CLC). Built to solve a real problem: tutors needed a quick way to log how many students they helped. Simple interface, local storage, export.

The irony is that I mostly wrote this in the CLC. I'd never found a tally app with this particular data format, and it was much easier to have my phone always-on taking count than periodically marking a notebook. I ended up being the only user, because I didn't have an App Store account. But this was an "enjoy the journey, not the destination" project: the beauty of developing and improving something weekly that you actually use.

Code

The entire data model is 20 lines. Each tap appends a Date to an array in UserDefaults. The counter is userLog.count. "Users this hour" is a filter. No database, no Core Data, no schema migrations. Sometimes the best software is the software that just works.

class Counter: CustomStringConvertible {
    public var count: Int { return userLog.count }

    private var userLog: [Date] {
        get {
            UserDefaults.standard
                .object(forKey: "log") as? [Date] ?? []
        }
        set {
            UserDefaults.standard.set(newValue, forKey: "log")
            UserDefaults.standard.synchronize()
        }
    }

    public func increment() { userLog.append(Date()) }
    public func decrement() {
        if !userLog.isEmpty { userLog.removeLast() }
    }

    public func usersThisHour() -> Int {
        let hourOf = { (d: Date) in
            Calendar.current.component(.hour, from: d)
        }
        let now = hourOf(Date())
        return userLog.filter { hourOf($0) == now }.count
    }

    var description: String { return "\(count)" }
}

10. Grading Suite

Automated grading tools for CS 1570, the intro programming course. A style checker that enforces coding standards, a roster checker that validates submissions, a grader script that runs test cases, and a plagiarism checker.

Built out of necessity: grading hundreds of submissions by hand became unsustainable. I automated as much as possible so I could focus on the core concepts: algorithms, data structures, and programming paradigms.

The plagiarism checker never flagged anyone until assignment 8 out of 10; unironically, the hardest assignment of the year. Assignment 7 was a pair-programming project, assignment 8 was strict solo; and the same pair from assignment 7 decided to tackle assignment 8 together. I brought it to the instructor, and they asked my opinion on what we should do. Wanting to be fair, I proposed:

They split the work evenly, they should split the grade evenly: take each score and divide by two.

Output

Output is emitted as markdown so it drops straight into whatever report format the course coordinator wanted:

## student_submission.cpp

**80 Column Rule**

- Line 42: `    if (studentName == "John" && assignment.isComplete()`

**Tabs**

- Line 17: `    int counter = 0;`

**Non-Uppercase Constants**

- Line 8: `const int maxStudents = 60;`
- Line 9: `const double passingGrade = 70.0;`

**Header Guards Don't Match**

- Line 3: `#ifndef STUDENT_H`

**Missing Documentation (12 Functions, 4 Lines of Comments)**

Code

Every rule is a regex; most of them look like someone leaned on the keyboard. A sampler:

# 80-column rule: match anything, then demand a non-space in column 81.
# Trailing whitespace counts as a violation, which was the point.
column = r".{80}\S"

# Tabs: anchor to start of line, look for one tab character.
tabs = r"\A\t"

# Non-uppercase constants: "const <type> <name>;" where <name>
# has any lowercase letter. The nested char classes and optional
# assignment tail are what make it ugly.
constants = r"const\s+([a-zA-Z]|_)([a-zA-Z]|[0-9]|_)*\s+" \
            r"(([a-zA-Z]|_)([a-zA-Z]|[0-9]|_)*|\s*,\s*)*" \
            r"([a-zA-Z]|_)([A-Z]|[0-9]|_)*[a-z]+([A-Z]|[0-9]|_)*(\s*=\s*.+)*;"

# Switch without default: grab a whole switch block, then
# re-search inside for `default:`.
switch_block = r"switch\s*\(.*\)\s*\{[^\{;]+\}"

# Header-guard matcher: capture the #ifndef name and #define name, compare them.
header_guard = r"#ifndef\s*(.*)\n#define\s*(.*)"

# Header-comment detector: // or * or whitespace, then
# "File" / ".cpp" / ".hpp" / ".h". Paired with a separate
# /(Author|author)/ check for the author line.
header = r"(\/\/|\*|\s)+.*(File|file|.hpp|.cpp|.h)"

By The Numbers

1. TeX: 31,043 lines
2. C/C++ Header: 28,235 lines
3. C++: 17,246 lines
4. SQL: 11,184 lines
5. Python: 7,758 lines
6. C: 2,667 lines
7. Shell: 1,513 lines
8. Assembly: 656 lines
9. MATLAB: 337 lines

Commit Activity by Hour

+-------------------------------------------------------+
| Commit Activity by Hour                               |
+-------------------------------------------------------+
| Hour   | Commits | Distribution                       |
+-------------------------------------------------------+
| 00:00  |      14 | ███████                            |
| 01:00  |       4 | ██                                 |
| 02:00  |      11 | ██████                             |
| 03:00  |       5 | ██                                 |
| 04:00  |       0 |                                    |
| 05:00  |       0 |                                    |
| 06:00  |       0 |                                    |
| 07:00  |       4 | ██                                 |
| 08:00  |       7 | ███                                |
| 09:00  |      32 | █████████████████                  |
| 10:00  |      34 | ██████████████████                 |
| 11:00  |      30 | ████████████████                   |
| 12:00  |      28 | ███████████████                    |
| 13:00  |      21 | ███████████                        |
| 14:00  |      31 | ████████████████                   |
| 15:00  |      24 | █████████████                      |
| 16:00  |      36 | ███████████████████                |
| 17:00  |      20 | ██████████                         |
| 18:00  |      25 | █████████████                      |
| 19:00  |      40 | █████████████████████              |
| 20:00  |      41 | ██████████████████████             |
| 21:00  |      64 | █████████████████████████████████  |
| 22:00  |      44 | ████████████████████████           |
| 23:00  |      16 | ████████                           |
+-------------------------------------------------------+
| Total commits: 545                                    |
+-------------------------------------------------------+

Peak activity: 9 PM with 64 commits.

Activity Heatmap

                          ACTIVITY HEATMAP
──────────────────────────────────────────────────────────────────────

          Jan  Feb  Mar  Apr  May  Jun  Jul  Aug  Sep  Oct  Nov  Dec
        ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
   2014 │  ░ │    │    │    │    │    │    │    │    │    │    │    │
        ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤
   2015 │    │    │  ░ │    │    │    │    │    │    │    │  ░ │  ░ │
        ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤
   2016 │  ░ │  ░ │ ██ │ ██ │ ██ │    │  ░ │    │    │  ░ │  ▒ │  ░ │
        ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤
   2017 │  ░ │ ▒▒ │ ▒▒ │ ██ │  ▒ │    │    │  ▒ │ ▒▒ │  ▒ │  ░ │  ░ │
        ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤
   2018 │ ██ │ ██ │ ██ │ ▒▒ │    │    │    │    │    │    │    │    │
        └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘

──────────────────────────────────────────────────────────────────────
             ░ 1-10     ▒ 11-30     █ 31-50     ██ 51+

                   Spring semesters: Jan-May
                     Fall semesters: Aug-Dec

Lines of Code by Year

                     LINES OF CODE BY YEAR
──────────────────────────────────────────────────────────

      2014       2015       2016       2017       2018
        │          │          │          │          │
        │          │          │          │      ████████
        │          │          │          │      ████████
        │          │          │      ████████   ████████
        │          │          │      ████████   ████████
        │          │      ████████   ████████   ████████
        │          │      ████████   ████████   ████████
        │      ████████   ████████   ████████   ████████
    ████████   ████████   ████████   ████████   ████████
  ────────────────────────────────────────────────────────
      ~2k       ~10k       ~20k       ~25k       ~35k

For the notes and problem sets themselves, see Academia Notes.

To my peers and professors at Missouri S&T: thank you. You made those four years special, and I remember them fondly. The late nights coding, the early morning classes where I'd take my first sips of coffee, the many fruitful discussions in between. All of it.