Karmel

01What it is

Think NYT Games but with numbers instead of letters. The app is named after a similar math game I played in 7th grade, and it exists because I refused to let the postfix expression algorithm I wrote in CSE12 exist in vain.

02How it's built

How are the expressions evaluated?

Converting the input into postfix order is what handles the precedence and the parentheses. Side note: while writing this project, I was reminded that stacks truly are the most adorable data structure. So literal, so petite, so cute.

Getting bored with this explanation? Skip to the non-computer-science-y part

Does every board have a verified solution?

Yes, I make the intern solve it by hand.

The completed path must be a Hamiltonian path on the 3x3 king graph: it visits every square once and moves like a king in chess.

The script that builds the daily puzzles generates a board and a target, hands the pair to the solver, and rejects the puzzle if the solver returns nothing.

The solver picks any one path, which fixes the order of the nine digits. The paths are tried in a shuffled but fixed order, so the pick is not biased toward one corner of the board. An interval dynamic program then covers every operator and every set of parentheses over that order, as illustrated below.

So how many of those tables would you have to build? In principle 784, one per possible Hamiltonian path on the 3x3 king graph. Not 362,880, which is what nine digits would come to if the order were free — (yes, this is a human-placed em dash) the adjacency narrows it down to just 784. Big savings! Yahoo!

In practice the code builds one (1) table. Mega savings! Yeehaw! Across a year's worth of games, all 300+ boards were solved on the very first path tried. That is because nine digits in nine squares are more flexible than they look: every target from 1 to 100, which is the range the game draws its targets from, has a path that lands on it, in 71 milliseconds.

The cost of one of those runs is O(n³ · C²). A run is any unbroken stretch of the path, and you pick one by choosing where it starts and where it stops. Two choices, each one of n spots, so about n² runs. They are the rows in the table above: the path 5 2 9 8 gives ten of them, from 5 on its own up to the whole 5 2 9 8. Each run then gets broken in two, and there are n places to break it, so n² runs times n places is n³ breaks to work through. Every break pairs what the left side can reach against what the right side can reach. n is nine (because the board is 3x3) and it is not going to change, so C, the cap on how many possible answers a run is allowed to keep, is the variable I can control.

What is the tech stack?

This is built entirely on a web stack using JavaScript/React. It ships as a PWA, so it "installs" straight from the browser on Android and on iOS. Players do not need to touch the app store.

Umami handles the product metrics, Sentry the error tracing and alerts.

03Delight engineering

When you solve the puzzle, the animation retraces the route you took across the board. The leaderboard shows everyone's path, so you get to see that someone hit the same target in a way you would never have thought of. Streaks give you a reason to come back tomorrow. The weekly recap turns seven small, forgettable moments into one story you can see.

The double-parenthesis key wraps what you already typed instead of tacking one on the end, because that is how players build an expression, with the parentheses coming as an afterthought. Making players follow the keyboard's layout instead is counterintuitive, and fixing it afterward is phone-throwing frustrating.

I also set it up as a PWA so it lives on a home screen instead of being a website in a tab, and wrote custom bottom sheets that move the way a native one does. A big part of making this app feel good, and therefore work well, is making it behave like it belongs to the phone rather than to a browser. Loading skeletons hold the shape of whatever is coming, so the board does not jump around while you are already reaching for it. The downside of a web-only stack is that it leaves me without haptic feedback or notifications. Darn.

04Edge cases I choose to live with

Why is Gmail the only sign-in option?

Sign-in via email links was previously available, but because the link needs to open in the same browser as the game, the feature would not work for any player who uses the app as an installed PWA. Perhaps I will offer regular email and password sign-in in the future. Heavy on the perhaps.

What if a player uses a huge factorial, like (9!)!?

A factorial that big will not hang the game, but no number will be returned as the running total. 9! is 362,880, and multiplying that many times runs past the largest number JavaScript can hold, so the game reports that expression as uncalculable.

Perhaps there is a better and faster way of calculating these egregiously large expressions; they must have taught it in CSE13.