loading...

Daily Challenge #115 - Look and Say Sequence

thepracticaldev profile image dev.to staff ・1 min read

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!

Discussion

pic
Editor guide
Collapse
wheatup profile image
Hao

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
Collapse
nataliedeweerd profile image
𝐍𝐚𝐭𝐚𝐥𝐢𝐞 𝐝𝐞 𝐖𝐞𝐞𝐫𝐝

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"?

Collapse
jbristow profile image
Jon Bristow

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.

Collapse
jbristow profile image
Jon Bristow

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"
Collapse
citizen428 profile image
Michael Kohl

Ruby solution with Enumerator:

def look_and_say_sequence(start, n)
  Enumerator.new do |e|
    current = start
    loop do
      e << current
      current =
        current
          .chars
          .chunk_while { |a, b| a == b }
          .map { |a| "#{a.count}#{a.first}" }
          .join
    end
  end
  .take(n)
  .last
end

Works as expected:

look_and_say_sequence('1', 1)
#=> "1"
look_and_say_sequence('1', 3)
#=> "21"
look_and_say_sequence('1', 5)
#=> "111221"
look_and_say_sequence('22', 10)
#=> "22"
look_and_say_sequence('14', 2)
#=> "1114"
Collapse
idanarye profile image
Idan Arye

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");
}