Introduction to Code-golf
This article features several examples so anyone with some programming knowledge can grasp the codegolfing concept by doing. The included challenges are solved by using the C# language. Code-golf is a competition to solve a particular problem in the fewest bytes of source code, using any programming language.
Code-golf is a section on the StackExchange network of sites, along with other programming related ares, like the well-known StackOverflow, Code Review, Software Engineering.
The section's full name is "Programming Puzzles & Code Golf" and describes itself as "a question and answer site for programming puzzle enthusiasts and code golfers". Great! So what does code-golf actually mean?
Code-golf is a competition to solve a particular problem in the fewest bytes of source code. By default, full programs and (anonymous) functions in any programming language are accepted.
There are also other competitions with different winning criteria:
- Fastest-code = a competition determined by the runtime performance of the submissions, benchmarked on the same machine.
- Fastest-algorithm = a competition won by the answer with the smallest asymptotic time complexity.
- Popularity-contest = a competition where the answer with the highest vote tally wins.
- Code-challenge = a competition for creative ways to solve a programming puzzle with an objective winning criterion not covered by other scoring tags.
- Restricted-source = a competition which imposes a restriction on the source code used to solve the challenge, for example, having no numbers in the source code.
A language is a form of communication, composed of signs, meanings and a connection between them.
Languages can be classified in:
- natural languages
- formal languages (including programming languages)
Natural languages are complex, open to interpretation and context dependant. They have loose syntax, their symbols can have multiple meanings as the language evolves.
Programming languages are simple and unambiguous while also evolving.
Our current model of computing requires a machine to be able to unambiguously interpret a statement, so programming languages are "context free", i.e. the action required of a statement is unambiguous and does not depend on the surrounding statements.
Can be classified in:
Alright, enough with the theory, time to get down to business. Some examples to illustrate code-golf.
Note: It's best to write code in whatever programming language you feel comfortable with. The following challenges will be solved using C#. You can try them online at .NET Fiddle.
1. Output the Sign.
Given a number N, output the sign of N:
- If N is positive, output 1
- If N is negative, output -1
- If N is 0, output 0
N will be an integer within the representable range of integers in your chosen language.
One can write either a full program, or a function. Let's write a function.
int f(int N)
{
if (N > 0)
return 1;
else if (N < 0)
return -1;
return 0;
}
91 bytes. Not very efficient. Let's minimize the function by removing all unnecesary whitespace:
int f(int N){if(N>0)return 1;else if(N<0)return-1;return 0;}
60 bytes. Better. Yes, the C# compiler will consider `return-1` correct. And improvements can still be done - the `else` is unneeded, even though the function is less efficient by removing it. However, we'll switch to the ternary operator to save even more bytes.
int f(int N){if(N>0)return 1;else if(N<0)return-1;return 0;}
36 bytes by chaining the ternary operator twice.
Let's try an anonymous function:
N=>N>0?1:N<0?-1:0;
18 bytes by removing the boilerplate code. However a definition is still necessary for multiple uses. We'll have:
Func<int, int> f = N=>N>0?1:N<0?-1:0;
At this point you might be wondering - doesn't C# and its libraries provide us with such a function? Of course! There's a built-in: Math.Sign!
N=>Math.Sign(N);
16 bytes!
Unbeatable built-in? We can try to reduce the size again:
N=>N>0?1:N>>31;
15 bytes! What wizardry is this?!?
Let's take a closer look. With some whitespace, the code becomes:
N=> N>0 ? 1 : N>>31;
If N is strictly positive, the result is 1. No issues whatsoever. But if it is not, the sign bit is taken and shifted to the right. All other bits take its value. 0 will remain 0. But a negative number becomes `111..1`, which is the representation of -1 in the computer's memory.
Test it out with the following lines:
Console.WriteLine(Convert.ToString(0, 2)); // 0 Console.WriteLine(Convert.ToString(0>>31, 2)); // 0 Console.WriteLine(Convert.ToString(-15, 2)); // 11111111111111111111111111110001 Console.WriteLine(Convert.ToString(-15>>31, 2)); // 11111111111111111111111111111111
Sometimes skill beats language
2. Leap Years
Take an input which will be a year from 1801 to 2400, and output if it is a leap year or not.
Note that leap years are not ever four years always. 1896 is a leap year, but 1900, 2100, 2200 are not.
Test cases:
1936 / 2272 / 2400 are leap years
1805 / 1900 are not leap years
We'll go for an anonymous function from the start:
y=>DateTime.IsLeapYear(y);
...and we used a built-in again to bring the code down to 26 bytes!
With the function definition the code becomes:
Func<int, bool> f = y=>DateTime.IsLeapYear(y);
It's hard to beat a built-in function. We can still try:
y=>y%25<1?y%16<1:y%4<1;
Done! 23 bytes!Let's explains what's going on:
y => y % 25 < 1 ? // the shorter form of `y % 25 == 0` - if the year number is divisible by 25 y % 16 < 1 // and if it's also divisible by 16, it is a multiple of 25*16 = 400, so it's a leap year : y % 4 < 1 // otherwise (not divisible by 25) it's a leap year if it is a multiple of 4 (since the 25 * 16 case is already covered);
Again, skill beats language
3. Press any key to continue
Your task is to create a program that will display the following text, wait for the user to press a key (it is okay to ignore keys like ctrl, alt, caps lock, etc.), and then terminate the program:
Press any key to continue...
The program must exit immediately after a key is pressed. Also, the program must be fairly portable (i.e no OS-specific headers or modules, runs outside of an IDE, etc.).
C# will qualify, since MonoDevelop exists for Linux.
This time a full program is necessary:
using System;
class P
{
static void Main()
{
Console.Write("Press any key to continue...");
Console.Read();
}
}
By removing the whitespace we bring the code down to 103 bytes:
using System;class P{static void Main(){Console.Write("Press any key to continue...");Console.Read();}}
Not much we can do from this point. However, since `Console` is repeated we can define an alias for it.
using C=System.Console;class P{static void Main(){C.Write("Press any key to continue...");C.Read();}}
101 bytes!
CTRL, ALT, SHIFT are ignored. The pressed key will be echoed on screen if printable.
Echo can be disabled by replacing C.Read() with C.ReadKey(0<1) at the cost of 6 more bytes. `0<1` is evaluated to false, so echo is now disabled.
Display the letter "A" alone, without anything else. Both the lowercase and uppercase versions are acceptable, but not any lookalike / homoglyph versions.
However, you must not use any of the below characters in your code, regardless of the character encoding that you pick:
A / a, U / u, X / x, +, &, #, 0, 1, 4, 5, 6, 7, 9
Finally, a restricted-source challenge!
We can't write a full program because of `Main` is required and already contains the letter A. It's difficult to do even from a function, since there are no implicit conversions from other types to the char types.
Let's try this:
()=>(3<2).ToString()[3-2];
Evrika! This returns `a`! And in only 26 bytes!
Explanation:
3<2 evaluates to `False`, which is then converted to a string. A character from the string has can be accessed by using the index operator []. `a` is situated at index 1 (3-2).
All the examples have put an emphasis on the shortest code used to solve a challenge. Sometimes the performance is really important, especially in a real life situation. A difficult problem might also be treated as a programming puzzle and assessed according to different criteria.
Visit the site for a lot more challenges!
- learn your language properly! (built-ins FTW!)
- focus on optimization [less is more!]
- encourages creativity
- continuous learning
- hard to read and understand code
- often sub-par code from a performance point of view
- hard to maintain and modify code
- treat it as a learning experience
- learn to improve your real-world code
