11
\$\begingroup\$

Challenge

The goal of this challenge is to make a function that takes two paragraphs and output a concatenated result with removing the duplicated overlapped lines due to redundancy (but a single copy of the part of overlapped lines should be kept to avoid information loss). Each input paragraph is with the follows specifications.

  • The leading/trailing spaces in each line have been removed.

  • No empty line.

The output merged paragraph follows the rules as below.

  • Input paragraph 2 is concatenated after input paragraph 1

  • If the line(s) from the start of the input paragraph 2 is / are sequenced same (overlapped) as the end of input paragraph 1, just keep single copy of the sequenced duplicated lines.

  • The definition of duplicated lines here:

    • The content in two line should be totally the same, no “partial overlapping” cases need to be considered.

    • The content sequence in two blocks of lines should be totally the same.

Example Input and Output

  • Inputs

    Input paragraph 1 example:

    Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers.
    It's built and run by you as part of the Stack Exchange network of Q&A sites.
    With your help, we're working together to build a library of programming puzzles and their solutions.
    We're a little bit different from other sites. Here's how:
    Ask questions, get answers, no distractions
    This site is all about getting answers. It's not a discussion forum. There's no chit-chat.
    

    Input paragraph 2 example:

    We're a little bit different from other sites. Here's how:
    Ask questions, get answers, no distractions
    This site is all about getting answers. It's not a discussion forum. There's no chit-chat.
    Good answers are voted up and rise to the top.
    The best answers show up first so that they are always easy to find.
    The person who asked can mark one answer as "accepted".
    Accepting doesn't mean it's the best answer, it just means that it worked for the person who asked.
    Get answers to practical, detailed questions
    Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do.
    Not all questions work well in our format. Avoid questions that are primarily opinion-based, or that are likely to generate discussion rather than answers.
    
  • Expected Output

    enter image description here

    The two block of text are the same, so keep single overlapped part after merging.

    enter image description here

    Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers.
    It's built and run by you as part of the Stack Exchange network of Q&A sites.
    With your help, we're working together to build a library of programming puzzles and their solutions.
    We're a little bit different from other sites. Here's how:
    Ask questions, get answers, no distractions
    This site is all about getting answers. It's not a discussion forum. There's no chit-chat.
    Good answers are voted up and rise to the top.
    The best answers show up first so that they are always easy to find.
    The person who asked can mark one answer as "accepted".
    Accepting doesn't mean it's the best answer, it just means that it worked for the person who asked.
    Get answers to practical, detailed questions
    Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do.
    Not all questions work well in our format. Avoid questions that are primarily opinion-based, or that are likely to generate discussion rather than answers.
    

Rules of Challenge

This is . The answer with the least bytes wins.

\$\endgroup\$
17
  • 2
    \$\begingroup\$ Can we take input as a list of lines? \$\endgroup\$ – caird coinheringaahing Jan 22 at 4:06
  • 2
    \$\begingroup\$ Overall this looks to be a good challenge but just for future reference, it's recommended to run challenge ideas through the Sandbox first. That way you can receive feedback and refine the spec before the challenge goes live. \$\endgroup\$ – Dingus Jan 22 at 6:16
  • 1
    \$\begingroup\$ If we have ABDC and CBDC, do we remove a C and then a BDC? If there's multiple choices for what to remove, how do we choose? I think this can lead to different end results. \$\endgroup\$ – xnor Jan 22 at 6:57
  • 1
    \$\begingroup\$ I think by the way that phrasing the challenge in terms of sentences makes the examples harder follow and the statement of the rules more confusing. Just using letters as in tsh's comment seems cleaner. \$\endgroup\$ – xnor Jan 22 at 7:00
  • 1
    \$\begingroup\$ @JimmyHu Ok, so it sounds like I shouldn't be trying to apply the merging rule recursively. Is this right then: we find the longest suffix of the first input that's a prefix of the second input, remove it from one of them, and concatenate, like a Portmanteau? (The prefix and suffix are in terms of the list of lines, so no breaking mid-line.) I think this is also the same as, find the shortest list that contains the first input as a prefix and the second input as a suffix. \$\endgroup\$ – xnor Jan 22 at 8:55

