23
\$\begingroup\$

Background

The Look and Say Sequence is built up by reading off the digits of previous entries in the sequence, counting the number of digits in groups of the same digit. For example:

1 => 11 # (one 1)
11 => 21 # (two 1s)
21 => 1211 # (one 2, then one 1)
1211 => 111221 # (one 1, then one 2, then two 1s)

This sequence was the subject of various previous challenges. A simple Python 3 implementation of the generating function is:

>> from itertools import groupby
>> def look_and_say(obj):
      return "".join(f"{len(list(group))}{digit}" for digit, group in groupby(str(obj)))

Try it online!

Challenge

The purpose of this challenge is to implement an inverse Look and Say function. Given a Look and Say representation of a non-negative integer, your code should return the smallest non-negative integer for which the input is its Look and Say. Note that this is not the same as general Run Length Decoding, since the output must encode back precisely to the input: see the examples below for some of the subtleties involved.

This is , so shortest code in bytes wins, with all the standard loopholes forbidden. Input can be passed in (or returned) as either an integer or a string.

Test cases

10 => 0 # (1 zero)
12 => 2 # (1 two)
123 => 333333333333 # (12 threes)
1234 => 2444 # (1 two, 3 fours)
1232 => 222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222 # (123 twos, since 2222 would return 42 not 1232)
2019 => 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 # (201 nines, since the only non-negative starting with 0 is 0)
2109 => 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 # (210 nines, since 11 would return 21 not 2109)
123456 => 244466666
123454 => 333333333333444444444444444444444444444444444444444444444 # (12 threes, 45 fours)
124234 => 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222444 (124 twos, 3 fours, which is smaller than the alternatives)

Invalid inputs

Since there are no integers which have the following Look and Say representations, the behaviour for these inputs is undefined:

1
3
20
100
1010
10010
\$\endgroup\$
  • 2
    \$\begingroup\$ I'd like to recommend some more test cases:22334, 33224, 10101 and 10111, I think they would cover some more edge cases. \$\endgroup\$ – flawr Nov 21 at 12:37
  • \$\begingroup\$ With an input of 121212, I assume that a response of 312 (three 12's) is not a valid response? \$\endgroup\$ – Keeta Nov 22 at 12:46
  • 1
    \$\begingroup\$ @Keeta That goes the wrong way. It's 312 as input does not have 121212 as a valid response. \$\endgroup\$ – Taemyr Nov 22 at 13:59
10
\$\begingroup\$

05AB1E, 11 bytes

∞<ÅΔÅγs.ιJQ

Try it online!

Computes the look and say of all integers until finding one that matches the input. Will timeout for large outputs.

\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 111 bytes

f=([x,y,...s],p,o=O='',m='')=>x?y?f([y,...s],p,o,m+=x,+m&&y^p&&f(s,y,o+y.repeat(m))):O||0:!O||O[o.length]?O=o:0

Try it online!

Commented

f = (                     // f is a recursive function taking:
  [x, y,                  //   x, y = next two characters from the input string
         ...s],           //   s[]  = array of remaining characters
  p,                      //   p    = previous repeated digit, initially undefined
  o =                     //   o    = current output
  O = '',                 //   O    = shortest output so far
  m = ''                  //   m    = current multiplier, as a string
) =>                      //
  x ?                     // if x is defined:
    y ?                   //   if y is defined:
      f(                  //     do an unconditional recursive call:
        [y, ...s], p, o,  //       where y is put back in the input
        m += x,           //       and x is appended to m
        +m &&             //       if m is not zero'ish
        y ^ p &&          //       and y is not equal to p:
        f(                //         do another recursive call:
          s, y,           //           where p is updated to y
          o + y.repeat(m) //           and y is appended to o, m times
        )                 //       end of inner recursive call
      )                   //     end of outer recursive call
    :                     //   else:
      O || 0              //     return O, or 0 if it's empty
  :                       // else:
    !O || O[o.length] ?   //   if O is still empty or o is shorter than O:
      O = o               //     update O to o
    :                     //   else:
      0                   //     do nothing
\$\endgroup\$
5
\$\begingroup\$

Jelly, 13 bytes

DŒrUDF⁼³µ1#@0

Try it online!

A full program that takes a list of digits and returns the first number that generates that as its look-and-say. Tries all numbers until one matches so will be slow for some inputs.

Alternatives

Jelly, 25 bytes

DŒṖṪxḌƊ€F$€ḌDŒrUƊDF⁼ʋƇDṢḢ

Try it online!

A monadic link taking an integer. Generates all possible inverse look-and-says (including invalid ones) and then tests them by seeing whether generating a look-and-say results in the input. Returns the smallest valid one.

Jelly, 30 bytes

ŒṖUZḢEƲƝẸ$ÐḟṪxḌƊ€€ẠƇF€ḌD$ƑƇḌṢḢ

Try it online!

A monadic link taking a list of digits. Generates all possible inverse look-and-says (including invalid ones) and then tests them by seeing whether they violate any rules. Returns the smallest valid one.

Thanks to @ØranJohansen for pointing out a problem with the last two.

\$\endgroup\$
  • \$\begingroup\$ Your fast versions fail for the last two test cases. \$\endgroup\$ – Ørjan Johansen Nov 21 at 5:48
  • \$\begingroup\$ @ØrjanJohansen fixed. I thought I could go for the first one. I checked on the first few thousand numbers as input, but annoyingly missed the fact the last two test cases had stopped working! I’ve restored the sort before heading. \$\endgroup\$ – Nick Kennedy Nov 21 at 7:27
3
\$\begingroup\$

Perl 5 (-ap), 133 bytes

/^(?{@l=()})((?!0)(.+?)(.)(?{local@l=(@l,$3x$2)}))*$(?{push@r,"@l"})^/;$_=(sort{$a=~y,,,c-length$b}grep!/^0./&!/(.) \1/,@r)[0];y/ //d

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This fails for the last 124234 test case. \$\endgroup\$ – Ørjan Johansen Nov 21 at 5:51
  • \$\begingroup\$ indeed there's a problem, it doesn't backtracks for all cases, with (.+?) -> 1-2,4-2,3-4 1-2,423-4 12-4,23-4 and (.+) -> 12423-4 *124-2,3-4* 12-4,23-4 1-2,423-4 however (.+) will not work with 123456, to be reviewed \$\endgroup\$ – Nahuel Fouilleul Nov 21 at 8:23
  • \$\begingroup\$ maybe due to regex optimization to avoid catastrophic bactracking which would be wanted in this case \$\endgroup\$ – Nahuel Fouilleul Nov 21 at 8:42
2
\$\begingroup\$

Python 2, 200 166 165 bytes

lambda n:min(int(r)for r in b(n)if str(int(r))==r)
b=lambda n:[int(n[:i])*n[i]+v for i in range(1,len(n))for v in b(n[i+1:])if int(n[:i])*(n[i]!=v[:1])]if n else['']

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 81 bytes

->n{(0..1/0.0).find{|r|r.to_s.chars.chunk{|w|w}.map{|a,b|[b.size,a]}*''==n.to_s}}

Try it online!

Brute force approach, could be 5 bytes shorter on a newer version of Ruby, but it doesn't matter because it's slow as hell for most numbers.

\$\endgroup\$
1
\$\begingroup\$

Japt, 16 bytes

Brute force approach that'll crap out for larger outputs.

@¥Xò¦ ËÎiDlÃq}as

