Is it a valid hidden word?

Question

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 code-golf 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

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. — Value Ink, Oct 20 at 18:46
@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. — Wheat Wizard, Oct 20 at 18:48
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. — Value Ink, Oct 20 at 19:01
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? — Greg Martin, Oct 21 at 4:14
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 — Nick Kennedy, Oct 21 at 13:26

Neil · Accepted Answer · 2023-10-20 20:53:49Z

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.

Arnauld · Accepted Answer · 2023-10-21 12:20:06Z

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

Gives incorrect answer on AXB XC, ABC -- the B is in the middle so it isn't a bookend but your code returns true. — Value Ink, Oct 20 at 19:17
@ValueInk Thank you for reporting this. I misread the spec. Should be fixed. — Arnauld, Oct 20 at 19:59
Incorporating the RegEx from @Neil’s Retina answer shortens this to 74 bytes: tio.run/… — Nick Kennedy, Oct 21 at 11:35

Nick Kennedy · Accepted Answer · 2023-10-21 13:54:01Z

2

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.

answered Oct 21 at 13:54

Nick Kennedy

19k3 gold badges16 silver badges40 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2023-10-21 15:46:55Z

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

Value Ink · Accepted Answer · 2023-10-20 18:57:26Z

1

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!

answered Oct 20 at 18:57

Value Ink

12.5k1 gold badge16 silver badges42 bronze badges

Add a comment |

Jonah · Accepted Answer · 2023-10-21 03:49:52Z

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 }:@}..

Also 52: -.@rxin*[([e.g@(]\~#)~,-~&#(g=.}:@}.)@(]\.)])' '-.~] — Jonah, Oct 20 at 21:14

l4m2 · Accepted Answer · 2023-10-21 16:33:18Z

1

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

edited Oct 21 at 16:33

answered Oct 20 at 19:15

l4m2

20.5k2 gold badges19 silver badges85 bronze badges

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

Add a comment |

Neil · Accepted Answer · 2023-10-20 21:43:09Z

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

Stack Exchange Network

Is it a valid hidden word?

Test cases

8 Answers 8

Retina 0.8.2, 41 bytes

JavaScript (ES6), 74 bytes

JavaScript (ES6), 86 bytes

Commented

R, 77 bytes

Jelly, 19 bytes

How?

Ruby, 95 bytes

J, ^{52 51} 45 bytes

J, 52 bytes

JavaScript (Node.js), 123 bytes

Charcoal, 32 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
string
decision-problem
or ask your own question.

Linked

Hot Network Questions

Is it a valid hidden word?

Test cases

8 Answers 8

Retina 0.8.2, 41 bytes

JavaScript (ES6), 74 bytes

JavaScript (ES6), 86 bytes

Commented

R, 77 bytes

Jelly, 19 bytes

How?

Ruby, 95 bytes

J, 52 51 45 bytes

J, 52 bytes

JavaScript (Node.js), 123 bytes

Charcoal, 32 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

J, ^{52 51} 45 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
string
decision-problem
or ask your own question.