Friday Programming Quiz (It's back) [modified]
-
Simple, how about a hard one? Given a tic-tac-toe board where the board can be represented by a one-dimensional array of chars with 'X' being x, 'Y' being y, and all others being empty such that the top left most square is the 0 index, followed by the middle square on the top row as the 1 index ....
0 | 1 | 2
_____________
3 | 4 | 5
_____________
6 | 7 | 8Write an algorithm to display the number of winning combination available for each X and O based on the game state when passed an array in under n^2.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Simple, how about a hard one? Given a tic-tac-toe board where the board can be represented by a one-dimensional array of chars with 'X' being x, 'Y' being y, and all others being empty such that the top left most square is the 0 index, followed by the middle square on the top row as the 1 index ....
0 | 1 | 2
_____________
3 | 4 | 5
_____________
6 | 7 | 8Write an algorithm to display the number of winning combination available for each X and O based on the game state when passed an array in under n^2.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest HemingwayHa! I think I did this in first year uni :) Wow, I did some scary (but still cool) code back then, in C!
Ennis Ray Lynch, Jr. wrote:
under n^2.
What is n suppose to be?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
Ha! I think I did this in first year uni :) Wow, I did some scary (but still cool) code back then, in C!
Ennis Ray Lynch, Jr. wrote:
under n^2.
What is n suppose to be?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
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
var list1 = ['A','B','C','D'];
var list2 = ['B','A','X','S','L','D'];var result = list1.filter(function(i) list2.indexOf(i) >= 0)
.concat( list2.filter(function(i) list1.indexOf(i) < 0 ) );Javascript 1.8 (tested on Firefox 3.0.1)
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...
-
That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest HemingwayEnnis 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. 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)your kidding right?
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
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):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
-
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
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 -
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
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 -
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 -
var list1 = ['A','B','C','D'];
var list2 = ['B','A','X','S','L','D'];var result = list1.filter(function(i) list2.indexOf(i) >= 0)
.concat( list2.filter(function(i) list1.indexOf(i) < 0 ) );Javascript 1.8 (tested on Firefox 3.0.1)
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...
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 -
: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...
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 -
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 -
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![^]