Friday Programming Quiz (It's back) [modified]

[leppie]

Ennis Ray Lynch, Jr. wrote:

That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.

Jeez. I hope you being sarcastic... :| What is n, the size of the input? Size of the board?

xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)

[Ennis Ray Lynch Jr]

your kidding right?

Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway

[Paul Conrad]

:eek:

"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

[Nish Nishant]

Judah Himango wrote:

var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));

Hey Judah, I would probably replace that with :

var list2ElementsNotInList1 = list2.Except(list1);

Regards, Nish

---

Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link

[Nish Nishant]

In fact this would be even more straightforward :

var result = list1.Intersect(list2).Concat(list2.Except(list1));

Regards, Nish

---

Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link

[Shog9 0]

:cool:

You must be careful in the forest Broken glass and rusty nails If you're to bring back something for us I have bullets for sale...

[Nish Nishant]

Ah you have a one-liner too I see - in fact the same algorithm as the one in mine.

Regards, Nish

---

Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link

[Nish Nishant]

Thank you :-)

Regards, Nish

---

Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link

[Shog9 0]

Yeah, same algorithm, but more verbose so i split it into two lines.

You must be careful in the forest Broken glass and rusty nails If you're to bring back something for us I have bullets for sale...

[Joe Woodbury]

This is Friday, so my steps were: 1) Pick up phone 2) Call junior programmer Hank 3) Tell him this is due ASAP 4) Go home

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

[PIEBALDconsult]

I think my Set[^] class/struct was my first article. (It wasn't, but I wrote the class before the others.)

PIEBALD.Types.Set<char> a = new PIEBALD.Types.Set<char> ( 'A' , 'B' , 'C' , 'D' ) ;
PIEBALD.Types.Set<char> b = new PIEBALD.Types.Set<char> ( 'B' , 'A' , 'X' , 'S' , 'L' , 'D' ) ;

foreach ( char c in ( a & b ) + b ) ...

A HashSet didn't preserve the order, and isn't as expressive. X|

System.Collections.Generic.HashSet<char> c = new System.Collections.Generic.HashSet<char> ( a ) ;
System.Collections.Generic.HashSet<char> d = new System.Collections.Generic.HashSet<char> ( b ) ;

System.Collections.Generic.HashSet<char> f = c ;
f.IntersectWith ( d ) ;
f.UnionWith ( d ) ;

foreach ( char e in f )

I've been considering reworking Set to use a HashSet rather than a Dictionary (originally it used a Hashtable).

modified on Friday, August 1, 2008 9:08 PM

[Rama Krishna Vavilala]

PIEBALDconsult wrote:

( a & b ) + b

It took me a while to understand that code:)

Proud to be a CPHog user

[PIEBALDconsult]

I had to access my article to figure out what operator I used for intersection. Then found that the order of operations is wrong. :( Ha! a & b | b works as required. I've been looking forward to a good FPQ for ages, I keep trying to think of my own.

[leppie]

Ennis Ray Lynch, Jr. wrote:

your kidding right?

Sorry, I went to sleep :) No, I wasn't kidding. I meant what is n in relation to the problem. Does it refer to the 'variable' amount of 'squares'? Does it refer to the 'variable' amount of winning combinations? Does it refer to the 'width' of the board? Is it the number of sheep I count before I pass out? From your problem statement, all of the above are constant, (9, 8, 3, 42). You get what I am saying? Remember O(3000000000n) is still O(n).

xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)

[Stuart Dootson]

In Haskell:

import Data.List

munge a b = (a `intersect` b) ++ (b \\ a)

a `intersect` b retrieves the stable intersection of a with b. b \\ a takes all elements in a out of b. Job's a good'un! [edit]Should have read the Data.List documentation *before* answering rather than after! The code should be

munge a b = a `intersect` b ++ filter (not.(`elem` a)) b

\\ only deletes the first instances of elements of b that are also in a, i.e. ("ABA"\\"A" == "BA" which is not what's wanted here) [/edit]

modified on Saturday, August 2, 2008 7:13 AM

[Gary R Wheeler]

CTypedPtrList<CPtrList,_TCHAR *> list1,list2,list3;
 
list1.AddTail(_T("A"));
list1.AddTail(_T("B"));
list1.AddTail(_T("C"));
list1.AddTail(_T("D"));
 
list2.AddTail(_T("B"));
list2.AddTail(_T("A"));
list2.AddTail(_T("X"));
list2.AddTail(_T("S"));
list2.AddTail(_T("L"));
list2.AddTail(_T("D"));
 
POSITION p1 = list1.GetHeadPosition();
 
while (p1 != NULL) {
 
_TCHAR *s1 = list1.GetNext(p1);
 
POSITION p2 = list2.GetHeadPosition();
 
while (p2 != NULL) {
 
POSITION r2 = p2;
 
_TCHAR *s2 = list2.GetNext(p2);
 
if (_tcsicmp(s1,s2) == 0) {
list3.AddTail(s1);
list2.RemoveAt(r2);
}
 
}
 
}
 
list3.AddTail(&list2);

BTW: I did compile and run this; it works. While it does alter list2 in the process, a version that doesn't wouldn't be difficult.

Software Zen: delete this;
Fold With Us![^]

[Gary R Wheeler]

Gone over to the Dark Side*, have we hmm? * I'll be polite and not use the 'm'-word.

Software Zen: delete this;
Fold With Us![^]

[Ennis Ray Lynch Jr]

I think you may have a fundamental misunderstanding of Algorithm efficiency analysis and I am not going to explain it because, like I said it is a large topic. I don't mean to be rude about it I am just not in a pedantic mood at the moment and the books on the subject do a much better job than I would.

Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway

[leppie]

Ennis Ray Lynch, Jr. wrote:

I think you may have a fundamental misunderstanding of Algorithm efficiency analysis

No, I dont, you are misunderstanding what I am asking you. The way I see it, given the constant nature (the board size does not change, neither does the total number of winning combinations) of your problem statement, and the small size of the problem, this problem would probably be solved in O(1), or O(log n) in the worst case where n would refer to the (constant) size of the board. This would be using a precomputed lookup table/tree for all game states (3^9). Now, if n was not constant, I would likely not be able to do so. But even in that case, the problem should not take more than O(n). Maybe I am reading/misunderstanding your problem statement. :~

xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)

[Ennis Ray Lynch Jr]

The nature of the solution dictates the efficiency. It is not up to me to state what n is, it is for the author of the solution to calculate. The problem in the context I wrote it is a trick question because an experienced developer would likely write an n^n solution and an inexperienced developer would be more likely to author the O(1) solution. Thus the kicker would be most low-level developers might be stumped on actually grasping the problem and then more experienced developers would be stumped on grasping the solution. I think if you actually attempted to author a solution and then checked the efficiency after the fact my question becomes a lot more apparent.

Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway