← Blog Home

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.

Commentary

Leave a Comment

Vezious says: January 6, 2018
Awesome. Looking forward to 2018.
Thetacah says: January 6, 2018
Sounds fun! ;3
natsaa says: January 6, 2018
Thanks for the challenge! This was a lot of fun, but I don't have enough time to do anything past the first challenge. For anyone interested, heres my code: Original Challenge: https://pastebin.com/qnAk8J4G Elite #1: https://pastebin.com/k6GbJvpD
Z_Doctor says: January 7, 2018
There are some inconsistencies with the first challenge. (1) For the set {1, -2, 3, -4, 5, 6} becomes "-2, -4, 1, 3, 5, 6", -4 is placed after -2 even though -4 is less than -2. (2) In the same set 5 and 6 are separated and not 5-6, however in the set {1, 2, 5, 6, 7} becomes "1-2, 5-7", 1 and 2 are consecutive and only a set of two but are treated as a range and a later challenge addresses this.
evaera says: January 7, 2018
Thanks, the challenges went through a few revisions and I didn't update all of them correctly because I was in a rush to get this out. Fixed it now :)
chess123mate says: January 7, 2018
@natsaa: Your Elite #1 has incorrect output for {1, 2, 3, 3}: "1-3, 3 x2" My submission (contains all levels with test code): https://pastebin.com/MZTbzsDk You can change what tests it runs at the bottom of the file. Note that for the last expected output of Level 2, I changed {1, 1, 1, 1, 5, 1, 5} to "1 x4, 5, 1, 5" instead of "1 x3, (1, 5) x2" (I explain why in the code).
chess123mate says: January 7, 2018
Overall it was a fun challenge =) I felt I got to practice writing good code (though it's not perfect or anything, but it was very easy to debug compared to most code I've written before!) By the way, did anyone else submit to Snack Break 26? Usually there's an announcement of other submissions at the beginning of the Snack Breaks.
superhudhayfa says: January 7, 2018
Not a single idea what it wants me to do. 1-4, What? Can someone please explain. Thanks.
chess123mate says: January 7, 2018
@superhudhayfa: The idea is for you to write code that takes in a table like {1, 2, 3, 4} and transforms it into the string "1-4". Of course, it should handle all cases, not just the listed ones.
farrizbb says: January 7, 2018
Might actually do this challenge, good luck to others!
farrizbb says: January 7, 2018
Might actually do this challenge, good luck to others!
kools says: January 8, 2018
Awesome challenge and I love seeing more on the blog! I'll give it a go when I have more time this week.
mattscy says: January 8, 2018
Here’s my go at the original challenge: https://pastebin.com/SFwvQmmY Going to try the elite challenges later.
hiimgoodpack says: January 13, 2018
I don't get the second and third example on the regular challenge.
chess123mate says: January 14, 2018
@hiimgoodpack you're supposed to sort the list first (for both Challenge and Elite 1)
Ad