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

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 4

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 5

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 6

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 7

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 8

BASH

#!/bin/bash
read len
read data
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

Answer 9

Golfscript - 40 39

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

Answer 10

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 11

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 12

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 13

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 14

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 15

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