22
\$\begingroup\$

In this challenge, you receive a string as input containing a string of X's, Y's and Z's eg. "XYZZ". X, Y and Z represent a particular character. This pattern is then compared with a second string input. If the pattern exists as a substring in the second input, return True, otherwise, return False. Once a pattern is found in the word, the program stops searching and returns True.

Examples

Pattern: "XXYY"

succeed ---> True (pattern found: ccee)
success ---> False (pattern not matched)
balloon ---> True (pattern found: lloo)

Pattern: "XYXYZ"

bananas ---> True (pattern found: nanas)
banana  ---> False (pattern not found)
  • Note: This is not the actual input. This is an example of how the program should work. Your program should output True or False, or other Truthy/Falsy values.

Other important/useful information

  • The pattern does not need to contain an X, Y and a Z, it could contain X's and Y's or even (although somewhat pointless) just X's.
  • The pattern cannot be empty, but this will not be used as a test case.
  • The search string will not be empty, and will be lowercase.
  • The alphabetic order of X, Y and Z in the pattern does not matter.
  • X, Y and Z must be unique characters.
  • You may use any library you wish.
  • The score is determined by the code size, in bytes. Lowest score wins.

Good luck!

\$\endgroup\$
15
  • \$\begingroup\$ The pattern can be anything. I probably should have mentioned that the pattern doesn't have to have an X, Y, and a Z, it could have just an X and a Y. Those patterns are just examples, though, so feel free to come up with your own examples with those patterns. \$\endgroup\$
    – notHalfBad
    Mar 14, 2017 at 9:09
  • \$\begingroup\$ What do you mean "the pattern exists"? As a contiguous chunk? As a substring? Can, say, X and Y stand for the same thing? \$\endgroup\$
    – xnor
    Mar 14, 2017 at 9:09
  • \$\begingroup\$ @xnor X and Y must be independent of eachother, and what I mean by the pattern existing is that anywhere in the string there is a substring that matches the pattern. I will add these to my challenge description to clarify. \$\endgroup\$
    – notHalfBad
    Mar 14, 2017 at 9:11
  • 3
    \$\begingroup\$ Related. (Same thing, but asks for exact matches of the pattern, not for substrings.) \$\endgroup\$ Mar 14, 2017 at 9:14
  • 4
    \$\begingroup\$ More details: Can the pattern be empty? The search string? Will the search string only use lowercase letters? Will the pattern be alphabetically first among equivalent patterns, i.e. use X first then Y then Z? \$\endgroup\$
    – xnor
    Mar 14, 2017 at 9:14

12 Answers 12

12
\$\begingroup\$

Perl 5, 85 bytes

Saved 40 bytes thanks to Peter Taylor's suggestion! (see my older version bellow to see the differences)

83 bytes of code + -pl flag.

s/./$h{$&}?"\\$h{$&}":($h{$&}=$.,join("",map"(?!\\$_)",1..$.++)."(.)")/ge;$_=<>=~$_

Try it online!

XYXYZ is transformed into ((?!\1).)((?!\1)(?!\2).)\1\2((?!\1)(?!\2)(?!\3).) (yup, some of the tests can't be true, but it's shorter that way), and the second input is then checked against that regex. (see the explanations of my older version to get more intuition of how it works)


My older version:
Thanks to Arnauld for pointing out a mistake I made in my first version.
113 bytes of code + -pl flags, and -Mre=eval.

s/./$h{$&}?"\\$h{$&}":($h{$&}=++$i,"(.)")/ge;$_.='(?{++$c;$\=1if!grep$v{$c}{${$_}}++,1..'.(keys%h).'})^';<>=~$_}{

Try it online!

On the example XYXYZ: the first regex will convert the pattern to (.)(.)\1\2(.), and add at the end a test to check if $1, $2 and $3 are different: if so, $\ is set to one. Then, the second input is testes against this regex, and $\ is implicitely printed at the end.
The regex generated for XYXYZ is (.)(.)\1\2(.)(?{++$c;$\=1if!grep{$v{$c}{${$_}}++}1..3})^.
(I'll to add a bit more details to the explanations when I have a moment)

\$\endgroup\$
5
  • \$\begingroup\$ So, Using regex to turn non-regex to regex? coolio \$\endgroup\$ Mar 14, 2017 at 10:04
  • \$\begingroup\$ @Arnauld Indeed, thanks. (I must have read the challenge too fast, my bad). Had to double the bytecount to fix it, but it works now! \$\endgroup\$
    – Dada
    Mar 14, 2017 at 10:50
  • \$\begingroup\$ Would it not be golfier to generate a regex like (.)((?!\1).)\1\2((?!\1)(?!\2).)? \$\endgroup\$ Mar 14, 2017 at 11:19
  • \$\begingroup\$ @Peter Taylor maybe.. I vaguely thought of it, but it seemed harder (read longer) to generate.. I'll have another look when I have a moment. \$\endgroup\$
    – Dada
    Mar 14, 2017 at 11:30
  • \$\begingroup\$ @Peter Taylor nevermind, it's going to be 30 bytes shorter; I'll update that in a bit, thanks :) \$\endgroup\$
    – Dada
    Mar 14, 2017 at 12:16
10
\$\begingroup\$

Jelly, 9 bytes

=þ
ẆÇ€ċÇ}

