16
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


Oh no, Santa spilled wine all over his great book. Now most of the letters are illegible. How will Santa now know who is groovy and who is unspeakable?

Challenge

There was once a sequence of words, like this:

groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable

However, most of the letters have gone missing and now it looks like this:

    v    oo   g      unsp        gr   y gro            b   uns

Then squashed together:

voogunspgrygrobuns

Your task is to recover the shortest sequence of words that could reduce to the given damaged string.

Note: The words will never have any overlapping characters. Since the book uses different words in different languages you need to handle different words.

Test Cases

Word A Word B Sentence Result
a b ab a b
ab cd abcd ab cd
ab cd abc ab cd
ab cd ac ab cd
ab cd bd ab cd
ab cd bda ab cd ab
ab cd aa ab ab
ooq dr ooqdr ooq dr
ooq dr oooqdr ooq ooq dr
groovy unspeakable voogunspgrygrobuns groovy groovy groovy unspeakable groovy groovy unspeakable unspeakable
\$\endgroup\$
3
  • \$\begingroup\$ Are we always given exactly two words? \$\endgroup\$
    – Arnauld
    Dec 19, 2022 at 22:40
  • \$\begingroup\$ @Arnauld yes, always exactly 2 \$\endgroup\$
    – mousetail
    Dec 20, 2022 at 5:29
  • \$\begingroup\$ @tsh Sorry, that should indeed be a b \$\endgroup\$
    – mousetail
    Dec 20, 2022 at 6:35

12 Answers 12

5
\$\begingroup\$

05AB1E, 14 bytes

‚[DNãvyJæ³åiyq

Try it online!

‚[DNãvyJæ³åiyq
‚              # pair
 [             # infinite loop
  D            # double
   N           # push current loop index
    ã          # cartesian power
     v         # for loop
      y        # push current element
       J       # join
        æ      # powerset
         ³å    # does it contain third input?
           iyq # if true, push current element and terminate
\$\endgroup\$
1
  • \$\begingroup\$ I/O is flexible by default, so you can take the first two inputs already as a single pair, removing the need for the leading (and ³ can then be ² or I): 13 bytes. \$\endgroup\$ Dec 27, 2022 at 11:55
4
\$\begingroup\$

Jelly, 16 bytes

I salvaged a previous blunder so this is now almost certainly beatable!

eⱮÐƤƤŒP€}SSÐṂḢ€ị

A dyadic Link that accepts the sentence on the left and the pair of words on the right and yields a list of words.

Try it online!

How?

Effectively greedily consumes the longest prefix of the remaining sentence that is a substring of one of the words and then adds that word to the, initially empty, result. The actual implementation analyses every sublist of the sentence and identifies the ends of the words and which one each is and then constructs the result.

eⱮÐƤƤŒP€}SSÐṂḢ€ị - Link: Sentence, Words
        }        - using the right argument, Words:
       €         -   for each word:
     ŒP          -     powerset -> all substrings of the word
    Ƥ            - for prefixes of Sentence:
  ÐƤ             -   for suffixes of that prefix:
 Ɱ               -     map across the pair of word substring lists with:
e                -       exists in?
         S       - sum the columns -> list of pairs [n,0] or [0,n] where n is
                                      the distance to the next word boundary.
           ÐṂ    - keep those pairs with minimal:
          S      -   sum (i.e the [1,0] and [0,1] entries marking ends of words.)
             Ḣ€  - head each -> 1 if word 1, 0 if word 2
               ị - index (1-based and modular) into (Words)
\$\endgroup\$
4
\$\begingroup\$

Python3, 119113 bytes:

lambda a,b,s:' '.join(a if x[0]in a else b for x in re.split(f"({'?'.join(a)}?|{'?'.join(b)}?)",s)if x);import re

Try it online

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to the site! Great first answer \$\endgroup\$
    – mousetail
    Dec 20, 2022 at 11:42
  • 1
    \$\begingroup\$ Nice answer! You can put f= in the header since your function isn't recursive. \$\endgroup\$
    – The Thonnu
    Dec 20, 2022 at 12:10
  • 1
    \$\begingroup\$ And you can save a few more bytes by importing re separately: 113 bytes \$\endgroup\$
    – The Thonnu
    Dec 20, 2022 at 12:12
  • 1
    \$\begingroup\$ Thanks! Updated my answer. \$\endgroup\$
    – David
    Dec 20, 2022 at 13:33
3
\$\begingroup\$

Python3, 190 bytes:

Y=lambda a,b:a==''if''in[a,b]else Y(a[a[0]==b[0]:],b[1:])
f=lambda a,b,s,r=[]:r if''==s else f(a,b,s[(M:=max([x for x in range(1,len(s)+1)if Y(s[:x],a)+Y(s[:x],b)])):],r+[[a,b][Y(s[:M],b)]])

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Retina, 46 bytes

