20
\$\begingroup\$

A marquee is a low-tech board that allows customizable letters. For example, here is a marquee:

SALE ON SNEAKERS

However, someone might come along and vandalize it by removing letters to send a different message:

S     N    AKE

Given two non-empty string inputs, an original message and a new message, determine whether the new message can be created by removing characters from the original message. Spaces left by removal can be compressed, as above, or left in, as in the becoming t e by removing the h. Both messages will only contain letters and spaces, case is up to you.

Test Cases

"the", "the" -> true
"the", "t e" -> true
"the", "te" -> true
"te", "t e" -> false
"then i walked", "the" -> true
"then i walked", "niald" -> true
"abcde", "abj" -> false
"a b c d e", "abcde" -> true
"y today", "yt" -> true
"sale on sneakers", "snake" -> true
"today", "toad" -> false
"today", "tyy" -> false
"the sale on sneakers", "t e snake" -> true
"this is a sign", "th s i  a s  n" -> true
"the sale on sneakers", "the salon sneakers" -> true
"the sale on sneakers", "the sal  on sneakers" -> true
"a   b   c", "abc" -> true
"a   bc", "a  b  c" -> false
"a   b   c", "a       c" -> true
"a   b   c", "a        c" -> false
"the", " the" -> false
"the", " h " -> true
"the", "h" -> true
\$\endgroup\$
13
  • 3
    \$\begingroup\$ @cairdcoinheringaahing in this challenge, removed letters leave spaces that create different outputs than that problem. \$\endgroup\$
    – Stephen
    Jan 2 at 23:49
  • 2
    \$\begingroup\$ In which case, I'd recommend adding some test cases where that's clear. So far, only the "the", "t e" is different. And even with the spaces, it just means that this is a superset of the linked challenge, as so is still a dupe (my VTC still stands) \$\endgroup\$ Jan 2 at 23:52
  • \$\begingroup\$ Can strings have multiple consecutive spaces? \$\endgroup\$
    – xnor
    Jan 2 at 23:59
  • 2
    \$\begingroup\$ Is this right: we're checking if we can take the first string and do some repeated combinations of removing a letter and replacing a letter with a space, to make the second string? \$\endgroup\$
    – xnor
    Jan 3 at 0:31
  • 1
    \$\begingroup\$ @EasyasPi added \$\endgroup\$
    – Stephen
    Jan 4 at 17:32

19 Answers 19

12
\$\begingroup\$

Brachylog, 7 bytes

{|∧Ṣ}ᵐ⊇

Try it online!

I should not be surprised to learn that it's considerably faster if I put the at the end. Takes the original marquee through the input and the target through the output.

{   }ᵐ     The input variable, with each element
 |         possibly
  ∧Ṣ       replaced by a space,
      ⊇    has the output variable as a subsequence.

Can also go the other way around, for another two bytes: {|Ṣ∧l₁}ᵐ⊆

\$\endgroup\$
0
8
\$\begingroup\$

J, 25 bytes

