Help understanding some C# code

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.

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:
Thanks for your help here. I got so frustrated and burned out on this one that I only came back today to check it out again. I didn't see any comments past #10 until today. I appreciate your attempt to simplify things for me in comment #10, but I'm still struggling a bit to understand the code.

Since I'm apparently slow on the uptake here, perhaps if you could distill the code (either the original, or your simplified version) by associated line numbers for the following components I hopefully can pick it up a bit easier.

Code lines for how all the possible ship positions are generated
Code lines that recursively check to see if the ship will collide with another ship

My main thing is trying to understand the recursion component so I can see how to apply the concept in VBA for Excel.

Thank you again for your help.
I will check this out and whatever other comments you might have. I feel like I'm getting better about wrapping my arms around it.
 
Let's start off with a high level overview of the approach taken here. Imagine having many sheets of graphing paper each 10x10. On each sheet of graphing, the spots taken by a single ship are blocked out. There'll be a stack of paper for all the carrier positions, a stack for the battleship, a stack for the cruiser, a stack for the submarine, and a stack for the patrol boat. Start off with an blank sheet of paper and put that in your left hand. The recursion starts: Pick up a sheet of paper from the first stack and put it on top of the paper in your left hand and hold it up to the light. See if there are no overlapping blocks (meaning there are no collisions). If there are collisions, return that sheet you just picked up, and pick up the next sheet from the first stack, and try again.

If there are no collisions, then the next level of recursion starts: pick up another sheet of paper from the second stack of paper and put it on top of the papers in your left hand. See if there are no overlapping blocks. If there are collisions, return that sheet you just picked up, and then pick up the next sheet from the second stack. See if there are any collisions. If there are no collisions, then the next level of recursion starts.

Continue doing this until you get past the patrol boat stack. If you made it past the patrol boat stack, then that pile of papers in your left hand is a configuration of non-colliding ships. Count that as one possible configuration.

After counting that as one position, we bubble back up the recursion one level. Take the patrol boat sheet of paper from your left hand and return it to the patrol boat stack. Pick up the next sheet from the patrol boat stack. See if there are any collisions. Like previously, if there is a collision, return that sheet, move on to the next sheet, and try again. If there is no collision, then go down to the next level of recursion. Like in the previous paragraph, count that as another position.

When you've run out of patrol boat positions, then you'll bubble back up another level. Remove the submarine sheet of paper from your left hand and return it to the submarine stack. Pick up the next sheet from the submarine stack. See if there are any collisions.. Like previously, if there is a collision, return that sheet, move on to the next sheet, and try again. If there is no collision, then go down to the next level of recursion. Start from the beginning of the patrol boat stack of sheets, and repeat checks and recursion.

When you've run out of the submarine positions, the same bubbling up procedure is also done to the cruiser to get to try out all the cruiser sheets. The same will also happen to all the battleship and carrier sheets as well.

Now going to the code. We have the Field struct be that 10x10 graphing paper. Each stack of positions for a ship type is stored in a List<Field> (lines 38-42). Those 5 lists are kept in an array _positions (line 36). The recursion starts on line 15 with a blank Field, and a depth of 0.

This recursion depth nicely coincides with the array position of each list. So when depth is 0, it happen to be the carrier position list referenced by _positions[depth] on line 25. When depth is 1, it is the battleship; when depth is 2, it is the cruiser, etc.

When depth is 5, we would be out of range of our _positions array since the arrays are zero based. This means that we've gone past the patrol boat and we should count one configuration. (See lines 20-21).

The field from line 19 is our left hand that is holding on to the sheets of paper that we've accepted so far as non-colliding. The loop on lines 25-32 does the work of going through each of the ship positions. Line 30 checks to see if the current ship position p collides with the current field. If there is no collision, a recursive call is done on line 31. The depth for the next recursive call is increased by depth + 1.

The call to p.MergeWith(field) creates a new Field which is the effect as if you held up the stack of papers in your left hand up to the light and the effective spots that are taken. This is a temporary value it only exists for the lifetime of the called recursive function. When the function returns, that value is discarded which has the same effect of taking that topmost sheet from our left hand.

