Friday Programming Quiz (It's back) [modified]
-
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
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
-
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
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
-
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
PIEBALDconsult wrote:
( a & b ) + b
It took me a while to understand that code:)
Proud to be a CPHog user
-
PIEBALDconsult wrote:
( a & b ) + b
It took me a while to understand that code:)
Proud to be a CPHog user
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.
-
your kidding right?
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest HemingwayEnnis 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) -
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
In Haskell:
import Data.List munge a b = (a `intersect` b) ++ (b \\ a)a `intersect` bretrieves the stable intersection of a with b.b \\ atakes 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 bemunge 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
-
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
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
list2in the process, a version that doesn't wouldn't be difficult.Software Zen:
delete this;
Fold With Us![^] -
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
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. 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)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 -
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 HemingwayEnnis 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. 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)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 -
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![^]Actually no, just trying to be humorous.
Anyone who thinks he has a better idea of what's good for people than people do is a swine. - P.J. O'Rourke
-
Actually no, just trying to be humorous.
Anyone who thinks he has a better idea of what's good for people than people do is a swine. - P.J. O'Rourke
:laugh: Did Hank get it done asap?
"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
-
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 linkNifty!
Tech, life, family, faith: Give me a visit. I'm currently blogging about: Upon this disciple I'll build my new religion? The apostle Paul, modernly speaking: Epistles of Paul Judah Himango