Run-length encoding: Difference between revisions

{{trans|Python}}

V count = 1

V prev = Char("\0")

V value = encode(‘aaaaahhhhhhmmmmmmmuiiiiiiiaaaaaa’)

print(‘Encoded value is ’value.map(v -> String(v[1])‘’v[0]))

{{out}}

Output is in hexadecimal but is otherwise correct.

.stack 1024 ; load SP with 0400h

.data ; no data segment needed

OutputRam byte 256 dup (0)

{{out}}

=={{header|Action!}}==

CHAR c

BYTE len

PrintE("decoded:")

PrintE(decoded)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Run-length_encoding.png Screenshot from Atari 8-bit computer]

=={{header|Ada}}==

with Ada.Strings.Fixed; use Ada.Strings.Fixed;

procedure Test_Run_Length_Encoding is

Put_Line (Encode ("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"));

Put_Line (Decode ("12W1B12W3B24W1B14W"));

Sample output:

<pre>

Note: The following uses iterators, eliminating the need of declaring arbitrarily large CHAR arrays for caching.

STRING output := "12W1B12W3B24W1B14W";

print(c)

# OD # );

Output:

<pre>

=={{header|APL}}==

[1] count←∣2-/((1,(2≠/rll),1)×⍳1+⍴rll)~0

[2] ret←(⍕count,¨(1,2≠/rll)/rll)~' '

∇

Sample Output:

<pre>

=={{header|AppleScript}}==

-- encode :: String -> String

end repeat

v

{{Out}}

<pre>W12B1W12B3W24B1W14

=={{header|Arturo}}==

join map chunk split s => [&] 'x ->

(to :string size x) ++ first x

print ["decoded:" decoded]

{{out}}

=={{header|AutoHotkey}}==

MsgBox % rle_decode(key)

}

Return output

=={{header|AWK}}==

'''Encoding'''

FS=""

}

}

printf("%d%c", j, cp)

'''Decoding'''

RS="[0-9]+[^0-9]"

final = "";

END {

print final

=={{header|BaCon}}==

LOCAL result$, c$ = LEFT$(txt$, 1)

encoded$ = Rle_Encode$(rle_data$)

PRINT "Encoded: ", encoded$

{{out}}

<pre>RLEData: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

{{trans|PowerBASIC}}

DECLARE FUNCTION RLEncode$ (i AS STRING)

outP = outP + tmp2

RLEncode$ = outP

Sample output (last one shows errors from using numbers in input string):

=={{header|BASIC256}}==

function FBString(lon, cad$)

# Definimos la función String en BASIC256

print decoded$

end

{{out}}

La salida es similar a la de [[#BASIC|BASIC]], mostrada arriba.

=={{header|BBC BASIC}}==

The run counts are indicated by means of character codes in the range 131 to 255.

PRINT "Input: " input$

rle$ = FNencodeRLE(input$)

ENDIF

ENDWHILE

=={{header|Befunge}}==

Pipe the output of the program-it's more reliable.

{{works with|CCBI|2.1}}

<temp var for when char changes

format:

the validity of this program is NOT affected p-

>^

=={{header|Bracmat}}==

= character otherCharacter acc begin end

. :?acc

)

& run-length$WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

<pre> 12W1B12W3B24W1B14W</pre>

=={{header|Burlesque}}==

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

=[{^^[~\/L[Sh}\m

=={{header|C}}==

Encoder that can deal with byte streams. Can encode/decode any byte values and any length with reasonable efficiency. Also showing OO and polymophism with structs.

#include <stdlib.h>

return 0;

See [[Run-length encoding/C]]

=== Linq ===

<!--Martin Freedman 22/02/2018-->

using System.Linq;

using static System.Console;

}

}

Output:

<pre>raw = WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Many solutions do not follow the suggested output guideline in the challenge (not helped by its wording), instead producing a list of tuples or equivalent. This is much simpler (especially for decode) and the following provides an equivalent of those (IMHO deficient) solutions, to make comparisons easier.

using System.Linq;

using static System.Console;

string.Join(",", list.Select(t => $"[{t.i},{t.c}]"));

}

Output:

<pre>raw = WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Stringbuilder version. Might be more performant but mixes output formatting with encoding/decoding logic.

<!--Martin Freedman 22/02/2018-->

using System.Linq;

using static System.Console;

}

}

