Questions tagged [kolmogorov-complexity]

Kolmogorov complexity, informally, is the amount of code it takes to describe or produce a constant object, such as a string or image. When posting a challenge in this category, please make sure it adds something new to existing challenges.

Filter by
Sorted by
Tagged with
20 votes
35 answers
3k views

Generate a Universal-binary-function Lookup Table

This is tangentially related to my quest to invent an esoteric programming language. A table of the binary numbers 0 .. 15 can be used to implement a Universal Binary Function using indexing ...
luser droog's user avatar
  • 4,917
3 votes
3 answers
1k views

Print element from the periodic table [duplicate]

Your task is simple: given a number as an input, you have to print the English name of the chemical element with that atomic number, up to and including ununoctium. For example, for an input of 77, ...
vsz's user avatar
  • 8,137
32 votes
42 answers
4k views

Print an arch of ascending / descending numbers

I figured an "arch" was the best way to describe this pattern of numbers: ...
Nathan Osman's user avatar
37 votes
41 answers
4k views

Print a string in as few distinct characters as possible

The task is simple: print The quick brown fox jumps over the lazy dog using as few distinct characters in your source code as possible. ...
ashastral's user avatar
  • 2,634
20 votes
69 answers
6k views

Print this Multiplication Table

Write shortest code to print the following Multiplication Table: ...
matrix42's user avatar
  • 665
31 votes
22 answers
15k views

Count from 1 to 100... in Roman Numerals

Write a program that count from 1 to 100 in Roman Numerals and print these numbers by standard output. Each one of the numbers must be separated by spaces. You cannot use any built in function to ...
Averroes's user avatar
  • 4,117
7 votes
5 answers
4k views

Normal distribution values

Write the shortest program possible which outputs a table of Normal distribution values phi(z) = Integral[t from -infty to z of e^(-t^2/2) /sqrt(2 pi) dt] for <...
student's user avatar
  • 71
34 votes
9 answers
3k views

Who's that Pokémon? [closed]

Input: an integer N between 1 and 151 Output: the Nth Pokemon. Rules You may use one data file. You may not use any already made data decompression algorithms. This includes libraries and other ...
cardboard_box's user avatar
15 votes
26 answers
3k views

Smile! Just smile [duplicate]

It's well known that Brainf*ck is very bad at Kolmogorov-complexity problems, for example, it requires around 100 characters just to print "Hello world". However, there might be texts where Brainf*ck ...
vsz's user avatar
  • 8,137
100 votes
140 answers
21k views

Print this diamond

This question has been spreading like a virus in my office. There are quite a variety of approaches: Print the following: ...
Eric Wilson's user avatar
  • 1,109
7 votes
13 answers
1k views

Generate the names of the keys on a piano

On a standard 88 key piano, each key has a scientific name. The first three keys are A0, B♭0, and B0. The keys then proceed through C1, D♭1, D1, E♭1, E1, F1, G♭1, G1, A♭1, A1, B♭1, B1, and start over ...
user avatar
20 votes
42 answers
5k views

Calculate golden ratio

Write the shortest code, in number of bytes, to display, return, or evaluate to the golden ratio (that is, the positive root of the quadratic equation: \$x^2-x-1=0\$, approximately 1.618033988749895), ...
user avatar
17 votes
17 answers
2k views

Display the result of doing 8 perfect shuffles of a deck of cards

Explanation A perfect shuffle is where a deck of cards is split exactly in half and the cards from each pile are alternately interleaved. The original bottom cards and the original top card must be ...
Peter Olson's user avatar
  • 7,742
47 votes
44 answers
19k views

Draw A Sierpinski Triangle

The Sierpinsky Triangle is a fractal created by taking a triangle, decreasing the height and width by 1/2, creating 3 copies of the resulting triangle, and place them such each triangle touches the ...
Kibbee's user avatar
  • 959
290 votes
73 answers
79k views

We're no strangers to code golf, you know the rules, and so do I

Write the shortest program that prints the entire lyrics of "Never Gonna Give You Up" by Rick Astley. Rules: Must output the lyrics exactly as they appear in the above pastebin*. Here's the raw dump:...
Polynomial's user avatar
  • 4,526
65 votes
113 answers
18k views

List of primes under a million

This is my first code golf question, and a very simple one at that, so I apologise in advance if I may have broken any community guidelines. The task is to print out, in ascending order, all of the ...
Delan Azabani's user avatar
50 votes
10 answers
17k views

Write the shortest program that generates the most compiler warnings and errors

The challenge: Write a very short program that, when compiled, creates the most amount of compiler warnings and errors. It can be written in any programming language. Scoring: The score is ...
user avatar
25 votes
2 answers
13k views

Shortest ELF for "Hello world\n"? [duplicate]

Is it possible to write (pack) a shorter than 145 bytes version of a program with "Hello world" (plus new line) output if the length of the program is measured as a number of bytes in program's ELF (...
Yauhen Yakimovich's user avatar
16 votes
15 answers
1k views

Calculate a user's privileges on CodeGolf.SE

The Challenge Your goal is to write the shortest program possible that will take a list of events (such as upvote, downvote, etc) and return the user's reputation and the privileges that he has ...
PhiNotPi's user avatar
  • 29.1k