Returns the number of times the pattern was found, non-zero being truthy and zero being falsy.

Try it online!

How it works

ẆÇ€ċÇ}  Main link. Left argument: s (string). Right argument: p (pattern)

Ẇ       Window; generate all substrings of s.
 ǀ     Map the helper link over the substrings.
    Ç}  Apply the helper link to p.
   ċ    Count the number of times the right result appears in the left result.


=þ      Helper link. Argument: t (string)

=þ      Compare all characters of t for equality with all characters of t, yielding
        a square matrix of Booleans.
\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 94 bytes

f=
(p,s)=>s.match(p.replace(/./g,c=>m[c]||(t=r,r=`(?!\\${++g})`+r,m[c]=`\\`+g,t),g=m=[],r=`(.)`))
<div oninput=o.textContent=!!f(p.value,s.value)><input id=p placeholder=Pattern><input id=s placeholder=String><span id=o>

Works by transforming the pattern into a regexp, e.g. for XYXYZ it generates /(.)(?!\1)(.)\1\2(?!\2)(?!\1)(.)/.

I notice an interesting distinction between PCRE and JavaScript regexp: in PCRE, \<n> fails (and therefore (?!\<n>) succeeds) before the capture group is defined, while JavaScript it succesfully matches the empty string (and therefore (?!\<n>) fails).

\$\endgroup\$
7
\$\begingroup\$

Python 2, 70 bytes

f=lambda p,s:s>''and(map(s.find,s[:len(p)])==map(p.find,p))|f(p,s[1:])

Try it online!

Checks if a string matches a pattern using the method in this answer. Uses a prefix of the search string whose length equals the pattern. Chops off the first character of the string string until a match is found, or False if it becomes empty


73 bytes:

f=lambda p,s:s>''and(map(s.find,s)==map(p.find,p))|f(p,s[1:])|f(p,s[:-1])

Try it online

Checks if a string matches a pattern using the method in this answer. Recursively checks all substrings by branching into removing the first or last character until the string is empty.

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

Python 3, 100 bytes

l=len
f=lambda p,s:l(p)<=l(s)and(l({*zip(p,s)})==l({*p})==l({s for _,s in{*zip(p,s)}})or f(p,s[1:]))

Try it online!

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 19 16 bytes

ÙœJv¹y…XYZ‡²åi1q

Try it online!


ÙœJ              # Get powerset of all unique characters in string.
   v             # Loop through each...
    ¹            # Push input word.
     y           # Push current set of letters in powerset.
      …XYZ‡      # Replace each of the 3 letters in the original word with XYZ.
           ²å    # Check if second input is in this string, push 1 if it is.
             i1q # If 1, push 1 and quit.

Will return 1 if true, null if not true.


This can be 14 bytes if returning the possible values of XYZ is allowed:

05AB1E, 14 bytes

ÙœJv¹y…XYZ‡²å—

Try it online 2!

\$\endgroup\$
4
  • \$\begingroup\$ Assuming that a non-empty string is truthy in 05AB1E and that an empty one is falsy, your second version should comply with the spec. \$\endgroup\$
    – Dennis
    Mar 14, 2017 at 20:49
  • 1
    \$\begingroup\$ Wrong result on input "abcd" and "XYZZ". You need to add a fourth letter as a default substitution. \$\endgroup\$
    – G B
    Mar 15, 2017 at 9:43
  • \$\begingroup\$ @Dennis: If we go by the meta post the only truthy values in 05AB1E is 1 and True (which is usually a drawback for these kinds of challenges), but if the challenge spec can be interpreted as allowing us to define truthy/falsy for the challenge the second version works as you say. \$\endgroup\$
    – Emigna
    Mar 15, 2017 at 13:06
  • \$\begingroup\$ @Emigna Oh, I was unaware of that. \$\endgroup\$
    – Dennis
    Mar 15, 2017 at 13:10
