For the last two years, every couple of month or so an article appears claiming “C# is faster than VB.NET”. I agree C# is possibly very slightly faster, I won’t argue. Perhaps it is only fair. Perhaps it is to compensate the fact that C# programmers are probably not as good a VB programmers. You understand that, it is time to revive a good old war like we had years ago between Atari and Amiga. If we can't decide which Language is best, let's see which programmers are best, whether it is VB programmers or C# programmers.
The Mac Mahon problem
The problem I want to challenge you is this one.
You have to complete a puzzle made of 24 pieces. The pieces are displayed in the picture at the beginning of this article.
- All the 24 pieces must be used.
- Each piece can be rotated to any orientation.
- Each segment color must match the color of the adjoining segment.
- The puzzle border must be of the same color (red in this case).
This problem can be reproduced on cardboard to play as a solitaire.
A valid solution
This is one solution of the problem.
As you can see
- It uses all 24 pieces.
- The border is all red.
- Each piece shares a color with each of its neighbours.
The challenge is to make a program which looks for solution for this puzzle. The program has to count how many solutions the puzzle has, and then do it as fast a possible. The existing code is already searching, but not very fast. I let my computer run 24 hours and it did not complete…
by Pascal GANAYE
|10,000 results in more than 24 hours. Did not complete|
|15/03/2005||Added a few optimizations||106624 solutions in 90 minutes|
No submission yet
|17/03/2005||Marc Clifton started a C#.||77,306 solutions in about 60 minutes|
I would love to see another language here. If you have a try, please post something in the forum below.
Point of Interest
As you can see, each piece is divided in 4 triangles and filled with 3 colours. Mathematically this is a nice problem, because this it is not 24 arbitrary chosen pieces but every single combination. There are 3*3*3*3 = 81 possibilities. But If you remove the duplicates you end up with only 24 different pieces.
- I will post one submission in each submitted language. You can also use this page forum at the bottom.
- The program can use any sort of optimisation as long as it stays managed .NET and native language (can’t use MSIL).
- All optimisation must be described. Please no hard coded solution.
I suggest a notation structure for the solutions. If you name the piece A0,B0,C0,...X0.
| A0 || B0 || C0 || D0 || E0 || F0 |
| G0 || H0 || I0 || J0 || K0 || L0 |
| M0 || N0 || O0 || P0 || Q0 || R0 |
| S0 || T0 || U0 || V0 || W0 || X0 |
The rotated version of B0 would be called:
B1 (90 degrees anti-clockwise)
B2 (180 degrees), and
B3 (270 degrees).
Then a solution like this one
could be written like this:
B2 D0 I0 L0 J0 G0
A0 C2 V0 S0 T2 O3
K0 F0 X0 W0 U0 Q3
H2 E0 P2 R2 M2 N3
or even as a single line like this:
This will probably help to compare our results.
You can see mine here.
I hope you realize, I don't take this language war very seriously. I just love the Mac-Mahon problem. How can we live without knowing for sure how many solutions there are?