# Run-Length Encoding

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 length, `n`, of the list on the first line.

On the second line, a space-separated list of integers representing the list of integers.

Output Format

A space separated list of integers. The first 2 integers represent the first run, the next 2 integers the second run and so on. For each pair of integers representing a run, the first integer represents the length of the run and the second represents the value of the integer in the run.

Sample Input

1.

``````5
1 1 3 2 2
``````

2.

``````3
1 1 1
``````

Sample Output

1.

``````2 1 1 3 2 2
``````

2.

``````3 1
``````

Limits

``````0<n<10000
``````
-
 Similar to golf.shinh.org/p.rb?Look+and+say and stackoverflow.com/questions/3908513/code-golf-morris-sequence – Nabb Feb 18 '11 at 10:08 ignore this. :-\ – st0le Feb 18 '11 at 10:46 I think you should give a more tricky input, like 36/1 1 1 1 1 1 3 3 3 3 3 2 2 7 7 7 7 4 4 9 9 9 9 9 9 9 9 9 4 4 8 3 3 3 3 0, giving 6 1 5 3 2 2 4 7 2 4 9 9 2 4 1 8 4 3 1 0, to ensure correct output when there are several distinct sequences of same number. – PhiLho Jul 28 '11 at 19:55

# sh - 3329 28

``````read;echo`xargs -n1|uniq -c`
``````

Usage:

``````\$ cat input|sh 1015.sh
2 1 1 3 2 2
``````
• `read` skips the first line

• `xargs -n1` reads the reast and outputs each number on one line:

``````1
1
3
2
2
``````
• `uniq -c` filters adjacent matching lines (with the `c` switch it also prints the number of adjancent lines) :

``````2 1
1 3
2 2
``````
• `echo` sees those numbers as separate arguments and just prints them separated by a space:

``````2 1 1 3 2 2
``````
-
WTF? How is that possible? – FUZxxl Feb 18 '11 at 20:16
added explanations :-) – user300 Feb 18 '11 at 20:26
Very nice! (more chars) – J B Feb 18 '11 at 20:50
You might be able to replace `tail -n1|` with a well-placed `read;` – J B Feb 18 '11 at 20:52
And the `tr` can be replaced with an `xargs`. `read;echo`xargs -n1|uniq -c`` for 28 characters. – J B Feb 18 '11 at 21:03
show 1 more comment

## Perl, 46 5668

``````\$_=<>;s/(?{\$a=1})(\d+)( \1(?{++\$a}))*/\$a \$1/g
``````

Run with the `p` command-line option (counted in code size):

``````\$ perl -pe '\$_=<>;s/(?{\$a=1})(\d+)( \1(?{++\$a}))*/\$a \$1/g'
5
1 1 3 2 2
=> 2 1 1 3 2 2
3
1 1 1
=> 3 1
``````
-

# Ruby - 57

``````\$><<[*\$<][-1].gsub(/(\d+)( \1)*/){"#{\$&.split.size} "+\$1}
``````

Ungolfed:

``````length = STDIN.readline
print input.gsub(/(\d+)( \1)*/) { |match|
"%d %s" % [ match.split.size, \$1 ]
}
``````
-
Fails on integers more than 2 digits wide. – J B Feb 18 '11 at 16:10
oops ! thanks, fixed now – user300 Feb 18 '11 at 16:17

# Scala - 136

``````def f(s:Seq[_]):String=if(s.isEmpty)""else{val(l,r)=s.span(s.head==);l.size+" "+s.head+" "+f(r)}
``````
-
 Beautiful! I attempted a recursive solution, but it was longer than my attempt above. And I totally missed the span function, the key here. I also didn't know you can do s.head==, a devious trick! Note: according to my editor, that's 135 chars (with LF), and 133 if we don't count the newlines (as others did). – PhiLho Jul 28 '11 at 19:42 @PhiLho I did a `wc` on it. You probably don't have a LF on the last line, and I did. I think LF must be counted, because they have actual meaning here -- I'd have to use `;` if I made it a one-liner. – Daniel Sobral Jul 28 '11 at 20:58 I agree we should count the LF as they are significant separators, but it looks like Python programs above doesn't count them, while they are as significant... You can get rid of the trailing LF for golf purpose (I too always have it!). And even use a plain 'print' as hamsterofdeath did. Note: I like your version because it is readable even in the golf state! – PhiLho Jul 29 '11 at 5:40 You can get this down to 126 by changing `s.isEmpty` -> `s==Nil`; `s.head` -> `s(0)`; `println` -> `print` – Luigi Plinge Nov 25 '11 at 4:35 also first `readLine` -> `readInt` – Luigi Plinge Nov 25 '11 at 5:00

# Scala - 101 characters

This is based on the regex solution. I didn't know this was valid regex in Java, actually! (Scala's regex is based on Java's)

``````print("(\\d+)( \\1)*".r.replaceAllIn({readLine;readLine},m=>(m.matched split' 'size)+" "+m.group(1)))
``````
-

``````import List
main=interact\$unwords.(>>= \x->[show\$length x,x!!0]).group.tail.words
``````

Number of elements in the list is ignored.

-

Python 100 Characters

``````c=l=0
input()
for i in raw_input().split():
if i!=l and c:print c,l,;c=1
else:c=c+1
l=i
print c,l
``````
-

BASH

``````#!/bin/bash
count=0
found=0
for i in `echo \$data`
do
DATA[count]=\$i
((count++))
done
for ((bi=0;bi<\$len;))
do
count=\$bi
i=\$bi
for((;i<\$len;i++))
do
if [ \${DATA[bi]} -eq \${DATA[i]} ]; then
((found++))
else
break
fi
done
bi=\$i
printf "\$found \${DATA[count]} "
found=0
done
echo
``````
-
ideone.com/vQd2f – Aman ZeeK Verma Feb 18 '11 at 13:11
GENIUS!!!!!!!!! – Thomas Eding Jul 28 '11 at 20:35

# Golfscript - 40 39

``````~-1](;(:<1\@{:b={)<}{' '<' '1b:<}if}/;;
``````
-
you can leave the `[` out, the `]` will push one for you automatically – gnibbler Feb 19 '11 at 9:23
thanks :) _____ – user300 Feb 19 '11 at 10:13

## Python - 92

Here's my attempt, which is mostly what I had before I posted this question, though for some reason I used a literal space instead of a comma.

``````from itertools import*
r=raw_input
r()
for k,g in groupby(r().split()):print len(list(g)),k,
``````
-

## Python - 106 chars

Very simple conceptually, but some very expensive words weigh it down

``````from itertools import*
input()
print" ".join(`len(list(j))`+' '+i for i,j in groupby(raw_input().split()))
``````
-
 Wow. Haskell shorter than Python. That's nice. – FUZxxl Feb 18 '11 at 9:12 You don't consider the first line of input. – fR0DDY Feb 18 '11 at 9:16 @fR0DDY, ah well there goes another 8 strokes – gnibbler♦ Feb 18 '11 at 9:26

C 101 Characters

``````#define p printf("%d %d ",c,l)
main(c,i,l){gets(&i);for(c=0;~scanf("%d",&i);l=i)i!=l&&c?p,c=1:c++;p;}
``````
-

## Python - 110 chars

``````import re;R=raw_input;R()
print" ".join(`len(x[0].split())`+' '+x[1]for x in re.findall(r"((\d+)( \2)*)",R()))
``````
-
Why do you add two Python answers, where the other one is better then this one? – FUZxxl Feb 18 '11 at 19:49
@FUZxxl: 2 different methods of doing it. – JPvdMerwe Feb 18 '11 at 20:49

# Scala - 141 chars

