9
\$\begingroup\$

The Universal Crossword has a set of guidelines for crossword puzzle submissions.

In this challenge we are going to be concerned with their rules for hidden word themes. A hidden word clue consists of a clue and a word. It can either be a "word break" or a "bookend".

For a word break the word must not appear as a contiguous substring of the clue, but if all the spaces are removed from the clue, then it is a contiguous substring with a non-empty prefix and suffix. Some examples:

  • POOR HOUSE, RHO: is valid. Solution: POOR HOUSE
  • IMPROPER USE, PERUSE: is not valid. It appears separated by a space: IMPROPER USE, but the suffix is empty.
  • SINGLE TRACK, SINGLET: is not valid. It appears separated by a space: SINGLE TRACK, but the prefix is empty.
  • PLANE TICKET, ET: is not valid. The word appears separated by a space: PLANE TICKET, but it also appears contiguously: PLANE TICKET.

For a bookend the word must appear as a combination of a non-empty prefix and a non-empty suffix of the clue, but is not a contiguous substring. Bookends may span word breaks, but are not required to. The clue must not appear as a contiguous substring to be a valid bookend.

  • SINGLE TRACK, SICK: is valid. Solution: SINGLE TRACK
  • YOU MUST DOT YOUR IS AND CROSS YOUR TS, YURTS: is valid. Solution: YOU MUST DOT YOUR IS AND CROSS YOUR TS
  • STAND CLEAR, STAR: is valid, even though there are two solutions: STAND CLEAR and STAND CLEAR
  • START A WAR, STAR: is not valid since the word is a prefix of the clue.
  • TO ME, TOME: is valid. It can be split multiple ways including ways with empty prefixes and suffixes.
  • TWO BIRDS WITH TWO STONE, TONE: is not valid since the word is a suffix of the clue
  • IMPROPER USE, PERUSE: is not valid. It appears as a suffix and is not a contiguous substring: IMPROPER USE, but the prefix needs to be non empty for a bookend.

You will take as input a word (consisting of letters A-Z) and a clue (consisting of letters A-Z and spaces) and you must determine if the word is a valid solution to the clue by the above rules.

If the input is a valid pair you must output one consistent value, if it is not you must output a distinct consistent value.

This is so the goal is to minimize the size of your source code as measured in bytes.

Test cases

Valid:

POOR HOUSE, RHO
SINGLE TRACK, SICK
YOU MUST DOT YOUR IS AND CROSS YOUR TS, YURTS
STAND CLEAR, STAR
TO ME, TOME
IN A PICKLE, NAP

Invalid:

IMPROPER USE, PERUSE
SINGLE TRACK, SINGLET
PLANE TICKET, ET
START A WAR, STAR
TWO BIRDS WITH ONE STONE, TONE
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Is AA AAB, AAA valid? It can be hidden in the middle with a prefix of the first A, but it can also be put at the beginning, which is invalid. \$\endgroup\$
    – Value Ink
    Oct 20, 2023 at 18:46
  • \$\begingroup\$ @ValueInk That's valid. It is not a contiguous substring, and it is a contiguous substring of the spaceless clue with a non-empty prefix and suffix. \$\endgroup\$
    – Wheat Wizard
    Oct 20, 2023 at 18:48
  • 1
    \$\begingroup\$ Second half seems to be codegolf.stackexchange.com/questions/194929/is-it-a-circumfix with the added stipulation that the word also cannot appear contiguously in the input. \$\endgroup\$
    – Value Ink
    Oct 20, 2023 at 19:01
  • \$\begingroup\$ Can you add a valid test case that is a word break where multiple spaces must be removed to find the word in the clue? \$\endgroup\$ Oct 21, 2023 at 4:14
  • \$\begingroup\$ I was going to ask whether a word could span more than one break; the wording (and @GregMartin’s question) imply that they can. So presumably BRUNO RAN GENTLY could be a clue for ORANGE \$\endgroup\$ Oct 21, 2023 at 13:26

8 Answers 8

3
\$\begingroup\$

Retina 0.8.2, 41 bytes

 |^(.+)¶.*\1

^(.+)(.+)¶(\1.*\2$|.+\1\2.)

Try it online! Takes input as the word and clue on separate lines but link is to test suite that splits on comma and exchanges the word and clue. Explanation:

 |^(.+)¶.*\1

