Recursively generating the look-and-say sequence

I have a pattern where every number is counted by the number of repetitions. A new resulting number is formed by adding that repetition to the front of that value. The resulting pattern would look like this.

1. 1
2. 11
3. 21
4. 1211
5. 111221

so:

indexnumbercomment
0      1       one + 1 ->11
1      11       two + 1 -> 21
2      21       one + 2 + one + 1 -> 1211

etc...

I was given a number 4, and I needed to produce the resulting number 1211.

My approach was to use a recursive function that used every subsequent iteration starting from 0 to evaluate every resulting value until I reached my target iteration.

Runtime Complexity: I decremented the number recursively O(N) as I carried the resulting evaluation result.

At every recursive step, I produced every result by walking the resulting values, counting the repetitions as I went along. I stored every key-value pairs along an Index represented by a synecdochic key in a line of contiguous repetition. I tallied the repetitions until I had a key-value pair at the intersection of every index.

I then assembled the value by swapping the key values pairs at every index into a new object array which I used to repeat the process. O(C)

I then used reduce to format the results and repeat the process O(F)

O(N *C +F) = O(N^2)

space complexity is O(N^2) since the amount of space needed to process doubles on every resulting iteration.

Are my Time and Space analysis correct, did I miss a much simpler approach where I might have been able to take advantage of Fibonacci, XOR or some other simpler mathematical approach? and could this have been done better programmatically by using some other type of data structure, or could it have been written in some other concise way?

function countStay(num) {
if (num === 1) {
return 1
}

return drill(num, )
}

function drill(exitCount, result) {
const map = {
0: {}
},
arr = [];
let count = 0,
index = 0;
result = result.reduce((acc, a, i, aa) => {
if (aa[i - 1] && aa[i] && a !== aa[i - 1]) {
index += 1
count = 0
map[index] = {
[a]: count
}
}
if (((map || {})[index] || {})[a] && count !== 0) {
map[index][a] = count += 1
arr[index] = [count, a]
}
if (!((map || {})[index] || {})[a] && count === 0) {
count += 1
map[index] = {
[a]: count
}
arr[index] = [count, a]
}
return acc = {
arr
}
}, {})

result = join(result)
exitCount--
if (exitCount <= 1) {
return result.join('')
}
return drill(exitCount, result)
}

function join(result) {
return result = result.arr.reduce((acum, a) => acum.concat(a), [])
}
console.log(countStay(4))

• I haven't looked enough at your code to post an answer but take a gander at PCG's answers to generate this sequence. Note: Look at just the algos because the code is an unreadable mess by design Jul 26 '18 at 23:50
• In your complexity analysis, what do you mean by N, C, and F? Jul 27 '18 at 21:02
• @200_success thanks for correcting the question. They are just placeholders for N. I use different letters to keep track of the time complexity at every depth of iteration. I move them out in the end.
– Rick
Jul 28 '18 at 18:50

It seems like you tried too hard to avoid all loops by limiting yourself to .reduce() and recursion. While JavaScript supports functional programming to some extent, sticking to pure FP everywhere will likely lead to clunky code. A better strategy would be to define some functions that look pure from the outside, but might be implemented in an imperative style. (Your code isn't pure FP anyway: the index += 1 statements perform mutation.)

I don't think that countStay and drill are well designed functions. It's not clear to me what each of them is supposed to accomplish. countStay seems to be a trivial wrapper around drill. At first glance, all I can see is that drill contains a lot of code, and that it calls itself recursively. In particular, it's hard to read because the variable names are cryptic. map is obviously a map, and arr is obviously an array, but what are their purpose?

Suggested solution

I would define three functions, each of which has a clear purpose and is easily testable. Instead of recursion, I've used iterateN, which is inspired by Haskell. Then, it's easy to compose them to obtain the result. This solution is simpler and more readable than yours.

/**
* Split an array of items into runs of identical values;
* yield [item, runLength] for each run.
*
* runLengthEncode('bookkeeper'.split('')) =>
* ['b', 1], ['o', 2], ['k', 2], ['e', 2], ['p', 1], ['e', 1], ['r', 1]
*/
const runLengthEncode = function*(items) {
if (items.length) {
let groupStart = 0, groupItem = items;
for (let i = 1; i < items.length; i++) {
if (items[i] != groupItem) {
yield [groupItem, i - groupStart];
groupStart = i;
groupItem = items[i];
}
}
yield [groupItem, items.length - groupStart];
}
};

/**
* Given a number (as an integer or string), produce its successor
* in the look-and-say sequence (as a string).
*
* nextLookAndSay('1211') => '111221'
*/
const nextLookAndSay = (n) => {
let accum = [];
for (let group of runLengthEncode(n.toString().split(''))) {
accum.push(group, group);
}
return accum.join('');
};

/**
* The result of f(f(f ... f(init))), where the function f is applied n times
* to the initial value.
*
* iterateN(2, (s) => s + 'o', 'b') => 'boo'
*/
const iterateN = (n, f, init) => {
while (n--) { init = f(init); }
return init;
};

console.log(iterateN(3, nextLookAndSay, '1'));

• Given an entry that has L digits, generating the next entry takes O(L) time and O(L) space. The length of the nth entry is O(1.304^n), the total work to obtain the nth entry would be given by the geometric series 1 + 1.3 + 1.3^2 + … + 1.3^n, or O(1.304^n). Jul 28 '18 at 21:43