Determing if a shot results in a split

7 8 9 10
 4 5 6
  2 3
   1

So, I spent the majority of my weekend working working on my bowling tracking app for my mobile. eMbedded Visual C++ is not the most pleasant IDE to work with, so I started writing it as a desktop app which I will later port to the mobile. So far I have implemented an owner drawn check box that allows the user the toggle the presence if a given pin in a leave. Once that was completed, I start writing classes to model a shot, a frame, and a game. As I mentioned in a previous post, I wanted to be able to track statistics related to leaving and converting splits. It turns out determining if a leave is a split or not is not the most trivial thing to implement.

I wasn't really sure how to start, so I got up from the computer, pulled out some pencil and paper, and started writing down various splits as fast as I could think of them. It quickly became apparent that enumerating all possible (or even all realistic) splits was an unfeasible choice for implementation. At this point, it occurred to this could be viewed as a pattern recognition problem. As such, I considered attacking the problem with a finite state automaton. Unfortunately, I have never been a big fan of implementing FSAs, which probably stems from my disdain for my old compilers professor. I was hoping to find another solution.

That is when I turned to my old friend, graph theory. As a result, I developed the following algorithm to determine if a leave is a split:

1. If a leave contains the head pin (or 1-pin), it is not a split.
   
2. If a leave contains fewer than two pins, it is not a split.
   
3. Let each pin in the leave represent a node. Each node has a vertex to every other pin that is diagonally adjacent and to every other pin that is directly in front or behind it (what is known to bowlers a "sleeper"). If there exists a path of vertices from each node to every other node, the leave it not a split. Otherwise, it is.
   

For some additional clarification, here are some examples of diagonally adjacent pins:
(1, 2), (1,3), (2,4), (2,5), etc.

The following would not be diagonally adjacent:
(1,4), (1,6), (4,5), (1,5), (2,8) (3, 9)

The last three examples above are the "sleeper" leaves.

So now that I had an algorithm, it was time to implement it. For the implementation code to make sense, some other pieces of the puzzle must be addressed. The first thing is to determine how a leave would be represented. I could have used a string containing the number of the pins left, like "7 10", but that wouldn't have been to efficient although it would have been convenient at times. I could have also used a ten element array of booleans indicating if each pin were present. That also seemed a little bit wasteful, and since I do want to port this to a mobile device in the future, I wanted something more conservative. In the end, I decided to use a bitmapped word to represent the results of each shot. The zero bit being set indicated the 1-pin was present, and so on. I now had six extra bits I could use. I decided to use the additional bits to indicate a miss (gutter), a foul, a strike, and a spare. I am left with two unused bits. Using this scheme, you can store everything you every wanted to know about a game of bowling twenty-one words, or forty-two bytes if you prefer. The bitmap was defined as part of a class that models a single shot (be it first or second, or third shot if the bowler marked in the tenth). Here's a snippet:

class CShot : public CObject
{
public:
 CShot();
 virtual ~CShot();

 int GetCount();
 virtual void Serialize(CArchive& ar);
 void SetResult(WORD wResult);

 WORD GetResult();
 static const WORD ONEPIN = 0x0001;
 static const WORD TWOPIN = 0x0002;
 static const WORD THREEPIN = 0x0004;
 static const WORD FOURPIN = 0x0008;
 static const WORD FIVEPIN = 0x0010;
 static const WORD SIXPIN = 0x0020;
 static const WORD SEVENPIN = 0x0040;
 static const WORD EIGHTPIN = 0x0080;
 static const WORD NINEPIN = 0x0100;
 static const WORD TENPIN = 0x0200;
 static const WORD MISS = 0x0400;
 static const WORD FOUL = 0x0800;
 static const WORD STRIKE = 0x1000;
 static const WORD SPARE = 0x2000;
            ...
protected:
 WORD m_wResult;
};

Since the concept of a split doesn't make sense as the result of a second shot, the function for determining weather or not a leave is a split could not be part of CShot. Instead it is a member function in the class I used to represent a single, non-tenth frame of bowling, CFrame. Here is the relevant portion of the CFrame class definition:

class CFrame : public CObject
{
public:
 CFrame();
 virtual ~CFrame();
            ...
 bool IsMark() const;
 virtual bool IsSpare() const;
 virtual bool IsStrike() const;
 bool IsSplit() const;
 bool IsOpen() const;
 virtual void Serialize(CArchive &ar);
 void SetFirstShot(CShot* pShot);
 void SetSecondShot(CShot* pShot);

protected:
 CShot* m_pFirstShot;
 CShot* m_pSecondShot;

private:
 operator=(const CFrame& Frame) {};
 CFrame(const CFrame& Frame) {};
};

Finally, the implementation of this elementary application of graph theory:

bool CFrame::IsSplit() const
{
 ASSERT(m_pFirstShot != 0);
 WORD wResult = m_pFirstShot->GetResult();

 // A leave cannot be considered a spilt if it contains the head pin
 if (wResult & CShot::ONEPIN) return false;
 
 int nCount = m_pFirstShot->GetCount();
 
 // There has to be at least two pins standing to be a split
 if (nCount == 9 || IsStrike()) return false;

 int nPinsLeft = NUMPINS - nCount;

 while (nPinsLeft)
 {
  if (wResult & CShot::TENPIN)
  {
   if ((wResult & (CShot::SIXPIN)) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::TENPIN;
    nPinsLeft--;
   }
  }
  else if (wResult & CShot::NINEPIN)
  {
   if ((wResult & (CShot::THREEPIN | CShot::FIVEPIN | CShot::SIXPIN)) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::NINEPIN;
    nPinsLeft--;
   }
  }
  else if (wResult & CShot::EIGHTPIN)
  {
   if ((wResult & (CShot::TWOPIN | CShot::FOURPIN | CShot::FIVEPIN)) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::EIGHTPIN;
    nPinsLeft--;
   }
  }
  else if (wResult & CShot::SEVENPIN)
  {
   if ((wResult & CShot::FOURPIN) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::SEVENPIN;
    nPinsLeft--;
   }  
  }
  else if (wResult & CShot::SIXPIN)
  {
   if ((wResult & CShot::THREEPIN) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::SIXPIN;
    nPinsLeft--;
   }
  }
  else if (wResult & CShot::FIVEPIN)
  {
   if ((wResult & (CShot::TWOPIN | CShot::THREEPIN)) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::FIVEPIN;
    nPinsLeft--;
   }
  }
  else if (wResult & CShot::FOURPIN)
  {
   if ((wResult & CShot::TWOPIN) == 0)
    return (nPinsLeft > 1);
   else
   {
    wResult &= ~CShot::FOURPIN;
    nPinsLeft--;
   }
  }
  else
  {
   return (nPinsLeft > 1);
  }
 }

 return false;
}

I ended up writing a bunch of additional code to generate the bitmapped word for a given leave represented as string. Then I stuffed a crap load of different leaves in an array with every other one being a split. I wrote a loop that iterated through the array and called the IsSplit function verifying I got the expected result. I know this code works for any realistic leave, and I am pretty sure it would work for any unrealistic leave as well. And if you have spent much time at a bowling alley, you have definitely heard stories about some pretty unrealistic leaves. :)

I think there is a more elegant recursive solution in there somewhere, but I think this implementation is still fairly clean. Most of the unwieldiness stems from the bitmapped representation of the leave. But since this is totally different than the kind of problems I have to solve at work, it has made for a refreshing little additional challenge to my little hobby project. And I think that is cool...