Friday Programming Quiz [modified]

Rama Krishna Vavilala

While you are waiting for a build that crashes or may be not. Here is a simple programming problem (not question). The objective is to write the following function:

string GetIntersection(string csvString1, string csvString2) {

}

csvString1 and csvString2 both contain comma separated list of unique values. The values can be in any order and they don't contain commas. The objective is to return a new CSV string which contains value from both the lists. e.g. csvString1: cat,rat,dog,lion csvString2: lion,elephant,mouse,tiger,rat,dog output: lion,rat,dog The coolest implementation of the function I have seen, so far, happens to be in JavaScript. Feel free to use any library functions. -- modified at 15:18 Friday 27th October, 2006

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan

David Crow

Can't you just use set_intersection()?

"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15

"Judge not by the eye but by the heart." - Native American Proverb

Rama Krishna Vavilala

Sure. (I hope you mean stl set_intersection.)

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan

David Stone

LINQ: (Note: Completely untested. I haven't set up Visual Studio on my new laptop yet. ;P Should work though.)

string GetCsvIntersection(string csv1, string csv2)
{
var list1 = new List<String>(Regex.Split(csv1, ","));
var list2 = new List<String>(Regex.Split(csv2, ","));

var result = new StringBuilder();
foreach (string item in list1.Intersect(list2))
{
    result.AppendFormat("{0},", item);
}

return result.Remove(result.Length - 1, 1).ToString();

}

Last modified: 2hrs 8mins after originally posted -- Yeah. Okay. LINQ still isn't as cool as Javascript

Oh geez... the forum keeps spinning... you'll take care o f it i'm sure, c'ause ... yeah, i neede this. *cough* anyway good job finding the bug. -Shog9 on...a Firefox bug.

ToddHileHoffer

My coworker always tells me I write way more code then I need to. But at least it works! string GetResulst(string x, string y) { Regex r = new Regex("[,]"); System.Collections.Specialized.StringCollection Group1 = new System.Collections.Specialized.StringCollection(); System.Collections.Specialized.StringCollection Group2 = new System.Collections.Specialized.StringCollection(); System.Collections.Specialized.StringCollection Results = new System.Collections.Specialized.StringCollection(); Array Ary1 = r.Split(x); Array Ary2 = r.Split(y); foreach (string z in Ary1) { Group1.Add(z); } foreach (string z in Ary2) { Group2.Add(z); } foreach (string z in Group1) { if (Group2.Contains(z) && Results.Contains(z) == false) Results.Add(z); } string Result = ""; foreach (string z in Results) { Result += z + ","; } return Result.Remove(Result.Length - 1, 1); }

how vital enterprise application are for proactive organizations leveraging collective synergy to think outside the box and formulate their key objectives into a win-win game plan with a quality-driven approach that focuses on empowering key players to drive-up their core competencies and increase expectations with an all-around initiative to drive up the bottom-line. But of course, that's all a "high level" overview of things --thedailywtf 3/21/06

David Stone

Um. Yeah. That's too much. ;P

Mandrake, do you realize that in addition to fluoridating water, why, there are studies underway to fluoridate salt, flour, fruit juices, soup, sugar, milk, ice cream. Ice cream, Mandrake. Children's ice cream.

Rama Krishna Vavilala

David Stone wrote:

list1.Intersect(list2).ToString();

I wonder whether that will work?

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan

ToddHileHoffer

Ooops I replied to the wrong message. My coworker always tells me I write way more code then I need to. But at least it works! string GetResulst(string x, string y) { Regex r = new Regex("[,]"); System.Collections.Specialized.StringCollection Group1 = new System.Collections.Specialized.StringCollection(); System.Collections.Specialized.StringCollection Group2 = new System.Collections.Specialized.StringCollection(); System.Collections.Specialized.StringCollection Results = new System.Collections.Specialized.StringCollection(); Array Ary1 = r.Split(x); Array Ary2 = r.Split(y); foreach (string z in Ary1) { Group1.Add(z); } foreach (string z in Ary2) { Group2.Add(z); } foreach (string z in Group1) { if (Group2.Contains(z) && Results.Contains(z) == false) Results.Add(z); } string Result = ""; foreach (string z in Results) { Result += z + ","; } return Result.Remove(Result.Length - 1, 1); }

how vital enterprise application are for proactive organizations leveraging collective synergy to think outside the box and formulate their key objectives into a win-win game plan with a quality-driven approach that focuses on empowering key players to drive-up their core competencies and increase expectations with an all-around initiative to drive up the bottom-line. But of course, that's all a "high level" overview of things --thedailywtf 3/21/06

David Crow

Rama Krishna Vavilala wrote:

(I hope you mean stl set_intersection.)

Why?

"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15

"Judge not by the eye but by the heart." - Native American Proverb

Lost User

Here is my answer in C#. I couldnt find List<>.Intersect() anywhere on MSDN public string GetIntersection(string csvString1, string csvString2) { string[] stringAry1 = csvString1.Split(new char[] { ',' }); List stringList = new List(); foreach (string str in stringAry1) { if (csvString2.Contains(str)) { stringList.Add(str); } } return String.Join(",", stringList.ToArray()); } sorry about the formatting. My browser is Opera

David Stone

So do I, honestly. :-D Anybody with VS and the May LINQ CTP installed want to try it out?

Once you wanted revolution
Now you're the institution
How's it feel to be the man?

Judah Gabriel Himango

I thought about a couple solutions. Most of the options are either compact and poor performance, or verbose and high performance. Here's one compact solution:

string GetIntersection(string csvString1, string csvString2)
{
foreach (string str in csvString2.Split(','))
if (!csvString1.Contains("," + str + ",") && !csvString1.EndsWith(str))
csvString1 += "," + str;

 return csvString1;

}

Of course, I'd never write code like that as it's hugely inefficient due to the excessive string concatenation. You could make a more efficient version with a StringBuilder, char array, or List of strings, but they'd be more verbose. :)

Tech, life, family, faith: Give me a visit. I'm currently blogging about: God-as-Judge, God-as-Forgiver The apostle Paul, modernly speaking: Epistles of Paul Judah Himango

jesarg

Your code will return false positives if csvString1 has element "hi" and csvString2 has element "hide".

David Stone

J.Doli wrote:

I couldnt find List<>.Intersect() anywhere on MSDN

It's not there yet. You only get List<T>.Intersect() if you install the LINQ CTPs.

Oh geez... the forum keeps spinning... you'll take care o f it i'm sure, c'ause ... yeah, i neede this. *cough* anyway good job finding the bug.
-Shog9 on...a Firefox bug.

Lost User

thanks for pointing that out. Here is my next try. public string GetIntersection(string csvString1, string csvString2) { List stringList = new List(csvString2.Split(new char[] { ',' })); List results = new List(); foreach (string str in csvString1.Split(new char[] { ',' })) { if (stringList.Contains(str)) { results.Add(str); } } return String.Join(",", results.ToArray()); } I dont like it that much, i just keep thinking that there is a better way.

David Stone

It won't. Also, my string splitting is wrong. I've modified it with the correct answer.

Oh geez... the forum keeps spinning... you'll take care o f it i'm sure, c'ause ... yeah, i neede this. *cough* anyway good job finding the bug.
-Shog9 on...a Firefox bug.

Ennis Ray Lynch Jr

Sue me, I am lazy and uncreative right now. StringBuilder sb = new StringBuilder(); Hashtable table = new Hashtable(); string[] splitList = csvString1.Split(new char[]{','}); foreach(string s in splitList){ table[s] = s; } splitList = csvString2.Split(new char[]{','}); foreach(string s in splitList){ table[s] = s; } foreach(string s in table.Values){ sb.Append(s); } return sb.ToString();

On two occasions I have been asked [by members of Parliament], 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question. - Charles Babbage

Matt Gerrans

Yeah. You need to get a smaller monitor. Your team will thank you. BTW: "but at least it works" is a commonly used rationale (or excuse) for code that usually doesn't work very well at all. Remember, good code is about readability too. If it wasn't for that, we wouldn't keep source code after it was compiled once. Code is for people, not computers. All computers care about is the machine instructions.

Matt Gerrans

Joe Woodbury

For the heck of it I threw together a C++ version. Note that the CMTrieIntT class is one of my own implementations of a trie and is extremely fast. (I have a case insensitive version that could also be used.)

int GetString(LPCTSTR& pStr)
{
	while (*pStr == ',')
		pStr++;

	int len = 0;

	while (pStr[len] && pStr[len] != ',')
		len++;

	return len;
}

CString GetIntersection(LPCTSTR pStr1, LPCTSTR pStr2)
{
	CMTrieIntT trie;

	for ( ; ; )
	{
		int len = GetString(pStr1);
		if (len == 0)
			break;

		trie.Add(pStr1, 0, len);

		pStr1 += len;
	}

	CString rval;

	for ( ; ; )
	{
		int len = GetString(pStr2);
		if (len == 0)
			break;

		if (trie.KeyExists(pStr2, len))
		{
			if (rval.GetLength() > 0)
				rval += ',';

			rval.Append(pStr2, len);
		}

		pStr2 += len;
	}

	return rval;
}

Anyone who thinks he has a better idea of what's good for people than people do is a swine. - P.J. O'Rourke

Henrik Husted

my $l1 = "cat,rat,dog,lion"; my $l2 = "lion,elephant,mouse,tiger,rat,dog"; my (%h1,%h2); foreach(split ",", $l1) { $h1{$_}=$_;} foreach(split ",", $l2) { $h2{$_}=$_;} foreach( sort keys %h1 ) { if( $h2{$_} ) { print "$h1{$_}\n"; } }