Kansas City Shuffle
or Best mathematical insight
On this site we often see answers in languages specifically designed for short code, or designed to be fast. Sometimes, a nice golfing trick or speed-up technique surprises us with its ingenuity, beyond the standard use of that language.
And occasionally an answer shows up that uses an unexpected approach to greatly simplify the problem, and makes us wonder how the author could ever think of that. This usually involves some far-from-obvious mathematical equivalence, or a particularly simple approach to the problem that was not evident at all (once revealed, other answers often follow the same approach).
This category is for the answer with the best mathematical insight or unexpected approach that led to greatly simplifying the problem, in any challenge type (code golf, fastest code, or others). The insight should have led to a significant improvement according to the challenge's metric (code
length, run time, or whatever applicable).
Nominations:
Nominated by TimmyD
An easy enough challenge (that xnor even helped tighten up before answering), but practically every answer posted says something like "Uses xnor's algorithm". The algorithm itself is a simple conclusion of the challenge setup, but approaches it from an unintuitive angle, resulting in an elegant approach that many others utilized.
Nominated by wat
Dennis simplified this whole challenge by showing that the numbers form a telescopic series, making answers much easier than completing the original problem as intended.
Nominated by DJMcMayhem
Is it a Proth number is one of my favorite challenges I've posted. The premise is very simple:
Can a number N be expressed as
N = k * 2^n + 1
Where k is an odd positive integer and n is a positive integer such that 2^n > k
Which is a fairly straightforward thing to test for. Dennis flipped this on it's head, and threw in a bunch of bit-shifting magic, and almost an entire paper of mathematical analysis to prove it worked. I remember watching answers pouring in after his, all claiming
Uses Dennis's algorithm
Self-nomination
This answer tackles the decision problem "Is this number a Giza number?" by observing a beautiful mathematical property of all Giza numbers, and applying this insight into the solution. Instead of analyzing the problem purely from a programmatic standpoint, the code, and the explanation, highlights the relationship between Giza numbers and repdigits, and takes full advantage of it in the code.
Self-nomination
It's quite common to reduce a "real-world" problem to a single mathematical formula, but this answer expands a mathematical formula to an elaborate real-world problem. By doing so, a simple pattern becomes apparent that would be hard to detect in the mathematical definition of the sequence. This allows to replace the combinations in the original formula (which would require a lengthy implementation in Python and other languages that lack the built-in) with a doubly-recursive function that uses only elementary operations.
Self-nomination
While determining coprimality is straightforward in programming languages with a GCD built-in and computing the GCD with the Euclidean algorithm is also quite easy, filtering all coprimes from a range requires two function definitions, which take a toll on the byte count. This answer does something different: it uses multiplicative inverses modulo n to detect coprimes. Not only makes this computing the GCD unnecessary, it manages to solve the problem with a simple loop. The algorithm from the original Python was successfully ported to JavaScript, which also lacks a GCD built-in.
Self-nomination
This is an insight I'm proud of that didn't get much visibility.
The problem is to evaluate an arithmetic expression in a variant of the complex numbers where j^2 = 1. It would seem like you need to parse the expression and resolve how each operator acts on this new type of number.
Instead, I use the fact that both the numbers j=1 and j=-1 satisfy j^2 = 1. So, the resulting equality must hold for them as well. Evaluating the input expression as Python code on these values gives a system of two equations that can be solved for the output. This allows a 62-byte solution, far shorter than anything with parsing.
Self-nomination
Computing the Carmichael function can be a straightforward loop or recursive function in languages that have coprimality or GCD built-ins, but some languages (e.g., Python) lack both. This answer defines a different mathematical function which definition uses only elementary arithmetic operations; determining coprimality or calculating GCDs is not required. The answer also contains a formal proof that this function is identical to the Carmichael function and provides a concise, recursive implementation.
Self-nomination
Superficially, the problem at hand seems entirely unrelated to coprimality or Euler's totient function. Yet, this answers uses a unique approach based on the latter, which has a particularly concise implementation in the chosen language. While that approach saved only one byte over the straightforward solution, the approach is most unexpected and achieved a 10% reduction of the score.
