John Franklin
Member
- Joined
- Jan 22, 2022
- Messages
- 17
- Programming Experience
- 5-10
Hello all. I dabbled in C# a couple of years ago, but didn't really progress much past the beginner phase. The code below is a C# answer I found to a challenge I solved via Excel/VBA, but whereas my code takes hours to find the solution, the C# code below takes around 3 minutes(!). I was blown away by that and since my C# skills are pretty minimal at this point, I don't completely understand how the code works. So, to that end, I was hoping someone could help give me an understanding of what's going on in this code and how it is determining the solution. I don't know how involved that is, but if someone has the time and inclination, I'd really like to learn/understand how this code finds the solution. Many thanks to whomever is willing to help me with this!
The challenge this code solves is based off the old game Battleship and finds the answer of how many unique starting boards are there for the game Battleship. Meaning, how many ways are there to place all the ships of various cell lengths (5,4,3,3,2) vertically or horizontally (no diagonals) in a 10x10 grid with no overlap/intersection of ships. I was a bit shocked at the answer, but the code below confirmed my answer, and did it WAY WAY faster than my code, which is why I'd like to understand how the C# works.
The challenge this code solves is based off the old game Battleship and finds the answer of how many unique starting boards are there for the game Battleship. Meaning, how many ways are there to place all the ships of various cell lengths (5,4,3,3,2) vertically or horizontally (no diagonals) in a 10x10 grid with no overlap/intersection of ships. I was a bit shocked at the answer, but the code below confirmed my answer, and did it WAY WAY faster than my code, which is why I'd like to understand how the C# works.
C#:
using System;
using System.Collections.Generic;
namespace test4
{
class BShip
{
class BPat
{
private readonly long mask1;
private readonly long mask2;
public BPat(long m1, long m2)
{
mask1 = m1;
mask2 = m2;
}
public bool canMerge(long m1, long m2)
{
return (m1 & mask1) == 0 && (m2 & mask2) == 0;
}
public void mergeWith(ref long m1, ref long m2)
{
m1 |= mask1;
m2 |= mask2;
}
}
static private readonly IList<BPat>[] ship = new List<BPat>[5];
static void Main()
{
for( int ln = 2; ln<=5; ln++ )
{
IList<BPat> list = new List<BPat>();
// by symmetry, we can restrict the len5 ship to being vertical and in the top left quarter of the field.
int mxx = ln == 5 ? 5 : 10;
int mxy = ln == 5 ? 3 : 10;
for (int x = 0; x < mxx; x++)
{
for (int y = 0; y < mxy; y++)
{
placeShip(list, ln, x, y, 0, 1);
if( ln!=5) placeShip(list, ln, x, y, 1, 0);
}
}
ship[5-ln] = list;
}
ship[4] = ship[3]; // extra len 3 ship
ship[3] = ship[2];
long count = search(0, 0L, 0L);
// 8 symmetries
Console.WriteLine(count * 8);
}
static long search(int depth, long m1, long m2)
{
if (depth == 5) return 1;
long count = 0;
foreach (BPat p in ship[depth])
{
if( depth == 0 ) Console.WriteLine(count);
if( p.canMerge(m1,m2))
{
long oldm1 = m1, oldm2 = m2;
p.mergeWith(ref m1,ref m2);
count += search(depth + 1, m1, m2);
m1 = oldm1;
m2 = oldm2;
}
}
return count;
}
static void placeShip(IList<BPat> list, int ln, int x, int y, int dx, int dy)
{
if (x + dx*(ln-1) >= 10 || y + dy*(ln-1) >= 10) return;
int loc = 10*y + x;
long m1 = 0, m2 = 0;
for (int i = 0; i < ln; i++)
{
if (loc >= 50) m2 |= 1L << (loc - 50);
else m1 |= 1L << loc;
loc += 10*dy + dx;
}
BPat p = new BPat(m1, m2);
list.Add(p);
}
}
}
Last edited:
But as Skydiver said, it's possible (I think even likely) that the C# code uses a faster algorithm than your own code. In my opinion that is for you to work out. You hardly need any C# skills to study and understand the algorithm used here. The logic would be the same in any language.
