A new challenge
In building our TypeScript compiler, we wanted to try out a fun new challenge. Can it solve problems devs use to train for their tech interviews? Obviously it isn’t a developer, so it is using no functional code. The compiler attacks these problems using only the type system!
The full article explores how the TypeScript compiler can be leveraged to solve LeetCode problems, demonstrating its practical applications and flexibility. It highlights TypeScript’s ability to infer types based on context, making it a robust tool for algorithmic problem-solving on platforms like LeetCode’s Two Sum problem.
The Problem
Caveats
There are a couple of caveats we’ll make to this process right away though.
* TypeScript has no mathematical operations for numbers in the type system.
* Given that we have to build them, we’re going to limit our number range to [-512,512].
We can’t submit these results obviously, but I will add some of the test cases to check our “solutions”.
* Everything has to compile with just stock tsc to ensure we are getting the full type checking fun though we will be using the latest versions of the language to get the best chance for success.
Our Strategy
This is meant to be a fun challenge, so we go straight into a more complex solution to this problem. A naive approach to finding the pairs could use two for loops, but since looping in the type system is already hard, this isn’t necessarily the best strategy anyway. Instead, we take a single pass through the data while keeping a “hash map” of previously calculated deltas to find the pairs.
With no mathematical primitives already in the type system, we start by creating a few. We must be able to detect negative values, an addition and subtraction component and a higher level Subtract that handles positive/negative combinations. We’ll also use the increment/decrement strategy from the TypeScript SQL Parser series and just recursively call them until the add/subtract operations finish.
This calculates the difference between the current value and the desired value to populate the hash map. Next, add the single pass solution that will approximate the for loop while tracking the current state.
Putting this into the simple main.ts driver, the results for the sample solutions come back correctly and also indicate when there is no valid combinations.
Optimizing the Solution
This numeric creativity seems pretty solid on the surface, but upon further examination, the types in the structuredTypeRelatedTo blocks, Subtract shows up like a sore thumb. The actual source of the problem is the recursive search, calling recursive subtract and using the result as a key in a dynamic object. In retrospect that was a bit of a bad idea.
Just adding another layer to infer the Subtract calls appropriately as numbers satisfies the system and saves about 170k types.
See the Code
Check out the code in the full article and in our SQL parsing series on GitHub!
Check out the full article to go in depth with code samples:
Or go straight for the repository:
