Run-Length Encoding

Question

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

Answer 1

sh - 33 29 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
  

Answer 2

Perl, 46 56 68

$_=<>;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

Answer 3

Haskell (84 82)

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

Number of elements in the list is ignored.

Answer 4

Ruby - 57

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

Ungolfed:

length = STDIN.readline
input = STDIN.readline
print input.gsub(/(\d+)( \1)*/) { |match|
    "%d %s" % [ match.split.size, $1 ]
}

Answer 5

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,

Answer 6

Scala - 136

def f(s:Seq[_]):String=if(s.isEmpty)""else{val(l,r)=s.span(s.head==);l.size+" "+s.head+" "+f(r)}
readLine
println(f(readLine split' '))

Answer 7

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)))

Answer 8

R, 33 bytes

Late answer....

cat(t(mapply(c,rle(scan()[-1]))))

Ungolfed

scan()[-1]      # read in from stdin [-1] drops first element
rle(..)         # perform run length encoding (return list with lengths and values)
mapply(c, list) # converts list to matrix
t()             # transposes this matrix so when extracted as a vector is length value ...
cat()           # writes to stdout (separated by space)

Answer 9

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()))

Answer 10

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;}

Answer 11

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

Answer 12

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()))

Answer 13

Golfscript - 40 39

~-1](;(:<1\@{:b={)<}{' '<' '1b:<}if}/;;

Answer 14

CJam, 11 bytes (non-competing)

l;l~]e`e_S*

CJam interpreter online (test case provided by this comment).

Explanation:

l;l~]e`e_S*
l           Get input line
 ;          Remove ToS
  l         Get input line
   ~        Evaluate code
    ]       Wrap the stack in an array (from [-mark)
     e`     Run-length encode
       e_   Flatten
         S  Space (' ')
          * Join

Answer 15

Retina, 23 bytes (non-competing)

Since this challenge pre-dates Retina, this answer is non-competing.

Thanks to @MartinEnder who helped me save 23 (!!) bytes and helped me understand some new features to (hopefully) produce better examples of Retina code in the future!

A1`
(\d+)( \1|)*
$#2 $1

Explanation

The first line is AntiGrep with a limit of 1 to remove the first line. Then we match any integer followed by either a space and the same integer or nothing which handles our count correctly, so we can just replace with the number of matches of group 2 ($#2), and the original integer ($1).

Try it online!

Answer 16

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))

Answer 17

Stacked, noncompeting, 34 bytes

([prompt]2*eval)behead flatrle out

Confirms strictly with the IO format. Try it here!

Or, we can use the builtin for 7 bytes: flatrle (or $flatrle).

Answer 18

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)}}
var p=g(n.head)
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
readLine // Thanks Daniel!
val line = readLine

// 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... :-)

Answer 19

JavaScript, 126 bytes

(x,j=0)=>(x=x.split` `).reduce((a,v,i)=>(v!=x[i-1]?(a[++j]=[]):a[j]).push(v)&&a,[]).reduce((a,v)=>a+v.length+" "+v[0]+" " ,"")

I'm guessing this can be reduced further, but I'm just happy it works.

First I split based on the space, then I convert the array from [1,1,1,2,2,3,3] to a series of array representing each run [[1,1,1],[2,2],[3,3]], then I reduce that again to produce the required output of "3 1 2 2 2 3".