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]

Filter by
Sorted by
Tagged with
306
votes
23answers
41k 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 ...
244
votes
36answers
46k views

Paint Starry Night, objectively, in 1kB of code

Note: Anders Kaseorg has been awarded the accept for now, to draw attention to his great answer, but the challenge is by no means over! I will award a 1000 point bounty to anyone who takes the top ...
59
votes
10answers
7k 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 ...
41
votes
17answers
8k 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 ...
40
votes
9answers
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: ...
38
votes
2answers
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 ...
37
votes
11answers
1k 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 ...
36
votes
19answers
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 ], ...
35
votes
10answers
2k 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 ...
34
votes
14answers
6k 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 ...
33
votes
29answers
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, <...
31
votes
20answers
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: <...
31
votes
8answers
2k 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 ...
30
votes
11answers
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 ...
29
votes
2answers
2k 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 ...
28
votes
15answers
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 ...
27
votes
8answers
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 ...
26
votes
21answers
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 ...
25
votes
6answers
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. ...
25
votes
1answer
771 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 ...
24
votes
12answers
2k views

Print a Ternary Value

Put simply, you are to print out the following number: ...
22
votes
10answers
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 ...
22
votes
3answers
810 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 ...
22
votes
2answers
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: ...
20
votes
1answer
473 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 ...
19
votes
19answers
2k 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 ...
19
votes
14answers
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\$ ...
19
votes
12answers
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 ...
19
votes
7answers
777 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 ...
19
votes
5answers
840 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? ...
17
votes
32answers
1k 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 ...
17
votes
3answers
674 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 ...
17
votes
2answers
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 ...
17
votes
2answers
830 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 ...
15
votes
7answers
897 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*...
15
votes
4answers
830 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 ...
15
votes
2answers
823 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, ...
14
votes
4answers
600 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 ...
12
votes
13answers
1k views

The weird and wild bean game

Maybe some of you already know this game: you have a collection of jelly beans of different colors. For every color, the bean can have different tastes, some are good and some are bad, and you cannot ...
12
votes
9answers
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 ...
12
votes
4answers
592 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: ...
12
votes
1answer
755 views

Lossless English language text compression challenge [closed]

Challenge: Your challenge (should you choose to accept it) is to compress and decompress the 5MB "Complete Works of William Shakespeare" as found here: http://www.gutenberg.org/cache/epub/100/pg100....
11
votes
11answers
1k views

Output code-sized Lorem Ipsum

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 ...
11
votes
7answers
1k views

Thwart LZMA2 compression

Goal Create a program or pair of programs that collectively disrupt and fix files with the intent of preventing LZMA2 from working effectively. The disrupt and fix routines must be reciprocal, so ...
11
votes
10answers
2k views

Cheat activated

Background The game Grand Theft Auto: San Andreas went down in history also thanks to its wide selection of cheats. They're almost 90 and anyone who has ever touched this game, no doubt has tried ...
11
votes
1answer
686 views

Write a compressing util for gzip files

The task of this challenge is as following: Write a program that reads a file of reasonable size (let's say <16 MB) from stdin or anywhere else (however you like, but must not be hardcoded), and ...
11
votes
6answers
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 ...
11
votes
5answers
644 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 ...
10
votes
12answers
2k views

Simple State Sales Tax Calculator

Sales taxes in the United States are complicated, to say the least. Generally, there's a state sales tax (there are a handful of states that do not collect a state sales tax), but there could also be ...
10
votes
5answers
920 views

Breaking Bad - ize any string (compression) [duplicate]

The TV series "Breaking Bad" replaced the letters Br and Ba with a periodic-table like representation, printing [Br35]eaking [Ba56]d. Create a program ...