Notice also that line 31 also has the count += picking up the return value from the lower levels of recursion. This is how the total count eventually bubbles up to the top level of the recursion. At the level of the patrol boat, the counts only increment by one for each iteration of the loop that doesn't find a collision. But then that count of less than 180 non-collisions is return up to the submarine level. The counts at that level increment by the hundreds.

One of the major speed gains that the C# code has is that ability to "hold up the graph papers up to the light to check for collisions". The Field contains 2 64-bit integers. Each element of the 10x10 grid maps to a bit in one of the two 64-bit integers. When an element is occupied, the bit is turned on. (lines 91-98). In one operation, a collision check is performed, as compared to iterating over each grid position to see if a collision will happen. This fast check is done by line 71 in CanMerge() which performs two AND operation between 2 pairs of 64-bit integers. The fast merge can be done with just two OR operations.

The code for marking the cells occupied by a ship is done by computing the appropriate x,y coordinates for the ship given its orientation (see 76-89). Albeit the slow operation of having to compute which bit needs to be marked being done by Mark(), this pays off later because of being able to do the fast AND and OR operations for collision checks and merging.

To determine the positions of the ships on a blank sheet, GenerateShipPositions() (line 49-53) computes the furthest X and Y starting positions for a ship of given length which will not exceed the range of the 10x10 grid in both vertical and horizontal orientations. Similarly GenerateCarrierPositions() (lines 46-47) restricts the positions to the 5x8 grid in the vertical position. GenerateShipPositions() lines 56-62 walks the ship through all those valid positions and creates a new Field to be put into the list.

When the various Generate*Positions().ToList() is called on lines 38-42, the lists are actually constructed.
 
Let's start off with a high level overview of the approach taken here. Imagine having many sheets of graphing paper each 10x10. On each sheet of graphing, the spots taken by a single ship are blocked out. There'll be a stack of paper for all the carrier positions, a stack for the battleship, a stack for the cruiser, a stack for the submarine, and a stack for the patrol boat. Start off with an blank sheet of paper and put that in your left hand. The recursion starts: Pick up a sheet of paper from the first stack and put it on top of the paper in your left hand and hold it up to the light. See if there are no overlapping blocks (meaning there are no collisions). If there are collisions, return that sheet you just picked up, and pick up the next sheet from the first stack, and try again.

If there are no collisions, then the next level of recursion starts: pick up another sheet of paper from the second stack of paper and put it on top of the papers in your left hand. See if there are no overlapping blocks. If there are collisions, return that sheet you just picked up, and then pick up the next sheet from the second stack. See if there are any collisions. If there are no collisions, then the next level of recursion starts.

Continue doing this until you get past the patrol boat stack. If you made it past the patrol boat stack, then that pile of papers in your left hand is a configuration of non-colliding ships. Count that as one possible configuration.

After counting that as one position, we bubble back up the recursion one level. Take the patrol boat sheet of paper from your left hand and return it to the patrol boat stack. Pick up the next sheet from the patrol boat stack. See if there are any collisions. Like previously, if there is a collision, return that sheet, move on to the next sheet, and try again. If there is no collision, then go down to the next level of recursion. Like in the previous paragraph, count that as another position.

When you've run out of patrol boat positions, then you'll bubble back up another level. Remove the submarine sheet of paper from your left hand and return it to the submarine stack. Pick up the next sheet from the submarine stack. See if there are any collisions.. Like previously, if there is a collision, return that sheet, move on to the next sheet, and try again. If there is no collision, then go down to the next level of recursion. Start from the beginning of the patrol boat stack of sheets, and repeat checks and recursion.

When you've run out of the submarine positions, the same bubbling up procedure is also done to the cruiser to get to try out all the cruiser sheets. The same will also happen to all the battleship and carrier sheets as well.

Now going to the code. We have the Field struct be that 10x10 graphing paper. Each stack of positions for a ship type is stored in a List<Field> (lines 38-42). Those 5 lists are kept in an array _positions (line 36). The recursion starts on line 15 with a blank Field, and a depth of 0.

This recursion depth nicely coincides with the array position of each list. So when depth is 0, it happen to be the carrier position list referenced by _positions[depth] on line 25. When depth is 1, it is the battleship; when depth is 2, it is the cruiser, etc.