rxin~[:,'.*',"#:rplc&' .'

Try it online!

Note: TIO link not working because it's an older version of J, but this works locally for me on J901

  • rxin~ ... The whole verb is dyadic J hook, asking if the right argument, after being transformed by the ... phrase, is a regex match in the left argument.
  • rplc&' .' The transformation of the right arg (the leftover marquee letters) first replaces all spaces with a ., since a space has to match something.
  • [:,'.*',"#: This phrase simply inserts .* between each of the letters, so that we match "removed and collapsed letters" too. It works by zipping ,. the string '.*' with each character of the right arg, and then flattening the result [:,.
\$\endgroup\$
7
\$\begingroup\$

Python 3.8, 50 46 bytes

lambda a,b:''in[b:=b[b[:1]in' '+c:]for c in a]

Try it online!

The code is simply a modification of @xnor's answer to a similar challenge: Is string X a subsequence of string Y?

\$\endgroup\$
6
\$\begingroup\$

Scala, 54 bytes

_./:(Set(""))(for(p<-_;c=_;q<-Seq(""," ",c))yield p+q)

Try it online! (The output says true when a test passes, it prints false and throws an exception otherwise).

Times out for the later inputs, but appears to work otherwise.

Input is curried. First it takes the original message, and returns a Set[String] containing possible messages. However, the Set also acts like a String => Boolean, so it accepts the new message as its second input.

_./:(        //Fold over original message
  Set("")    //Accumulator will eventually hold all possible messages
)(           //Cartesian-product-ish for comprehension
  for(
    p <- _   //For every possible message p already in the accumulator
    c = _    //Current character
    q <- Seq( //Sequence of possible cases:
      "",     //Delete the character, don't keep a space
      " ",    //Delete the character, leave a space
      c       //Keep the character
    )
  ) yield p + q //Add each case q to p
)
\$\endgroup\$
2
  • \$\begingroup\$ Yeah, I got confused by the test driver, sorry. I didn't realize it was testing against the test condition itself. \$\endgroup\$
    – EasyasPi
    Jan 5 at 3:15
  • 1
    \$\begingroup\$ Oh, yeah, I should probably have added that as a comment. \$\endgroup\$
    – user
    Jan 5 at 4:07
5
\$\begingroup\$

Wolfram Language (Mathematica), 26 23 bytes

FreeQ[#|" "|___?h&/@#]&

Try it online!

Input two lists of characters, curried, as f[original][new]. Returns False if the target can be reached, and True if it cannot.

Quite slow.

Normally ___ matches any sequence of zero or more elements. When subject to ? (PatternTest), it only matches if the test yields True for all elements of the sequence; since the test h is undefined, this only occurs when the sequence is empty.

                  /@#   (* if each letter of the original message*)
      #|" "|___?h&      (*  is still present, changed to a space, or missing *)
FreeQ[               ]& (* check that this does not describe the new message *)
\$\endgroup\$
5
\$\begingroup\$

Haskell, 43 bytes

(a:b)!(c:d)=b!([c|a/=c,c>' ']++d)
_!y=y==[]

Try it online!

This is just a modified version of the Levenshtein distance calculation. Instead of normal edits our permitted edits are:

  • Remove a character from string \$a\$
  • Replace a character from string \$a\$ with space.

I use one clever-ish trick. Because two cases only differ by whether the head is maintained, we can use a list comprehension to create the two cases in situ.

So

(a:b)!(c:d)|a/=c&&c>' '=b!(c:d)|1>0=b!d

(this could be shorter anyway but I've structured it like this for illustrative purposes)

becomes

(a:b)!(c:d)=b!([c|a/=c,c>' ']++d)
\$\endgroup\$
4
\$\begingroup\$

Perl 5 -pl, 26 bytes

y/ /./;s//.*/g;$_=<>=~/$_/

Try it online!

Takes the new resulting message first, followed by the original message, on separate lines.

\$\endgroup\$
1
  • \$\begingroup\$ Nice! I just came up with basically the same answer, except that you can drop the /s around $_ for -2! I was hoping there might be a way to match against the return from y/// or s///... Took me a minute to realise why it wasn't working... :P \$\endgroup\$ Jul 9 at 15:57
4
\$\begingroup\$

Jelly, 20 19 bytes

ßḢxn⁶anʋ¥@Ḣ};ʋɗṆ}ȧ?

Try it online!

Dyadic link that takes the original string as the left argument and the new string as the right argument. Uses something similar to @WheatWizerd's modified Levenstein algorithm, so it's very fast, unlike a brute force solution.

Explanation

I admit this explanation is more confusing that the code itself.

ßḢxn⁶¥anʋ@Ḣ};ʋɗṆ}ȧ?   Main dyadic link
                  ?   If
                 ȧ    both strings are non-empty
              ɗ       then (
ß                       Recursively apply this link to the left string
             ʋ          and to (
 Ḣ                        First character of the left string, removing it from the string
          Ḣ}              First character of the right string, removing it from the string
        ¥                 Apply this dyad to them
         @                in reverse (
  x                         Repeat the left character
       ʋ                    this many times (
   n⁶                         Is the left character not a space?
     a                        And
      n                       are the characters not equal?
       ʋ                    )
        ¥                 )
            ;             Join the result with the right string
             ʋ          )
              ɗ       )
               Ṇ}     else return the logical negation of the right string