Output:

<pre>raw = WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

This example only works if there are no digits in the string to be encoded and then decoded.

{

string input = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

}

return sb.ToString();

=== RegEx ===

Somewhat shorter, using Regex.Replace with MatchEvaluator (using C#2 syntax only):

using System.Text.RegularExpressions;

});

}

=={{header|C++}}==

#include <array>

#include <iterator>

std::cout.setf(std::cout.boolalpha);

std::cout << "Round trip works: " << (test_string == decoded_str) << '\n';

{{libheader|boost}}

#include <string>

#include <sstream>

}

return oss.str( ) ;

=={{header|Ceylon}}==

"Takes a string such as aaaabbbbbbcc and returns 4a6b2c"

assert (compress("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW") == "12W1B12W3B24W1B14W");

assert (decompress("24a") == "aaaaaaaaaaaaaaaaaaaaaaaa");

=={{header|Clojure}}==

(->> (partition-by identity s) (mapcat (juxt count first)) (apply str)))

(->> (re-seq #"(\d+)([A-Z])" s)

(mapcat (fn [[_ n ch]] (repeat (Integer/parseInt n) ch)))

=={{header|COBOL}}==

{{works with|GNU Cobol|2.0}}

IDENTIFICATION DIVISION.

PROGRAM-ID. run-length-encoding.

END-PERFORM

.

{{out}}

=={{header|CoffeeScript}}==

str.replace /(.)\1*/g, (w) ->

w[0] + w.length

console.log s = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

console.log encode s

<pre>

The following version encodes the number of ocurrences as an unicode character. You can change the way it looks by rotating the offset.

str.replace /(.)\1*/g, (w) ->

w[0] + String.fromCharCode(offset+w.length)

str.split('').map((w,i) ->

if not (i%2) then w else new Array(+w.charCodeAt(0)-offset).join(str[i-1])

<pre>

=={{header|Common Lisp}}==

(loop for x in (rest sequence)

with temp = (subseq sequence 0 1)

(run-length-encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

=={{header|D}}==

===Short Functional Version===

alias encode = group;

"WWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

assert(s.encode.decode.equal(s));

===Basic Imperative Version===

// Similar to the 'look and say' function.

writeln("Encoded: ", encoded);

assert(txt == encoded.decode);

{{out}}

<pre>Input: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

D's native string is utf-encoded. This version works for utf string, and uses a [[Variable-length_quantity|Variable-length Quantity]] [[Variable-length_quantity#D|module]].

import vlq;

auto sEncoded = RLE.init.encode(s).encoded ;

assert(s == RLE(sEncoded).decode(), "Not work");

output from "display.txt":

The code looks more complex than the third Python version because this also handles digits by escaping them with #.

std.algorithm;

"11#222##333";

assert(s == reDecode(reEncode(s)));

=={{header|Déjà Vu}}==

if not dup:

drop

rle "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

!. dup

{{out}}

<pre>[ & 12 "W" & 1 "B" & 12 "W" & 3 "B" & 24 "W" & 1 "B" & 14 "W" ]

=={{header|Delphi}}==

{{libheader| System.SysUtils}}

program RunLengthTest;

writeln(Data.Decode);

Readln;

{{out}}

<pre>

=={{header|E}}==

var seen := null

var count := 0

}

return result

# value: [[12, 'W'], [1, 'B'], [12, 'W'], [3, 'B'], [24, 'W'], [1, 'B'], [14, 'W']]

? unrle(rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"))

=={{header|Elena}}==

ELENA 4.x :

import system'routines;

import extensions;

s := compressor.decompress(s);

console.printLine(s)

{{out}}

<pre>

=={{header|Elixir}}==

def encode(str) when is_bitstring(str) do

to_char_list(str) |> encode |> to_string

|> Run_length.encode |> IO.inspect

|> Run_length.decode |> IO.inspect

{{out}}

=={{header|Emacs Lisp}}==

(let (output)

(with-temp-buffer

(count (skip-chars-forward (string char))))

(push (format "%d%c" count char) output))))

{{libheader|seq.el}}

(defun run-length-encode (str)

(apply #'concat (mapcar (lambda (items)

(format "%d%c" (length items) (car items)))

=={{header|Erlang}}==

A single-threaded/process version with a simple set of unit test.

-export([encode/1,decode/1]).

?_assert(decode(Expected) =:= PreEncoded),

?_assert(decode(encode(PreEncoded)) =:= PreEncoded)

A version that works on character lists:

-module(rle).

decode([{Count, Char}|T], Acc) ->

decode(T, [[Char || _ <- lists:seq(1, Count)]|Acc]).

=={{header|Euphoria}}==

function encode(sequence s)

pretty_print(1,s,{3})

puts(1,'\n')

Output:

=={{header|F Sharp|F#}}==

open System

open System.Text.RegularExpressions

|> List.map (fun m -> Int32.Parse(m.Groups.[1].Value), m.Groups.[2].Value)

|> List.fold (fun acc (len, s) -> acc + String.replicate len s) ""

=={{header|Factor}}==

sequences.extras sequences.repeating splitting.extras

splitting.monotonic strings ;

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

"12W1B12W3B24W1B14W"

{{out}}

<pre>

=={{header|FALSE}}==

=={{header|Fan}}==

** Generates a run-length encoding for a string

**

override Str toStr() { return "${count}${char.toChar}" }

=={{header|Forth}}==

: n>a (.) tuck a @ swap move a +! ;

: >a a @ c! 1 a +! ;

i c@ digit? if 10 * i c@ [char] 0 - + else

a @ over i c@ fill a +! 0 then

Example:

here 1000 + encode here 2000 + decode cr 3 spaces type

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

implicit none

end do

end subroutine

Output:

=={{header|FreeBASIC}}==

Dim As String initial, encoded, decoded

Print decoded

End

{{out}}

La salida es similar a la de [[#BASIC|BASIC]], mostrada arriba.

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=b30707043cb64effba91a2edc4d4be94 Click this link to run this code]'''

Dim sString As String = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

Dim siCount As Short = 1

Print sString & gb.NewLine & sHold.Join(", ")

Output:

<pre>

=={{header|Go}}==

Decoder kind of necessary to demonstrate task requirement that I can recreate the input.

import "fmt"

}

return string(d)

Output:

<pre>

=={{header|Groovy}}==

def encoded = new StringBuilder()

(text =~ /(([A-Z])\2*)/).each { matcher ->

}

decoded.toString()

Test code

def rleEncoded = rleEncode(text)

assert rleEncoded == '12W1B12W3B24W1B14W'

println "Original Text: $text"

Output:

<pre>Original Text: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

=={{header|Haskell}}==

===In terms of group===

-- Datatypes

encoded = rlencode input

decoded = rldecode encoded

{{Out}}

<pre>Encoded: [(12,'W'),(1,'B'),(12,'W'),(3,'B'),(24,'W'),(1,'B'),(14,'W')]

Or:

import Data.List (group, groupBy)

decode = runLengthDecode encode

mapM_ putStrLn [text, encode, decode]

{{out}}

<pre>WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

===In terms of span===

import Data.List (span)

src = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

encoded = encode src

{{Out}}

<pre>W12B1W12B3W24B1W14

===As a fold===

runLengths :: String -> [(Int, Char)]

showLengths :: [(Int, Char)] -> String

showLengths [] = []

{{Out}}

<pre>12W1B12W3B24W1B14W

=={{header|Icon}} and {{header|Unicon}}==

s := "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

procedure Repl(n, c)

return repl(c,n)

Sample output:

=={{header|J}}==

'''Solution:'''

'''Example:'''

12W1B12W3B24W1B14W

rld '12W1B12W3B24W1B14W'

Note that this implementation fails for the empty case. Here's a version that fixes that:

Other approaches include using <nowiki>rle ::(''"_)</nowiki> or <nowiki>rle^:(*@#)</nowiki> or equivalent variations on the original sentence.

A numeric approach, based on a discussion in the J forums (primarily [http://jsoftware.com/pipermail/programming/2015-June/042139.html Pascal Jasmin] and [http://jsoftware.com/pipermail/programming/2015-June/042141.html Marshall Lochbaum]):

Task example:

12 87

1 66

14 87

u: frle torle a.i.'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW'

Note that this approach also fails on the empty case.

=={{header|Java}}==

import java.util.regex.Pattern;

public class RunLengthEncoding {

System.out.println(decode("1W1B1W1B1W1B1W1B1W1B1W1B1W1B"));

}

Tests:

{{libheader|JUnit}}

import org.junit.Test;

}

=={{header|JavaScript}}==

===ES5===

Here's an encoding method that walks the input string character by character

var encoding = [];

var prev, count, i;

encoding.push([count, prev]);

return encoding;

Here's an encoding method that uses a regular expression to grab the character runs ({{works with|JavaScript|1.6}} for the <code>forEach</code> method)

var encoding = [];

input.match(/(.)\1*/g).forEach(function(substr){ encoding.push([substr.length, substr[0]]) });

return encoding;

And to decode (see [[Repeating a string#JavaScript|Repeating a string]])

var output = "";

encoded.forEach(function(pair){ output += new Array(1+pair[0]).join(pair[1]) })

return output;

===ES6===

By defining a generic ''group'' function:

'use strict';

// MAIN ---

return main();

{{Out}}

<pre>From: "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

A <code>.reduce()</code> based one-liner

const rlEncode = (s: string) => s.match(/(.)\1*/g).reduce((result,char) => result+char.length+char[0],"")

const rlValidate = (s: string) => /^(\d+\D)+$/.test(s)

const rlDecode = (s: string) => rlValidate(s) ? s.match(/(\d[a-z\s])\1*/ig).reduce((res,p) => res+p[p.length-1].repeat(parseInt(p)),"") : Error("Invalid rl")

=={{header|jq}}==

'''Utility function:'''

reduce .[] as $item

( [];

else . + [[$item, 1]]

end

'''Run-length encoding and decoding''':

explode | runs | reduce .[] as $x (""; . + "\($x[1])\([$x[0]]|implode)");

($pair[0:-1] | tonumber) as $n

| $pair[-1:] as $letter

'''Example''':

{{out}}

=={{header|Julia}}==

{{works with|Julia|0.6}}

encode(str::String) = collect((length(g), first(g)) for g in groupby(first, str))

decoded = decode(encoded)

println("Original: $original\n -> encoded: $encoded\n -> decoded: $decoded")

{{out}}

=={{header|K}}==

{{trans|J}}

'''Example:'''

"12W1B12W3B24W1B14W"

rld "12W1B12W3B24W1B14W"

=={{header|Kotlin}}==

Tail recursive implementation of Run Length Encoding

if (text.isEmpty()){

return prev

assert(runLengthEncoding("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

== "12W1B12W3B24W1B14W")

=={{header|Lasso}}==

local(orig = #str->values->asCopy,newi=array, newc=array, compiled=string)

while(#orig->size) => {

rlde('12W1B12W3B24W1B14W')

{{out}}

=={{header|Liberty BASIC}}==

'In$ ="aaaaaaaaaaaaaaaaaccbbbbbbbbbbbbbbba" ' testing...

next i

Decoded$ =r$

=={{header|LiveCode}}==

local charCount

put 1 into charCount

end repeat

return repStr

=={{header|Logo}}==

if empty? :str [output (word :out :count :last)]

if equal? first :str :last [output (encode bf :str :out :count+1 :last)]

make "foo "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

make "rle encode :foo

=={{header|Lua}}==

astable = Ct(C(1)^0)

end

return ret

=={{header|M2000 Interpreter}}==

Module RLE_example {

inp$="WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

}

RLE_example

{{out}}

The function

takes as input an arbitrary string of characters and returns a list of {c, n} pairs, where c is the character and n is the number of repeats. The function

recreates the string.

Example: For the string

here is the run-length encoding:

Check that the input string is recreated:

=={{header|Maxima}}==

[n: slength(a), b: "", c: charat(a, 1), k: 1],

for i from 2 thru n do

rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW");

=={{header|MMIX}}==

GREG @

Buf OCTA 0,0,0,0 integer print buffer

2H SET $4,#a print NL

GO $127,PChar

Example run encode --> decode:

<pre>~/MIX/MMIX/Rosetta> mmix rle

=={{header|Nim}}==

{{trans|Python}}

proc compress(input: string): string =

let compressed = Text.compress()

echo "Compressed: ", compressed

{{out}}

=={{header|Objeck}}==

class RunLengthEncoding {

return output;

}

<pre>encoding: 12W1B12W3B24W1B14W

=={{header|OCaml}}==

let len = String.length str in

let rec aux i acc =

let decode lst =

let l = List.map (fun (c,n) -> String.make n c) lst in

let e = encode "aaaaahhhhhhmmmmmmmuiiiiiiiaaaaaa" in

List.iter (fun (c,n) ->

) e;

print_endline (decode [('a', 5); ('h', 6); ('m', 7); ('u', 1); ('i', 7); ('a', 6)]);

;Using regular expressions

open Str

let () =

print_endline (encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW");

=={{header|Oforth}}==

StringBuffer new

s group apply(#[ tuck size asString << swap first <<c ]) ;

loop: i [ c <<c ] 0

]

{{out}}

=={{header|Ol}}==

(define (RLE str)

(define iter (string->list str))

(apply string-append (map (lambda (p)

(make-string (car p) (cdr p))) rle)))

Test:

(define str "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

(print str)

rle)

(print (decode rle))

{{Out}}

<pre>

</pre>

=={{header|Oz}}==

fun {RLEncode Xs}

for G in {Group Xs} collect:C do

{System.showInfo Data}

{Show Enc}

=={{header|PARI/GP}}==

if(s=="", return(s));

my(v=Vec(s),cur=v[1],ct=1,out="");

};

rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

Output:

<pre>%1 = "12W1B12W3B24W1B14W"

=={{header|Pascal}}==

procedure encode(s: string; var counts: array of integer; var letters: string);

decode(s, counts, letters);

writeln(s);

Output:

<pre>:> ./RunLengthEncoding

Simple version using ASCII numerals as length markers, like the example in the task description (won't work correctly on input strings that already contain digits):

shift =~ s/(.)\1*/length($&).$1/grse;

}

sub decode {

shift =~ s/(\d+)(.)/$2 x $1/grse;

Modified version that can take arbitrary byte strings as input (produces encoded byte strings that are compatible with the [[#C|C solution]]):

shift =~ s/(.)\1{0,254}/pack("C", length($&)).$1/grse;

}

sub decode {

shift =~ s/(.)(.)/$2 x unpack("C", $1)/grse;

Further modified version that supports compact representation of longer non-repeating substrings, just like the [[#C|C solution]] (so should be fully compatible with that solution for both encoding and decoding):

my $str = shift;

my $ret = "";

}

return $ret;

Demonstration of the third version:

dd my $str = "XXXXXABCDEFGHIoooooooooooooooooooooooooAAAAAA";

dd my $enc = encode($str);

{{out}}

=={{header|Phix}}==

Based on [[Run-length_encoding#Euphoria|Euphoria]], but uses a few string in place of sequence.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">encode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">s</span>