35 votes
11 answers
15k views

Brainf*** Golfer

One of easiest code written by a programming language is a program printing sequence of characters (ex. "Hello, world!"). However, some esoteric programming languages like Brainfuck, even this ...
JiminP's user avatar
  • 3,472
10 votes
10 answers
2k views

Encode an image inside of the source

The golf challenge is to encode and compress the following image inside a source file. To do this you need to write 3 functions: red, ...
Pubby's user avatar
  • 1,249
5 votes
6 answers
625 views

An Old Irish Blessing, reasked (without using encodings)

How much can you golf a program to print "An Old Irish Blessing" without using unprintable ASCII characters? That restricts us to ASCII characters 32-126 (better still, 32,65-90,97-122 and 13(CR)) ...
smci's user avatar
  • 177
6 votes
9 answers
7k views

ASCII Tux (Linux Penguin) [closed]

I once hacked upstart on my Ubuntu box so that a colored, themeable ASCII Tux displayed on the screen with the boot messages scrolling beneath him. I'm curious to ...
Kazark's user avatar
  • 307
14 votes
20 answers
9k views

Say "Hello" to the world in ASCII art

Challenge: Produce the following output using as few chars as possible: ...
Ilmari Karonen's user avatar
25 votes
26 answers
12k views

12 Days of Christmas Lyrics

I thought this would be a fun challenge for everyone and I'm curious to see the solutions people come up with. Print the "12 Days Of Christmas" lyrics ...
macek's user avatar
  • 369
30 votes
87 answers
15k views

Print a Christmas Tree

The Challenge Print a nice Christmas tree with it's own star at the top using the shortest code possible. The tree star is an asterisk (*) and the tree body is ...
Averroes's user avatar
  • 4,117
11 votes
29 answers
1k views

Display Peter's keyboard pattern

Assume an simple keyboard with this layout: 1 2 3 4 5 6 7 8 9 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z . , ? ! Peter's keyboard pattern can be ...
Peter Olson's user avatar
  • 7,742
29 votes
31 answers
4k views

There Was an Old Lady

Your goal is to write a program that prints the following poem exactly as it appears here: ...
Ethan Roseman's user avatar
9 votes
7 answers
2k views

Generating BF-code with single purpose

I'd like to see you create code (in any programming language) that output working BF (Brain***k) code. Your program have a single character input on stdin. The input should be one digit ("0", "1", "2",...
Peter Wirdemo's user avatar
13 votes
4 answers
558 views

Pinyin Combinations

Create a function that takes a string of a pinyin syllable as the argument, and returns true of the combination exists, false otherwise. Use "v" for "ü". Here is a full list of combinations. http://...
Ming-Tang's user avatar
  • 5,969
17 votes
9 answers
7k views

Shortest, lexicographically smallest generating string

A string x generates a string y if y is a substring of an infinite repeat of ...
Keith Randall's user avatar
6 votes
8 answers
1k views

LED Numbers and Letters

The program must print the following block of text of LED numbers exactly. ...
Ming-Tang's user avatar
  • 5,969
38 votes
40 answers
5k views

Print the alphabet four times

The program must print the alphabet four times: first in the normal alphabetical order, second in the order of a qwerty keyboard, third in the order of a dvorak keyboard, and lastly in reverse ...
Peter Olson's user avatar
  • 7,742
74 votes
164 answers
19k views

The alphabet in programming languages

Our task is to, for each letter of the (English) alphabet, write a program that prints the alphabet, in a language whose name starts with that letter. Input: none Output: ...
Joey Adams's user avatar
  • 10.6k
14 votes
12 answers
2k views

An Old Irish Blessing

I don't know who coined these words, and I'm not Irish, but I give you an Irish blessing: ...
Joey Adams's user avatar
  • 10.6k
16 votes
9 answers
3k views

Calculate digits of Pi

This is a somewhat different task. Calculate 1024 hexadecimal digits of π, beginning at the 1024th hexadecimal place. Formally: Your program should complete in less then 1 minute and produce the ...
FUZxxl's user avatar
  • 10.1k
21 votes
7 answers
2k views

The Tic Tac Toe Dictionary

A TicTacToe game can be represented by a string denoting the sequence of positions as the players make their move. 0 1 2 3 4 5 6 7 8 Assume ...
st0le's user avatar
  • 2,228
22 votes
6 answers
3k views

Koch Snowflake - codegolf

The Koch snowflake (also known as the Koch star and Koch island) is a mathematical curve and one of the earliest fractal curves to have been described. It is based on the Koch curve, which appeared in ...
gnibbler's user avatar
  • 15.1k
4 votes
3 answers
1k views

->The Tragedy of Macbeth<- [closed]

The Setup Here you can find the full text of The Tragedy of Macbeth. If you view the source, and save it as text, you will notice it comes out to 206,244 total characters (including the whitespace ...
Nick Larsen's user avatar
63 votes
117 answers
23k views

99 Bottles Of Beer [closed]

Recreate '99 bottles of beers on the wall'. The desired output is this: ...
Nick Berardi's user avatar

1
10 11 12 13
14