When depth is 5, we would be out of range of our _positions array since the arrays are zero based. This means that we've gone past the patrol boat and we should count one configuration. (See lines 20-21).

The field from line 19 is our left hand that is holding on to the sheets of paper that we've accepted so far as non-colliding. The loop on lines 25-32 does the work of going through each of the ship positions. Line 30 checks to see if the current ship position p collides with the current field. If there is no collision, a recursive call is done on line 31. The depth for the next recursive call is increased by depth + 1.

The call to p.MergeWith(field) creates a new Field which is the effect as if you held up the stack of papers in your left hand up to the light and the effective spots that are taken. This is a temporary value it only exists for the lifetime of the called recursive function. When the function returns, that value is discarded which has the same effect of taking that topmost sheet from our left hand.

Notice also that line 31 also has the count += picking up the return value from the lower levels of recursion. This is how the total count eventually bubbles up to the top level of the recursion. At the level of the patrol boat, the counts only increment by one for each iteration of the loop that doesn't find a collision. But then that count of less than 180 non-collisions is return up to the submarine level. The counts at that level increment by the hundreds.

One of the major speed gains that the C# code has is that ability to "hold up the graph papers up to the light to check for collisions". The Field contains 2 64-bit integers. Each element of the 10x10 grid maps to a bit in one of the two 64-bit integers. When an element is occupied, the bit is turned on. (lines 91-98). In one operation, a collision check is performed, as compared to iterating over each grid position to see if a collision will happen. This fast check is done by line 71 in CanMerge() which performs two AND operation between 2 pairs of 64-bit integers. The fast merge can be done with just two OR operations.

The code for marking the cells occupied by a ship is done by computing the appropriate x,y coordinates for the ship given its orientation (see 76-89). Albeit the slow operation of having to compute which bit needs to be marked being done by Mark(), this pays off later because of being able to do the fast AND and OR operations for collision checks and merging.

To determine the positions of the ships on a blank sheet, GenerateShipPositions() (line 49-53) computes the furthest X and Y starting positions for a ship of given length which will not exceed the range of the 10x10 grid in both vertical and horizontal orientations. Similarly GenerateCarrierPositions() (lines 46-47) restricts the positions to the 5x8 grid in the vertical position. GenerateShipPositions() lines 56-62 walks the ship through all those valid positions and creates a new Field to be put into the list.

When the various Generate*Positions().ToList() is called on lines 38-42, the lists are actually constructed.
Thank you for the detailed reply. I'm going to take a deeper dive this weekend when I have more free time. Thanks again!
 
Using the graph paper example, I have one more question then I'm good. Take the 5 cell length ship. That ship will fit in 120 total places on our 10x10 piece of graph paper, meaning there will be 120 sheets of graph paper for that length of ship, then those 120 individual pieces of paper are stored in a folder so all our graph papers for the 5 length ship are stored in one place. The same process is subsequently done for the other ships. That's how the description sounded to me. Is that correct?

Thanks again for the detailed explanation. It helped a lot.
 
Yes. The 5 lists are those folders. Then those folders are put into a file cabinet. That file cabinet is the array.
 
Lol. Sorry for the Columbo like "Just one more thing before I go...." routine, but from a technical standpoint, it sounds like those 120 individual graph sheets from above are actually 120 individual arrays, which themselves are stored in an array, basically an array of arrays containing our 120 sub arrays. That seems correct, but then I thought about it more and that would mean 760 individual arrays (120+140+160+160+180) and that didn't seem right.
 
That's correct 760 individual arrays.
 
Well, after grappling with the concept of 700+ arrays, I have another question for you. How does the C# code deal with the symmetry? For example, you really only need 15 of the 120 5 cell length arrays, then can multiply each individual result by 8, which C# seems to do as there is a line of code that multiplies a value by 8. In VBA, I ran the 120 through a filtering process that grouped the 120 into 15 groups of 8, then just picked the first one in each group to be representative of that group to run through the process. What does the C# code do relative to this?
 
See lines 45-47:
C#:
// by symmetry, we can restrict the len5 ship to being vertical and in the top left quarter of the field.
static IEnumerable<Field> GenerateCarrierPositions()
    => GenerateShipPositions(5, 5, 3, Orientation.Vertical);

