For the fun of it, two alternatives to shorten your solutions.

The first uses juxt and is mostly point-free, but terse:

(->> "aaaabbbcca"
     (partition-by identity)
     (map (juxt (comp str first) count))))

The second one with for, a bit chattier but also more legible:

(for [p (partition-by identity "aaaabbbcca" )]
  [(-> p first str) (count p)])

Since you were mentioning suggestions in the article, this is one of the

While not a (single) programming language, my first thought was to use uniq(1):

echo 'aaaabbbcca' | grep -o '.' | uniq -c

Way to nerd-snipe me.

Using regex:

(map (juxt first count)
     (str/split "aaaabbbcca" #"(?<=(.))(?!\1)"))

The regex is a little weird – basically, we want to split the string on any boundary where the characters before and after the boundary are different. So “aaaabbbcca” becomes four strings: [“aaaa” “bbb” “cc” “a”]. It does this by using a lookbehind for any character – the (?<=(.)) – and then a negative lookahead for not that character – (?!\1). We don’t want to include either of those characters in the match, so the characters are returned as part of the new strings.

The rest is relatively simple: juxt returns a function that takes a single argument, then returns a vector with the results of calling the two functions separately on that argument.

I don’t know that I’d write this in production code, but it is kind of fun.

Ruby one-liner, if you like long lines.

irb(main):007:0> "aaaabbbcca".split("").chunk_while {|a,b| a==b}.map {|a| [a.first, a.size]}
=> [["a", 4], ["b", 3], ["c", 2], ["a", 1]]

Never mind that it took 7 tries…..

If you don’t know of partition-by this code also works:

(defn translate [in]
  (loop [left in
         counts []]
    (if (empty? left)
       (map #(list (str (first %)) (second %)) counts)
       (recur (rest left)
              (if (= (first (last counts)) (first left))
                  (update-in counts [(dec (count counts)) 1] inc)
                  (conj counts [(first left) 1]))))))

Ugly as sin, but works. 8 minutes including writing this response, no documentation lookups, all in a readline environment. (I know about help but am not yet sure how to find useful functions other than scrolling around the cheatsheet)

Reading the Clojure solution involves following the thought process of how the author ended up there. Reading the equivalent Go solution has very little cognitive overhead.

How does Clojure programmers write code that is not just brief and elegant in the eyes of the author, but can also be read quickly by others without time consuming mental gymnastics?

Just because I haven’t seen these yet: in Ruby you can use Enumerable#tally and in Python you can use Counter (in ‘collections’)

Both of these give the equivalent result in one call, so are good for some golfing.

Not that the requirements say anything about space consumption, but most (all?) of the short solutions I’ve seen so far are not streaming friendly. Here’s a lazy version in Clojure that does not materialize intermediate sequences to count them:

(defn count-consecutive [coll]
  (letfn [(head [s]
            (lazy-seq
              (when-first [x s]
                (tail x 1 (next s)))))
          (tail [group acc s]
            (if-let [[x & xs] s]
              (lazy-seq
                (if (= group x)
                  (tail group (inc acc) xs)
                  (cons [group acc] (head s))))
              [[group acc]]))]
    (head coll)))

(count-consecutive "aaaabbbcca")

I like Ruby on this:

“aaaabbbcca”.chars.slice_when {|c,n| c != n }.map {|s| [s[0], s.size] }

I know this is a Clojure post, but out of curiosity I wrote it in Go (what I’ve been working in lately) just to see if I could solve it quickly. Took about 10 minutes, subtract 3-4 for fighting with runes:

package main

import "fmt"

type result struct {
	letter string
	count  int
}

func main() {
	const input = "aaaabbbcca"

	var ret []result
	currentLetter := string(input[0])
	countCurrentLetter := 1

	for _, elem := range input[1:] {
		elemAsString := string(elem)
		if currentLetter == elemAsString {
			countCurrentLetter++
		} else {
			ret = append(ret, result{currentLetter, countCurrentLetter})
			currentLetter = elemAsString
			countCurrentLetter = 1
		}
	}

	ret = append(ret, result{currentLetter, countCurrentLetter})

	fmt.Printf("%+v", ret)
}

It’s not particularly elegant, but it works.

Since everyone is posting their solutions, here’s mine in Erlang:

L = "aaaabbbcca",
lists:reverse(lists:foldl(
    fun
        (Elt, [ {[Elt], N} | R ]) -> [ {[Elt], N + 1} | R];
        (Elt, Acc) -> [{[Elt], 1} | Acc]
    end,
    [],
    L
)).
> [{"a",4},{"b",3},{"c",2},{"a",1}]

Racket:

(for/fold ([p #f]
           [cnt 0]
           [counts null]
           #:result (cdr (reverse (cons `(,p ,cnt) counts))))
          ([c (in-string "aaaabbbcca")])
  (if (equal? p c)
      (values c (add1 cnt) counts)
      (values c 1 (cons `(,p ,cnt) counts))))

I started using this question in job interviews a year or two ago and now this tweet and post has to go viral. Thanks a lot jerk!

I like this python one-liner solution (with some help from the standard library):

>>> [(k, len(list(g))) for k, g in itertools.groupby("aaaabbbcca")]
[('a', 4), ('b', 3), ('c', 2), ('a', 1)]

I saw that tweet and really enjoyed it. I spent a few minutes while doing other work kicking around the solution in F# in my head. It’s a good example of a question tough enough to exercise a few brain cells but not one of those “I’m the interviewer see how smart I am” things. Of course the best answer, which a few replies gave, was simply to print out the required result. Don’t write code you don’t have to, and since you were given the answer and you can write code to get that using only one statement, do it.

But of course that’s too cheeky. For the record, in F# it looks to me like:

“aaaabbbcca” |> Seq.countBy id;;

I don’t know how to make it any simpler than that.

Is it cheating to use the stdlib function that already does the work?

(frequencies "aaaabbbcca")
;; => {\a 5, \b 3, \c 2}

Or if you wanted to respect the types in the OP:

(->> "aaaabbbcca"
           frequencies
           (map (fn [[k v]] [(str k) v]))
           (into []))
;; => [["a" 5] ["b" 3] ["c" 2]]

Here’s my very elegant and short take in Sed:

h
: next_char
s/^/|\
/
t inc_start
: inc_start
s/^\([0-9]*\)0|/\11/; t inc_end
s/^\([0-9]*\)1|/\12/; t inc_end
s/^\([0-9]*\)2|/\13/; t inc_end
s/^\([0-9]*\)3|/\14/; t inc_end
s/^\([0-9]*\)4|/\15/; t inc_end
s/^\([0-9]*\)5|/\16/; t inc_end
s/^\([0-9]*\)6|/\17/; t inc_end
s/^\([0-9]*\)7|/\18/; t inc_end
s/^\([0-9]*\)8|/\19/; t inc_end
: inc_loop
s/^\([0-9]*\)9|/\1|0/
t inc_loop
s/^|/1/; t inc_end
b inc_start
: inc_end
s/\n\(.\)\1/|\
\1/
t inc_start
P
s/^[^[:space:]]*.//
s/\(.\).*/\1/p
g
s/\(.\)\1*//
/^$/q
h
t next_char

Result:

sh$ echo aaaabbbcca | sed -f my-take.sed
4
a
3
b
2
c
1
a

So, two things:

1. I don’t know that Run Length Encoding is the best filter for candidates, it feels a little bit on the puzzly side.
2. Here’s my quick and dirty solution using janet’s seq. It’s imperative, and not pretty and functional (janet can do both), but I was able to build it quickly, and it illustrates the power of seq (and loop), and I think it’d be nice and clear to explain for non-functional programmers:

(def input "aaaabbbcca")
(var old (string/from-bytes (input 0)))
(var cnt 0)
(pp (array/push (seq [c :in (map string/from-bytes input)
                      :after (++ cnt)
                      :when (not= old c)
                      :after (do (set cnt 0) (set old c))] 
                  [old cnt])
                [old cnt]))

# => @[("a" 4) ("b" 3) ("c" 2) ("a" 1)]

Since no one contributed a Rust example:

fn run_length_encode(ins: &str) -> Vec<(char, usize)> {
    let mut out = vec![];
    let mut i = ins.chars();
    if let Some(mut c) = i.next() {
        let mut count = 1;
        for new_c in i {
            if new_c == c {
                count += 1;
            } else {
                out.push((c, count));
                count = 1;
                c = new_c;
            }
        }
        out.push((c, count));
    }
    out
}

and in Haskell we can use group and mapMaybe for the heavy lifting:

import Data.List (group)
import Data.Maybe (mapMaybe)

runLengthEncode :: Eq a => [a] -> [(a, Int)]
runLengthEncode = mapMaybe f . group
  where 
    f [] = Nothing 
    f (x:xs) = Just (x, 1 + length xs) 

My simple procedural answer in Julia:

function rle(itr)
	acc = Tuple{eltype(itr), Int}[]
	x = iterate(itr)
	isnothing(x) && return acc # iterable is empty
	last, state = x
	n = 1
	for v in Iterators.rest(itr, state)
		if last == v
			n += 1
		else
			push!(acc, (last, n))
			last = v
			n = 1
		end
	end
	push!(acc, (last, n))
	return acc
end

Docstring:

rle(itr)

Give a run-length-encoding of iterable itr.

Bonus features:

• works on arbitrary iterables
• typed

Examples

julia> rle("aaabbca")
Tuple{Char, Int64}[('a', 3), ('b', 2), ('c', 1), ('a', 1)]

julia> rle(rand(Bool, 5))
Tuple{Bool, Int64}[(true, 1), (false, 1), (true, 3)]

julia> let io = IOBuffer("foo\nbar\n")
	       rle(eachline(io))
       end
Tuple{String, Int64}[("foo", 1), ("bar", 1)]

My initial solution, written in 11 minutes with the help of online documentation:

(vec (map
       (fn [run] (conj '() (count run) (first run)))
       (partition-by identity input)))

The hard part was discovering the partition-by function. Knowing about Ruby’s Enumerable#partition method helped a lot with that.

After reading some other answers, I decided I should not accept my hacky conj, and should look up the actual way to construct a list. My final solution:

(vec (map
       (fn [run] (list (first run) (count run)))
       (partition-by identity input)))

I was testing with ClojureScript, so first was enough to get a one-character string like "a". With Clojure on JVM, it is indeed necessary to use (comp str first) instead, as the post does.

I used vec and list because the original question specified the output using that syntax: [("a", 4), ("b", 3), ("c", 2), ("a", 1)]. When I look at the question more, though, I think that data structure was meant to be Python, so my vec was unnecessary.

Haskell.. Includes the newline, but that’s an easy fix..

main = interact soln

soln = show . reverse . go []

go counts [] = counts
go counts (x:xs) = go (inc x counts) xs

inc c ((x,ct):xs) | c == x = (x,ct+1):xs
inc c xs = (c, 1):xs

interesting interview-question, my problem with it is that the required effors totally depends on whether your language has this builtin or not.

for example, look at the python solution:

 [(a,len(list(b))) for a,b in itertools.groupby('aaabbbbbbcca')]

itertools.groupby does all the work, you just format the result to the required specification.

the article used clojure where partition-by seems to do the same.

if your language does not provide this function, you will have to reimplement it, or do something else. my point is, the effort is a lot larger.

to take the argument to the extreme: imagine the interview-question is : “how to reverse an array”, and some candidates use languages where “array.reverse” exists, and some use languages where it does not exist.