14
\$\begingroup\$

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 , 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.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ Maybe link a list of words? \$\endgroup\$
    – mousetail
    Commented Oct 10, 2022 at 14:59
  • 2
    \$\begingroup\$ This kinds of challanges are much cleaner if you allow both the input and the dictionary to be taken as arguments. This makes writing test cases easier, too. \$\endgroup\$
    – Jonah
    Commented Oct 10, 2022 at 15:13
  • 4
    \$\begingroup\$ @Jonah I thought that was implied, sorry. You may take the input and dictionary as input in any manner conforming to the I/O rules, which I believe also includes arguments. I will add this to the question. \$\endgroup\$
    – Ginger
    Commented Oct 10, 2022 at 15:31
  • 2
    \$\begingroup\$ Is it guaranteed that it always forms at least one word? \$\endgroup\$
    – Aiden Chow
    Commented Oct 10, 2022 at 15:36
  • 2
    \$\begingroup\$ Please provide some test cases \$\endgroup\$
    – qwr
    Commented Oct 11, 2022 at 5:16

13 Answers 13

7
\$\begingroup\$

Ruby, 40 bytes

-1 byte thanks to Dingus

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

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ @Dingus Good catch. Thanks! \$\endgroup\$
    – Jordan
    Commented Oct 10, 2022 at 23:47
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ The word need not start with the first sequence, so you need to use search instead of match. After that, this should be an improvement: lambda x,d:min(filter(re.compile('.*'.join(x)).search,d),key=len) \$\endgroup\$
    – m90
    Commented Oct 10, 2022 at 16:03
  • \$\begingroup\$ @m90 what does re.compile do? \$\endgroup\$
    – Aiden Chow
    Commented Oct 11, 2022 at 1:40
  • \$\begingroup\$ @AidenChow It returns a Regex object constructed from the input string. \$\endgroup\$ Commented Oct 11, 2022 at 1:53
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
7
  • 1
    \$\begingroup\$ -3 bytes \$\endgroup\$
    – Shaggy
    Commented Oct 10, 2022 at 15:42
  • \$\begingroup\$ @Shaggy oh right lol, thanks \$\endgroup\$ Commented Oct 10, 2022 at 15:47
  • \$\begingroup\$ w=>w.match(x.join`.*`) \$\endgroup\$
    – Neil
    Commented Oct 10, 2022 at 16:21
  • \$\begingroup\$ 78 bytes with reduce, 71 bytes with that and Neil's suggestion \$\endgroup\$ Commented Oct 10, 2022 at 16:22
  • \$\begingroup\$ @Neil wtf i didnt know that match implicitly converted to regexp cool \$\endgroup\$ Commented Oct 10, 2022 at 16:40
3
\$\begingroup\$

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.

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

Vyxal, 10 bytes

'?‛.*jr;Þg

Try it Online!

Takes in the dictionary and the partial transcription as lists.

\$\endgroup\$
2
+200
\$\begingroup\$

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.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ this should work \$\endgroup\$
    – emanresu A
    Commented Oct 23, 2022 at 5:05
  • \$\begingroup\$ @emanresuA what does : do again? \$\endgroup\$
    – Aiden Chow
    Commented Oct 23, 2022 at 5:26
  • \$\begingroup\$ : is the assignment meta-operator when put to the right of an operator. It has very high precedence. Y would also work, although the wrapper would need changing \$\endgroup\$
    – emanresu A
    Commented Oct 23, 2022 at 6:05
2
\$\begingroup\$

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

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

Perl 5 (-ap), 58, 51 bytes

7 bytes saved thanks to Xcali

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

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You don't need to use the join. You can just change the value of $" like this: Try it online! \$\endgroup\$
    – Xcali
    Commented Oct 26, 2022 at 16:53
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Python 3, 67 bytes

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

Try it online!

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

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
\$\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.