I misspoke above about accepting the 120 number for the carriers. There are less positions stored for the carrier. Only the vertical positions of the carriers in the 10x8 top left corner of the field.
 
Ok. I think I'm almost there. Here's the question for today. Let's say we're comparing one of our 4 length ship arrays with one of the 5 length ones. How does the C# code determine that an element is occupied in both arrays? For example, let's say the element at 3,5 in both arrays is occupied. How is that determined? In my VBA research, it seemed like the only solution to this was to loop through one of the arrays and see if the position of an occupied element is occupied in the other array- there isn't any sort of native function that does that type of thing.
 
See lines 91-98, and lines 70-71.

Lines 91-98 turn turn on a bit in a pair of 64-bit integers. Lines 70-71 perform an AND operation between two pairs of 64-bit integers. If the AND operation returns non-zero that means that bits in the first pair have corresponding bits on the second pair turned on.

As you recall from your Boolean logic, here the truth table for AND
C#:
  | F T
--+----
F | F F
T | F T

If false is 0, and true is 1, then you have:
C#:
  | 0 1
--+----
0 | 0 0
1 | 0 1

A 10x10 two dimensional array can be mapped into a one dimensional array by using the formula x + 10 * y (where x and y are 0 based). So the 10x10 two dimensional boolean array where false indicates an empty space, and true indicates a filled space can be mapped to a 100 element one dimensional boolean array.

That boolean array can be mapped into the bits of an integer. Using the same formula, the bit index that needs to be turned on will be the (x + 10 * y)-th bit.

Unfortunately, the current longest natural type built into the .NET Framework (and .NET Core), and also supports bit operators, and lets as quickly check the results is the 64-bit integer. So the code in lines 91-98 also knows how to overflow past the 64th bit into the next integer.

.NET Framework and .NET Core have the BitArray class that supports bit operations, but it has no quick way to check for results. One would have to iterate over all the bit results and would be quite slow. It would be almost as slow as checking pairs of booleans in separate arrays.
 
VBA supposedly supports bitwise operators:
I was speaking relative to comparing one array to another at a higher level, not at that the bit level, but you're right. I didn't know Logical/Bitwise Operators existed for VBA until I did more research. How is the boolean array mapped to the bits of the integer? Assuming I'm thinking right, that 1 dimensional 100 element array (converted from a 10x10 array) is basically a 100 bit binary number, just a sequence of 1s and 0s. Is that sequence of array elements converted to a 64 bit number? Is that the mapping you speak of? (You'll have to help me out with how the overflow code deals with the values greater than 64)

And i should mention that your explanation above regarding lines 91-98 and lines 70-71 was outstanding, as have been all your explanations. It totally made sense and I immediately set out to discover if this was translatable to VBA, which is how I came across the Logical/Bitwise Operators. It looks like the same type of mapping to a 64 bit number type is possible, but i didn't fully understand how the array values were being mapped to the 64 bit number.

Just out of curiosity, how complex is the original code i posted? What C# level of expertise could come up with that? Beginner? Intermediate? Advanced? Thanks again for all your help!


 
Just out of curiosity, how complex is the original code i posted? What C# level of expertise could come up with that? Beginner? Intermediate? Advanced?
That original code looked and felt like C code that was just translated into C#. It's about intermediate level of C programming because C likes to keep you close to the metal. Being close to the metal involves knowing how bits, bytes, and arrays work in memory. That is how C is traditionally taught: start off with the basics of how things are represented in binary. The intermediate kicks in when recursion is introduced.

As for how that maps to C# level, it would be closer to the high end of intermediate in terms of concepts because of the recursion and dealing with bits, but at the same time it is also at the beginner level because that is not how you write C# code. C# tends to be more object oriented, and less procedural, while C code is traditionally written procedurally, and only more advanced C programmers will apply object oriented approaches.
 
How is the boolean array mapped to the bits of the integer? Assuming I'm thinking right, that 1 dimensional 100 element array (converted from a 10x10 array) is basically a 100 bit binary number, just a sequence of 1s and 0s. Is that sequence of array elements converted to a 64 bit number? Is that the mapping you speak of?
Yes, that sequence of 1s and 0s becomes a 100-bit number. But since there is no natural 100 bit number in C# (yet), I used two 64-bit numbers instead. The first one, _low holds the lower 64-bits, and the second one, _high holds the remainder. In the original code you posted, the author of that code opted to put the lower 50 bits in m1 and the upper 50 bits in m2.

