| Submit | All submissions | Best solutions | Back to list |
PROG0030 - Run-length encoding |
Run-length encoding, RLE in short, is replacing repeated patterns in a text by the number of repetitions plus the pattern that is repeated. This way, a text that contains many repetitions can be saved under a strongly shortened form. For this assignment we will keep it at the simple form of run-length encoding that applies the following rules:
- Every sequence of 2 to 9 consecutive identical characters are coded by two characters. The first character is a digit that indicates the length of the sequence. The second character is the repeated character itself. A sequence of more than 9 consecutive identical characters is treated by coding the first 9 characters and afterwards coding the rest.
- A sequence of characters that doesn't contain any consecutive identical characters are coded by the digit 1, followed by the sequence of characters and again closed with 1. If the digit 1 occurs in the sequence, this digit is doubled.
Assignment
Write a function rle to which a string $s$ should be given as an argument. The function must print the coded form of the string $s$ as a result. This result is obtained by application of the simple run-length encoding scheme that was described in the introduction.
Example
>>> rle('AAAAAABCCCC') '6A1B14C' >>> rle('12344') '11123124'
Run-length encoding, kortweg RLE, is het vervangen van herhaalde patronen in een tekst door het aantal herhalingen plus het patroon dat herhaald wordt. Op deze manier kan een tekst die heel veel herhalingen bevat onder sterk ingekorte vorm opgeslagen worden. Voor deze opgave houden we het bij een eenvoudige vorm van run-length encoding die de volgende regels toepast:
- Elke reeks van 2 tot 9 opeenvolgende identieke karakters wordt gecodeerd door twee karakters. Het eerste karakter is een cijfer dat de lengte van de reeks aangeeft, en het tweede karakter is het herhaalde karakter zelf. Een reeks van meer dan 9 opeenvolgende identieke karakters wordt behandeld door eerst de eerste 9 karakters te coderen, en daarna de rest te coderen.
- Een reeks van karakters die geen opeenvolgende identieke karakters bevat wordt gecodeerd als het cijfer 1, gevolgd door de reeks van karakters, en opnieuw afgesloten door het cijfer 1. Als het cijfer 1 zelf voorkomt in de reeks, dan wordt dit cijfer verdubbeld.
Opgave
Schrijf een functie rle waaraan een string $s$ als argument moet doorgegeven worden. De functie moet de gecodeerde vorm van de string $s$ als resultaat teruggeven, die bekomen wordt door toepassing van het eenvoudige run-length encoding schema dat in de inleiding beschreven werd.
Voorbeeld
>>> rle('AAAAAABCCCC') '6A1B14C' >>> rle('12344') '11123124'
| Added by: | Peter Dawyndt |
| Date: | 2011-07-20 |
| Time limit: | 5s-10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | |
| Resource: | None |
RSS