Try it

@¥Xò¦ ËÎiDlÃq}as     :Implicit input of integer U
@                    :Function taking an integer string X as argument
 ¥                   :  Test U for equality with
  Xò                 :  Partition X on
    ¦                :    Inequality
      Ë              :  Map each D
       Î             :    First character of D
        i            :    Prepend
         Dl          :    Length of D
           Ã         :  End map
            q        :  Join
             }       :End function
              a      :Return the first integer that returns true when passed through that function
               s     :After converting it to a string
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 67 bytes

⊞υ⟦0ωS⟧Fυ«≔§ι²θF∨‹θ1Lθ¿∧κ⁻§θκ§ι⁰⊞υ⟦§θκ⁺§ι¹×§θκI…θκ✂θ⊕κ⟧»I⌊EΦυ¬⊟ιI⊟ι

Try it online! Link is to verbose version of code. Generates all integers with the given look-and-say sequence and outputs the minimum thereof. Explanation:

⊞υ⟦0ωS⟧

Start by pushing a list of three items to the predefined list. The first item (initially 0) represents the previous repeated digit (thus preventing the generated number from beginning with 0), the second item (initially an empty string) represents the integer so far (as a string), while the third item (initially the whole input) represents the remaining input to process.

Fυ«

Loop over the list. This automatically iterates over additional items as they are pushed to the list.

≔§ι²θ

Get the remaining input into a dedicated variable. This saves several bytes as this variable is used multiple times. It does force me to wrap the block in braces, but this is offset by allowing me to use an if to save a byte.

F∨‹θ1Lθ

Loop over the string, but if it begins with a zero, only loop once (which gets ignored anyway, but this is a byte golfer than not looping at all).

¿∧κ⁻§θκ§ι⁰

Ignore the first character of the string (because there is no number to multiply it by), and also any character equal to the previously processed digit for this entry.

⊞υ⟦§θκ⁺§ι¹×§θκI…θκ✂θ⊕κ⟧

Push the next potential step to the list, comprising the current digit, the integer so far with the current digit repeated the prefix number of times, and the suffix.

»I⌊EΦυ¬⊟ιI⊟ι

After all possible steps have been processed, filter those that consumed the input exactly, and output the smallest resulting value.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.