\$\endgroup\$
4
\$\begingroup\$

C (gcc), 55 51 bytes

f(char*a,char*b){for(;*a;)*a++-*b&*b-32||b++;b=*b;}

Try it online!

-Saved 4 thanks to @Davide

  • Output 0 if can be vandalized, truth if not.

  • we iterate Marquee(a) until end of one of the two inputs : we increment result(b) if current letters are equal or if we need a space. Finally we return *b which is \0 if compatible

\$\endgroup\$
3
  • \$\begingroup\$ 51 bytes \$\endgroup\$ Jan 22 at 1:28
  • \$\begingroup\$ Or if you want even this one where the logic of the code is more explicit \$\endgroup\$ Jan 22 at 1:46
  • 1
    \$\begingroup\$ @Davide nice one! Thanks! \$\endgroup\$
    – AZTECCO
    Feb 1 at 9:09
4
\$\begingroup\$

K (ngn/k), 26 bytes

-3 bytes by converting to tacit form

{(1_t_x;!0)@^t:(x?y)*~^y}/

Try it online!

Returns !0 if the marquee can't be vandalized, and some sort of string if it can be. To better standardize the output, ~(!0)~ can be inserted at the start of the function, i.e. {~(!0)~x{(1_t_x;!0)@^t:(x?y)*~^y}/y}.

  • {...}/ use a reduction, seeded with the original marquee text, running over the text to test
  • ~^y check if the current character in the input to test is not " ". (" " is the null character, so we can test this by using ~^, i.e. not null)
  • * multiply this by...
  • (x?y) the index of the first match in the (remaining) marquee text. This will return 0N (also a null) if the character is not present. 0N*1 remains 0N, whereas 0N*0 results in 0.
  • t: store this in variable t
  • (...)@^t index into the list, using whether or not t is null. If it is null, the second item will be selected. If it is not null, it'll be the first item.
  • (1_t_x;!0) !0 here is a sentinel value, used to indicate that the test text is invalid (because it contains at least one invalid character, or is too long, etc etc.). t_x drops t characters from the beginning of the (remaining) marquee text. To make sure the modified test text lines up, we always want to remove at least one character, hence the 1_.
\$\endgroup\$
3
\$\begingroup\$

Retina, 24 bytes

