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.
666
questions
17
votes
12
answers
1k
views
Day of the week of an ambiguous date
Goal
Write a program or function that returns the day of the week for a date, eg.
01/06/2020 -> Mon
However, it's unknown if the date is in the format mm/...
- 8,570
35
votes
108
answers
4k
views
Numbers by Position
Challenge
Print the numbers:
1
22
333
4444
55555
666666
7777777
88888888
999999999
In that order.
I/O
Takes no input. The numbers can have any delimiters desired (...
- 1,921
26
votes
26
answers
5k
views
Print a list of iPhones
Write the shortest program that prints, in order, a complete list of iPhone iterations, according to this site:
...
- 17.9k
2
votes
0
answers
167
views
Predictor Generator [closed]
Write a program that when given a string \$S\$, it generates a program of the same language as itself.
The generated program, when given a continuous substring of \$S\$, should predict the next ...
- 659
0
votes
0
answers
151
views
Let's learn a bit French: 99 Bottles [duplicate]
The 99 bottles in French
The lyrics of the song goes like this:
...
- 727
31
votes
20
answers
4k
views
Print this maximally long URL
Task
This one is simple. We want to compress a URL, but don't trust URL shorteners.
Write a program that prints to stdout (or a 0-argument function that returns) the following, working URL:
http://...
- 29k
8
votes
6
answers
802
views
How predictable is popular music?
The McGill Billboard Project annotates various audio features of songs from a random sample of the Billboard charts. I scraped this data to produce the following file of chord progressions:
...
- 2,249
30
votes
17
answers
7k
views
.-...--..---.-...--..... the red-nosed reindeer
Can you recover a sequence of letters from a sequence of dots and dashes? In Morse code, x is represented by -..-, but without ...
- 2,249
26
votes
28
answers
4k
views
Even and Odd Numbers
Sandbox
Adapted from exercise 4 of 100 little Keg exercises
The ability to repeat chunks of code within a program is an important part of any programming language. Also just as important is the ...
- 23.8k
8
votes
3
answers
747
views
What is a short code for generating this matrix in R?
I can see that it is 101 'moving to the right' but I cannot think of a short way to generate it in R language.
\$\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 ...
- 89
45
votes
36
answers
7k
views
Draw the Ionising Radiation Hazard Symbol
Draw the ionising-radiation-hazard-symbol in an arbitrary colour on a distinctly coloured background. The specific proportions were published in the June 27th 1974 issue of the Federal Register of the ...
- 43.2k
16
votes
1
answer
547
views
How short can you get?
You are to write a program that, when given an integer between 1 and 5 (or 0 and 4 if you wish to use 0-indexing), outputs one of Code, ...
- 48.2k
30
votes
12
answers
4k
views
Identify the Eeveelutions
Gah! It's a shame that Pokémon Sword and Shield won't introduce a new eeveelution. Let's mourn them with a code golf.
The objective is to, when given a type name as the input, output the name of the ...
- 4,173
20
votes
22
answers
6k
views
Pi to the power y, for small y's
Input
This task takes no input.
Output
Your code should compute and print (or return)
\$\pi^y\$ for all \$y = \frac11, \frac12, \frac13, \frac14, \frac15, \frac16, \frac17, \frac18, \frac19, \frac1{...
user9207
34
votes
61
answers
3k
views
-9
votes
1
answer
643
views
Don't get banned from stack exchange! [closed]
I'm sure this is going to spark some controversy, but let's do a practical demonstration.
The objective of this is simple, using the new code of conduct and no input, print out my pronouns ( "he/him"...
- 3,583
17
votes
6
answers
1k
views
From Plate to State
This is essentially the inverse of Generate a US License Plate
Challenge: Given a string that matches one of the below license plate formats, output all possible states that match that formatting. In ...
- 42.9k
44
votes
19
answers
10k
views
23
votes
10
answers
3k
views
Where are they calling from?
When making phone calls internationally, phone numbers are prefixed with a code indicating what country the number is located in. These codes are prefix codes, meaning that no code is a prefix of ...
- 3,615
21
votes
16
answers
4k
views
Escape the labyrinth!
You are trapped in this 5x5 labyrinth - each room is labelled from 1 to 25 and the exit is in room 1.
You are given as input the room you are currently in. Your task is to output the shortest ...
- 8,383
31
votes
28
answers
7k
views
Output a Super Mario Image
This is a problem on Luogu OJ. I decided to post it here because on Luogu OJ, many people, including me and my friend, are interested about how to solve this problem within the fewest characters.
...
- 3,826
73
votes
22
answers
19k
views
Draw the ☣ (Biohazard Symbol)
Draw the Biohazard symbol in an arbitrary colour on a distinctly coloured background. The specific proportions were published in the June 27th 1974 issue of the Federal Register of the US Government.
...
- 43.2k
47
votes
18
answers
6k
views
First Number to Contain Each Letter
Given a single letter from A to Z (except J and K) as input, output the smallest non-negative integer containing that letter in its written form. Assume numbers never contain the word "and", so ...
- 13.5k
59
votes
13
answers
8k
views
Who was president of the USA?
Challenge
Write a program that takes as input a day from April 30, 1789 to August 21, 2019 and returns as output who was president of the USA that day.
Notes
For the list of US presidents, the ...
- 669
29
votes
32
answers
3k
views
Output the list of musical notes
This task is simple: Write a program or function that outputs the list of all musical notes (using English note names) from A♭ to G♯.
All notes without a name consisting of a single letter (i.e. ...
- 1,329
35
votes
21
answers
5k
views
Telephone number in spoken words
Goal
Write a program or function that translates a numerical telephone number into text that makes it easy to say. When digits are repeated, they should be read as "double n" or "triple n".
...
- 8,570
30
votes
5
answers
2k
views
Print the new site header
The new site header has some bits of source code from various questions as the background. Here are the first 3 lines:
...
- 3,899
59
votes
35
answers
11k
views
Print the phrase "And she said, 'But that's his.'" using only the alphabet
Print the phrase And she said, 'But that's his.' using only the following characters: ...
- 729
55
votes
58
answers
16k
views
Print "N NE E SE S SW W NW"
This seems almost trivial, but since after some effort I was not able to beat the literal solution in J, I thought it might make a decent challenge (though, to be clear, this is not a J-specific ...
- 29k
1
vote
1
answer
193
views
Find 77 7-letter Magic Words [closed]
A magic word is a word whose Braille spelling contains precisely 26 dots (because the Morse code alphabet can be circularly encoded within). For example:
...
- 21
106
votes
12
answers
9k
views
Proving that a Russian cryptographic standard is too structured
The aim of this challenge is to find an impossibly short
implementation of the following function p, in the langage of your
choosing. Here is C code implementing it ...
- 951
22
votes
7
answers
2k
views
Surface of the 3x3x3 cube as a graph
Your task is to generate a graph with 54 vertices, each corresponds to a facet on a Rubik's cube. There is an edge between two vertices iff the corresponding facets share a side.
Rules
You may ...
- 36.2k
29
votes
23
answers
5k
views
Binary Numbers Magic Trick
The challenge is simply; output the following six 2D integer arrays:
...
- 109k
37
votes
7
answers
3k
views
List of Python versions
Python is the fastest-growing major programming language today. It is the most wanted language for the third year in a row, meaning that developers who do not yet use it say they want to learn it.[1]
...
- 45.1k
13
votes
13
answers
2k
views
Output the ŋarâþ crîþ alphabet song without using (m)any letters
Your goal is to write a program that takes no input and outputs the following text:
...
- 2,301
40
votes
26
answers
5k
views
Output the Arecibo Message
The Arecibo message is a 1974 interstellar radio message carrying basic information about humanity and Earth sent to globular star cluster M13 in the hope that extraterrestrial intelligence might ...
- 9,791
77
votes
66
answers
18k
views
Sing Baby Shark
"Baby Shark" is a children's song about a family of sharks. Having long been popular as a campfire song, it has been popularized since the mid-2000s by social media, online video and radio. - ...
- 997
-4
votes
2
answers
415
views
Print "beep boop bop" using complicated methods [duplicate]
This challenge is pretty simple: you need to alert / print / show to the user the text "beep boop bop" (or "beep\nboop\nbop", with newlines), but it needs to be obfuscated. (where you couldn't see ...
- 123
-6
votes
4
answers
406
views
This ain't it Chief
This is mostly for the memes. I regret existing.
Rules
Your code has to output, by either printing or showing in stdout, the phrase This ain't it Chief. in that ...
49
votes
35
answers
10k
views
There's a hole in the bottom of the sea
Whilst trying (and failing) have persuade my infant son to eat his dinner, I tried singing to him. Mid way through this song I realised the formulaic structure might lend itself well to code golfing!
...
- 6,012
2
votes
3
answers
187
views
All the digisibles [duplicate]
A natural number (written in the decimal base) is qualified as digisible if and only if it fulfills the following 3 conditions:
none of its digits is zero,
all the digits that compose it are ...
- 2,777
-2
votes
27
answers
882
views
Print a square!
Print this text:
_________
| |
| |
| |
|_________|
Shortest code wins. Notice the space at the start of the first line.
- 136
14
votes
10
answers
856
views
Kolmogorov Flexibility. A.K.A. Sale! \$38\%\$ Off All Codegolf While Stocks Last!
This is a restricted-source, kolmogorov-complexity, code-golf challenge to produce a fixed output with no input.
The output format, however, is flexible - it may be printed to standard out, printed to ...
- 94k
9
votes
14
answers
944
views
Simulate a Cisco Ping
Premise:
For those in networking, you've most likely sent a ping to or from some device to make sure everything's properly connected. Cisco, a popular company in networking[citation needed], has a ...
- 4,012
36
votes
51
answers
5k
views
Print all lexicographically increasing numbers under 10000
A lexicographically increasing number is an integer whose digits are in strictly increasing order. Print all lexicographically increasing numbers under 10000.
Here are lines of the expected output:
...
- 469
44
votes
25
answers
12k
views
Tribute to Stan Lee
Unfortunately one of the greatest comic book writers passed away yesterday afternoon. Lots of Hollywood stars, musicians, actors, and many other people are paying tribute to this awesome writer, so we ...
21
votes
46
answers
2k
views
Multiplicity Test
Use any programming language to display numbers between 1 and 99 (including both) in such a way, so that:
the numbers are separated by single space,
if a number is divisible by 3, it should be in ...
- 1,109
-12
votes
21
answers
481
views
Sequence and Series
Use any programming language to display numbers divisible by 1000000 that are greater than 1 and less than 10000000. Each number should be displayed in new line. Your program should display exactly:
<...
- 1,109
24
votes
17
answers
3k
views
10
votes
26
answers
2k
views
Let's play tennis 2: east-west game
There is a challenge Let's play tennis by Daniel. He proposes to place a court in the North-South direction. My proposal is to create a court to play tennis in the East-West direction too.
You ...
- 6,795