Recently, I've been a fairly active member of the Code Golf and Coding Challenges (CGCC) community, a site dedicated to programming challenges. Users can post questions (like 'output "Hello World!" in as little code as possible'), and then other users can post answers that solve those challenges.
I've focused on two main areas of interest: answering long-unsolved questions, and answering questions in TypeScript's type system. Long-unsolved questions tend to relate to rather varied domains and be of high difficulty. Providing answers and explanations to these questions is very rewarding, especially as such contributions are highly valued by the community.
What follows is a sample of six of my most interesting answers on the site.
This question was famously the longest outstanding unanswered question: to a create a program that takes a regular expression and outputs its complement. Though it was well-established that solving the challenge was possible, no answer had been posted during the 7.5 years since it was asked. Solving it involved working with multiple advanced computer science topics, including Nondeterministic Finite Automata, Thompson's Algorithm, and Brzozowski's Method.
This answer won the "Wild card" category in Best of CGCC 2021, with the nominator describing it as: "... could easily have been nominated for Most Complex Answer or Best Explanation, but @tjjfvi already has another worthy contender in those categories!"
Regular expressions (regexes) are a tool in computer science used to describe sets of strings (of text). For example, you could write a regex that describes strings made of lowercase letters, or strings that represent a number.
The complement of a regex is another regex that includes all strings the original regex doesn't — for example, the complement of a regex representing strings composed of all lowercase letters would be a regex representing strings that contain at least one uppercase letter or other non-letter character (like a number).
This question was unanswered for nearly two years, and involves a particularly interesting topic: Mathematical Knot Theory, which deals with knotted loops of string. Dowker notation is a way to describe mathematic knots, but every knot has infinitely many possible descriptions. The coding challenge, thus, is to determine if two arbitrary descriptions are of the same knot.
Solving this challenge involves repeatedly applying the Reidemeister moves to simplify the knots; once simplified, it is relatively trivial to determine if they are isotopic.
Dowker notation encodes the locations where the string of a knot crosses over itself, meaning that the one knot has many different representations in Dowker notation, depending on the placement of parts of the knot. For example, the unknot (which is just a simple loop) usually has zero crossings, but a figure-eight (which is isotopic to the unknot — it is just a loop that has been twisted) has one crossing — meaning that the two would have different Dowker notations, despite being equivalent.
To determine if two knots are equivalent, thus, is non-trivial, as the two knots may have extra twists that don't actually change what kind of knots they are. Thus, the two knots must be reduced before they can be checked for equivalency. To do so, my program essentially "fidgets", continually manipulating and simplifying the knots. If they're ever identical, then the two knots are isotopic. If the program fully reduces the knots, and the two knots have never been identical, it can know for sure that the two knots aren't isotopic.
To "fidget" with the knots, my program applies the three Reidemeister moves (I: adding a twist into the knot; II: moving a string over another string; III: moving a string over a crossing). As it does so, it ensures that it never adds additional crossings, by only using the I and II moves in reverse. Once no further reduction can be done in that manner, it cycles and mirrors the knot, and applies III where it can. For each of the resulting knots, it repeats this process, and memoization is used to avoid redundant computation.
Unanswered for 6.5 years, this challenge is to implement a parser for Context Free Grammars (CFGs).
Like the regexes from above, CFGs describe sets of strings, but they're a little more powerful — you can make a CFG from any regex, but there are CFGs that have no equivalent regex. For example, you can create a CFG describing valid mathematical equations, but not a regex.
Unanswered for over 6 years, this challenge is to read the output of
(an ascii art generator) and output the original text. This is difficult because
figlet, letters are "squished together" causing their outlines to overlap.
Here's an example of
figlet's output (for the text
_____ ___ ____ _ _____ _____ _____ _______ _______
| ___|_ _/ ___| | | ____|_ _| |_ _| ____\ \/ /_ _|
| |_ | | | _| | | _| | | | | | _| \ / | |
| _| | | |_| | |___| |___ | | | | | |___ / \ | |
|_| |___\____|_____|_____| |_| |_| |_____/_/\_\ |_|
My program scans through the text looking for patterns matching chunks of the letters, which means that a single letter can have multiple patterns. Consequently, the standard representation of all the patterns would be very large, 23094 bytes (~20 pages of text).
Part of the challenge is to make your code as short as possible, so I wrote a custom compression algorithm to reduce the size by over 35 times (to only 649 bytes). Excluding the table, the program is smaller than the size of the 'FIGLET TEXT' above!
Quines are a special kind of program: one which outputs its own source code. Many recreational programming sites — including CGCC — will compile collections of the shortest quine in every programming language. I found, however, that at least one language was missing from the collections. This answer — a quine in TypeScript Types — remedies that, and is, to my knowledge, the first of its kind.
In the month of December, a CGCC user posted a new question every day through the 25th — like an advent calendar, but with programming challenges! I embarked on a personal mission to solve as many as I could in TypeScript Types.
I fully accomplished the mission, successfully answering all 25 questions using TypeScript types. My set of answers was nominated for Best of CGCC 2021.