Questions tagged [compression]
Related to compressing or decompressing arbitrary data. Challenges which relate to compressing a single specific input should instead be tagged [kolmogorov-complexity]
95
questions
317
votes
24
answers
45k
views
Write Moby Dick, approximately
Here is a 1.2Mb ASCII text file containing the text of Herman Melville's Moby-Dick; or, The Whale. Your task is to write a program or function (or class, etc. -- see below) which will be given this ...
- 7,182
257
votes
37
answers
49k
views
Paint Starry Night, objectively, in 1kB of code
Note: a 1000 point bounty is still available for this challenge, which I will create and award if anyone takes the top score without using built-in compression.
Below is a ...
- 7,182
59
votes
10
answers
8k
views
Encode Images into Tweets (Extreme Image Compression Edition) [closed]
Based on the very successful Twitter image encoding challenge at Stack Overflow.
If an image is worth 1000 words, how much of an image can you fit in 114.97 bytes?
I challenge you to come up with a ...
- 28.8k
50
votes
7
answers
7k
views
Reverse Zip Bomb
A zip bomb is a compressed file, designed so that unpacking it yields the biggest file possible. These are fairly well known, and there are examples of 42 KB files which expand into multiple petabytes ...
- 17.7k
43
votes
17
answers
10k
views
Smallest chess board compression
Write an algorithm or program that can encode and decode a chess board. The goal is to make the smallest representation of a chessboard that could be used (once decoded) to determine all movement ...
- 531
42
votes
9
answers
6k
views
Text compression and decompression — "Nevermore."
With the recent discussion about the use of compression tools in code golf, I thought it would be a nice challenge to write your own text compressor and decompressor.
Challenge:
Write two programs: ...
- 20.6k
39
votes
2
answers
2k
views
Musical Tweet Challenge
This is the audio version of the Twitter image encoding challenge.
Design an audio compression format that can represent at least one minute of music in 140 bytes or less of printable UTF-8-encoded ...
- 6,571
37
votes
12
answers
2k
views
lc's dvntrs n Wndrlnd
The task
Today's special offer: consonants and punctuation for FREE!
Your program or function will be given as input the first 6 paragraphs of Lewis Carroll's famous novel Alice's Adventures in ...
- 179k
36
votes
18
answers
3k
views
Bracket Expansion!
Your challenge is to expand some brackets in a program's input as shown:
Find a string s between two matching brackets [ and ], ...
- 13.5k
35
votes
16
answers
7k
views
Sudoku Compression
Your job is to write a program (or two separate programs) in any language that:
Can take a completed Sudoku board as input (in any logical format) and compress it into a string of characters
Can take ...
- 2,181
35
votes
10
answers
3k
views
Help me recognise my monster
Background
The computer game NetHack dates from 1987, before the use of graphics in computer games was widely established. There are lots of monsters in the game, and potentially a lot need to fit on ...
user62131
34
votes
29
answers
3k
views
Is it a prefix code?
In information theory, a "prefix code" is a dictionary where none of the keys are a prefix of another. In other words, this means that none of the strings starts with any of the other.
For example, <...
- 57.9k
32
votes
20
answers
3k
views
Golf a golf chart
Given a distance in meters as an integer \$60\le d \le 260\$, return the number of clubs that may be used according to the following arbitrary chart, where both \$min\$ and \$max\$ are inclusive:
<...
- 179k
32
votes
8
answers
3k
views
Latin square compression
A Latin square is a square that has no repeated symbols in the rows or columns:.
13420
21304
32041
04213
40132
And as many Sudoku players know, you don't need ...
- 14.4k
31
votes
2
answers
3k
views
Compress an image to a 4 KiB preview
In this challenge you will be creating an image preview compression algorithm. It's goal is to
reduce an arbitrary image file to a 4 KiB preview image, that can be used to quickly identify images
with ...
- 38.9k
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,277
30
votes
11
answers
2k
views
Which wire to cut
This task is about compressing and processing a sequence of conditionals.
In the game Keep Talking and Nobody Explodes, a bomb defuser must disarm a bomb with the help of instructions relayed by ...
- 141k
29
votes
24
answers
3k
views
Converting "0xUsernames"
0xUsernames
There's so many people using a messaging service that they're running out of space to store all the usernames! To fix this, they are going to start storing usernames as hexadecimal, where ...
- 14.5k
27
votes
8
answers
2k
views
Somewhere On The Tube ...But On Which Lines?
The London Underground A.K.A. The Tube is the oldest underground railway in the world, it currently consists of eleven lines* servicing 267 named stations (strictly 269** stations since "Edgware ...
- 97.9k
25
votes
14
answers
2k
views
25
votes
7
answers
3k
views
Big big numbers
Whilst trying to golf several of my answers, I've needed to write large integers in as few characters as possible.
Now I know the best way to do that: I'll be getting you to be writing this program.
...
- 28.4k
25
votes
1
answer
835
views
Maximal discrepancy-2 sequence with minimal entropy
Background
As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
- 208k
22
votes
10
answers
2k
views
Compressing the Atomic Ionization Energies
This is a different type of compression challenge. In a normal kolmogorov-complexity challenge, you are required to recreate a list exactly. Here, you are allowed to round the values in any way you ...
- 28.8k
22
votes
3
answers
861
views
Golfing Strings
I have always failed to give an answer for kolmogorov-complexity challenges which require string compression, the main reason being that I don't know to use string compression tools as effectively as ...
- 23.1k
22
votes
2
answers
2k
views
Lossy ASCII art compression
Background
PICASCII is a neat tool that converts images into ASCII art.
It achieves different degrees of brightness by using the following ten ASCII characters:
...
- 208k
21
votes
16
answers
4k
views
Who needs 8 bits for one character?
Given a string and the characters used to encode it, you need to compress the string by only using as many bits as each character needs. You will return the character codes for each character needed ...
- 12.7k
21
votes
10
answers
886
views
Move to the printable ASCII front
Background
The move-to-front transform (MTF) is a data encoding algorithm designed to improve the performance of entropy encoding techniques.
In the bzip2 compression algorithm, it is applied after ...
- 208k
20
votes
12
answers
4k
views
All your base 97 are belong to us
Many programming languages are written using solely printable ASCII, tabs and newlines. These 97 characters are then stored in 8-bit bytes (which are actually capable of holding 256 different ...
- 9,366
20
votes
3
answers
518
views
Decompress an integer, Jelly style
Jelly has compressed string literals, using the “...» delimiters. The way these work is by interpreting the ... as a base-250 ...
- 48.4k
20
votes
1
answer
520
views
Diff compression [closed]
For this challenge, you need to compress a diff. A diff is some data that represents the difference between two strings. For this challenge, you need to provide one or more programs that can:
Input ...
- 14.4k
19
votes
37
answers
2k
views
Compactify the input
Given a word, your task is to compact it by saving its first character and removing any other vowel (aeiou).
Input
Your input can be the word in STDIN, a function argument or any other input format ...
- 5,335
19
votes
19
answers
3k
views
Run-Length Encoding [duplicate]
Write a program uses run-length encoding to shorten a list of non-negative integers it has to read in.
You can assume the non-negative integers can fit in 32bit signed integers.
Input Format
The ...
- 2,944
19
votes
14
answers
2k
views
Let's decompress a bit
Given a compressed string \$s\$ made of printable ASCII characters (32 to 126), your task is to print or return the original text by applying this simple decompression algorithm:
Start with \$k=0\$
...
- 179k
18
votes
5
answers
867
views
Boggle Board Compression
When working on Non-Palindromic Polyglot Boggle, I found it quite tedious to pack the codes as efficiently as possible onto the Boggle board, even with only two strings. But we're programmers, right? ...
- 195k
18
votes
3
answers
714
views
Burrows, Wheeler and Back
Background
The Burrows–Wheeler transform (BWT) is a reversible permutation of the characters of a string that results in large runs of similar characters for certain types of strings such as plain ...
- 208k
18
votes
2
answers
892
views
Thwart Lepton compression
Dropbox recently released Lepton (GitHub), a method that losslessly compresses JPEG images round-trip, saving an average of 22%.
Because of the pigeonhole principle, any general compression algorithm ...
- 3,287
17
votes
2
answers
1k
views
Monopoly Compression
Given a string representing the current state of a game of Monopoly at the beginning of a player's turn, compress all the necessary data into the smallest output. Answers will be judged by output size ...
- 19.7k
15
votes
7
answers
925
views
Send a cosmic call
The cosmic call is a message sent into space in 1999 and 2003.
It's made of 23 127*127px monochrome bitmap images, as detailed here.
Your mission is to write a program that displays the entire 127*...
- 5,811
15
votes
4
answers
937
views
Palindrome Compression
Challenge
Write a program that compresses and decompresses ASCII text losslessly. It should be specialized to work well with palindromes, including case-insensitive and punctuation-insensitive ...
- 9,861
15
votes
4
answers
675
views
Implement bzip2's run-length encoding
Background
After applying the BWT (as seen in Burrows, Wheeler and Back) and the MTF (as seen in Move to the printable ASCII front), the bzip2 compressor applies a rather unique form of run-length ...
- 208k
14
votes
14
answers
1k
views
Output code-sized Lorem Ipsum [closed]
Output the same length of Lorem ipsum your code is!
Rules:
Code can't be identical to output
No compression libraries
Shortest program in two weeks wins
No network usage, file reading and other ...
- 20.7k
14
votes
2
answers
509
views
What's my TIO uniqueness?
Try it online! currently has 680 listed languages, all of which are searchable. For most of those languages, when searching for it, you don't have to enter the entire string. For example, entering <...
- 48.4k
14
votes
2
answers
1k
views
Create the least compressible picture
"A picture is worth a thousand words"—so the old saying goes. The average word is about four characters long, so a picture conveys 4kB of information. But how much entropy, rather than information, ...
- 1,517
13
votes
8
answers
618
views
Compress and decompress
Your task is to make a bidirectional compressor. It takes a list of bytes as input and returns a list of bytes as output. It has the property than whenever it is iterated twice it returns the original ...
- 6,785
13
votes
12
answers
2k
views
I want 8 bits for every character!
This is the reverse of this challenge.
Given an encoded list of codepoints and the characters used to encode it, you need to decompress it to its original string.
For example, given the encoded list <...
- 12.7k
12
votes
9
answers
2k
views
Naïve compression
using Prefixed Length Code
We are going to implement a compression of text (string, array/list of characters/bytes) by simple substitution of each character by a binary code, based on the frequency of ...
- 20.9k
12
votes
4
answers
5k
views
Lorem Ipsum Compressor
Write a program which can compress/decompress randomly generated Lorem Ipsum text.
Devise your own lossless algorithm. You may compress your data further using an existing algorithm afterwards, but ...
- 1,945
12
votes
4
answers
625
views
Strategies for representing a given large integer using arithmetic expression
I have a specific number in mind, but it's part of a challenge I'm doing, and I don't want people to do (all) the work for me.
Here is a number which has the same digits, but shuffled:
...
- 279
12
votes
5
answers
691
views
Implement a URL shortener
URLs are getting too long. So, you must implement an algorithm to shorten a URL.
i. The Structure of a URL
A URL has 2 main parts: a domain and a path. A domain is the part of the URL before the ...
user46167
12
votes
6
answers
7k
views
Compressing RLE data to draw ASCII art
This question is based on what I came up with to answer another question.
Sometimes the questions here ask to draw some ASCII art. One simple way to store the data for the art is RLE (run-length ...
- 12.7k