~(0G`
.
[ $&]?
^
$¶
$
$$

Try it online! Takes newline-separated input, but link includes test suite that converts from comma-separated input on newline-separated test cases. Explanation:

~(`

Interpret the output of the rest of the program as a program (specifically a Count stage) and execute that on the original input.

0G`

Keep the original marquee.

.
[ $&]?

Replace each character with an optional character class of itself or space.

^
$¶
$
$$

Anchor the list of character classes to ensure that the match starts at the beginning of the vandalised marquee and ends at the end of the input.

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

Ruby, 38 bytes

->o,s{o[/#{s.tr(" ",?.).chars*".*"}/]}

Try it online!

Outputs a string for truthy values, otherwise nil for falsey.

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

Python 3, 79 \$\cdots\$ 73 70 bytes

Saved a byte thanks to Jonah!!!
Saved 3 bytes thanks to dingledooper!!!
Saved 2 bytes thanks to caird coinheringaahing!!!
Saved 3 bytes thanks to Arnauld!!!

lambda m,v:match(sub(*' .',sub('(^|\S)',r'\1.*',v)),m)
from re import*

Try it online!

Returns a truthy value if the new message can be created by removing characters from the original message or None otherwise.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ You should be able to replace .+ with . \$\endgroup\$
    – Jonah
    Jan 3 at 0:47
  • 1
    \$\begingroup\$ @Jonah Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Jan 3 at 0:53
  • \$\begingroup\$ 75 bytes \$\endgroup\$ Jan 3 at 1:32
  • \$\begingroup\$ @dingledooper Very nice - thanks! :D \$\endgroup\$
    – Noodle9
    Jan 3 at 1:36
  • \$\begingroup\$ -2 bytes. For once, import* is actually helpful \$\endgroup\$ Jan 3 at 2:01
3
\$\begingroup\$

Python 3, 69 89 86 bytes

def p(s,v,a=1):
 for c in v:_,x,s=s.partition(c);a*=c==x;s=(s," "+s)[x!=" "]
 return a

Try it online!

Dropped to 86 thanks to Danis

I haven't posted just a function before, but I think that's allowed for this one from reading the description? This returns 1|0 not True|False so I'll have to add a few more bytes if that's a requirement.

It just relies on the partition call to throw away characters from the front of the original string. And if the next character in the "vandalized" string isn't found the a*=c==x statement zeros out the accumulated answer.

Sadly... I missed the rule that when a character is replaced, it can match a blank the comes after it in the "vandalized" string. Accommodating that added more code.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can usually return any two district values representing True or False so using their direct integer mappings of \$1\$ and \$0\$ is fine. \$\endgroup\$
    – Noodle9
    Jan 3 at 16:42
  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$
    – Danis
    Jan 3 at 16:55
  • 1
    \$\begingroup\$ This seems to fail one of the new tests. \$\endgroup\$
    – EasyasPi
    Jan 4 at 19:56
  • \$\begingroup\$ Thanks for the heads up.. I'll check it out. \$\endgroup\$
    – cnamejj
    Jan 5 at 21:29
  • \$\begingroup\$ Yeah, leading spaces break the code... annoying, I'll work on a fix. \$\endgroup\$
    – cnamejj
    Jan 7 at 3:03
3
\$\begingroup\$

Charcoal, 24 bytes

≔⪪⮌S¹θUMS∧∧θ№⁺ ι§θ±¹⊟θ¬θ

Try it online! Link is to verbose version of code. Takes input as the new and original messages and outputs a Charcoal boolean, i.e. - if the transformation is possible, nothing if not. Inspired by my answer to Speed of Lobsters. Explanation:

≔⪪⮌S¹θ

Get the new message and reverse it and split it into characters (so we can pop from the list).

UMS∧∧θ№⁺ ι§θ±¹⊟θ

Loop over the original message, and pop the next character from the new message if it is a space or the next character from the original message.

¬θ

Check whether the list is now empty.

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

Bash + coreutils, 53 51 bytes

grep -q `sed -E 's/ /./g;s/(.)/.*\1.*/g'<<<$2`<<<$1

Try it online!

Rough port of Jonah's J answer using regex, I am sure there is a better way.

Takes two strings as arguments in the order of the test cases.

Exit code is 0 for a match, 1 for a mismatch.

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

R, 105 104 bytes

function(a,b){for(x in el(strsplit(gsub(" ",".",b),""))){c=sub(paste0(".*?",x),"",a);if(a==c)T=F;a=c};T}

Try it online!

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

05AB1E, 22 14 bytes

v¬DyQsðQ~i¦]õQ

First input is the original message, second input the new message.

Modification of my 05AB1E answer for the Speed of Lobsters challenge (thanks @Neil for the tip, resulting in -8 bytes).

Try it online or verify a few more test cases.

Explanation:

v            # Loop over the characters `y` of the (implicit) input original_message:
 ¬           #  Get the first character without popping the string
             #  (which uses the implicit input new_message the first iteration)
  D          #  Duplicate this first character
         i   #  If
   yQ        #  this first character is equal to the current character `y`
        ~    #  OR
     sðQ     #  this first character is a space:
          ¦  #   Remove this first character from the new_message
]            # Close both the if-statement and loop
 õQ          # And check if the new_message is now empty
             # (after which the result is output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It occurred to me that this challenge is somewhat similar to Speed of Lobsters, which prompted me to adapt my Charcoal answer for this challenge. Could you do the same sort of thing perhaps? \$\endgroup\$
    – Neil
    Jan 21 at 22:56
  • \$\begingroup\$ @Neil Thanks for the tip, that indeed saved 8 bytes! :) \$\endgroup\$ Jan 22 at 8:04
1
\$\begingroup\$

Raku, 62 bytes

->\a,\b {a~~/<{join ".*",map {" "eq$_??"."!!"'$_'"},b.comb}>/}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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