Snack Break Problem #27

Snack Break problems have been a running blog series on Scripting Helpers for the past three years, originally started by Unclear. Since then, the authors and frequency of posts has changed, but the purpose is the same: Provide a quick and thought-provoking challenge for new programmers to overcome and experienced programmers to perfect. To start off our third year running of problems to solve, we have another challenge ready to go.

This challenge deals in the wonderful realm of data compression. That is, taking some amount of data, and transforming it into a format that is shorter, but still means the same thing. The data can then be transformed back into the original somewhere else. In this challenge, you will be dealing with a list of numbers.

This challenge contains four levels, each getting progressively more difficult. The standard challenge will give you an introduction to data compression, and the three elite challenges that follow will build upon that.

The Challenge

Given a list of numbers, you are to create a human-readable list that will express the list in a more compact format. To do so, you can combine ranges of numbers into a set, so the list {1, 2, 3, 4} becomes "1-4", the list {7, 4, 6, 2, 8} becomes "2, 4, 6-8", and so on.

You should write a function that can transform a table of numbers into a string following the above format.

Expected Output

• {1, 2, 3, 4} becomes "1-4"
• {7, 4, 6, 2, 8} becomes "2, 4, 6-8"
• {1, -2, 3, -4, 5, 6} becomes "-4, -2, 1, 3, 5-6"
• {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} becomes "1-10"
• {1, 2, 5, 6, 7} becomes "1-2, 5-7"

Elite Challenge: Level 1

Up until now, what happens when there is a duplicate number in the list has been undefined. For the elite challenge, you should make duplicate numbers appear only once but be followed with a multiplier, like "10 x2". Additionally, ranges of only two numbers (e.g. 1-2) should not appear, and instead be written as (1, 2)

Expected Output

• {1, 2, 5, 6, 7} becomes "1, 2, 5-7"
• {1, 1, 2, 3, 4} becomes "1 x2, 2-4"
• {1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 2, 2, 3, 3, 4, 4} becomes "1 x4, 2 x4, 3 x4, 4 x4"

Elite Challenge: Level 2

Unlike the previous two challenges, here you will maintain the order of the set, but still compress the complexity by detecting repeating patterns. You will still combine numbers in ranges when they appear next to each other. Patterns should be surrounded by parenthesis, with an x2, x3, x4, etc. following it based on how many times the pattern repeats.

Expected Output

• {1, 2, 3, 4} becomes "1-4"
• {4, 2, 3, 1} becomes "4, 2, 3, 1"
• {1, 2, 1, 2} becomes "(1, 2) x2"
• {1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7} becomes "(1 x2, 2 x2, 3 x2, 4 x2) x2, 5-7"
• {1, 2, 1, 2, 1, 2, 1, 2} becomes "(1, 2) x4"
• {1, 1, 1, 1, 5, 1, 5} becomes "1 x3, (1, 5) x2"

Elite Challenge: Level 3

For this final challenge, you will maintain the behavior as you created in Level 2, however, it should also be able to detect patterns inside of other patterns, in order to compress the data even further.

• {1, 3, 5, 1, 2, 1, 2, 1, 2, 7, 9, 5, 1, 3, 5, 1, 2, 1, 2, 1, 2, 7, 9, 5} should become "(1, 3, 5, (1, 2) x3, 7, 9, 5) x2"

In the above set, the first pattern becomes with "1, 3, 5" and then repeats "1, 2" three times before ending with "7, 9, 5". Then, the entire thing repeats twice.

Discussion

We welcome discussion of this challenge in our Discord server. You can also feel free to leave a comment on this blog post. Answers can be DM'd to "eryn" on the Discord server, or left in the comments below with a link to a Pastebin post if you want to share with everyone.