# Doppleganger challenge

• (4 Pages)
• 1
• 2
• 3
• 4

## 55 Replies - 20636 Views - Last Post: 03 September 2012 - 02:25 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=241261&amp;s=5b51f3ccb90e4c2c7f01881a334449f8&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #31 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Doppleganger challenge

Posted 28 July 2011 - 03:56 AM

Here is a java one that uses BitSets. O(max(lenA+lenB), maxVal)
It falls over if either of your lists contain negative numbers or Integer.MAX_VALUE. The latter is an easy fix but I lift it out for the sake of simplicity.

```	static List<Integer> doppleganger(List<Integer> A, List<Integer> B)/> {
BitSet bits = toBits(A);
bits.and(toBits(B)/>);

List<Integer> C = new ArrayList<Integer>();
int i = -1;
while ((i = bits.nextSetBit(i+1)) != -1) {
}
return C;
}

static BitSet toBits(List<Integer> L) {
BitSet bits = new BitSet();
for(int i : L) bits.set(i, true);
return bits;
}

```

### #32 m-e-g-a-z

• Winning

Reputation: 497
• Posts: 1,457
• Joined: 19-October 09

## Re: Doppleganger challenge

Posted 28 July 2011 - 04:27 AM

baavgai, on 27 July 2011 - 08:53 PM, said:

Hmm... what if the lists look like [ 2, 5, 5, 5, 8, 3, 3, 12 ], [ 12, 5, 5, 1, 3, 3, 3, 4 ].

The answer I'd want ( order doesn't matter): [3, 3, 12, 5, 5]

That's far more fun:

Spoiler

### #33 Nallo

• D.I.C Regular

Reputation: 165
• Posts: 258
• Joined: 19-July 09

## Re: Doppleganger challenge

Posted 28 July 2011 - 06:11 AM

A rewrite of atraub's sorted list algorithm in haskell:
Spoiler

### #34 Curtis Rutland

• （╯°□°）╯︵ (~ .o.)~

Reputation: 5103
• Posts: 9,283
• Joined: 08-June 10

## Re: Doppleganger challenge

Posted 28 July 2011 - 09:26 AM

A rewrite of Nallo's rewrite of atraub's sorted list algorithm in F#:

Spoiler

Edit, this prints the matches in reverse order. If we want them ascending instead of descending, change this line:
```//| h::t              -> x::h::t
| h::t              -> h::[email protected]::[]

```

Example usage:
```doppelganger [1; 2; 3; 4; 4; 5; 5;] [8; 2; 4; 3;] |> printfn "%A"
//include if running as console application
```

Edit 2: I think I like this version better, it has less needless pattern matching, and I changed some naming up to make it more obvious to me:

Spoiler

Example usage:
```intersect [1; 2; 3; 4; 4; 5; 5;] [8; 2; 4; 3;] |> printfn "%A"
//include if running as console application
```

This post has been edited by Curtis Rutland: 28 July 2011 - 12:04 PM

### #35 Curtis Rutland

• （╯°□°）╯︵ (~ .o.)~

Reputation: 5103
• Posts: 9,283
• Joined: 08-June 10

## Re: Doppleganger challenge

Posted 28 July 2011 - 10:45 AM

Also, my version using a HashSet in F#:
Spoiler

Edit: a shorter version using Set instead of HashSet
Spoiler

This post has been edited by Curtis Rutland: 28 July 2011 - 12:06 PM

### #36 atraub

• Pythoneer

Reputation: 828
• Posts: 2,236
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 28 July 2011 - 06:41 PM

### #37 Nallo

• D.I.C Regular

Reputation: 165
• Posts: 258
• Joined: 19-July 09

## Re: Doppleganger challenge

Posted 28 July 2011 - 07:03 PM

Quote

Any high level language will do fine... but no functional languages

I am sorry sir. I missed that order

### #38 fromTheSprawl

• Bloodborne

Reputation: 522
• Posts: 2,102
• Joined: 28-December 10

## Re: Doppleganger challenge

Posted 28 July 2011 - 07:38 PM

But isn't 5 always a 5? Then if you see a 5 in one set and two or three 5's in the other it would still need to show 5 since a doppelganger is a complete copy of something?

Or I'm just plain lazy. Here is the ugly code I made with PLSQL, hope to do baavgai's implementation in the future(more laziness!):
Spoiler

Hid it in spoilers so as not to blind your eyes.

### #39 Curtis Rutland

• （╯°□°）╯︵ (~ .o.)~

Reputation: 5103
• Posts: 9,283
• Joined: 08-June 10

## Re: Doppleganger challenge

Posted 28 July 2011 - 08:41 PM

atraub, on 28 July 2011 - 08:41 PM, said:

It's fun though. I mean, I could do that in Python or C#, but I'm trying to learn F#, so why not? I mean, sure, F# has a Sequence type with methods to do intersection automatically, but I'm actually implementing the filtering myself, without a set. Using the haskell version of your code, of course, but it's still fun.

Also, @Nallo,

atraub, on 27 July 2011 - 02:58 PM, said:

Fine, functional languages too

### #40 anonymouscodder

Reputation: 126
• Posts: 710
• Joined: 01-January 10

## Re: Doppleganger challenge

Posted 28 July 2011 - 09:00 PM

bash
Spoiler

This post has been edited by anonymouscodder: 28 July 2011 - 09:05 PM

### #41 atraub

• Pythoneer

Reputation: 828
• Posts: 2,236
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 28 July 2011 - 09:41 PM

haha I'm not judging, it's pretty hardcore that you guys want to do this in f#, haskell, and now bash!

### #42 baavgai

• Dreaming Coder

Reputation: 7160
• Posts: 14,925
• Joined: 16-October 07

## Re: Doppleganger challenge

Posted 29 July 2011 - 07:09 AM

Well, to round it out...

I'll admit, I'm not real comfortable with functional languages. That is one of the many reasons I like Python; you can have fun with functional stuff without loosing your comfortable imperative home.

In Erlang, here's a one liner:
Spoiler

However, it feels like it's cheating more than a little, because of the sets. Then again, sorting also feels like a cop out.

So, with no libraries at all ( I wrote my own lists:member equiv ), Erlang solution.

Spoiler

There are probably a more clever ways to do that. I actually did a functional no no with anti tail end recursion, but it seems a reasonable solutions to me. The trick here is no built ins, which honestly make it too easy.

### #43 atraub

• Pythoneer

Reputation: 828
• Posts: 2,236
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 29 July 2011 - 08:38 AM

baavgai, on 29 July 2011 - 10:09 AM, said:

...sorting also feels like a cop out...

Harsh

### #44 baavgai

• Dreaming Coder

Reputation: 7160
• Posts: 14,925
• Joined: 16-October 07

## Re: Doppleganger challenge

Posted 29 July 2011 - 09:38 AM

Lol!

atraub, on 27 July 2011 - 03:26 PM, said:

Haha don't be lame brewer! Create an actual algorithm for solving the problem

### #45 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

## Re: Doppleganger challenge

Posted 29 July 2011 - 10:50 AM

so i was reading Sergio Tapia's blog(here) about learning C Curt posted his F# snippet. i then translated it to Haskell which it had been translated from before. Curt pointed out that that bit of code went from Python->Haskell->F#->Haskell. so here is my bit of code.

Spoiler

oddly it got shorter with each translation

also for the hell of it here is one in Lua
Spoiler

This post has been edited by ishkabible: 29 July 2011 - 11:04 AM