12
\$\begingroup\$

Introduction

Consider two strings A and B of the same length L, and an integer K ≥ 0. For the purposes of this challenge, we say that the strings are K-compatible, if there exists a string C of length K such that A is a contiguous substring of the concatenation BCB. Note that A is a substring of BAB, so A and B are always L-compatible (but may also be K-compatible for some other K < L).

Input

Your inputs are two strings of the same positive length, consisting of upper- and lowercase ASCII letters.

Output

Your output shall be the lowest non-negative integer K such that the inputs are K-compatible.

Example

Consider the inputs

A = HHHHHH
B = HHttHH

They are not 0-compatible, because A is not a substring of HHttHHHHttHH. They are also not 1-compatible, because A is not a substring of HHttHH#HHttHH no matter which letter is placed on the #. However, A is a substring of HHttHHHHHHttHH, where C is the two-letter string HH. Thus the inputs are 2-compatible, and the correct output is 2.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

The compatibility condition is symmetric, so swapping the two inputs should not change the output.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

Leaderboard

Here's a Stack Snippet to generate a leaderboard and list of winners by language. To make sure your answer shows up, start it with a header of the form

## Language, N bytes

You can keep old scores in the header by using the strikethrough tags: <s>57</s> will appear as 57.

/* Configuration */

var QUESTION_ID = 78736; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 32014; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (! /<a/.test(lang)) lang = '<i>' + lang + '</i>';
    lang = jQuery(lang).text().toLowerCase();

    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.uniq > b.uniq) return 1;
    if (a.uniq < b.uniq) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/Sites/codegolf/all.css?v=617d0685f6f3">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>

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

Pyth, 16

lhf}QjT,vzvz+k.:

Find the shortest substring of A that when inserted between two copies of B results in a string that contains A.

This could be two bytes shorter if the second line didn't have quotes, but that feels weird?

Test Suite

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

Python 3, 155 168 157 bytes

Total is the length of A. Compare the beginning of A to the end of B and subtract that from total. Compare the beginning of B to the end of A and subtract that from total. Return the absolute value of total unless total is equal to the length, in which case return 0.

def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

Edit: Handle the f("abcdab","cdabcd")==2 case

\$\endgroup\$
  • 3
    \$\begingroup\$ Unfortunately this doesn't work for f("abcdab", "cdabcd") which should be 2. \$\endgroup\$ – Neil Apr 27 '16 at 19:58
  • \$\begingroup\$ @Neil Good catch. I'll add that to the test cases. \$\endgroup\$ – Zgarb Apr 27 '16 at 21:17
  • 1
    \$\begingroup\$ That was unexpected. (Global Twitch Emotes) \$\endgroup\$ – F. George Feb 11 '17 at 23:01
  • \$\begingroup\$ @mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu I was looking at the image and thinking 'This is a nifty debugger idea to use emojis, but I dont see a bug...'. I think that add-on would wreak havoc on this site. \$\endgroup\$ – NonlinearFruit Feb 12 '17 at 2:28
3
\$\begingroup\$

Retina, 49 bytes

.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+
$#4

Try it online! (Slightly modified to run all tests at once.)

The trick is that we need to backtrack over the part of A that we don't find in B, and so far I haven't found a way to do this without rather annoying lookarounds and balancing groups.

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

Jolf, 40 Bytes

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

Try it!

I'm quite new to Jolf, learned a lot while figuring this out. Seems a bit awkward, still could probably could be golfed down further. Even knocked off 2 bytes while writing this explanation.

Explanation:

  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print
\$\endgroup\$
  • \$\begingroup\$ I haven't tried in earnest, and this may be an optimal solution, but I suggest trying to map over ranges. (s0zli will give you an array [0 ... length i] if you wish to try this approach.) \$\endgroup\$ – Conor O'Brien Apr 28 '16 at 22:30
  • \$\begingroup\$ @Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, I'll give that a look... also is there an if command that I jmissed while looking through the documentation/source or is the only option ? with an irrelevant third argument? \$\endgroup\$ – swells Apr 29 '16 at 11:23
  • \$\begingroup\$ ? is the closest to an if there is in Jolf. It's like a ternary if. ?ABCs returns B` if a is true, and C otherwise. \$\endgroup\$ – Conor O'Brien Apr 29 '16 at 11:27
2
\$\begingroup\$

05AB1E, 20 bytes

Code:

õ)²Œ«v¹y¹««²åiyg}})ß

Uses CP-1252 encoding. Try it online!.

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

JavaScript (ES6), 110 bytes

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

Works by slicing ever longer pieces out of the middle of a until they match the two ends of b. The loop is not infinite as it will stop on or before i == a.length.

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