Help understanding some C# code

[John Franklin]

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.

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);
      }
   }
}

 

[John Franklin]

Good stuff. Another excellent tutorial. So, a couple of questions for today. Does the code iterate/loop through the 1d array and assign the bit values as you described above that way? Secondly, what is the recursion section of the code responsible for doing, creating, etc.?

 

[Skydiver]

Does the code iterate/loop through the 1d array and assign the bit values as you described above that way?

Yes. See lines 76-89

Secondly, what is the recursion section of the code responsible for doing, creating, etc.?

It's the process of grabbing a sheet from the folder and putting it into the left hand, and then looking at the papers through the light to see if there are any collisions. If no collision, then the next level recursion repeats the process of picking up a sheet from the next folder. The recursion keeps happening until there are no more folders, and a configuration is counted. Then you bubble up one level of recursion and put the topmost sheet back into the folder it came from and pickup the next sheet in the folder, check for collisions, and work your way down again. If you've exhausted the current folder, then bubble up again.

Instead of just reading my description. Try it out for yourself with. Just do 3 sheets for each ship so that you are not bogged down.

 

[John Franklin]

Thanks. My end game is to try to replicate the concepts you're helping me with here into VBA, much like the C code was modified for C# use. To that end, I'm trying understand both the concepts and the code mechanics that carry out those concepts. This uses concepts (like recursion and bit level comparisons, for example) that I've never used myself or really even seen used when looking at the VBA code of others. Take recursion for example. When I researched it relative to VBA, there just wasn't a lot out there that I found useful. The mechanics of it was often described via the same example- a Sub procedure makes a Function call and passes a value to the Function. The Function ends up calling itself and modifies that original passed value to iterate through until the escape/exit value triggers an exit. It didn't help that most of these recursion descriptions seemed to indicate that you could achieve the same type thing via a series of nested FOR loops, so that was a bit confusing to me, as in what would the benefit of using recursion be then?

What you described above for how recursion works here is identical in concept to what my VBA code does, but my code doesn't use recursion in the manner described above regarding passing a value to a function which then calls itself. Mine just uses a series of nested FOR loops to grab the first 5 element item and compare it to the first 4 element item. If no intersect/overlap, get the first 3 item element. If intersect or overlap, go to the next 4 item and continue until no intersect/overlap. This just repeats and works its way down to the 2 item level. Once you've found a 2 item that doesn't intersect any of the other four, that's counted as one configuration, then we bubble up to the next 3 item and keep going. This just continues until we've bubbled back up through all the 5 element items. Maybe what I'm doing is technically recursion, but it doesn't seem like it based on the descriptions/examples I've seen of it, namely the function calling itself aspect.

With your latest tutorial, I'm thinking I'm finally at level where I can start translating to VBA. The bit mapping/comparison aspect should be interesting. Let me ask you this. You shared why you thought this started out as C code and that C# code wouldn't be written like that. As someone who's obviously proficient in C#, what would you do differently? If you were starting this from scratch, how would you write the code? Would it just look like the modified code of the original that you posted (which I believe was done that way for my benefit), or would it look different?

 

[Skydiver]

The recursive code lets you add more ships simply by adding more lists into the array at line 36. With your nested for loops, you'll need to add more levels of nesting.

In computer science, there is an axiom that any recursive code can be re-written to be iterative. One approach of doing that iterative implementation is by hardcoding the levels of recursion just like you have done with your nested for loops. Another approach is to use queues and stacks to keep track of the levels of recursion.

What I would have done differently is that my initial implementation would have had a 10x10 two dimensional array of booleans in a Field class to first make sure that I code that was working correctly, albeit slowly. Then I would have used a profiler to determine where the bottlenecks and/or most used areas of code are at. Although intuitively it would have been the array comparison and merging, but it's good to have data to back that up, as well as an objective measure to compare against when refactoring the code. Only then would I start refactoring that area of code to either use parallelism (e.g. multiple threads) or use bit fields. Only once I've gone down the bit field path would I have converted the class Field into a struct Field, due to performance improvements that can be gained when not using an object reference to 100+ bytes and instead using a value type that is only 128 bits (16 bytes).

 

[John Franklin]

Would your way translate into speed gain? Every time I ran the original code it completed in under four minutes, so improving on that impressive speed would be...even more impressive.

What would need to be added to my nested loops to beef up the levels nesting?

 

[Skydiver]

See post #13. ~90 seconds for the code in post #10.

 

[John Franklin]

When the 2D arrays are originally created, meaning the 15 for the 5 element arrays, 140 for the 4 element arrays, etc., why aren't they just created as 1D arrays right then? If they just end up being 1D anyway, why not just create them that way from the get go? We may just be talking about milliseconds here in terms of conversion time, but it does seem like it would save a step.

 

[Skydiver]

Programs must be written for people to read, and only incidentally for machines to execute.

- Harold Abelson

Fixed size 2D arrays are implemented by modern compilers to be 1D in memory anyway. So it just comes down to what is easier to understand (and maintain).

field[x + 10 * y] = true;
:
if (field[x + 10 * y])
{
}

vs.

field[x, y] = true;
:
if (field[x, y])
{
}

 

[John Franklin]

Hi Skydiver. Well, it's been about a year since I posted my original call (cry?) for help. Thanks in large part to your help and patience, the prototype I completed in Excel/VBA gets the result anywhere from 2 minutes 37 seconds to 2 minutes 47 seconds. Not as blazing as C#, but not too shabby considering the limitations of VBA vs. C#.

With no true multithreading available, I had to jury rig that component, but once that fell into place, the result time went from 15 minutes and change down to what I mentioned above. Maybe I could squeeze a few more seconds out of it, but I think I've pretty much reached the end game based on the limitations of Excel and my system, so I think I'm ending this long journey.

Thanks again for all your help!