current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 10 down vote favorite

Strings with Context

For the purposes of this challenge, a string with context is a triple of strings, called the left context, the data part, and the right context. It represents a substring of a longer string. We use the vertical pipe | as a separator, so an example of a string with context is cod|e-go|lf, where the left context is cod, the data is e-go, and the right context is lf. This example represents the substring e-go of code-golf.

Now, to concatenate two strings with context, we proceed as follows, using aa|bcc|dee and cc|de|eee as examples. We align the strings as in the diagram

a a|b c c|d e e
      c c|d e|e e e

so that their data parts are adjacent. The data part of the concatenation is the concatenation of the data parts, in this case bccde. The left context is the part that extends the furthers to the left of the first data part, in this case aa. Similarly, the right context is eee, so the concatenation is the string with context aa|bccde|eee. For a second example, consider a|bb|cd and aabb|cd|, where the second word has a empty right context. The alignment diagram is

  a|b b|c d
a a b b|c d|

where the left context of the second word extends further than that of the first. The concatenation is aa|bbcd|.

But wait, there's a gotcha: if the letters of the alignment diagram don't match, the concatenation doesn't exist! As an example, the diagram of aa|bb|cc and c|c|c is

a a|b b|c c
      c|c|c

where the b and c on the fourth column disagree, so they cannot be concatenated.

The Task

Your job is to write a program that takes in two strings with context whose parts are separated by | as above, and outputs their concatenation if it exists, and something else if not. The "something else" can be any value, including no output, as long as it's not a valid string with context, and it is the same in all cases. However, throwing an error is not acceptable. You can give either a STDIN-to-STDOUT program or a function, and anonymous functions are accepted as well. The smallest byte count wins, and standard loopholes are disallowed.

Test Cases

aa|bcc|dee cc|de|eee -> aa|bccde|eee
a|bb|cd    aabb|cd|  -> aa|bbcd|
a|b|cccd   aab|cc|c  -> aa|bcc|cd
a|b|c      b||cd     -> a|b|cd
aa|bb|cc   c|c|c     -> None
aaa|b|c    abb|cd|d  -> None
|bb|cd     abb|c|ed  -> None
a|b|c      a||cd     -> None
share|improve this question

2 Answers 2

up vote 3 down vote accepted

Haskell, 184 182 201 199

s&t|[x,y,z,a,b,c]<-foldr(?)[[]]$s++'|':t,z#(b++c),r a#r(x++y)=r(y!r a)%x++'|':y++b++'|':b!z%c|0<1=""
r=reverse
l=length
(!)=drop.l
'|'?s=[]:s
c?(a:b)=(c:a):b
(#)a=and.zipWith(==)a
a%b|l a>l b=a|0<1=b

too bad Haskell doesn't have a built-in split function like most languages. I had to define my own myself.

example run:

"|a|"&"|b|" -- returns "|ab|"
"|a|x"&"|b|" -- returns ""

if there isn't a match an empty string will be returned. otherwise the result would be returned.

partial explanation:

foldr(?)[[]] is a function which splits on the char '|'.

# is a function which gets two strings, and returns weather or not they match.

if everything matches, % , which gets two strings and returns the longest of them, is used to calculate the output. the ! function removes from the contexts the part which is matched by the data of the other string so it can be inputted to %.

share|improve this answer
    
Hmm, I'm afraid that throwing an error is not an acceptable output method, especially for a function. Adding |1<2="" to the definition of & should solve that. I'm sorry I didn't specify this more explicitly in the specs, I'll edit it in. –  Zgarb Dec 2 '14 at 11:11
    
@Zgarb Actually, this would not fix it. Is returning a string with too many '|' signs when the strings don't match okay? –  proud haskeller Dec 2 '14 at 12:39
    
Sure, as long as it is the same string for all non-matching inputs. –  Zgarb Dec 2 '14 at 12:43
up vote 3 down vote

Python (242 bytes)

import itertools as i
s='|'
j=''.join
r=reversed
m=lambda a,b:j(j(*set(p+q))for p,q in i.izip_longest(a,b,fillvalue=''))
def c(A,B):
 u,v,w,x,y,z=(A+s+B).split(s)
 try:return j(r(m(r(u+v),r(x))))[:-len(v)]+s+v+y+s+m(w,y+z)[len(y):]
 except:0

Explanation

The lambda function m returns the longer of two strings as long as they share a common prefix. It does this by concatenating the empty string '' in place of any missing values, then turning the result (which may take the forms aa, ab, a, or b in cases of match/mismatch/unequal lengths) into a set of unique characters at each position. join expects a single argument, so unpacking a set with more than one element will cause it to raise a TypeError.

The main function then

  • uses m to combine the left context and data part the first word with the left context of the second (from right to left over reversed strings)
  • concatenates data parts,
  • and again uses m to combine the right context of the first word with the data part and right context of the second

The two original words' data parts are trimmed from the right and left sides of the new contexts.

Since we know that misalignments cause m to raise a TypeError, in these cases we catch the exception and implicitly return None.

Testing

TESTCASES = [
    ('aa|bcc|dee', 'cc|de|eee', 'aa|bccde|eee'),
    ('a|bb|cd', 'aabb|cd|', 'aa|bbcd|'),
    ('a|b|cccd', 'aab|cc|c', 'aa|bcc|cd'),
    ('a|b|c', 'b||cd', 'a|b|cd'),
    ('aa|bb|cc', 'c|c|c', None),
    ('aaa|b|c', 'abb|cd|d', None),
    ('|bb|cd', 'abb|c|ed', None),
    ('a|b|c', 'a||cd', None),
]

for A, B, R in TESTCASES:
    print '{:<10} {:<9} -> {}'.format(A, B, c(A, B))

Output

aa|bcc|dee cc|de|eee -> aa|bccde|eee
a|bb|cd    aabb|cd|  -> aa|bbcd|  
a|b|cccd   aab|cc|c  -> aa|bcc|cd 
a|b|c      b||cd     -> a|b|cd    
aa|bb|cc   c|c|c     -> None      
aaa|b|c    abb|cd|d  -> None      
|bb|cd     abb|c|ed  -> None      
a|b|c      a||cd     -> None
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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