Look & Say - Voluntary Code Golf

Show-off time.
We had a fun little team coding challenge at work: Interdisciplinary groups of three to four developers implement an algorithm in a short timebox; afterward, they share their results and expericenes.

In this session, the task was to implement the well-known look-and-say sequence, starting at 1 and with 9 iterations.
The interesting fact about this sequence is, though it seems like a mathematical problem at first glance, it’s simply just a challenge for the human eye. This smells like pattern matching.

So, as a regex evangelist, my first reflex was to dig out some weird and rarely used feature - the backreference. But fist things first, the final solution:

1
2
3
4
5
6
7

i = 0, x = /([0-9])\1*/g
l = (v, r, n = '') => {
  while((r = x.exec(v)) !== null) n += `${r[0].length}${r[1]}`
  console.log(n)
  if(i++ < 8) l(n)
}
l(1)

For the sake of readability, here’s a more elaborate version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let interactions = 0;
const regex = /([0-9])\1*/g;

const lookAndSay = (value) => {
  let result;
  let newValue = '';
  while((result = regex.exec(value)) !== null) {
    newValue += `${result[0].length}${result[1]}`;
  }
  
  console.log(newValue);
  
  interactions++;
  if(interactions < 9) {
    lookAndSay(newValue);
  }
}

lookAndSay(1);

Core piece here is of course the regular expression ([0-9])\1*, so let’s dive into these ten characters:

1. Identify single numbers
   The character class [0-9] matches each number from 0 to 9:
   /[0-9]/g.exec('3333') returns 3.

2. Capture single numbers
   The parentheses around the character class ([0-9]) captures the match, a single number:
   /([0-9])/g.exec('3333') returns 3 and also capturing group 1 containing 3.

3. Match an identical subsequent number
   To repeat the match from the previous - here first - capturing group, the backreference \1 is used:
   /([0-9])\1/g.exec('3333') returns 33 plus same capturing group 1 containing 3.

4. Repeat for each identical subsequent number
   Repetition for all subsequent identical numbers is achieved by the * quantifier:
   /([0-9])\1/g.exec('3333') returns 3333 plus same capturing group 1 containing 3.

The rest of the code is then pretty self-explanatory:

1
2
3

while((result = regex.exec(value)) !== null) {
  newValue += `${result[0].length}${result[1]}`;
}

We iterate through the regex matches of our input value, and for each match, the length of the match and capturing groups character is appended to the new result:
In our sample 3333, 43 would be appended.

Then, print the new result to the console, increment iterations, check iteration count and recurse until max iterations are reached. Done.

Things I enjoyed

Regex. I ❤️ Regex. Even though it’s a number sequence and numbers need to be counted, it’s basically just a pattern matching challenge. Con: Readability & performance depending on engine; Pro: Time & character count 😀

Code Golf. Even if it was not the goal to write compact code, I could not resist.

Javascript. Not my preferred language, but with all it’s quirks and inconsistencies, it is the perfect language for code golfing.