September 2, 2016 9:00 AM
I took this exercise from a blog on C programming, and the solution was a fearsome recital of pointer manipulation, with the sense of the pointers reversed as they marched down the lists in parallel (the author gave some reason for not marching down the lists one at a time, but it didn’t make sense to me), and auxiliary pointers to something (I never figured that part out, but I’ll admit I didn’t try very hard). It reminded me why I don’t like C.
The solution is very simple. Reverse both lists, then scan them backwards from the end until they differ:
(define (merge-point xs ys)
(let loop ((xs (reverse xs)) (ys (reverse ys)) (zs (list)))
(cond ((or (null? xs) (null? ys))
(values (reverse xs) (reverse ys) zs))
((equal? (car xs) (car ys))
(loop (cdr xs) (cdr ys) (cons (car xs) zs)))
(else (values (reverse xs) (reverse ys) zs)))))
Since the consequents of the first and third cond clauses are the same, you could combine them if you want. Here are some examples:
> (merge-point '(1 2 3 7 8 9) '(4 5 6 7 8 9)) (1 2 3) (4 5 6) (7 8 9) > (merge-point '(1 2 3) '(4 5 6)) (1 2 3) (4 5 6) () > (merge-point '(3 4 5) '(1 2 3 4 5)) () (1 2) (3 4 5) > (merge-point '(1 2 3) '(1 2 3)) () () (1 2 3)
You can run the program at http://ideone.com/9mf8zf.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
Here’s a solution in Java.
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class MergePoint { public static class Result<T> { public List<T> prefix1 = new ArrayList<>(); public List<T> prefix2 = new ArrayList<>(); public List<T> suffix = new ArrayList<>(); } public static <T> Result<T> merge_point(List<T> l1, List<T> l2) { Result<T> result = new Result<>(); int suffix_len = 0; while (true) { int index1 = l1.size() - 1 - suffix_len; int index2 = l2.size() - 1 - suffix_len; if (index1 < 0 || index2 < 0) break; if (!l1.get(index1).equals(l2.get(index2))) break; ++suffix_len; } for (int i = 0; i < l1.size() - suffix_len; ++i) result.prefix1.add(l1.get(i)); for (int i = 0; i < l2.size() - suffix_len; ++i) result.prefix2.add(l2.get(i)); for (int i = l1.size() - suffix_len; i < l1.size(); ++i) result.suffix.add(l1.get(i)); return result; } public static void main(String[] args) { List<Character> l1 = new ArrayList<>(); Collections.addAll(l1, 'a', 'b', 'c', 'x', 'y', 'z'); List<Character> l2 = new ArrayList<>(); Collections.addAll(l2, 'g', 'h', 'i', 'x', 'y', 'z'); Result<Character> result = merge_point(l1, l2); System.out.print("List 1 Unique Prefix\n" + result.prefix1 + "\n\n"); System.out.print("List 2 Unique Prefix\n" + result.prefix2 + "\n\n"); System.out.print("Common Suffix\n" + result.suffix + "\n"); } }Output:
By Daniel on September 2, 2016 at 4:48 PM
Here is one for Julia (0.000088 sec to execute, applying a total of 64 memory allocations).
function main{T = ny
x, y = x_, y_
else
x, y = y_, x_
nx, ny = ny, nx
end
dn = ny – nx # negative difference of lengths
for i = (nx – ny + 1):(nx – 1)
j = dn + i
if all(x[i:end] .== y[j:end])
return x[1:(i-1)], y[1:(j-1)], x[i:end]
end
end
return x_, y_, Array(T, 0)
end
This code is optimized for unequal lists, although it works quite fast on equal ones too. As usual, no external libraries were used.
By Zack on September 2, 2016 at 6:04 PM
For some reason the code didn’t paste properly. Here it is again, this time on a .png file: https://app.box.com/s/0fhupoyexwx26dv6trb7ud8mgs30ntz9
By Zack on September 2, 2016 at 6:11 PM
In Common Lisp :
(defun merge-point (lst1 lst2) (let ((res (merge-point-helper (reverse lst1) (reverse lst2) nil))) (list (nreverse (car res)) (nreverse (cadr res)) (caddr res)))) (defun merge-point-helper (lst1 lst2 common) (if (or (null lst1) (null lst2)) (list lst1 lst2 common) (if (equal (car lst1) (car lst2)) (diverge-point (cdr lst1) (cdr lst2) (cons (car lst1) common)) (list lst1 lst2 common))))A few tests:
By Jérôme Radix (@_jradix_) on September 2, 2016 at 8:27 PM
An error in my last comment, the code is :
(defun merge-point (lst1 lst2) (let ((res (merge-point-helper (reverse lst1) (reverse lst2) nil))) (list (nreverse (car res)) (nreverse (cadr res)) (caddr res)))) (defun merge-point-helper (lst1 lst2 common) (if (or (null lst1) (null lst2)) (list lst1 lst2 common) (if (equal (car lst1) (car lst2)) (merge-point-helper (cdr lst1) (cdr lst2) (cons (car lst1) common)) (list lst1 lst2 common))))By Jérôme Radix (@_jradix_) on September 2, 2016 at 8:35 PM
In Python3.
from itertools import zip_longest def merge_point(a, b): ita, itb = reversed(a), reversed(b) suffix, prefixa, prefixb = [], [], [] for x, y in zip_longest(ita, itb): if x != y: if x: prefixa.append(x) if y: prefixb.append(y) break else: suffix.append(x) prefixa += ita prefixb += itb return prefixa[::-1], prefixb[::-1], suffix[::-1] r5 = [1, 2, 3, 4, 5] tests = [(r5, [6, 7, 3, 4, 5]), ([1, 2, 3, 4, 8], [6, 7, 3, 4, 5]), (r5, r5), (r5, [3, 4, 5]), ([3, 4, 5], r5), ([1, 3, 4, 5], r5) ] for t in tests: print("input:{:40s} output:{:s}".format(str(t), str(merge_point(*t)))) """ input:([1, 2, 3, 4, 5], [6, 7, 3, 4, 5]) output:([1, 2], [6, 7], [3, 4, 5]) input:([1, 2, 3, 4, 8], [6, 7, 3, 4, 5]) output:([1, 2, 3, 4, 8], [6, 7, 3, 4, 5], []) input:([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]) output:([], [], [1, 2, 3, 4, 5]) input:([1, 2, 3, 4, 5], [3, 4, 5]) output:([1, 2], [], [3, 4, 5]) input:([3, 4, 5], [1, 2, 3, 4, 5]) output:([], [1, 2], [3, 4, 5]) input:([1, 3, 4, 5], [1, 2, 3, 4, 5]) output:([1], [1, 2], [3, 4, 5]) """By Paul on September 3, 2016 at 7:48 AM
(defun merge-point (lst1 lst2)
(do ((l1 (reverse lst1) (cdr l1))
(l2 (reverse lst2) (cdr l2))
(merge-point ‘()))
((or (and (null l1) (null l2)) (not (eq (car l1) (car l2))))
(values (reverse l1) (reverse l2) merge-point))
(push (car l1) merge-point)))
By Scott on September 6, 2016 at 12:58 AM
package test;
public class MergePoint {
public static int mergePoint(int a[],int b[]){
int aMergePoint=a.length;
int bMergePoint=b.length;
int alength=a.length;
int blength=b.length;
for(int i=alength-1,j=blength-1;i>=0 && j>=0 && a[i]==b[j]; i–,j–){
aMergePoint–;bMergePoint–;
}
System.out.println(“\n aMergePoint”+ aMergePoint);
System.out.println(“Suffix”);
for(int i=aMergePoint;i<a.length;i++){
System.out.print(a[i]);
}
System.out.println("\nAPrefix");
for(int i=0;i<aMergePoint;i++){
System.out.print(a[i]);
}
System.out.println("\nBPrefix");
for(int i=0;i<bMergePoint;i++){
System.out.print(b[i]);
}
for(int i=aMergePoint;i<aMergePoint;i++){
System.out.print(a[i]);
}
return aMergePoint ;
}
public static void main(String args[]){
int a[]={1,2,3,4,5,6,7,8,9};
int b[]={5,6,7,4,5,6,7,8,9};
mergePoint(a,b);
}
}
By akshaya pandey on September 7, 2016 at 11:06 AM
@Jérôme. Great job implementing this in Lisp; not many people could handle that! This reminds me of my university days when I scribbled a few Lisp scripts myself. I’m quite curious about the performance of this language for this task, so any information about that would be very much appreciated.
By Zack on September 8, 2016 at 10:22 AM
In Common Lisp, using the built-in functions MISMATCH and SUBSEQ:
(defun merge-point (xs ys &key (test #'eql)) (let ((m (length xs)) (n (length ys)) (i (mismatch (reverse xs) (reverse ys) :test test))) (if (null i) (values () () xs) (values (subseq xs 0 (- m i)) (subseq ys 0 (- n i)) (subseq xs (- m i))))))By Johan on September 13, 2016 at 3:59 PM
in PHP
function find_merge($A,$B) {
$a=array_values($A);
$b=array_values($B);
$l=sizeof($A);
$merge=true;
for($i=0; $i<$l ;$i++) {
if($a[$i]==$b[$i]) {
if($merge) {
$mp=$i;
$merge=false;}
}else {$merge=true;
$mp=$l;}
}
$bb=array_slice($b,0,$mp);
$aa=array_slice($a,0,$mp);
$am=array_slice($a,$mp);
return print_r([$aa,$bb,$am]);
}
By Aquiles Peña on October 20, 2016 at 8:25 PM