4
\$\begingroup\$

Java 7, 177 176 173 bytes

Object c(String p,String s){int i=p.length();if(s.length()<i)return 0>1;for(;i-->0;)if(p.indexOf(p.charAt(i))!=s.indexOf(s.charAt(i)))return c(p,s.substring(1));return 1>0;}

Explanation:

Object c(String p, String s){                             // Method with two String parameters and Object return-type
  int i = p.length();                                     //  Index that starts at the length of the pattern
  if(s.length() < i)                                      //  If the length of the input is smaller than the length of the pattern
    return 0>1;//false                                    //   Simply return false
  for(;i-->0;)                                            //  Loop from 0 to length_of_pattern
    if(p.indexOf(p.charAt(i)) != s.indexOf(s.charAt(i)))  //   If the index of the characters of the pattern and input aren't matching
     return c(p, s.substring(1));                         //    Return the recursive-call of pattern and input minus the first character
                                                          //  End of loop (implicit / single-line body)
  return 1>0;//true                                       //  If every index of the characters are matching: return true
}                                                         // End of method

Test code:

Try it here.

class M{
  static Object c(String p,String s){int i=p.length();if(s.length()<i)return 0>1;for(;i-->0;)if(p.indexOf(p.charAt(i))!=s.indexOf(s.charAt(i)))return c(p,s.substring(1));return 1>0;}

  public static void main(String[] a){
    System.out.println(c("XXYY", "succeed"));
    System.out.println(c("XXYY", "success"));
    System.out.println(c("XXYY", "balloon"));

    System.out.println(c("XYXYZ", "bananas"));
    System.out.println(c("XYXYZ", "banana"));
  }
}

Output:

true
false
true
true
false
\$\endgroup\$
4
\$\begingroup\$

PHP, 89 Bytes

A Gift from @Christoph and @Titus

for(;$v=$argv[1][$i++];)$r.=$$v?"\\".$$v:"(.)".!$$v=++$j;echo preg_match("#$r#",$argv[2]);

PHP, 105 Bytes

A Gift from @Christoph

foreach(str_split($argv[1])as$v)$r.=$x[$v]?"\\$x[$v]":"(.)".!$x[$v]=++$y;echo preg_match("#$r#",$argv[2]);

PHP, 167 Bytes

[,$a,$b]=$argv;foreach($s=str_split($a)as$v)$r[]=$k++>strpos($a,$v)?"\\".(1+array_search($v,array_keys(array_count_values($s)))):"(.)";echo preg_match(_.join($r)._,$b);
\$\endgroup\$
8
  • 1
    \$\begingroup\$ You should be able to save 2 bytes by using ++$p instead of ($p+1), though I haven't actually tested it. \$\endgroup\$
    – user59178
    Mar 14, 2017 at 14:26
  • 1
    \$\begingroup\$ Doesn't work for me: Sandbox. Anyway a golfed version of the code: [,$a,$b]=$argv;foreach(str_split($a)as$k=>$v)$r.=$k==($p=strpos($a,$v))?"(.)":"\\".++$p;echo preg_match("#$r#",$b);. \$\endgroup\$
    – Christoph
    Mar 14, 2017 at 15:54
  • 1
    \$\begingroup\$ Take this as a gift: [,$a,$b]=$argv;foreach(str_split($a)as$v)$r.=$x[$v]?"\\$x[$v]":'(.)'.!$x[$v]=++$y;echo preg_match("#$r#",$b); (Note that you should keep your old scores using <strike>) \$\endgroup\$
    – Christoph
    Mar 14, 2017 at 20:19
  • 1
    \$\begingroup\$ @Christoph A Gift was the learning effort with the ! . It is more worth then the points that I could reach with your nice solution. \$\endgroup\$ Mar 14, 2017 at 20:54
  • 1
    \$\begingroup\$ I count 109, not 108. -3 bytes if you don´t copy $argv to $a and $b; -6 bytes with for(;a&$v=$argv[1][$i++];); -1 byte with longer variable names (indeed!: Use $vv instead of $v, $ii instead of $i, $rr instead of $r, $yy instead of $y and you can use $$vv instead of $x[$v]) \$\endgroup\$
    – Titus
    Mar 15, 2017 at 5:42
