Make a Court Transcriber

Question

Discussion in courtrooms often occurs at a high speed and needs to be accurately transcribed in case the text of the decision is needed in future cases. For this purpose, the stenographers who transcribe court discussions use specially designed keyboards with a small set of buttons, which are pressed in groups to spell out words with a single motion. For this challenge, you will write a program that does something quite similar.

The Challenge

Given a list composed of sequences of three letters, as well as another list of dictionary words, return the shortest word containing all of them in sequence without overlaps. If there are multiple shortest words, you may return any of them. Your program may accept the dictionary and letter sequences in any format conforming to the I/O rules.

Examples

[dic, ion, ary]: dictionary
[tra, scr, ber]: transcriber

This is code-golf, so shortest answer wins!

The dictionary used to check answers should be the SCOWL word list, usually available as /usr/share/dict/words on Debian GNU/Linux systems.

Answer 1

Ruby, 40 bytes

-1 byte thanks to Dingus

->d,a{d.grep(/#{a*".*"}/).min_by &:size}

Attempt This Online!

Answer 2

Japt -g, 9 bytes

ñÊfèVq*i.

Try it

ñÊfèVq*i.     :Implicit input of arrays U=dictionary & V=substrings
ñ             :Sort U by
 Ê            :  Length
  f           :Filter by
   è          :  Count occurrences of
    Vq        :    Join V with
      *i.     :    "*" prepended with "."
              :Implicit output of first element

Answer 3

Python 3.8 (pre-release), 76 75 bytes

-1 bytes thanks to @m90

lambda x,d:min(filter(re.compile('.*'.join(x)).search,d),key=len)
import re

Try it online!

Answer 4

J-uby, 45 bytes

Port of my Ruby answer. Unfortunately lost a few bytes by having to call Regexp.new manually instead of using a Regexp literal and interpolation.

(:grep|:min_by+:+@)%(~:*&".*"|~(:new&Regexp))

Attempt This Online!

Explanation

( :grep | :min_by + :+@ ) % (~:* & ".*" | ~(:new & Regexp))

                            (~:* & ".*" | ~(:new & Regexp))  # Construct regexp by joining array with ".*"
( :grep |                                                    # Search dictionary with it, then
          :min_by + :+@ )                                    # Get the smallest of the results by length

Answer 5

JavaScript (V8), 8279 bytes

d=>x=>d.filter(w=>RegExp(x.join`.*`).test(w)).sort((a,b)=>a.length-b.length)[0]

Try it online!

d=>x=>d.filter(w=>RegExp(x.join`.*`).test(w)).sort((a,b)=>a.length-b.length)[0]


d=>                                     // given a dictionary d
   x=>                                  // and (via currying) a list of three letter sequences x,
d.filter(w=>RegExp(          ).test(w)) // keep only the words from the dictionary which match
                   x.join`.*`           // a regular expression formed by joining each 3 character sequence with ".*" (explained later)
.sort((a,b)=>a.length-b.length)         // sort the newly filtered dictionary by length
                               [0]      // and return the first word (should be the shortest)

// Generated regex, using x=["tra", "scr", "ber"] as an example

/tra.*scr.*ber/
 tra            // the first sequence of letters that needs to occur in the word anywhere
    .*          // any amount of intermediate characters (including 0)
      scr       // the second sequence that needs to occur
         .*     // 0 or more intermediate characters again
           ber  // the final sequence of characters that needs to occur

Might be possible to do this shorter with a reduce, but it escapes me. Maybe eval could make the regex shorter, but I don't see it.

LMK if there's a better way to format the TIO page, but I don't know how to import the big dictionary linked in the question. I'll probably make one with a bunch of test cases so you don't have to do your own.

I'm not worried so much though cause this should be theoretically correct assuming there's no weird edge cases :P

Answer 6

Retina, 33 bytes

0G`
,
.$*
~)`^
G`
0A`
N$`
$.&
0G`

Try it online! Takes a list of sequences on the first line followed by the dictionary but link includes bash wrapper that automatically appends /usr/share/dict/words to the input for you (does make the script slow though). Explanation:

0G`

Get just the list of sequences.

,
.$*

Replace the commas with .* (* is the string repetition operator in Retina 1, so it needs to be escaped.)

^
G`

Prefix G`.

~)`

Execute the result as Retina code on the original input.

0A`

Delete the list of sequences, which obviously matched itself.

N$`
$.&

Sort in ascending order of length.

0G`

Keep only the shortest word.

Answer 7

Vyxal, 10 bytes

'?‛.*jr;Þg

Try it Online!

Takes in the dictionary and the partial transcription as lists.

Answer 8

Pip, 23 22 20 bytes

-3 bytes thanks to @DLosc

{@(aJ`.*`N_FIbSK#_)}

Try It Online!

{@(aJ`.*`N_FIbSK#_)}          ; First argument = substrings = a 
                              ; Second argument = dictionary = b
{                  }          ; Create a function that...
 @(               )           ; takes the first element of...
           FIb                ; b, filtered by if...
         N_                   ; each element matches...
   aJ`.*`                     ; the regex formed by joining each substring with ".*"...
              SK#_            ; and sorted by the length of the word.

Answer 9

Bash, 88 86 bytes

for w in `<$1`;{ echo $w>$w;}
wc -m `printf "*%s*" ${@:2}`|sort -n|head -1|tr -d 0-9\ 

Try it online!

First argument is dictionary file. The followings are the three squence letters.

For each word in dict generate a file containing the word itself. printf "*%s*" ${@:2} generates the pattern **$2**$3**$4**... with the rest of the arguments. This pattern is used as a glob tu select files and count word length. wc -m otuputs length and filenames so sort -n|head -1|tr -d 0-9\ so sorts by length, gets first and deletes numbers and space.

Note: If your dictionary file is too large your filesystem has to handle such number of files on same directory (that's why is trimmed down in TIO).

Answer 10

Perl 5 (-ap), 58, 51 bytes

7 bytes saved thanks to Xcali

$"=".*";$_=(sort{$a=~y///c-length$b}grep/@F/,@_)[0]

Try it online!

Answer 11

Thunno, \$ 22 \log_{256}(96) \approx \$ 18.11 bytes

g".*"z1jAfkD.LZZz:AJAK

Attempt This Online!

Explanation

g".*"z1jAfkD.LZZz:AJAK  # Implicit input
g         k             # Filter:
       j                #  join
     z1                 #  the second input
 ".*"                   #  by ".*"
        Af              #  regex test
           D.L          # Duplicate, length of each
              ZZz:      # Zip and sort by length
                  AJAK  # Last item of first item
                        # Implicit output

Answer 12

Python 3, 67 bytes

lambda x,d:[e for e in d if re.match(".*?".join(x),e)][0]
import re

Try it online!

Answer 13

Wolfram Language (Mathematica), 121 bytes

MinimalBy[Select[ReadList["/usr/share/dict/words",String],StringMatchQ[#,StringExpression@@Riffle[s,___]]&],StringLength]

Try it online!

Wolfram Language (Mathematica), 82 bytes

MinimalBy[Select[d,StringMatchQ[#,StringExpression@@Riffle[s,___]]&],StringLength]

Try it online!

---

Original code is:

FindShortestWord[sequences_List, dictionary_List] := Module[
  {pattern, matchedWords},
  pattern = StringExpression @@ Riffle[sequences, ___];
  matchedWords = Select[dictionary, StringMatchQ[#, pattern] &];
  MinimalBy[matchedWords, StringLength]
]

(* Load the SCOWL word list *)
scowlWordList = ReadList["/usr/share/dict/words", String];

(* Test the function *)
sequences1 = {"dic", "ion", "ary"};
sequences2 = {"tra", "scr", "ber"};
FindShortestWord[sequences1, scowlWordList]//Print
FindShortestWord[sequences2, scowlWordList]//Print