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
17 votes
14 answers
3k 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 <...
naffetS's user avatar
  • 12.3k
43 votes
9 answers
7k 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: ...
Ilmari Karonen's user avatar
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 ...
user avatar
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 ...
JPvdMerwe's user avatar
  • 2,954
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 ], ...
MD XF's user avatar
  • 13.8k
319 votes
24 answers
46k 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 ...
N. Virgo's user avatar
  • 7,252
258 votes
37 answers
50k 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 ...
N. Virgo's user avatar
  • 7,252
36 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 ...
kukac67's user avatar
  • 2,189
22 votes
3 answers
882 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 ...
Beta Decay's user avatar
  • 23.3k
18 votes
3 answers
727 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 ...
Dennis's user avatar
  • 210k
15 votes
4 answers
709 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 ...
Dennis's user avatar
  • 210k
9 votes
5 answers
981 views

Write two programs that compress and decompress data

Challenge: Create a program that compresses a semi-random string, and another program that decompresses it. The question is indeed quite similar to this one from 2012, but the answers will most ...
Stewie Griffin's user avatar
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 ...
sbseltzer's user avatar
  • 531
34 votes
29 answers
4k 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, <...
DJMcMayhem's user avatar
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: <...
Arnauld's user avatar
  • 191k
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 ...
orlp's user avatar
  • 39.1k
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. ...
Blue's user avatar
  • 28.5k
25 votes
1 answer
841 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 ...
Dennis's user avatar
  • 210k
24 votes
17 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 ...
naffetS's user avatar
  • 12.3k
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: ...
Dennis's user avatar
  • 210k
21 votes
3 answers
594 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 ...
caird coinheringaahin g's user avatar
21 votes
10 answers
901 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 ...
Dennis's user avatar
  • 210k
20 votes
1 answer
537 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 ...
Nathan Merrill's user avatar
18 votes
5 answers
873 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? ...
Martin Ender's user avatar
15 votes
4 answers
992 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 ...
Beefster's user avatar
  • 9,901
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 ...
randomra's user avatar
  • 20.8k
12 votes
4 answers
633 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: ...
Christian Sonne's user avatar
9 votes
1 answer
2k views

The Most Durable Pokemon Types

Background This question is similar to this one. I have provided all of the information needed below. If you are familiar with the other challenge then note that we are ranking all defenses instead ...
Devin White's user avatar
5 votes
2 answers
601 views

Generate a self-extractor application

Create a program in any language, that takes an arbitrary binary input, and generates a valid C++11 program, which when compiled and run will print this binary input. So you could do this (on linux ...
SztupY's user avatar
  • 3,879
1 vote
4 answers
463 views

Send the pairs in smallest output

Write two programs A and B. Program A (the encoder) takes 1024 pairs of integers \$(k,v)\$, where \$0≤k<2^{32}\$ and \$0≤v<1024\$, and all \$k\$ will be different. It will output a single ...
l4m2's user avatar
  • 22.3k