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]
26
questions
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: ...
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 ], ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
14
votes
4answers
601 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 ...
7
votes
4answers
803 views
Write two programs that compresses and decompresses 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 ...
42
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 ...
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 ...
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:
...
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 ...
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, <...
1
vote
4answers
450 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 ...
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:
<...
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 ...
9
votes
1answer
1k 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 ...
5
votes
2answers
550 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 ...
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.
...
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? ...
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 ...
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 ...
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:
...
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 ...