14 Answers 14

7
\$\begingroup\$

Python 3.8 (pre-release), 104 bytes

def o(a,b,i=None):
 while(i:=a[:i].rfind(b[0]))+1:
  if b.find(a[i:])==0:return a[:i]+b
 return a+'\n'+b

Try it online!

I've come up with this as my first ever Code Golf challenge. Defines function o (short for overlay) which returns string a overlayed with string b, or their concatenation if there is no overlap.

It repetitively searches backwards in a for the first letter of b and, if a match is found, compares from that point on in a to the beginning of b until an overlap is found or a has been fully scanned.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Golf. We score the source code in bytes (unless specified otherwise), and using Try It Online! is recommended for demonstrating correctness of your code. Check out other Python answers on other challenges for how to use it effectively. It can also create a post template for you. \$\endgroup\$ – Bubbler Jan 22 at 6:48
  • 2
    \$\begingroup\$ Here is a Try It Online link for your solution, with a few improvements and a bug fix (if there is no overlap, there needs to be a newline in between a and b) \$\endgroup\$ – pxeger Jan 22 at 8:19
  • \$\begingroup\$ @pxeger: thanks for posting to Try It Online and for the bug fix. I'm not sure that intialising i to -1 instead of None is right, but then I have implemented a character based solution not a line based as required. \$\endgroup\$ – mhawke Jan 22 at 10:38
  • 2
    \$\begingroup\$ @Bubbler: thanks, just starting to find my way around here. I am blown away by some of the other solutions... they seem incredible. \$\endgroup\$ – mhawke Jan 22 at 10:40
  • 1
    \$\begingroup\$ @a25bedc5-3d09-41b8-82fb-ea6c353d75ae: Thanks for that. I have taken your +1 instead of ==-1 - that's a pretty clever trick. As for the rest I had to reinstate initialisation of i to None to cover single trailing character overlap, and insert a new line when there is no overlap. \$\endgroup\$ – mhawke Jan 23 at 22:35
2
\$\begingroup\$

Retina 0.8.2, 14 bytes