Delete spaces in the clue, but delete the word if is is a contiguous substring of the clue, which prevents the following match from succeeding.

^(.+)(.+)¶(\1.*\2$|.+\1\2.)

Check that the word either bookends or is now contained in the clue.

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

JavaScript (ES6), 74 bytes

A significantly shorter version suggested by Nick Kennedy and using Neil's regular expression.

Expects (clue)(word). Returns a Boolean value.

c=>w=>c.match(w)</^(.+)(.+),(\1.*\2$|.+\1\2.)/.test([w,c.split` `.join``])

Try it online!


JavaScript (ES6), 86 bytes

Expects (clue)(word). Returns a Boolean value.

The "bookend" test is based on the method used by Deadcode in this answer.

c=>w=>c.match(w)</^(.+)(.+),\1.*\2$/.test([w,s=c.split` `.join``])+!!s.match(`.${w}.`)

Try it online!

Commented

c =>                // outer function taking c = clue
w =>                // inner function taking w = hidden word
c.match(w)          // look for w in c; the comparison will succeed 
<                   // if this is null and the right side is > 0
/^(.+)(.+),\1.*\2$/ // regular expression for the "bookend" test
.test([             // applied to this array coerced to a string:
  w,                //   the word, followed by a comma
  s = c.split` `    //   followed by s,
       .join``      //   which is c without spaces
]) +                // end of test()
!!s.match(`.${w}.`) // for word breaks, we look for w in s with at
                    // least one char. before and one char. after
\$\endgroup\$
4
  • \$\begingroup\$ Gives incorrect answer on AXB XC, ABC -- the B is in the middle so it isn't a bookend but your code returns true. \$\endgroup\$
    – Value Ink
    Oct 20, 2023 at 19:17
  • \$\begingroup\$ @ValueInk Thank you for reporting this. I misread the spec. Should be fixed. \$\endgroup\$
    – Arnauld
    Oct 20, 2023 at 19:59
  • 1
    \$\begingroup\$ Incorporating the RegEx from @Neil’s Retina answer shortens this to 74 bytes: tio.run/… \$\endgroup\$ Oct 21, 2023 at 11:35
  • \$\begingroup\$ @NickKennedy Very nice! \$\endgroup\$
    – Arnauld
    Oct 21, 2023 at 12:20
2
\$\begingroup\$

R, 77 bytes

\(x,y,`/`=grepl)"^((.+)(.+)) (\\2.*\\3$|.+\\1.)"/paste(y,gsub(" ","",x))&!y/x

Attempt This Online!

A function taking two character arguments and returning a logical value. Inspired by @Neil’s Retina answer so be sure to upvote that one too! The regular expression here is slightly different because of R’s requirement to escape backslashes.

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

Jelly, 19 bytes

Uses some of Unrelated String's answer to Is it a circumfix? saving bytes over using the "outfix quick", ÐƤ.

