dev.to staff

Posted on Nov 12, 2019

Daily Challenge #115 - Look and Say Sequence

#challenge

The look and say sequence is a sequence in which each number is the result of a "look and say" operation on the previous element.

For example, starting with "1": ["1", "11", "21, "1211", "111221", ...]. You can see that the second element describes the first as "1(times number)1", the third is "2(times number)1" describing the second, the fourth is "1(times number)2(and)1(times number)1" and so on.

Your goal is to create a function which takes a starting string (not necessarily the classical "1") and return the nth element of the series.

Examples:
lookAndSaySequence("1", 1) === "1" lookAndSaySequence("1", 3) === "21" lookAndSaySequence("1", 5) === "111221" lookAndSaySequence("22", 10) === "22" lookAndSaySequence("14", 2) === "1114"

Good luck!

This challenge comes from giacomosorbi on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (5)

Hao • Nov 13 '19 • Edited

Here's a one line solution in javascript.

Zero readability, maximum coolness. 😎

const lookAndSaySequence = (text, count) => count <= 1 ? text : lookAndSaySequence(text.match(/(.)\1*/g).map(frag => `${frag.length}${frag[0]}`).join(''), count - 1);

console.log(lookAndSaySequence('1', 1));    // 1
console.log(lookAndSaySequence('1', 3));    // 21
console.log(lookAndSaySequence('1', 5));    // 111221
console.log(lookAndSaySequence('22', 10));  // 22
console.log(lookAndSaySequence('14', 2));   // 1114

𝐍𝐚𝐭𝐚𝐥𝐢𝐞 𝐝𝐞 𝐖𝐞𝐞𝐫𝐝 • Nov 12 '19 • Edited

I completely didn't understand the description here... For those also struggling, here's the explanation from wikipedia for what a "Look and Say sequence" is:

To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
1211 is read off as "one 1, one 2, then two 1s" or 111221.
111221 is read off as "three 1s, two 2s, then one 1" or 312211.

Actually, following this, isn't the above code incorrect? In that:

lookAndSaySequence("1", 1) === "1"

should be:

lookAndSaySequence("1", 1) === "11"

As it's "one 1"?

Jon Bristow • Nov 13 '19

I think you're approaching the problem from an array offset point of view (start at 0) where 0 should return the input with no transformations applied. Likewise, 2 would give the result after two iterations.

The problem statement is approaching it from an ordinal perspective. In their view, 1 should be the un-mutated input.

I think they tried to call this out by noting "1": ["1", "11", "21, "1211", "111221", ...], but I agree that it isn't very clear from the text alone.

Jon Bristow • Nov 12 '19 • Edited

Kotlin, because I'm prepping a mini talk on declarative style...


tailrec fun speak(
    remaining: String,
    curr: String = "",
    currCount: Int = 0,
    output: String = ""
): String {
    return when {
        remaining.isEmpty() && curr.isBlank() -> output
        remaining.isEmpty() -> "$output$currCount$curr"
        curr.isEmpty() -> speak(
            remaining.substring(1),
            curr = remaining.substring(0, 1),
            currCount = 1,
            output = output
        )
        remaining.startsWith(curr) -> speak(
            remaining.substring(1),
            curr = curr,
            currCount = currCount + 1,
            output = output
        )
        else -> speak(
            remaining.substring(1),
            curr = remaining.substring(0, 1),
            currCount = 1,
            output = "$output$currCount$curr"
        )
    }
}

fun lookAndSaySequence(input: String, times: Int): String {
    require(times > 0) { "times must be > 0" }
    return generateSequence(input) { speak(it) }.drop(times-1).first()
}

SPOILERS: base64decode('SXQncyBqdXN0IHJ1bi1sZW5ndGgtZW5jb2Rpbmch')

bonus:

lookAndSaySequence("aardvark", 5) === "3112311a13211r13211d13211v13211a13211r13211k"
lookAndSaySequence("Billions and Billions", 3) === "111B111i121l111i111o111n111s111 111a111n111d111 111B111i121l111i111o111n111s"

Idan Arye • Nov 13 '19

Rust: play.rust-lang.org/?version=stable...

pub struct LookAndSaySequence(String);

impl Iterator for LookAndSaySequence {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        let mut result = String::new();
        let mut prev_digit = None;
        let mut counter = 0;
        let mut it = self.0.chars();
        let mut result = loop {
            let digit = it.next();
            if digit == prev_digit {
                counter += 1;
            } else {
                if let Some(prev_digit) = prev_digit {
                    use std::fmt::Write;
                    write!(&mut result, "{}{}", counter, prev_digit).unwrap();
                }
                counter = 1;
                prev_digit = digit;
            }
            if digit.is_none() {
                break result;
            }
        };
        std::mem::swap(&mut self.0, &mut result);
        Some(result)
    }
}

pub fn look_and_say_sequence(seed: &str, index_that_starts_at_one_who_does_that_its_2019: usize) -> String {
    LookAndSaySequence(seed.to_owned()).nth(index_that_starts_at_one_who_does_that_its_2019 - 1).expect("endless iterator")
}

fn main() {
    assert_eq!(look_and_say_sequence("1", 1), "1");
    assert_eq!(look_and_say_sequence("1", 3), "21");
    assert_eq!(look_and_say_sequence("1", 5), "111221");
    assert_eq!(look_and_say_sequence("22", 10), "22");
    assert_eq!(look_and_say_sequence("14", 2), "1114");
}

DEV Community

Daily Challenge #115 - Look and Say Sequence

Top comments (5)

Read next

eq and ne in PyTorch

Challenges and Solutions in Implementing AI for Software Testing

Key differences between BPMN diagrams and Optimajet .NET Workflow Engine process schemes

isclose and equal in PyTorch