4
\$\begingroup\$

C#, 184 165 155 bytes

thanks aloisdg!

bool c(string p,string n){for(int l=p.Length,i=0,j;i<l;i++)for(j=i;j>=0;)if(p[i]==p[j]==(n[i]!=n[j--]))return l!=n.Length&&c(p,n.Substring(1));return 2>1;}

backtracking solution, as a bonus it works with a pattern with any characters!

    public static bool c(string p,string n)
    {
        for (int l = p.Length, i = 0, j; i < l; i++)
            for (j = i; j >= 0;)
                if (p[i]==p[j]==(n[i]!=n[j--]))
                    return l != n.Length && c(p,n.Substring(1));
        return 2>1;
    }
\$\endgroup\$
5
  • \$\begingroup\$ i just noticed golfing it exposed logic i didnt use, will update soon \$\endgroup\$ Mar 14, 2017 at 14:51
  • 2
    \$\begingroup\$ First of all, why the var s=l==n.Length;? You only use it at return s?!s: (where !s is always false), so it can be changed to return l==n.Length?0>1:. Also, what is this: (n[i]!=n[j]||n[i]!=n[j]). You check n[i]!=n[j] twice.. This will always be true or true / false or false.. :S \$\endgroup\$ Mar 14, 2017 at 16:09
  • \$\begingroup\$ The double check actually left over from a bigger if system that disappeared in golfing, so s was used alot, i wil improve it further. Thanks! \$\endgroup\$ Mar 14, 2017 at 16:22
  • \$\begingroup\$ You can decalre all your variable in one line int l = p.Length,i = 0, j; \$\endgroup\$
    – aloisdg
    Mar 15, 2017 at 17:28
  • \$\begingroup\$ Can move your i++ and your j-- inside the for loop. for example: for(j=i;j>=0;)if(p[i]==p[j]==(n[i]!=n[j--])) \$\endgroup\$
    – aloisdg
    Mar 15, 2017 at 17:29
3
\$\begingroup\$

Ruby, 63 61 bytes

->a,b{a.chars.permutation.any?{|w|a.tr((w|[])*'','XYZW')[b]}}

Instead of searching for a regex pattern, just try substituting 'X','Y' and 'Z' in all possible ways, and find a literal match.

(Actually the same concept as carusocomputing's 05AB1E answer)

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

JavaScript (ES6), 92 89 87 86 bytes

Takes input p (pattern) and s (string) in currying syntax (p)(s). Returns 0 / 1.

p=>g=s=>s&&g(s.slice(1))|[...p].every((C,i,x)=>C==(x[c=s[i]]=x[c]||'XYZ'[c&&j++]),j=0)

Formatted and commented

p =>                             // main function: takes pattern p as input, returns g
  g = s =>                       // g = recursive function: takes string s as input
    s &&                         // if s is not empty:
      g(s.slice(1))              //   do a recursive call, starting at the next character
    |                            // merge the result with this iteration
    [...p].every((C, i, x) =>    // for each character C at position i in p:
      C ==                       //   check whether C is matching the next expected
      (                          //   character, which is either:
        x[c = s[i]] = x[c] ||    //   - a substitution character already associated to s[i]
        'XYZ'[c && j++]          //   - the next substitution character ('X', 'Y' or 'Z')
      ),                         //   - undefined if c = s[i] doesn't exist or j > 2
      j = 0                      //   initialize j = pointer in 'XYZ'
    )                            //

Test cases

let f =

p=>g=s=>s&&g(s.slice(1))|[...p].every((C,i,x)=>C==(x[c=s[i]]=x[c]||'XYZ'[c&&j++]),j=0)

console.log(f("XXYY")("succeed"))   // 1
console.log(f("XXYY")("success"))   // 0
console.log(f("XXYY")("balloon"))   // 1
console.log(f("XYXYZ")("bananas"))  // 1
console.log(f("XYXYZ")("banana"))   // 0

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

Mathematica 18 characters (not counting string & pattern)

StringContainsQ[string,pattern]

Examples:

StringContainsQ["succeed", x_ ~~ x_ ~~ y_ ~~ y_]

True

StringContainsQ["bananas", x_ ~~ y_ ~~ x_ ~~ y_ ~~ z_]

True

\$\endgroup\$
1
  • \$\begingroup\$ This is invalid because it doesn't take the string and pattern as string inputs as required. \$\endgroup\$
    – lirtosiast
    Jul 12, 2019 at 17:04

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.