Doppleganger challenge

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

55 Replies - 12215 Views - Last Post: 03 September 2012 - 02:25 PM Rate Topic: -----

#31 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1940
  • View blog
  • Posts: 4,029
  • 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) {
			C.add(i);
		}
		return C;
	}

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


Was This Post Helpful? 0
  • +
  • -

#32 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 496
  • View blog
  • Posts: 1,453
  • Joined: 19-October 09

Re: Doppleganger challenge

Posted 28 July 2011 - 04:27 AM

View Postbaavgai, 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

Was This Post Helpful? 0
  • +
  • -

#33 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • 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

Was This Post Helpful? 1
  • +
  • -

#34 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4438
  • View blog
  • Posts: 7,720
  • 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::t@x::[]



Example usage:
doppelganger [1; 2; 3; 4; 4; 5; 5;] [8; 2; 4; 3;] |> printfn "%A"
//include if running as console application
System.Console.ReadKey() |> ignore


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
System.Console.ReadKey() |> ignore

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

Was This Post Helpful? 1
  • +
  • -

#35 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4438
  • View blog
  • Posts: 7,720
  • 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

Was This Post Helpful? 0
  • +
  • -

#36 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Doppleganger challenge

Posted 28 July 2011 - 06:41 PM

haskell and f#.... wow guys...
Was This Post Helpful? 0
  • +
  • -

#37 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • 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 :stuart:
Was This Post Helpful? 0
  • +
  • -

#38 fromTheSprawl  Icon User is offline

  • Monomania
  • member icon

Reputation: 513
  • View blog
  • Posts: 2,056
  • 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.
Was This Post Helpful? 0
  • +
  • -

#39 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4438
  • View blog
  • Posts: 7,720
  • Joined: 08-June 10

Re: Doppleganger challenge

Posted 28 July 2011 - 08:41 PM

View Postatraub, on 28 July 2011 - 08:41 PM, said:

haskell and f#.... wow guys...


:D

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,

View Postatraub, on 27 July 2011 - 02:58 PM, said:

Fine, functional languages too

Was This Post Helpful? 0
  • +
  • -

#40 anonymouscodder  Icon User is offline

  • member icon

Reputation: 126
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#41 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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!
Was This Post Helpful? 0
  • +
  • -

#42 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • 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. :P

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.
Was This Post Helpful? 0
  • +
  • -

#43 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Doppleganger challenge

Posted 29 July 2011 - 08:38 AM

View Postbaavgai, on 29 July 2011 - 10:09 AM, said:

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


Harsh
Was This Post Helpful? 0
  • +
  • -

#44 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,596
  • Joined: 16-October 07

Re: Doppleganger challenge

Posted 29 July 2011 - 09:38 AM

Lol! :P

View Postatraub, on 27 July 2011 - 03:26 PM, said:

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

Was This Post Helpful? 0
  • +
  • -

#45 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • 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

Was This Post Helpful? 0
  • +
  • -

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