19
\$\begingroup\$

This question already has an answer here:

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
\$\endgroup\$

marked as duplicate by mbomb007 code-golf Aug 8 at 14:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Similar to golf.shinh.org/p.rb?Look+and+say and stackoverflow.com/questions/3908513/code-golf-morris-sequence \$\endgroup\$ – Nabb Feb 18 '11 at 10:08
  • \$\begingroup\$ 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. \$\endgroup\$ – PhiLho Jul 28 '11 at 19:55

19 Answers 19

24
\$\begingroup\$

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
    
\$\endgroup\$
  • \$\begingroup\$ WTF? How is that possible? \$\endgroup\$ – FUZxxl Feb 18 '11 at 20:16
  • \$\begingroup\$ added explanations :-) \$\endgroup\$ – Arnaud Le Blanc Feb 18 '11 at 20:26
  • \$\begingroup\$ Very nice! (more chars) \$\endgroup\$ – J B Feb 18 '11 at 20:50
  • 1
    \$\begingroup\$ You might be able to replace tail -n1| with a well-placed read; \$\endgroup\$ – J B Feb 18 '11 at 20:52
  • 2
    \$\begingroup\$ And the tr can be replaced with an xargs. read;echo`xargs -n1|uniq -c` for 28 characters. \$\endgroup\$ – J B Feb 18 '11 at 21:03
5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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 ]
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Fails on integers more than 2 digits wide. \$\endgroup\$ – J B Feb 18 '11 at 16:10
  • \$\begingroup\$ oops ! thanks, fixed now \$\endgroup\$ – Arnaud Le Blanc Feb 18 '11 at 16:17
3
\$\begingroup\$

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,
\$\endgroup\$
3
\$\begingroup\$

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' '))
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – PhiLho Jul 28 '11 at 19:42
  • \$\begingroup\$ @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. \$\endgroup\$ – Daniel C. Sobral Jul 28 '11 at 20:58
  • \$\begingroup\$ 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! \$\endgroup\$ – PhiLho Jul 29 '11 at 5:40
  • \$\begingroup\$ You can get this down to 126 by changing s.isEmpty -> s==Nil; s.head -> s(0); println -> print \$\endgroup\$ – Luigi Plinge Nov 25 '11 at 4:35
  • \$\begingroup\$ also first readLine -> readInt \$\endgroup\$ – Luigi Plinge Nov 25 '11 at 5:00
3
\$\begingroup\$

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)))
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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()))
\$\endgroup\$
  • \$\begingroup\$ Wow. Haskell shorter than Python. That's nice. \$\endgroup\$ – FUZxxl Feb 18 '11 at 9:12
  • \$\begingroup\$ You don't consider the first line of input. \$\endgroup\$ – fR0DDY Feb 18 '11 at 9:16
  • \$\begingroup\$ @fR0DDY, ah well there goes another 8 strokes \$\endgroup\$ – gnibbler Feb 18 '11 at 9:26
2
\$\begingroup\$

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;}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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()))
\$\endgroup\$
  • \$\begingroup\$ Why do you add two Python answers, where the other one is better then this one? \$\endgroup\$ – FUZxxl Feb 18 '11 at 19:49
  • 3
    \$\begingroup\$ @FUZxxl: 2 different methods of doing it. \$\endgroup\$ – JPvdMerwe Feb 18 '11 at 20:49
2
\$\begingroup\$

Golfscript - 40 39

~-1](;(:<1\@{:b={)<}{' '<' '1b:<}if}/;;
\$\endgroup\$
  • 1
    \$\begingroup\$ you can leave the [ out, the ] will push one for you automatically \$\endgroup\$ – gnibbler Feb 19 '11 at 9:23
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think you can remove the third and fourth lines if you change the fifth to (\d+)( \1)*. \$\endgroup\$ – ETHproductions Nov 2 '16 at 16:57
  • \$\begingroup\$ @ETHproductions and the last two... How did I not see that :| Thanks! \$\endgroup\$ – Dom Hastings Nov 2 '16 at 17:04
  • \$\begingroup\$ ...except now it fails on inputs containing 111, 1111, etc. :| \$\endgroup\$ – ETHproductions Nov 2 '16 at 17:08
  • \$\begingroup\$ @ETHproductions Hmmm, but only if they\re the last numbers?! Sad. Ok, I'll delete and play. Thanks! \$\endgroup\$ – Dom Hastings Nov 2 '16 at 18:24
  • \$\begingroup\$ @ETHproductions Can't figure that out right now, so I've rolled back to your revision and I'll probably take a look after I've eaten. That'll probably help! :) \$\endgroup\$ – Dom Hastings Nov 2 '16 at 18:33
1
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Cool! Don't forget to mention it is Scala. And prepend the title with # to get it big. \$\endgroup\$ – PhiLho Jul 28 '11 at 19:44
  • \$\begingroup\$ 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. \$\endgroup\$ – PhiLho Jul 28 '11 at 19:53
  • \$\begingroup\$ 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 \$\endgroup\$ – PhiLho Jul 28 '11 at 20:20
  • \$\begingroup\$ Add a line of equal signs (=) underneath the title to turn it into a title. \$\endgroup\$ – Daniel C. Sobral Jul 29 '11 at 12:45
  • \$\begingroup\$ @PhiLho If it's a one-liner script, one can use scala -e '...' to run it! :-) \$\endgroup\$ – Daniel C. Sobral Jul 29 '11 at 12:48
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How about: Console.in.readLine;Console.in.readLine.split(" ").groupBy(f=>f).mapValues(_.size).map(e=>e._2+" "+e._1).mkString(" ") \$\endgroup\$ – jrudolph Jul 28 '11 at 14:07
  • \$\begingroup\$ Hmm, no that's of course no RLE what I've posted. \$\endgroup\$ – jrudolph Jul 28 '11 at 14:13
  • \$\begingroup\$ 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. \$\endgroup\$ – PhiLho Jul 28 '11 at 18:59
0
\$\begingroup\$

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".

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Is this noncompeting? \$\endgroup\$ – Zacharý Dec 23 '16 at 23:30
  • \$\begingroup\$ @ZacharyT Ah, yes, of course. \$\endgroup\$ – Conor O'Brien Dec 23 '16 at 23:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.