Crash course on how binary numbers work. Let's start off with just 4 bits (called a nibble), and their corresponding values:
C#:
binary => decimal = computed as
0000 =>  0 = 0 * 8 + 0 * 4 + 0 * 2 + 0 * 1
0001 =>  1 = 0 * 8 + 0 * 4 + 0 * 2 + 1 * 1
0010 =>  2 = 0 * 8 + 0 * 4 + 1 * 2 + 0 * 1
0011 =>  3 = 0 * 8 + 0 * 4 + 1 * 2 + 1 * 1
0100 =>  4 = 0 * 8 + 1 * 4 + 0 * 2 + 0 * 1
0101 =>  5 = 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1
0110 =>  6 = 0 * 8 + 1 * 4 + 1 * 2 + 0 * 1
0111 =>  7 = 0 * 8 + 1 * 4 + 1 * 2 + 1 * 1
1000 =>  8 = 1 * 8 + 0 * 4 + 0 * 2 + 0 * 1
1001 =>  9 = 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1
1010 => 10 = 1 * 8 + 0 * 4 + 1 * 2 + 0 * 1
1011 => 11 = 1 * 8 + 0 * 4 + 1 * 2 + 1 * 1
1100 => 12 = 1 * 8 + 1 * 4 + 0 * 2 + 0 * 1
1101 => 13 = 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1
1110 => 14 = 1 * 8 + 1 * 4 + 1 * 2 + 0 * 1
1111 => 15 = 1 * 8 + 1 * 4 + 1 * 2 + 1 * 1

But binary is simply base 2 (just like decimal is base 10). So we can look at a binary digit as:
C#:
d c b a
where
a as the value * 1 == value * (2 raised to the 0th power)
b as the value * 2 == value * (2 raised to the 1st power)
c as the value * 4 == value * (2 raised to the 2nd power)
d as the value * 8 == value * (2 raised to the 3rd power)

This places: a, b, c, d are also called bit positions where the exponent of 2 describes the position.

So let's start off with a value of 1: 0001 binary. To get from 1 to 2, we multiply 1 by 2 and get 0010 binary. And then when we multiply 2 by 2 again we get 4: 0100 binary. Again multiply by 4 by 2 to get 8: 1000 binary. Makes sense, right since 1, 2, 4, 8 are just powers of 2.

But also notice how the 1 simply shifted over from one place digit over to the next place digit to the left. The number of places shifted over to the left corresponds to the exponent of 2. (This also works out for any binary number be it the binary number has 8 bits, 12 bits, 16 bits, 24 bits, 32 bits, 64 bits, 128 bits, etc. as long as the language has a way of representing a number with that number of digits.)

The shift operator << is used to do the shifting. See lines 95 and 97 in my code and line 82 and 83 of the code you posted.

By using the OR bitwise operator (|, we can turn on the corresponding bit. So for example, we start off with zero, and we want to turn on the 3rd bit: we would do:
C#:
   0000
|  1000
-------
=  1000
and then we go on to turn on the 0th bit:
C#:
   1000
|  0001
-------
=  1001
or in code:
C#:
int value = 0;
value = value | (1 << 3);
value = value | (1 << 0);
or using the OR assignment operator syntatic sugar:
C#:
int value = 0;
value |= 1 << 3;
value |= 1 << 0;

So how to deal with the overflow of going over 64-bits? Notice in my code's line 94 a check is first made to see if the bit to be turned on is greater than or equal to 64. If it is, line 95 is executed were the bit - 64-th bit of _high is turned on. Similarly, in the original code you posted, if the bit is greater than or equal to 50, the loc - 50-th bit of m2 is turned on.

As noted previously the bit position is determined by the x,y position. Bits 0 to 9 correspond to the 1st row. Bits 10-19 correspond to the second row. Bits 20-29 correspond to the third row. Etc. Notice how the formula works out to be x + 10 * y where x and y are zero based. This is the mapping of the grid position to the bit position.
 
Back
Top Bottom