ḲFŒṖḢ;ṪƊ€;ṖḊẆƊƲḟẆ{i

A dyadic Link that accepts the clue on the left and the answer on the right and yields a positive integer (truthy) if valid or zero (falsey) otherwise.

Try it online! (Some tests have been shortened in the middle since the algorithm is inefficient.)

How?

ḲFŒṖḢ;ṪƊ€;ṖḊẆƊƲḟẆ{i - Link: Clue, Answer
Ḳ                   - split {Clue} on space characters
 F                  - flatten -> Squished
              Ʋ     - last four links as a monad - f(Squished):
  ŒṖ                -   all partitions (no empty parts)
       Ɗ€           -   for each: last three links as a monad - f(Partition):
    Ḣ               -     head (remove first part and yield it)
      Ṫ             -     tail (remove last part of that and yield it ...
                                                ...or integer zero* if nothing left)
     ;              -     concatenate
                         -> Bookends (plus an invalid one with a trailing zero*)
             Ɗ      -   last three links as a monad - f(Squished):
          Ṗ         -     pop (remove the tail character)
           Ḋ        -     dequeue (remove the head character)
            Ẇ       -     all sublists
                         -> Hiddens
         ;          -   {Bookends} concatenate {Hiddens} -> Potential Answers
                Ẇ{  - sublists of {Clue}
               ḟ    - {Potential Answers} filter discard {Clue sublists}
                       -> Valid Answers (plus an invalid bookend with a trailing zero*)
                  i - 1-indexed index of {Answer} in* {Valid Answers} ...
                                                 ...or zero if not found
                      
                       * Integer zero wont match a zero character
\$\endgroup\$
1
\$\begingroup\$

Ruby, 95 bytes

Bookends code is a slight tweak of my old answer to Is it a circumfix?

->s,w{t=s.tr' ','';(t=~/.#{w}./||(1...~-z=w.size).any?{w==t[0,_1]+t[_1-z..]}&&z<t.size)&&!s[w]}

Attempt This Online!

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

J, 52 51 45 bytes

-.@rxin*[e.((]#~#@[>:#\@](-.|."{[),&#)-.&' ')

Attempt This Online!

This approach allows us to avoid treating the two cases of bookends and word breaks as separate:

  • -.@rxin* Not in the unaltered string
  • * And...
  • -.&' ' Remove spaces from haystack
  • #\@] Create the integers 1..n (where n is length of haystack)
  • ,&# Create the integers n and m, the lengths of needle and the haystack. I'll explain why below.
  • -. Remove n and m from 1..n (again, why below). Call this our "rotation list".
  • |."{[ Do every rotation of 1..n in our rotation list. The rotations we are leaving out are precisely the ones where our haystack abuts the left or right side, which are the illegal ones. We now have a matrix, with each row representing a legal rotation.
  • #@[>: In every row, change the numbers 1..m (where m is length of needle) to 1 and the rest to 0, so now we have a matrix of the legal rotations of, eg, 1 1 1 0 0 0 0 0 (if the needle had length 3).
  • ]#~ Now use the rows of legal 0-1 masks to filter the no-spaces input. These represent all possible bookends and word breaks.
  • [e. Is the needle in any of those?

J, 52 bytes

-.@rxin*[((rxin g)+.[e.-~&#(g=.}:@}.)@(]\.)])' '-.~]

Attempt This Online!

Another nice candidate for J's outfix adverb. Reading through other answers I was reminded that this approach is similar to my answer on Is it a cirumfix as well.

  • -.@rxin Does not appear in unaltered string
  • * and...
  • (rxin g) Does appear in the no-spaces ' '-.~] string, after that string has its first and last elements removed g=.}:@}.
  • +. or...
  • -~&#(g=.}:@}.)@(]\.) Matches one of the outfixes (of appropriate length -~&#) after the set of all such outfixes has its first and last elements removed }:@}..
\$\endgroup\$
1
  • \$\begingroup\$ Also 52: -.@rxin*[([e.g@(]\~#)~,-~&#(g=.}:@}.)@(]\.)])' '-.~] \$\endgroup\$
    – Jonah
    Oct 20, 2023 at 21:14
1
\$\begingroup\$

JavaScript (Node.js), 123 bytes

x=>y=>(z=x.split` `.join``,g=i=>z[i]==y[i]?g(i+1):y[i]&&i*z.endsWith(y.slice(i))||eval(`/.${y}./`).test(z))(0)&&!x.match(y)

Try it online!

-1B from noodle man

\$\endgroup\$
1
  • \$\begingroup\$ Save a byte with z=x.split` `.join`` \$\endgroup\$
    – noodle man
    Oct 21, 2023 at 12:12
0
\$\begingroup\$

Charcoal, 32 bytes

‹№θη∨№⁻θ η⊙η∧κ¬∨⌕⁻θ …ηκ⌕⮌⁻θ ⮌✂ηκ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a valid clue, nothing if not. Explanation:

 №                                  Count of
   η                                Input word in
  θ                                 Input clue
‹                                   Is less than
     №                              Count of
         η                          Input word in
       θ                            Input clue
      ⁻                             With spaces removed
    ∨                               Logical Or
           η                        Input clue
          ⊙                         Any index satisfies
             κ                      Current index
            ∧                       Logical And
                  θ                 Input clue
                 ⁻                  With spaces removed
                ⌕                   Does not start with
                     η              Input word
                    …               Truncated to length
                      κ             Current index
               ∨                    Logical Or
                          θ         Input clue
                         ⁻          With spaces removed
                        ⮌           Reversed
                       ⌕            Does not start with
                              η     Input word
                             ✂      Sliced from
                               κ    Current index
                            ⮌       Reversed
              ¬                     Logical Not
\$\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.