DEV Community

dev.to staff
dev.to staff

Posted on

9

Daily Challenge #115 - Look and Say Sequence

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!

Feature flag article image

Create a feature flag in your IDE in 5 minutes with LaunchDarkly’s MCP server 🏁

How to create, evaluate, and modify flags from within your IDE or AI client using natural language with LaunchDarkly's new MCP server. Follow along with this tutorial for step by step instructions.

Read full post

Top comments (5)

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

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
 
wheatup profile image
Hao • 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
Collapse
 
jbristow profile image
Jon Bristow • 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"
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");
}

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

👋 Kindness is contagious

Dive into this thoughtful piece, beloved in the supportive DEV Community. Coders of every background are invited to share and elevate our collective know-how.

A sincere "thank you" can brighten someone's day—leave your appreciation below!

On DEV, sharing knowledge smooths our journey and tightens our community bonds. Enjoyed this? A quick thank you to the author is hugely appreciated.

Okay