Winners
- First Place: Michael Ware of TAB Computer Systems, INC. out of East Hartford, CT.
Michael submitted his winning solution on 2008-05-12 13:20:11.513. He has generously designated
Connecticut Food Bank as the beneficiary of the $250 cash award. In addition
Michael received a license for xSQL Bundle Professional Edition.
- Second Place: Brian May, Web Applications Developer with STG Inc. out of Ashville, NC. Brian submitted his winning
solution on 2008-05-12 14:31:20.507 and received a license for xSQL Bundle Professional Edition.
Puzzle: let's assume you have 12 INT variables A, B, C, D, E, F, G, H, I,
J, K, L and you know that 11 of them contain the same value whereas one of them
contains a value that is different from the others. You have access to a
COMPARE(x,y) function that returns 0 when x=y, 1 when x>y, 2 when x<y. It so
happens that this COMPARE(x,y) function is very expensive so the goal is to
minimize calls to that function. Your job is to write a piece of code
(pseudocode) that identifies the variable which contains the different value
with the least possible number of compare(x,y) calls.
Winning Solution:
Winning solution presented below was submitted by Michael Ware on 2008-05-12 13:20:11.513
// Three COMPARE()s max
// Starting set A,B,C,D,E,F,G,H,I,J,K,L
// First compare
ABCD_EFGH=COMPARE(A+B+C+D,E+F+G+H)
IF ABCD_EFGH = 0
// I,J,K, or L is different
// Second compare
AI_JK = COMPARE(A+I,J+K)
IF AI_JK = 0
L is different
ELSE
// I,J or K is left
// Third compare
J_K = COMPARE(J,K)
IF J_K = 0
I is different
ELSEIF J_K = AI_JK
K is different
ELSE
J is different
END IF
END IF
ELSE
// A,B,C,D,E,F,G or H is Different
// Second compare using A,B,D,E,F
// (exclude C,G & H)(E & D swap sides)
ABE_DFL = COMPARE(A+B+E,D+F+L)
IF ABE_DFL = 0
// C,G or H is different
// Third Compare
G_H = COMPARE(G,H)
IF G_H = 0
C is different
ELSEIF G_H = ABCD_EFGH
(G had swapped sides)
H is different
ELSE
(H on same side)
G is different
END IF
ELSEIF ABE_DFL = ABCD_EFGH
// E & D are not it or sign would change
// A,B or F is different
// Third Compare
A_B = COMPARE(A,B)
IF A_B = 0
F is different
ELSEIF A_B = ABE_DFL
(B swapped sides)
A is different
ELSE
(A on same side)
B is different
END IF
ELSE
// Moving E or D changed direction
// Third Compare
IF COMPARE(A,E)=0
D is different
ELSE
E is different
END IF
END IF
END IF
Don't forget!
Please do check out our products - they are listed on the right hand panel - they are professional grade
and chances are you won't have to pay anything. Can't get better than that!
Tell your friends
Last but not least, please do tell your friends and colleagues about the xSQL Puzzle of the Month - the more people
compete the more fun it is for all! Digg it, blog about it, bookmark it - do whatever you like but do help us!
|