~(L$`¶(.+)
\G$1(?!\G)¶$1
(?<=G\w+)
?
^
L#-2$$`

Try it online! Takes the squashed word on the first line and the pair of words on the other two lines. Explanation: Very similar to the extended version below but the last stage hard-codes the number of words.

63 bytes for a version that decodes any number of words with non-overlapping letters:

~(L$`¶(.+)
\G$1(?!\G)¶$1
(?<=G\w+)
?
^(?=((!)|[^!])+)
L#-$#2$$`

Try it online! Takes the squashed word on the first line and original words on subsequent lines. Explanation:

~(

Evaluate the output of the rest of the program as a program on the original input.

L$`¶(.+)

For each original word...

\G$1(?!\G)¶$1

... construct an anchor to match after the previous word (easiest way to limit the matches to the first line), the word to be processed below, an anchor to not match after the previous word (to ensure at least one letter matched) and a copy of the word on its own line to act as a replacement.

(?<=G\w+)
?

Suffix ?s to each letter in the word, making each letter match optionally (but greedily).

^(?=((])|[^]])+)
L#-$#2$$`

Prefix a List command with the multiple greedy match and replacement option.

In the given example, the resulting program looks like this:

L#-2$`\Gg?r?o?o?v?y?(?!\G)
groovy
\Gu?n?s?p?e?a?k?a?b?l?e?(?!\G)
unspeakable

Explanation:

L#-2$`

List matches of two regexes each with their own match result. (In this case only one of the regexes can match at a given point but the #- option normally allows Retina to choose which regex depending on which matches earlier in the string.)

\Gg?r?o?o?v?y?(?!\G)

Greedily match as much of the word groovy as possible, matching at least one character.

groovy

If this match succeeds then the resulting list item is the word groovy.

\Gu?n?s?p?e?a?k?a?b?l?e?(?!\G)
unspeakable

Similarly for the word unspeakable.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 83 bytes

s=>a=>(g=i=>(e=t=>r=t^1?a[t&1]+[,e(t/2)]:'')(i).match([...s].join`.*`)?r:g(i+1))(1)

Try it online!

As a compare with find

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 77 bytes

a=>b=>g=(t,s='',...r)=>s.match([...t].join`.*`)?s:g(t,...r,(s&&=s+' ')+a,s+b)

Attempt This Online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 30 bytes

Fθ«F¬№ωι«≔⎇№ηιηζω⟦ω⟧»≔Φω›λ⌕ωιω

Try it online! Link is to verbose version of code. Takes the squashed sentence as the first input. Explanation:

Fθ«

Loop over the characters of the squashed sentence.

F¬№ωι«

If the current character isn't present in the current string (initially the empty string), then...

≔⎇№ηιηζω

... update the current string to the word that contains the current character, and...

⟦ω⟧

... output that word on its own line.

»≔Φω›λ⌕ωιω

Delete up to the first occurrence of the current character in the current word.

37 bytes for a version that decodes any number of words with non-overlapping letters:

SθWS⊞υιFθ«F¬№ωι«≔⊟Φυ№λιω⟦ω⟧»≔Φω›λ⌕ωιω

Try it online! Link is to verbose version of code. Takes the squashed sentence as the first input followed by a list of newline-terminated words.

\$\endgroup\$
3
\$\begingroup\$

Pyth, 22 bytes

Kwm?-dzKzhf!-T+yzyK./w

Try it online!

Takes the two words as the first two inputs and the sentence as the third. Returns a list.

Brutally slow brute force method.

Explanation

                          # z=input() implicitly
Kw                        # set K to the second input
                   ./w    # all partitions of the third input (given sorted by number of elements in the partition)
          f               # filter over lambda T
           !              # not (true for empty list)
            -T            # remove from T 
              +yzyK       # sum of the power sets of the first two inputs
         h                # take the first element of the filtered list (this will be a valid partition with the least elements)
  m                       # map each element (d) to
   ?-dzKz                 # z if d consists of characters in z, K otherwise
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES10), 86 bytes

Expects (sentence)(word_list). Returns a comma-separated string of words.

s=>a=>(g=b=>b.find(w=>w.match([...s].join`.*`))||g(b.flatMap(p=>a.map(q=>p+[,q]))))(a)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Excel (ms365), 241 bytes

enter image description here

Formula in D1:

=LET(x,SEQUENCE(LEN(C1)),y,SCAN(C1,x,LAMBDA(a,b,LET(z,MAP(x,LAMBDA(c,TEXTJOIN("*",,MID(a,SEQUENCE(c),1)))),SUBSTITUTE(a,TAKE(TOCOL(IF(SEARCH(z,A1:B1),LEFT(a,x),),2),-1),,1)))),TOCOL(IF(FIND(LEFT(VSTACK(C1,FILTER(y,y<>""))),A1:B1),A1:B1,),3))
\$\endgroup\$
1
\$\begingroup\$

Pip, 41 bytes

Y@_NIag@yMFIc@(@>(aJW"?").`|`.@>(bJW"?"))

Try It Online!

Expects the first word, second word and sentence as inputs. Shamelessly stole the regex from @David's answer. Full test suite here (Thanks to @emanresuA for help with the test suite)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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