[anonymouscodder]

javascript

Spoiler

function foo(a, B)/> {
	var c = a.concat(B)/>.sort(function(a, B)/> { return a - b; });
	var d = [];
	var last = null;
	for(var i = 0; i < c.length; ++i) {
		if(last === c[i])
			d.push(c[i]);
		last = c[i];
	}
	return d;
}
var arr = foo([1, 2, 4, 5, 6, 8, 10], [1, 3, 5, 7, 9, 10])
for(var i = 0; i < arr.length; ++i)
	document.write(arr[i] + ' ');

This post has been edited by anonymouscodder: 29 July 2011 - 11:47 AM

[atraub]

Lua and Javascript too? This is madness!

[AdamSpeight2008]

F#

open System.Linq;;
let xs1= [ 2; 5; 5; 5; 8; 3; 3; 12 ]
let xs2= [ 12; 5; 5; 1; 3; 3; 3; 4 ]
let re=xs1.Intersect(xs2)

[Curtis Rutland]

Well, yeah. Most of these languages already have a built in Intersect method. The point was to do it yourself. Like when the teacher makes you write a sort algorithm.

Also, you can use Set.intersect as well, and skip importing the Linq namespace.

[baavgai]

Given our current legion of languages, this seemed like a glaring omission.

ANSI-C

Spoiler

int *mergeList(const int *list1, int list1Size, const int *list2, int list2Size, int *resultSize) {
	int i, size = 0;
	int *results = malloc(list1Size>list2Size?list1Size:list2Size * sizeof(int));
	
	for(i=0; i<list1Size; i++) { 
		int j, found;
		int value = list1[i];
		for(j=0, found=0; j<size && !found; j++) { found = results[j]==value; }
		if (!found) {
			for(j=0, found=0; j<list2Size && !found; j++) { found = list2[j]==value; }
			if (found) { results[size++] = value; }
		}
	}
	*resultSize = size;
	return results;
}

[Nallo]

I felt like doing a different Algorithm in Python, using an AVL tree. So again it is n log n + m log n.

Spoiler

class AvlNode(object):
    
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
        self.height = 0
        self.marked = False
    

class AvlTree(object):

    def __init__(self):
        self.root = None

    def height(self, node):
        if node == None:
            return -1
        else:
            return node.height

    def balance_factor(self, node):
        return self.height(node.left) - self.height(node.right)

    def update_height(self, node):
        subtreeheights = [self.height(child)
                          for child in (node.left, node.right)]
        node.height = 1 + max(subtreeheights)
    
    def _rotate(self, rot_node, rs, os):
        pivot = getattr(rot_node, os)
        
        pivot.parent = rot_node.parent
        if pivot.parent is None:
            self.root = pivot
        else:
            if pivot.parent.left is rot_node:
                pivot.parent.left = pivot
            elif pivot.parent.right is rot_node:
                pivot.parent.right = pivot
        
        setattr(rot_node, os, getattr(pivot, rs))
        if getattr(rot_node, os) is not None:
            getattr(rot_node, os).parent = rot_node

        setattr(pivot, rs ,rot_node)
        rot_node.parent = pivot

        self.update_height(rot_node)
        self.update_height(pivot)
        
    def _rotate_left(self, rot_node):
        rotation_side = "left"
        opposite_side = "right"
        self._rotate(rot_node, rotation_side, opposite_side)
        
    def _rotate_right(self, rot_node):
        rotation_side = "right"
        opposite_side = "left"
        self._rotate(rot_node, rotation_side, opposite_side)

    def _rebalance(self, node):
        while node is not None:
            self.update_height(node)
            if self.balance_factor(node) == -2:
                if self.balance_factor(node.right) == -1:
                    #right-right case
                    self._rotate_left(node)
                else:
                    #right-left case
                    self._rotate_right(node.right)
                    self._rotate_left(node)
            elif self.balance_factor(node) == 2:
                if self.balance_factor(node.left) == 1:
                    #left-left case
                    self._rotate_right(node)
                else:
                    #left-right case
                    self._rotate_left(node.left)
                    self._rotate_right(node)
            node = node.parent

    def insert(self, key):
        """inserts new node if key not already in tree"""
        new = AvlNode(key)
        if self.root == None:
            self.root = new
        node = self.root
        while True:
            if key < node.key:
                if node.left == None:
                    node.left = new
                    new.parent = node
                    break
                node = node.left
            elif key > node.key:
                if node.right == None:
                    node.right = new
                    new.parent = node
                    break
                node = node.right
            else:
                return None
        self._rebalance(new)

    def find(self, key):
        node = self.root
        while node is not None:
            if key < node.key:
                node = node.left
            elif key > node.key:
                node = node.right
            else:
                return node
        return None


def doppelganger(seq1, seq2):
    shorter, longer = sorted([seq1, seq2], key = len)
    tree = AvlTree()
    for el in shorter:
        tree.insert(el)
    result = []
    for x in longer:
        node = tree.find(x)
        if node is None or node.marked is True:
            continue
        else:
            result.append(x)
            node.marked = True            
    return result

[atraub]

This could be my most successful challenge ever:

note to self, include all languages in challenges from now on



thanks to everyone who participated!!

This post has been edited by atraub: 30 July 2011 - 12:13 PM

[Curtis Rutland]

atraub, on 30 July 2011 - 01:28 PM, said:

note to self, include all languages in challenges from now on

Even if you don't, we'll probably still pop in and drop them on you.

[xGeovanni]

Everything must be one line.

def commonElements(listA, listB):
    return [elA for elA in listA for elB in listB if elA == elB]

[sepp2k]

xGeovanni, on 03 September 2012 - 10:17 PM, said:

Everything must be one line.

def commonElements(listA, listB):
    return [elA for elA in listA for elB in listB if elA == elB]

That way commonElements([1,1], [1,1]) will return [1,1,1,1].

[xGeovanni]

sepp2k, on 03 September 2012 - 02:16 PM, said:

That way commonElements([1,1], [1,1]) will return [1,1,1,1].

Fine.

def commonElements(listA, listB):
    return [elA for elA in listA if elA in listB]

Got a problem with that one?