CGAC2022 Day 20: Reconstruct Santa's Book

Question

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

Answer 1

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

Answer 2

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)

Answer 3

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

Answer 4

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!

Answer 5

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.

Answer 6

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

Answer 7

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!

Answer 8

Charcoal, 30 bytes

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

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

Ｆθ«

Loop over the characters of the squashed sentence.

Ｆ¬№ωι«

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:

ＳθＷＳ⊞υιＦθ«Ｆ¬№ωι«≔⊟Φυ№λιω⟦ω⟧»≔Φω›λ⌕ωιω

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.

Answer 9

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

Answer 10

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!

Answer 11

Excel (ms365), 241 bytes

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))

Answer 12

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)