a purely functional scala solution. i am using 2 hacks here (beginning and end markers = "a", have to cut them off at the end :()

"a" is the program parameter

the full working code is

``````package hstar.randomstuff

import tools.nsc.io.File

/**
* Developed with pleasure :)<br>
* User: HoD<br>
* Date: 28.07.11<br>
* Time: 19:37<br>
*/

object RLEEncoder {
def main(a: Array[String]) {
print(((0,"","")/:(File(a(0)).lines.toSeq(1).split(' '):+"a"))((a,c)=>if(a._2!=c)(0,c,a._3+' '+a._1+' '+a._2)else(a._1+1,c,a._3))._3.drop(4))
}
}
``````

the actual logic is

``````print(((0,"","")/:(File(a(0)).lines.toSeq(1).split(' '):+"a"))((a,c)=>if(a._2!=c)(0,c,a._3+' '+a._1+' '+a._2)else(a._1+1,c,a._3))._3.drop(4))
``````
-
 Cool! Don't forget to mention it is Scala. And prepend the title with # to get it big. – PhiLho Jul 28 '11 at 19:44 Mmm, I had to change File(a(0)) to tools.nsc.io.File(args(0)), so that's 157 chars. And it counts one less than needed. – PhiLho Jul 28 '11 at 19:53 Note: with the changes I suggest, your line works as a Scala script: scala RLE.scala input.txt; the off-by-one error is fixed with (1,c,a._3 instead of (0,c,a._3 – PhiLho Jul 28 '11 at 20:20 Add a line of equal signs (`=`) underneath the title to turn it into a title. – Daniel Sobral Jul 29 '11 at 12:45 @PhiLho If it's a one-liner script, one can use `scala -e '...'` to run it! :-) – Daniel Sobral Jul 29 '11 at 12:48

# Scala - 247 196

(+ 4 separators)

Being a beginner at Scala, I found the challenge interesting for a functional approach, but I fear I haven't took a concise approach. I guess a seasoned Scala coder will make a one liner... Particularly if I missed a useful collection method!

Anyway, here is the golfed version, even if it is out of competition:

``````readLine;val n=(readLine+" z").split(' ')
def g(v:String)={var a=1
(n:String)=>{if(n==v){a+=1;Nil}else List(a,v)}}
print(n.tail.flatMap{n=>val r=p(n);if(r!=Nil)p=g(n);r}.mkString(" "))
``````

I feel the newlines should be counted (as spaces) as here they are mandatory separators. But well, the Python scripts above doesn't count them (while they are mandatory too), so I hadn't either...

The uncompressed version, with comments for my own benefit:

``````// Read the stdin, skipping the first line, returning the second one
// cat input.txt | scala RLE.scala

// Add an arbitrary symbol that is dropped in the process... (trigger last sequence processing)
val numbers = (line + " z").split(' ')
println(numbers mkString " ")

/** Returns a closure to process the given value in the sequence to come */
def getSeq(value: String) =
{
var acc = 1
// Make a closure over value and acc
(n: String) =>
{
if (n == value)
{
acc += 1
Nil
}
else // Different value, return the cumulation so far
{
List(acc, value)
}
}
}

var process = getSeq(numbers.head) // Initial closure
/** Processes the numbers in the sequence. */
def accumulate(n: String) =
{
val p = process(n)
if (p != Nil) // We got a result
{
process = getSeq(n) // We need a fresh function over the new sequence that starts
}
p
}

println(numbers.tail.flatMap(accumulate).mkString(" "))
``````

Feels clumsy with ugly hacks (the additional symbol, using head and tail...) but at least it works...

[EDIT] I used some of the tricks shown by Daniel Sobral to shorten a bit my code. I kept my original design/algorithm to be distinctive... :-)

-
 How about: Console.in.readLine;Console.in.readLine.split(" ").groupBy(f=>f).mapValues(_.size).map(e=>e._2+" "+e._1).mkString(" ") – jrudolph Jul 28 '11 at 14:07 Hmm, no that's of course no RLE what I've posted. – jrudolph Jul 28 '11 at 14:13 Yeah, I rejected groupBy as it returns a Map, while we need to keep order and to have identical "keys" within the result. The Console.in.readLine is useful, though. – PhiLho Jul 28 '11 at 18:59