ms`$(.+)^\1
$1

Try it online! Assumes that neither paragraph will be matched in its entirety. Explanation: The leading $ ensures that the capture begins with a newline, while the inner ^ ensures that it ends with a (possibly the same) newline. It then remains to delete the duplicate.

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

APL+WIN, 19 bytes

Prompts for the second paragraph followed by the first as nested vectors of lines:

(∨⌿<\x^.=⍉x)⌿x←⊃⎕,⎕

Try it online! Thanks to Dyalog Classic

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

05AB1E, 13 bytes

.s€»ʒÅ?}θK¹»ì

First input as a list of lines, second as a multi-line string. (Taking multi-line input as a list of lines is allowed by default.)

Try it online.

Would be 1 byte longer if we can take both inputs as multi-line strings: try it online.
Would be 3 bytes shorter if partial lines could also overlap: try it online.

Explanation:

.s          # Get a list of suffices of the first (implicit) input-list of lines
  €         # Map over each suffix:
   »        #  And join them by newlines
    ʒ       # Then filter of these string-suffices:
     Å?     #  And keep the one that the second (implicit) input-string starts with
    }θ      # After the filter: keep only the last/longest suffix
      K     # Remove this overlapping text from the second (implicit) input-string
       ¹»   # Push the first input-list, and join it by newlines
         ì  # And prepend it to the other string
            # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 52 bytes

I/O format: lists of strings. Expects (b)(a).

b=>g=a=>a.some((s,i)=>b[i]!=s)?[a.shift(),...g(a)]:b

Try it online!

Test cases stolen borrowed from @dingledooper.

Commented

b =>               // anonymous outer function taking the 2nd paragraph b[]
g = a =>           // inner recursive function g taking the 1st paragraph a[]
  a.some((s, i) => // for each line s at position i in a[]:
    b[i] != s      //   truthy if the i-th line of b is not equal to s
  ) ?              // end of some(); if truthy:
    [              //   create an array consisting of:
      a.shift(),   //     the 1st line removed from a[]
      ...g(a)      //     followed by the lines returned by a recursive call
    ]              //   end of array
  :                // else:
    b              //   stop the recursion and return b[]
\$\endgroup\$
2
\$\begingroup\$

Python 2, 59 51 bytes

8 bytes thanks to @ovs

Input is taken as two lists of strings.

f=lambda a,b:`a`[:-1]in`b`and b or[a.pop(0)]+f(a,b)

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Hi, new here but curious. Your solution expects the paragraphs to be supplied as lists of lines, but that's not the spec, it should be strings (I think?). So shouldn't some of your setup code be included in your byte count? \$\endgroup\$ – mhawke Jan 22 at 10:48
  • \$\begingroup\$ @mhawke This is allowed by default. \$\endgroup\$ – Arnauld Jan 22 at 10:55
  • \$\begingroup\$ @Arnauld: OK thanks for that. \$\endgroup\$ – mhawke Jan 22 at 11:07
  • \$\begingroup\$ If you append the last element of b to the result of f(a,b[:-1]), you don't need s: 52 bytes \$\endgroup\$ – ovs Jan 22 at 12:58
  • \$\begingroup\$ And one more byte can be saved if you modify a instead of b: 51 bytes \$\endgroup\$ – ovs Jan 22 at 13:04
2
\$\begingroup\$

Wolfram Language (Mathematica), 32 31 bytes

{a___,d=b___}±{d,c___}={a,b,c}

Try it online!

Defines an operator ± (PlusMinus).

Mathematica's pattern-matching does the entirety of the work here:

{a___,b___}±{b___,c___}=    (* function of two lists, where (b___) a possibly-empty postfix of the first is a prefix of the second: *):
  {a,b,c}                   (* concatenate. *)
\$\endgroup\$
1
  • \$\begingroup\$ I upvoted just because of all the underscores. \$\endgroup\$ – user Jan 22 at 18:44
2
\$\begingroup\$

Perl 5 (-0777p), 20 bytes

s/^(.*
)
\1|^
/$1/ms

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Fails with 0, 1, 2 as first input and 1, 22, 333 as second input. \$\endgroup\$ – Neil Jan 22 at 11:27
  • \$\begingroup\$ @Neil, good catch, fixed \$\endgroup\$ – Nahuel Fouilleul Jan 22 at 17:03
  • \$\begingroup\$ Not entirely sure what behaviour is supposed to be when there are no lines in common, but your answer currently ignores that case. \$\endgroup\$ – Neil Jan 22 at 17:11
  • 1
    \$\begingroup\$ How can one specify the two input paragraphs? If fed with ABABC and CD, this currently deletes the repeated AB within the first paragraph, instead of correctly merging the paragraphs & deleting the overlapping C. Try it... \$\endgroup\$ – Dominic van Essen Jan 22 at 22:15
  • \$\begingroup\$ This issue was introduced when handling of no lines in common fixed now + 4bytes \$\endgroup\$ – Nahuel Fouilleul Jan 23 at 20:33
2
\$\begingroup\$

JavaScript (Node.js), 70 68 bytes

l=(a,b,c)=>b.startsWith(a.slice(c=~~c,-1))?a.slice(0,c)+b:l(a,b,++c)

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf! You might want to check out the tips page for Javascript. Also, I'd recommend using TIO, it can even generate Markdown for you. (I would just add a link with your code pasted in, but it gets too long for a comment) \$\endgroup\$ – user Jan 22 at 15:33
  • 1
    \$\begingroup\$ By the way, in TIO, right next to the button to run, there is a button to copy links. If you click on that, you'll see a few options, and the fifth one will say "Code Golf submission". There's a button on the right to copy the Markdown, and you can paste that here directly without having to write it all yourself. \$\endgroup\$ – user Jan 22 at 15:51
  • 1
    \$\begingroup\$ You can remove the leading var , which is not required. You can replace c=++c||1 with c=-~c. However, I don't think this answer is correct: it removes the last character and crashes if there's no common line at all. (Besides, it works on characters rather than paragraph lines.) \$\endgroup\$ – Arnauld Jan 22 at 16:05
2
\$\begingroup\$

AWK, 28 \$\cdots\$ 85 84 bytes

Added 44 bytes to fix a bug kindly pointed out by Dominic van Essen.
Added another 13 bytes to fix another bug pointed out by Dominic van Essen and JimmyHu.
Saved a byte thanks to cnamejj!!!

$0 in a&&m&&!h{h=a[$0]+1;next}h&&a[$0]==h{++h;next}!NF{m=1;next}!m{a[$0]=++i}{print}

Try it online!

Inputs the two paragraphs separated by an empty line from stdin.

\$\endgroup\$
10
  • \$\begingroup\$ This seems to ignore the order of lines: A,B,C & C,B,D only 'overlap' by 'C', so the output should be A,B,B,D but this outputs A,B,C,D. \$\endgroup\$ – Dominic van Essen Jan 22 at 12:16
  • \$\begingroup\$ @DominicvanEssen Fixed - thanks! :D \$\endgroup\$ – Noodle9 Jan 22 at 14:06
  • 1
    \$\begingroup\$ @JimmyHu Yes, typo by me. \$\endgroup\$ – Dominic van Essen Jan 22 at 17:34
  • 1
    \$\begingroup\$ I think there may still be a problem: ABC & ABCBD should give ABCBD, not ABCBCBD (although the all-in-one input makes it tricky to parse exactly what's going on...) \$\endgroup\$ – Dominic van Essen Jan 22 at 22:09
  • 1
    \$\begingroup\$ @JimmyHu It's good to go now - please check it out! :D \$\endgroup\$ – Noodle9 Jan 23 at 16:54
1
\$\begingroup\$

R, 77 74 71 61 bytes

Edit: -3 bytes and bug-fix thanks to Giuseppe

function(p,q){while(!all(p==(s=c(p[0:F],q))[seq(p)]))F=F+1;s}

Try it online!

Tries increasingly long prefixes of p (first paragraph) and joins q (second paragraph) onto them, until one is found whose first elements are equal to the whole of p (this will always happen when the 'prefix' grows to become the entirity of p, of course).

\$\endgroup\$
4
  • \$\begingroup\$ If input is always a character you can remove the a= but in the meantime, 73 bytes. \$\endgroup\$ – Giuseppe Jan 22 at 17:11
  • \$\begingroup\$ @Giuseppe - Thanks! \$\endgroup\$ – Dominic van Essen Jan 22 at 17:32
  • \$\begingroup\$ should you be using 0:F instead (and incrementing F)? Otherwise it will fail for input of letters[1:3] and letters \$\endgroup\$ – Giuseppe Jan 22 at 18:18
  • \$\begingroup\$ @Giuseppe - Yes, you're right, of course! Thanks again! \$\endgroup\$ – Dominic van Essen Jan 22 at 19:16
0
\$\begingroup\$

Perl 5, 42 bytes

sub f{join($;,@_)=~s,^((.+\n)*)$;\1,$1,mr}

Try it online!

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

Husk, 11 12 bytes

Edit: +1 byte to fix bug (when first paragraph is entirely within second)

ḟoΠz=³m`+⁰Θḣ

Try it online!

ḟ               # return first list that satisfies:
 oΠ             #   all truthy results of
   z=³          #   comparing each element to each element of arg1 
                # from this list:
      m         # for each of
          Θḣ    # the prefixes of arg1, beginning with the empty list,
       `+⁰      # append arg2
\$\endgroup\$
0
\$\begingroup\$

Jelly, 10 bytes

w@ÐƤṣ1Ḣ⁸ṁ;

A dyadic Link accepting lists of lines which yields a list of lines.

Try it online!

How?

w@ÐƤṣ1Ḣ⁸ṁ; - Link: P1, P2
  ÐƤ       - for posfixes, X, of P1:
w@         -   first 1-indexed index of sublist X in P2 (or 0 if not there)
    ṣ1     - split at occurrences of 1
      Ḣ    - head
       ⁸ṁ  - mould P1 like that
         ; - concatenate P2
\$\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.