Saturday, March 26, 2005

Solving 2nd order polynomials in x86 assembly

So, I got asked to tutor a co-worker in an x86 assembly course. I saw it as a great opportunity to fill a gap in my education. Overall, I think my computer science education is pretty good, but it is woefully inadequate when it comes to assembly. The only required course I took that had me "writing" any assembly was a computer organization course based around the Motorola 68000 in which we were only required to write assembly code on notebook paper. Even then, I recognized this could be a problem, so I took an electrical/computer engineering course, micro-processor system design, as an elective. We wrote most of the assembly for that class on notebook paper as well, although we did some very contrived tasks with DOS's debug.com program. Yeah, I wasn't kidding when I said my education is woefully inadequate when it comes to assembly.

My co-worker didn't need help with the early part of the course, so she didn't ask me for the tutoring until recently. That also meant I had a lot of catching up to do, but that was actually a good thing for me. If I am not being overwhelmed by a challenge, I tend to get bored. I ended up spending the majority of Thursday evening, all day Friday (I was off work), and most of today (Saturday) reading the textbook, hunting for other assembly resources, installing the software, and working on the course's current project.

Looking at the course material, I am fairly impressed. The author of the text was a former professor for the course, and he had provided some routines to the students for input and output. That is a smart move since one of the biggest obstacles in the early stages of learning assembly is that I/O is difficult, and a student doesn't get much feedback if they can't do any I/O. Also, they are using free tools for the course, which being a former student, I didn't like paying for extra crap even if I did get it at a better price than the general public. These are the tools for the course:

  • NASM - Netwide Assembler
  • DJGPP - A windows port of gcc

For windows, you will also need the contents of this zip file. For other platforms, check here (bottom of the page).

The way they do the projects in the course is to have driver program in C really only calls a function defined in the assembly code. Here's the source for that:


#include "cdecl.h"

int PRE_CDECL asm_main( void ) POST_CDECL;

int main()
{
  int ret_status;
  ret_status = asm_main();
  return ret_status;
}


The header cdecl.h is uninteresting. It just provides macros for portably handling the specification of the calling convention.

This particular project was to write a program to solve quadratic equations, so the instructor allowed the students to use scanf for reading in the floating point values since nothing like that was included in the afore mentioned I/O routines. Here's the one I wrote:

#include <stdio.h>
#include "cdecl.h"

void PRE_CDECL read_float(double* pd) POST_CDECL;

void read_float(double* pd)
{
    scanf("%lf", pd);
}


And honestly, that is about as much pure C I can stomach writing in a single sitting. Well, maybe it is not that bad, but I feel seriously tied down when I write C since I am a big OO fan. But anyway, on to my first assembly code that does anything mildly interesting. Oh, and by the way, my syntax highlighter doesn't work on assembly. When I mentioned it would be easy to extend to other languages, I was mainly thinking Java and C#. Okay so I am getting to the code for real this time:

%include "asm_io.inc"

%macro print_float 1
push dword[%1+4]
push dword[%1]
push dword ffmt
call _printf
%endmacro

%define a [ebp-8]
%define b [ebp-16]
%define c [ebp-24]
%define root1 [ebp-32]
%define root2 [ebp-40]
%define discriminant [ebp-48]

extern _read_float
extern _printf

segment .data
ffmt db "%12.4f", 0
minus_four dw -4
prompt db "Enter coefficients a, b, and c: ", 0
no_soln_msg db "No real roots", 0
soln_msg db "The roots are: ", 0
progress_msg db "Making progress...", 0

segment .bss


segment .text
global _asm_main
global _read_float
global print_float

_asm_main:
enter 0,0 ; setup routine
pusha
push ebp
mov ebp, esp
sub esp, 56
push ebx
mov eax, prompt
call print_string
lea eax, a
push eax
call _read_float
pop eax
lea eax, b
push eax
call _read_float
pop eax
lea eax, c
push eax
call _read_float
pop eax
fild word[minus_four] ; stack is -4
fld qword a ; stack is a, -4
fld qword c ; stack is c, a, -4
fmulp st1 ; stack is ac, -4
fmulp st1 ; stack is -4ac
fld qword b ; stack is b, -4ac
fld qword b ; stack is b, b, -4ac
fmulp st1 ; stack is b^2, -4ac
faddp st1 ; stack is b^2-4ac
ftst ; determine if discriminant is negative
fstsw ax
sahf
jb near no_real_roots

mov eax, soln_msg
call print_string
call print_nl
fsqrt ; stack: sqrt(b*b - 4*a*c)
fstp qword discriminant ; store result so calculation is not
; repeated
fld1 ; stack is 1.0
fadd st0 ; stack is 2.0
fld qword a ; stack is a, 2.0
fmulp st1 ; stack is 2.0*a
fld qword discriminant ; stack is sqrt(b^2-4ac), 2a
fld qword b ; stack is b, sqrt(b^2-4ac), 2a
fchs ; stack is -b, sqrt(b^2-4ac), 2a
fadd st1 ; stack is -b+sqrt(b^2-4ac), sqrt(b^2-4ac), 2a
fdiv st2 ; stack is (-b+sqrt(b^2-4ac))/2a,
; sqrt(b^2-4ac), 2a
lea eax, root1
fstp qword[eax] ; stack is sqrt(b^2-4ac), 2a
print_float eax
pop eax
pop eax
pop eax
call print_nl
fld qword b ; stack is b, sqrt(b^2-4ac), 2a
fchs ; stack is -b, sqrt(b^2-4ac), 2a
fsub st1 ; stack is -b-sqrt(b^2-4ac), sqrt(b^2-4ac), 2a
fdiv st2 ; stack is (-b-sqrt(b^2-4ax))/2a,
; sqrt(b^2-4ac), 2a
lea eax, root2
fstp qword[eax] ; stack is sqrt(b^2-4ac), 2a
print_float eax
ffree st1
ffree st2
jmp quit

no_real_roots:
ffree st0
mov eax, no_soln_msg
call print_string

quit:
pop ebx
mov esp, ebp
pop ebp
popa
mov eax, 0 ; return back to C
leave
ret

While I didn't say how long I spent doing the actual assembly code, it was a lot longer than I anticipated. I spent a considerable amount of time reading the floating point input and verifying it was correct. I also spent some time debugging issues with the stack which I think greatly improved my understanding of the stack in general. The last thing I struggled with was a completely stupid oversight on my part which involved popping values from the floating point stack. The ironic thing is that I had to do no debugging whatsoever of the root calculation code, and that was supposed to be the interesting part of this project.

For the sake of completeness, I will address building this code. If you download the zip file mentioned above for your particular platform, the first C program listed will already be there in driver.c. The compiled version of the assembly I/O routines will be in asm_io.o or asm_io.obj depending on your platform. The program for reading a floating point value should be pasted into a file saved as read_float.c. The assembly code was saved into a file named quadratic.asm. Under this situation, here are the commands to build this program:

nasmw -f coff quadratic.asm
gcc -o quadratic quadratic.o asm_io.o driver.c read_float.c

Path information has been omitted, but if you store the .c and .asm files in the same directory as nasmw.exe, you can run the commands as shown from the NASM directory. DJGPP stores environment variables that make invoking it from other directories convenient.

As a side note, I generally type the HTML for links while I am writing and fill in the URLs later. After filling in the in the URLs concerning my education, I am embarrassed by my university. Apparently certain departments quit updating their webpages about three years ago. If I may flaunt my impressive football knowledge, it make me sort of feel like Dave Krieg, the longtime Seattle Seahawks quarterback whose college (search for "defunct" on the resulting page) became defunct while he was still playing in the NFL. The sad thing is that my university doesn't have a good excuse for not updating their web pages, like CEASING TO EXIST like Dave Krieg's college. And the OU links came from the highest ranking google hits when searching for relevant terms, which means this pathetic practice is easily observed by anyone. Maybe it's because I don't donate any money to them, but then I again, I completely paid for my own education other than the $250 I got from the Young American Bowling Alliance. But I didn't set out to criticize my university with this post, so I guess I should just let it go.

This is probably not the last post you will see about x86 assembly from me, but with any luck, my next post will be about cryptography. I know everyone in on the edge of their seats now. ;)

Saturday, March 19, 2005

Syntax Highlighting: What every parent should know

So, with only one post in between my admitted dislike for implementing FSAs, what do I do but go out and volunteer to implement one in one of my comments.

If you are too lazy to follow the links, I don't blame you. But the jist of it is that gus complained about the lack of syntax highlighting in all the code I have been posting lately.

I can't blame him. I have been a huge Larry Osterman fan since the Channel 9 post about the completion of his twentieth year at Microsoft. But the one complaint, well, not really complaint, but suggestion for improvement I would make for his blog is syntax highlighting.

So now I have written a small, quick and dirty MFC app to turn code snippets into syntax highlighted HTML. I am sure others have done this before me, but I thought it would be more interesting to write the app, than Googling until I found one. Being a quick and dirty app, I implemented the source to HTMLized functions as members of the main window class. Let's have a look at the definition of the class, syntax highlighted with my new tool:


///
/// <summary>
/// This class models the main window of the Snippet2Html application
/// </summary>
/// <author>Jim Barnett</author>
/// <date>3/18/2005</date>
///
class CMainWindow : public CDialog
{
public:
    CMainWindow(CWnd* pParent = 0);
    afx_msg void OnBnClickedCopyToClipboard();
    afx_msg void OnBnClickedHtmlify();
    static const int NONE = 0;
    static const int SLASH = 1;
    static const int SLASHSLASH = 2;
    static const int SLASHSTAR = 3;
    static const int SLASHSTARSTAR = 4;
    static const int LITERAL = 5;
    static const int LITERALESCAPE = 6;
    static const int CHARLITERAL = 7;
    static const int CHARLITERALESCAPE = 8;
    static const CString COMMENTHTML;
    static const CString ENDCOMMENT;
    static const CString ENDSPECIAL;
    static const CString SPECIALHTML;
    static const CString INITHTML;
    static const CString ENDHTML;
    enum { IDD = IDD_SNIPPET2HTML_DIALOG };

protected:
    bool CheckForReservedWord(int nState, int& nPos, CString& sHtmlified) const;
    virtual void DoDataExchange(CDataExchange* pDX);
    int HandleReservedWord(int nPos, CString sToken, CString& sCode) const;
    void HtmlifyCode();
    bool IgnoreReserved(int nState) const;
    bool IsSpecial(CString sToken) const;
    virtual BOOL OnInitDialog();
    afx_msg void OnPaint();
    afx_msg HCURSOR OnQueryDragIcon();
    HACCEL m_hAccel;
    HICON m_hIcon;
    CString m_sCode;
    static CStringArray m_sReservedOrDirective;
    BOOL m_fWebForm;
    DECLARE_MESSAGE_MAP()
};


Not terribly interesting by itself, so lets move on to the main function of interest and its helpers:


void CMainWindow::HtmlifyCode()
{
    /*
     * Comment to prove multiline comments do not always fail :)
     */
 
    VERIFY(UpdateData(true));

    CString sHtmlified = _T("");

    TCHAR chCurrent;
    int nState = NONE;
    int nCurPos = 0;
    CString sToken;

    for (int i = 0; i < m_sCode.GetLength(); ++i)
    {
        chCurrent = m_sCode.GetAt(i);
        
        switch (chCurrent)
        {
        case _T(' '):
            sHtmlified += _T("&nbsp;");
            if (nState == SLASH) nState = NONE;
            break;

        case _T('\t'):
            sHtmlified += _T("&nbsp;&nbsp;&nbsp;&nbsp;");
            if (nState == SLASH) nState = NONE;
            break;

        case _T('\n'):
            if (nState == SLASHSLASH)
            {
                sHtmlified += ENDCOMMENT;
                nState = NONE;
            }
            else if (nState == SLASH) nState = NONE;
            sHtmlified += _T("<br>");
            if (!m_fWebForm) sHtmlified += _T("\r\n");
            break;

        case _T('/'):
            switch (nState)
            {
            case NONE:
                sHtmlified += chCurrent;
                nState = SLASH;
                break;

            case SLASH:
                nState = SLASHSLASH;
                sHtmlified += chCurrent;
                sHtmlified.Insert(sHtmlified.GetLength()-2, COMMENTHTML);
                break;

            case SLASHSTARSTAR:
                nState = NONE;
                sHtmlified += chCurrent;
                sHtmlified += ENDCOMMENT;
                break;

            default:
                sHtmlified += chCurrent;
                break;

            }
            break;

        case _T('*'):
            switch (nState)
            {
            case SLASH:
                nState = SLASHSTAR;
                sHtmlified += chCurrent;
                sHtmlified.Insert(sHtmlified.GetLength()-2, COMMENTHTML);
                break;

            case SLASHSTAR:
                nState = SLASHSTARSTAR;
                sHtmlified += chCurrent;
                break;

            default:
                sHtmlified += chCurrent;
                break;

            }
            break;

        case _T('\r'):
            break// eat it

        case _T('"'):
            switch (nState)
            {
            case LITERAL:
                nState = NONE;
                break;

            case LITERALESCAPE:
                nState = LITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;

        case _T('\''):
            switch (nState)
            {
            case CHARLITERAL:
                nState = NONE;
                break;
            
            case NONE:
                nState = CHARLITERAL;
                break;

            case CHARLITERALESCAPE:
                nState = CHARLITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;
                
        case _T('<'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&lt;");
            break;

        case _T('>'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&gt;");
            break;

        case _T('&'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&amp;");
            break;

        case _T('\\'):
            switch (nState)
            {
            case LITERAL:
                nState = LITERALESCAPE;
                break;

            case CHARLITERAL:
                nState = CHARLITERALESCAPE;
                break;

            case LITERALESCAPE:
                nState = LITERAL;
                break;

            case CHARLITERALESCAPE:
                nState = CHARLITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;

        default:
            if (!CheckForReservedWord(nState, i, sHtmlified))
                sHtmlified += chCurrent;
            if (nState == SLASH) nState = NONE;
            else if (nState == CHARLITERALESCAPE) nState = CHARLITERAL;
            break;

        }
    }

    sHtmlified = INITHTML + sHtmlified;
    sHtmlified += ENDHTML;
    m_sCode = sHtmlified;
    UpdateData(false);
}


bool CMainWindow::IgnoreReserved(int nState) const
{
    if ((nState == SLASHSLASH) || (nState == SLASHSTAR) 
        || (nState == SLASHSTARSTAR) || (nState == LITERAL)
        || (nState == LITERALESCAPE))
        return true;
    else
        return false;
}


bool CMainWindow::IsSpecial(CString sToken) const
{
    for (INT_PTR i = 0; i < m_sReservedOrDirective.GetCount(); ++i)
    {
        if (sToken == m_sReservedOrDirective[i]) return true;
    }

    return false;
}


void CMainWindow::HtmlifyCode()
{
    /*
     * Comment to prove multiline comments do not always fail :)
     */
 
    VERIFY(UpdateData(true));

    CString sHtmlified = _T("");

    TCHAR chCurrent;
    int nState = NONE;
    int nCurPos = 0;
    CString sToken;

    for (int i = 0; i < m_sCode.GetLength(); ++i)
    {
        chCurrent = m_sCode.GetAt(i);
        
        switch (chCurrent)
        {
        case _T(' '):
            sHtmlified += _T("&nbsp;");
            if (nState == SLASH) nState = NONE;
            break;

        case _T('\t'):
            sHtmlified += _T("&nbsp;&nbsp;&nbsp;&nbsp;");
            if (nState == SLASH) nState = NONE;
            break;

        case _T('\n'):
            if (nState == SLASHSLASH)
            {
                sHtmlified += ENDCOMMENT;
                nState = NONE;
            }
            else if (nState == SLASH) nState = NONE;
            sHtmlified += _T("<br>");
            if (!m_fWebForm) sHtmlified += _T("\r\n");
            break;

        case _T('/'):
            switch (nState)
            {
            case NONE:
                sHtmlified += chCurrent;
                nState = SLASH;
                break;

            case SLASH:
                nState = SLASHSLASH;
                sHtmlified += chCurrent;
                sHtmlified.Insert(sHtmlified.GetLength()-2, COMMENTHTML);
                break;

            case SLASHSTARSTAR:
                nState = NONE;
                sHtmlified += chCurrent;
                sHtmlified += ENDCOMMENT;
                break;

            default:
                sHtmlified += chCurrent;
                break;

            }
            break;

        case _T('*'):
            switch (nState)
            {
            case SLASH:
                nState = SLASHSTAR;
                sHtmlified += chCurrent;
                sHtmlified.Insert(sHtmlified.GetLength()-2, COMMENTHTML);
                break;

            case SLASHSTAR:
                nState = SLASHSTARSTAR;
                sHtmlified += chCurrent;
                break;

            default:
                sHtmlified += chCurrent;
                break;

            }
            break;

        case _T('\r'):
            break// eat it

        case _T('"'):
            switch (nState)
            {
            case LITERAL:
                nState = NONE;
                break;

            case LITERALESCAPE:
                nState = LITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;

        case _T('\''):
            switch (nState)
            {
            case CHARLITERAL:
                nState = NONE;
                break;
            
            case NONE:
                nState = CHARLITERAL;
                break;

            case CHARLITERALESCAPE:
                nState = CHARLITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;
                
        case _T('<'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&lt;");
            break;

        case _T('>'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&gt;");
            break;

        case _T('&'):
            if (nState == SLASH) nState = NONE;
            sHtmlified += _T("&amp;");
            break;

        case _T('\\'):
            switch (nState)
            {
            case LITERAL:
                nState = LITERALESCAPE;
                break;

            case CHARLITERAL:
                nState = CHARLITERALESCAPE;
                break;

            case LITERALESCAPE:
                nState = LITERAL;
                break;

            case CHARLITERALESCAPE:
                nState = CHARLITERAL;
                break;

            }
            if (nState == SLASH) nState = NONE;
            sHtmlified += chCurrent;
            break;

        default:
            if (!CheckForReservedWord(nState, i, sHtmlified))
                sHtmlified += chCurrent;
            if (nState == SLASH) nState = NONE;
            else if (nState == CHARLITERALESCAPE) nState = CHARLITERAL;
            break;

        }
    }

    sHtmlified = INITHTML + sHtmlified;
    sHtmlified += ENDHTML;
    m_sCode = sHtmlified;
    UpdateData(false);
}


bool CMainWindow::IgnoreReserved(int nState) const
{
    if ((nState == SLASHSLASH) || (nState == SLASHSTAR) 
        || (nState == SLASHSTARSTAR) || (nState == LITERAL)
        || (nState == LITERALESCAPE))
        return true;
    else
        return false;
}


bool CMainWindow::IsSpecial(CString sToken) const
{
    for (INT_PTR i = 0; i < m_sReservedOrDirective.GetCount(); ++i)
    {
        if (sToken == m_sReservedOrDirective[i]) return true;
    }

    return false;
}


bool CMainWindow::CheckForReservedWord(int nState, int& nPos, 
    CString& sHtmlified) const
{
    int nOrigPos = nPos;

    const CString sDelimiters = _T(" \n\t+-\\*~<>!=&;:.{}[]()|^%\\/?',=");

    // Get the next token
    CString sToken = m_sCode.Tokenize(
        _T(" \n\t+-\\*~<>!=&;:.{}[]()|^%\\/?',="), nOrigPos);

    CString sNextChars = (m_sCode.Left(nPos+sToken.GetLength())).Right(
        sToken.GetLength());

    bool fAtTokenStart = (nPos == 0) ? true
        : (sDelimiters.Find(m_sCode.GetAt(nPos-1)) != -1);

    if (IsSpecial(sToken) && !IgnoreReserved(nState) 
        && (sToken == sNextChars) && fAtTokenStart)
    {
        nPos += HandleReservedWord(nPos, sToken, sHtmlified);
        return true;
    }

    return false;
}


I guess you could say I cheated a little since I only used the automaton to do the highlighting of comments and wrote some helper functions to deal with the keywords/preprocessor directives. One of the main shortcomings of my simple approach is that context senstive preprocessor directives are not supported (such as the the #pragma once directive, particularly the "once" token. You could criticize the memory usage of this algorithm since I used another CString to insert the HTML rather than just inserting the HTML right into m_sCode. I think that would have been messier, and it would have been an unnecessary performance hack.

A lot of these web form interfaces don't let you have decently formatted HTML without screwing up your original intention. They tend to interpret <br>\n as two lines, which kept double spacing my code. The m_fWebForm boolean variable indicates wherther you want one big nasty line of HTML if true, or you want decently formatted, somewhat human readable HTML if false. It took a fair amount of work to figure out what truly caused the double-spaced code. This task proved to be much more of a learning experience than I intended, but I guess that could be a good thing.

I am already planning on some improvements. It would be really easy to add highlighting to string and char literals. If I modified it to read values from a file for some variables that are currently hard-coded, this app could be made language agnostic. I may do that just for the fun of it, but I am self-admitted C++ elitist.

So, that is it. Is this any better, gus?

Tuesday, March 15, 2005

Scoring a game of bowling

So, I have mostly finished writing the class to model a game of bowling. I have tested the game code, and it was kind of painful. While writing the code to test the scoring functions, I noticed the code base getting uglier and uglier. After feeling like most of the class was sufficiently debugged, I took a moment to reflect and realized most of the ugliness was in the test code, which made me feel a whole lot better about myself. I think I have way too fragile of an ego to post the debugging code, but since I have nothing to blog about outside the development of this application, I thought I would go ahead and post the scoring code.

Here is the definition of the class modelling a game of bowling:

class CGame : public CObject
{
public:
CGame();
virtual ~CGame();
void ScoreFrame(int nFrame);
void ScoreGame();
void ScoreTenthFrame();
void SetRegularFrame(CFrame* pFrame);
void SetTenthFrame(CTenthFrame* pTenthFrame);

#ifdef _DEBUG
int CalculateScoreByFrame(int nFrame);
void DumpGame();
void MakeFrame(int nFrame, TCHAR chFirst, TCHAR chSecond);
void MakeTenthFrame(TCHAR chFirst, TCHAR chSecond, TCHAR chThird);
void StringToGame(CString sGame);
static bool TestGame();
#endif

static const int NUMREGULARFRAMES = 9;
protected:
int m_nCompletedFrames;
int m_nScoredFrames;
int m_nScoreByFrame[NUMFRAMES];
CFrame* m_pFrames[NUMREGULARFRAMES];
CTenthFrame* m_pTenthFrame;

private:
operator=(const CGame& Game) {};
CGame(const CGame& Game) {};
};

I left the debugging member function declarations in there for an exercise to the read to imagine their ugliness. Believe me, it is probably worse than you imagine. I don't think this class is done, but it most of the way, and it is sufficiently defined to test the major points of functionality. Oh yeah, and NUMFRAMES is defined in a separate header of global constants. I hope you aren't surprised to learn its value is 10. So lets take a look at the highest level function, ScoreGame.

void CGame::ScoreGame()
{
for (int i = 0; i < NUMREGULARFRAMES; ++i)
ScoreFrame(i+1);

ScoreTenthFrame();
}

Pretty clean so far. You can't ask for too much more. So how about the function to score a non-tenth frame of bowling with a zero-based index as a parameter.

void CGame::ScoreFrame(int nFrame)
{
ASSERT(nFrame >= 1 && nFrame <= NUMREGULARFRAMES);

if (m_pFrames[nFrame-1]->IsMark())
{
m_nScoreByFrame[nFrame-1] = 10;
}
else
{
m_nScoreByFrame[nFrame-1] = m_pFrames[nFrame-1]->GetCount(1)
+ m_pFrames[nFrame-1]->GetCount(2);
}

if (nFrame >= 2)
{
if (m_pFrames[nFrame-2]->IsSpare())
{
m_nScoreByFrame[nFrame-2] += m_pFrames[nFrame-1]->GetCount(1);
}
else if (m_pFrames[nFrame-2]->IsStrike())
{
if (m_pFrames[nFrame-1]->IsStrike())
{
m_nScoreByFrame[nFrame-2] += 10;
}
else
{
m_nScoreByFrame[nFrame-2] += m_pFrames[nFrame-1]->GetCount(1)
+ m_pFrames[nFrame-1]->GetCount(2);
}
}
}

if (nFrame >= 3)
{
if (m_pFrames[nFrame-3]->IsStrike() && m_pFrames[nFrame-2]->IsStrike())
m_nScoreByFrame[nFrame-3] += m_pFrames[nFrame-1]->GetCount(1);
}
}

Still pretty clean here. Some people might bitch about the nesting level, but that is a style holy war I am not wanting to get involved in. Besides, if you have never worked in statements conditionals nested three deep, you are either some functional programming language sicko or a freshmen undergrad. So how about scoring tenth frame?

void CGame::ScoreTenthFrame()
{
// Check for double in 8th and 9th
if (m_pFrames[7]->IsStrike() && m_pFrames[8]->IsStrike())
{
m_nScoreByFrame[7] += m_pTenthFrame->GetCount(1);
m_nScoreByFrame[8] += m_pTenthFrame->GetCount(1)
+ m_pTenthFrame->GetCount(2);
}
else if (m_pFrames[8]->IsSpare())
{
m_nScoreByFrame[8] += m_pTenthFrame->GetCount(1);
}

m_nScoreByFrame[9] = m_pTenthFrame->GetCount(1)
+ m_pTenthFrame->GetCount(2);

if (m_pTenthFrame->IsMark())
m_nScoreByFrame[9] += m_pTenthFrame->GetCount(3);
}

This code still fairly clean. I suppose some CS professor or software architect type might ding me about the magic numbers, and the CTenthFrame class as opposed to CFinalFrame class with a member indicating the number of the final frame. But in all honesty, I have no intentions of this software being able to handle 15 frame games of bowling a la Randy Quaid in Kinpin. I don't have any inclination to make this score games of candle pin or duck pin, either, so all you Canucks, lay off. :) I guess you could bitch about the magic numbers in the ScoreFrame function as well. I have to say, I won't lose sleep if my application doesn't score games of bowling in bizarro world that number frames -5 to 5. I just don't think it is necessary to define something like:

const int NINTHFRAME = 8;

when I have it so firmly in grained that array indices are zero-based. As tangent, here is one of my favorite computer sciences quotes that undoubtedly exists to poke fun at programming language style preference holy wars:

Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration. (Stan Kelly-Bootle)

Okay, so I have hinted at underlying ugliness this entire post. It involves the functions for counting pinfall. Let's take a look at the ugliness in increasing order of ugly.

int CShot::GetCount()
{
switch (m_wResult)
{
case MISS:
case FOUL:
return 0;

case STRIKE:
return 10;

case SPARE:
return 10;

default:
int nCount = 0;
for (int i = 0; i < 10; ++i)
{
if ((m_wResult & (1 << i)) != 0)
++nCount;
}
return nCount;
}
}

Not *too* bad, but I can do better: :)

int CFrame::GetCount(int nShot)
{
ASSERT(nShot == 1 || nShot == 2);

if (nShot == 2 &&
((m_pSecondShot->GetResult() & (CShot::MISS | CShot::FOUL)) != 0))
return 0;

return (nShot == 1) ? m_pFirstShot->GetCount()
: m_pSecondShot->GetCount() - m_pFirstShot->GetCount();
}

Not terrible on its own, but now we have some layered ugliness. It is still prettier than Edward James Olmos.

int CTenthFrame::GetCount(int nShot)
{
ASSERT(nShot >= 1 && nShot <= 3);

switch (nShot)
{
case 1:
return m_pFirstShot->GetCount();

case 2:
if ((m_pSecondShot->GetResult() & (CShot::MISS | CShot::FOUL)) != 0)
return 0;

if ((m_pFirstShot->GetResult() & CShot::STRIKE) != 0)
{
return m_pSecondShot->GetCount();
}
else
{
return (m_pSecondShot->GetCount() - m_pFirstShot->GetCount());
}
case 3:
if ((m_pThirdShot->GetResult() & (CShot::MISS | CShot::FOUL)) != 0)
return 0;
else if (((m_pFirstShot->GetResult() & CShot::STRIKE) != 0)
&& ((m_pSecondShot->GetResult() & CShot::STRIKE) == 0))
return (m_pThirdShot->GetCount()-m_pSecondShot->GetCount());

return m_pThirdShot->GetCount();
}

return -1; // Unreachable without corrupting nShot
}

Now I know I have seen/worked with/written uglier code, but what bothers me about it is that the ugliness is a symptom of earlier architecture decisions I had made and, arguably, forgotten about with code developed later. But on the other hand, I feel reasonably confident about the extensible requirements of this code. I also realize it is doubtful a significant number of people. Plus, the size of this code base will not be terribly large when the application is finished. I think a developer has to know when to compromise elegance for productivity. Well, now that I seem to be going somewhere with this post, namely, appropriately evaluating the need for code quality for a situation, I feel like I am okay posting some of the uglier test code:

void CGame::MakeFrame(int nFrame, TCHAR chFirst, TCHAR chSecond)
{
TRACE(_T("MakeFrame: chFirst = %c, chSecond = %c\n"), chFirst, (chSecond) ? chSecond : _T('0'));

CShot* p1stShot = new CShot;
CShot* p2ndShot = 0;
WORD wResult = 0;
int nCount = 0;
int nFirstShotCount = 0;

switch (chFirst)
{
case _T('X'):
p1stShot->SetResult(CShot::STRIKE);
break;

case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
nCount = static_cast(chFirst - _T('0'));
for (int i = 0; i < nCount; ++i)
wResult |= (1 << i);
p1stShot->SetResult(wResult);
break;

case _T('-'):
p1stShot->SetResult(CShot::MISS);
break;

case _T('F'):
p1stShot->SetResult(CShot::FOUL);
break;

}

m_pFrames[nFrame]->SetFirstShot(p1stShot);

switch (chSecond)
{
case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
p2ndShot = new CShot;
nCount = static_cast(chSecond - _T('0'));
nFirstShotCount = p1stShot->GetCount();
wResult = p1stShot->GetResult();
for (int i = 0; i < nCount; ++i)
wResult |= (1 << (i+nFirstShotCount));
p2ndShot->SetResult(wResult);
break;

case _T('-'):
p2ndShot = new CShot;
p2ndShot->SetResult(CShot::MISS);
break;

case _T('F'):
p2ndShot = new CShot;
p2ndShot->SetResult(CShot::FOUL);
break;

case _T('/'):
p2ndShot = new CShot;
p2ndShot->SetResult(CShot::SPARE);
break;

}
if (p2ndShot != 0) m_pFrames[nFrame]->SetSecondShot(p2ndShot);
}

void CGame::MakeTenthFrame(TCHAR chFirst, TCHAR chSecond, TCHAR chThird)
{
TRACE(_T("MakeTenthFrame: %c, %c, %c\n"), chFirst, chSecond, (chThird) ? chThird : _T('0'));

CShot* p1stShot = new CShot;
CShot* p2ndShot = new CShot;
CShot* p3rdShot = 0;
int nCount = 0;
int nFirstShotCount = 0;
bool fMark = false;
WORD wResult = 0;

switch (chFirst)
{
case _T('X'):
fMark = true;
p3rdShot = new CShot;
p1stShot->SetResult(CShot::STRIKE);
break;

case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
nCount = static_cast(chFirst - _T('0'));
for (int i = 0; i < nCount; ++i)
wResult |= (1 << i);
p1stShot->SetResult(wResult);
break;

case _T('-'):
p1stShot->SetResult(CShot::MISS);
break;

case _T('F'):
p1stShot->SetResult(CShot::FOUL);
break;

}

m_pTenthFrame->SetFirstShot(p1stShot);

switch (chSecond)
{
case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
nCount = static_cast(chSecond - _T('0'));
if ((p1stShot->GetResult() & CShot::STRIKE) != 0)
{
nFirstShotCount = 0;
wResult = 0;
}
else
{
wResult = p1stShot->GetResult();
wResult &= ~(CShot::FOUL|CShot::MISS);
nFirstShotCount = p1stShot->GetCount();
}

for (int i = 0; i < nCount; ++i)
wResult |= (1 << (i+nFirstShotCount));
p2ndShot->SetResult(wResult);
break;

case _T('-'):
p2ndShot->SetResult(CShot::MISS);
break;

case _T('F'):
p2ndShot->SetResult(CShot::FOUL);
break;

case _T('/'):
fMark = true;
p3rdShot = new CShot;
p2ndShot->SetResult(CShot::SPARE);
break;

case _T('X'):
p2ndShot->SetResult(CShot::STRIKE);
break;

}

m_pTenthFrame->SetSecondShot(p2ndShot);

if (fMark)
{
switch (chThird)
{
case _T('X'):
p3rdShot->SetResult(CShot::STRIKE);
break;

case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
if (chSecond == _T('X') || chSecond == _T('/'))
{
nCount = chThird - _T('0');
for (int i = 0; i < nCount; ++i)
wResult |= (1 << i);
p3rdShot->SetResult(wResult);
}
else
{
// Handle strike on first ball, non-strike on second
// Reuse nFirstShotCount even though we want the second
// shot count
nCount = static_cast(chThird - _T('0'));
nFirstShotCount = p2ndShot->GetCount();
wResult = p2ndShot->GetResult();
for (int i = 0; i < nCount-nFirstShotCount; ++i)
wResult |= (1 << (i+nFirstShotCount));
p3rdShot->SetResult(wResult);
}
break;

case _T('-'):
p3rdShot->SetResult(CShot::MISS);
break;

case _T('F'):
p3rdShot->SetResult(CShot::FOUL);
break;

case _T('/'):
p3rdShot->SetResult(CShot::SPARE);
break;

}
m_pTenthFrame->SetThirdShot(p3rdShot);
}
}

void CGame::StringToGame(CString sGame)
{
bool fSecondShot = false;
int nLength = sGame.GetLength();
int nFrame = 0;
TCHAR chSecond = 0;
TCHAR chThird = 0;
int nStrikes = 0;

for (int i = 0; i < NUMREGULARFRAMES; ++i)
{
m_pFrames[i] = new CFrame;
}

m_pTenthFrame = new CTenthFrame;

for (int i = 0; i < nLength; ++i)
{
TCHAR chFirst = sGame.GetAt(i);

switch (chFirst)
{
case _T('X'):
switch (nFrame)
{
case 0: case 1: case 2: case 3: case 4:
case 5: case 6: case 7: case 8:
MakeFrame(nFrame, chFirst, 0);
++nStrikes;
++nFrame;
break;

case 9:
if ((sGame.GetAt(nLength-2) == _T('/'))
|| ((sGame.GetAt(nLength-3)) == _T('X')) && (nStrikes+i == 18))
{
chSecond = sGame.GetAt(nLength-2);
chThird = sGame.GetAt(nLength-1);
}
else
{
// Get last three shots and figure out if it were all in
// the 10th
chFirst = sGame.GetAt(nLength-3);
chSecond = sGame.GetAt(nLength-2);
chThird = sGame.GetAt(nLength-1);

// A bad game of bowling (no strikes) would consist of 18
// shots leading into the 10th

// check for X followed on shot two shots before end, then
// check length of string to figure out if that strike was
// in the ninth or tenth
if (chFirst == _T('X') && (i+nStrikes < 18))
{
chFirst = chSecond;
chSecond = chThird;
chThird = 0;
}
}
MakeTenthFrame(chFirst, chSecond, chThird);
++nFrame;
break;

}
break;

case _T('-'):
case _T('F'):
case _T('1'):
case _T('2'):
case _T('3'):
case _T('4'):
case _T('5'):
case _T('6'):
case _T('7'):
case _T('8'):
case _T('9'):
switch (nFrame)
{
case 0: case 1: case 2: case 3: case 4:
case 5: case 6: case 7: case 8:
++i;
chSecond = sGame.GetAt(i);
MakeFrame(nFrame, chFirst, chSecond);
++nFrame;
break;

case 9:
++i;
chSecond = sGame.GetAt(i);
chThird = (nLength - nStrikes == 2) ? 0 : sGame.GetAt(nLength-1);
MakeTenthFrame(chFirst, chSecond, chThird);
++nFrame;
break;

}
break;

}
}
}

void CGame::DumpGame()
{
CString sFmt;
CString sBuf;
CString sResult[10];
int nScoreByFrame = 0;
bool fMarkIn10th = false;

sFmt = _T("______________________________________________________________\n");
sFmt += _T("|1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |\n");
sFmt += _T("| %2s | %2s | %2s | %2s | %2s | %2s | %2s | %2s | %2s | %3s |\n");
sFmt += _T("| %3d | %3d | %3d | %3d | %3d | %3d | %3d | %3d | %3d | %3d |\n");
sFmt += _T("|_____|_____|_____|_____|_____|_____|_____|_____|_____|______|\n");

for (int i = 0; i < NUMREGULARFRAMES; ++i)
{
if (m_pFrames[i]->IsStrike())
{
// First shot was a strike
sResult[i].AppendChar(_T('X'));
}
else if (m_pFrames[i]->IsSpare())
{
if ((m_pFrames[i]->GetFirstShot()->GetResult() & CShot::MISS) != 0)
{
// First shot was a miss
sResult[i].AppendChar(_T('-'));
}
else if ((m_pFrames[i]->GetFirstShot()->GetResult()
& CShot::FOUL) != 0)
{
// First shout was a foul
sResult[i].AppendChar(_T('F'));
}
else
{
// First shot knocked down pins, but wasn't a strike
sResult[i].AppendChar(static_cast(
m_pFrames[i]->GetCount(1)) + _T('0'));
}
sResult[i].AppendChar(_T('/'));
}
else
{
// If we are in this block, we opened in the given frame
if ((m_pFrames[i]->GetFirstShot()->GetResult() & CShot::MISS) != 0)
{
// First shot was a miss
sResult[i].AppendChar(_T('-'));
}
else if ((m_pFrames[i]->GetFirstShot()->GetResult() & CShot::FOUL)
!= 0)
{
// First shot was a foul
sResult[i].AppendChar(_T('F'));
}
else
{
// First shot knocked down pins, but wasn't a strike and we
// didn't spare
sResult[i].AppendChar(static_cast(
m_pFrames[i]->GetCount(1))+_T('0'));
}

if ((m_pFrames[i]->GetSecondShot()->GetResult() & CShot::MISS) != 0)
{
// Second shot was a miss
sResult[i].AppendChar(_T('-'));
}
else if ((m_pFrames[i]->GetSecondShot()->GetResult()
& CShot::FOUL) != 0)
{
// Second shot was a foul
sResult[i].AppendChar(_T('F'));
}
else
{
// We knocked down pins on the second ball, but didn't spare
sResult[i].AppendChar(static_cast(
m_pFrames[i]->GetCount(2))+_T('0'));
}
}
}

// Now process the 10th frame, first shot
if ((m_pTenthFrame->GetFirstShot()->GetResult() & CShot::STRIKE) != 0)
{
fMarkIn10th = true;
sResult[9].AppendChar(_T('X'));
}
else if ((m_pTenthFrame->GetFirstShot()->GetResult() & CShot::MISS) != 0)
{
sResult[9].AppendChar(_T('-'));
}
else if ((m_pTenthFrame->GetFirstShot()->GetResult() & CShot::FOUL) != 0)
{
sResult[9].AppendChar(_T('F'));
}
else
{
sResult[9].AppendChar(static_cast(m_pTenthFrame->GetCount(1))
+ _T('0'));
}

// Process second shot in the tenth
if ((m_pTenthFrame->GetSecondShot()->GetResult() & CShot::SPARE) != 0)
{
fMarkIn10th = true;
sResult[9].AppendChar(_T('/'));
}
else if ((m_pTenthFrame->GetSecondShot()->GetResult()
& CShot::STRIKE) != 0)
{
sResult[9].AppendChar(_T('X'));
}
else if ((m_pTenthFrame->GetSecondShot()->GetResult()
& CShot::MISS) != 0)
{
sResult[9].AppendChar(_T('-'));
}
else if ((m_pTenthFrame->GetSecondShot()->GetResult()
& CShot::FOUL) != 0)
{
sResult[9].AppendChar(_T('F'));
}
else
{
// Handle an open in the 10th that knocked down pins on the second
// shot, or a strike followed by the first shot of a non-strike
if ((m_pTenthFrame->GetFirstShot()->GetResult() & CShot::STRIKE) != 0)
{
sResult[9].AppendChar(m_pTenthFrame->GetSecondShot()->GetCount()
+ _T('0'));
}
else
{
sResult[9].AppendChar((m_pTenthFrame->GetSecondShot()->GetCount()
- m_pTenthFrame->GetFirstShot()->GetCount() + _T('0')));
}
}

// Handle third shot in the 10th
if (fMarkIn10th)
{
if ((m_pTenthFrame->GetThirdShot()->GetResult() & CShot::STRIKE) != 0)
{
// Spared and then struck in 10th, or struck out in the 10th
sResult[9].AppendChar(_T('X'));
}
else if ((m_pTenthFrame->GetThirdShot()->GetResult() & CShot::SPARE)
!= 0)
{
// Struck then spared in the 10th
sResult[9].AppendChar(_T('/'));
}
else if ((m_pTenthFrame->GetThirdShot()->GetResult()
& CShot::MISS) != 0)
{
// Either threw a double or a spare, then a miss
sResult[9].AppendChar(_T('-'));
}
else if ((m_pTenthFrame->GetThirdShot()->GetResult()
& CShot::FOUL) != 0)
{
// Either threw a double or a spare, then a foul
sResult[9].AppendChar(_T('F'));
}
else
{
if (((m_pTenthFrame->GetFirstShot()->GetResult() & CShot::STRIKE) != 0)
&& (m_pTenthFrame->GetSecondShot()->GetResult() & CShot::STRIKE) == 0)
sResult[9].AppendChar(m_pTenthFrame->GetThirdShot()->GetCount()
- m_pTenthFrame->GetSecondShot()->GetCount()+_T('0'));
else if ((m_pTenthFrame->GetSecondShot()->GetResult() & CShot::SPARE) != 0)
sResult[9].AppendChar(m_pTenthFrame->GetCount(3)+_T('0'));
}
}

int nScore[10];

for (int i = 0; i < 10; i++)
nScore[i] = CalculateScoreByFrame(i);

sBuf.Format(sFmt, sResult[0], sResult[1], sResult[2], sResult[3],
sResult[4], sResult[5], sResult[6], sResult[7], sResult[8], sResult[9],
nScore[0], nScore[1], nScore[2], nScore[3], nScore[4], nScore[5],
nScore[6], nScore[7], nScore[8], nScore[9]);

TRACE(sBuf);
}

And why not at this point? The mother of the ugliness:

bool CGame::TestGame()
{
CStringArray TestGames;
CArray Games;
TestGames.Add(_T("XXXXXXXXXF-"));
TestGames.Add(_T("8/8/8/8/8/8/8/8/8/F2"));
TestGames.Add(_T("9/9-9/9-9/9-9/9-9/9-"));
// 1 2 3 4 5 6 7 8 9 10
TestGames.Add(_T("9/9/9/9/9/9/9/9/9/-1"));
// 12345678910
TestGames.Add(_T("XXXXXXXXXX9/"));
// 1 2 345678910
TestGames.Add(_T("9/9/XXXXXXXXXX"));
// 1234 56 78910
TestGames.Add(_T("XXX9/X9/XXXXXX"));
TestGames.Add(_T("XXX9/XX9/XXXXX"));
TestGames.Add(_T("XXX9/9/XXXXXXX"));
TestGames.Add(_T("11111111111111111111"));
TestGames.Add(_T("22222222222222222222"));
TestGames.Add(_T("33333333333333333333"));
TestGames.Add(_T("81188118811881188118"));
// 12345678901234567890
TestGames.Add(_T("9/9/9/9/9/9/9/9/9/9/9"));
// 12 34 56 78 910
TestGames.Add(_T("XF/X-/XF/X-/XF/X"));
TestGames.Add(_T("44444444444444444444"));
TestGames.Add(_T("--------------------"));
TestGames.Add(_T("8/8/8/8/8/8/8/8/8/8/8"));
TestGames.Add(_T("7/7/7/7/7/7/7/7/7/7/7"));
TestGames.Add(_T("6/6/6/6/6/6/6/6/6/6/6"));
TestGames.Add(_T("5/5/5/5/5/5/5/5/5/5/5"));
TestGames.Add(_T("4/4/4/4/4/4/4/4/4/4/4"));
TestGames.Add(_T("3/3/3/3/3/3/3/3/3/3/3"));
TestGames.Add(_T("2/2/2/2/2/2/2/2/2/2/2"));
TestGames.Add(_T("1/1/1/1/1/1/1/1/1/1/1"));
TestGames.Add(_T("-/-/-/-/-/-/-/-/-/-/-"));
TestGames.Add(_T("9-XXXXXXXXXXX"));
TestGames.Add(_T("9/XXXXXXXXXXX"));
TestGames.Add(_T("9-9-9-9-9-9-9-9-9-9-"));
TestGames.Add(_T("XXXXXXXXXXXX"));
TestGames.Add(_T("F/X-/XF/X-/XF/X-/"));
TestGames.Add(_T("X9/XXXXXXXXXX"));

for (int i = 0; i < TestGames.GetCount(); ++i)
{
Games.Add(new CGame);
Games[i]->StringToGame(TestGames[i]);
TRACE(_T("Game %d is %s\n"), i+1, TestGames[i]);
Games[i]->ScoreGame();
Games[i]->DumpGame();
delete Games[i];
}

return true;
}

Yeah, I got bit in the ass several times because I had no function that attempted to validate a string as a game of bowling before I fed it into the code that mattered. The point is that in realistic software development environments, this could would be refactored if it were to become anything more than throw away test-to-give-the-developer-a-warm-fuzzy code.

Oh, and it is way to big of pain in the the ass to spell check a post when you have this much code. Just assume all typos were either me being tired or having a good enough grasp of the english language to take some liberties with the rules.

Sunday, March 13, 2005

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...

Friday, March 04, 2005

My Phone Can Beat Up Your PDA

So, I bought the Motorola MPx220. It totally rules, and I am hella excited about the idea of having a phone I can write programs for. Or having a phone for which I can write programs. Whatever.

The camera is a bit of a disappointment, and I kind of wish it took regular SD cards instead of mini-SDs. Especially since I bought a 1 GB SD card thinking it would work. I did end up buying a 256 MB mini-SD, but I don't feel like quite the big man I would if I could carry a gig of Pictures of Richard Nixon on my phone.

The first application I want to write is a bowling tracker. After each frame, I can come tell it whether I threw a strike, a spare, or an open, and the pins I left as a spare if applicable. Then it would sync with a desktop component that would store everything in a database and calculate some meaningful values like:

Average Score
Average Score by Game (1st, 2nd, or 3rd of three game sets)
Strike Percentage
Spare Percentage
Single Pin Conversion Percentage
Multi-pin Spare Conversion Percentage
Split Leave Percentage
Split Conversion Percentage
etc.

I would like to make it capable of tracking more esoteric stats than you would even hear from a baseball announcer.

I am sure it would sell more copies than Windows 95 did. I mean, come on. Bowlers serious enough to take the effort to record each shot who also happen to have a smart phone running Windows? That is no niche market! Actually, I think I am the only one.

In bowling related news, I had the first nine strikes in the first game of league the week before last. I threw the first shot in the tenth too softly, it finished high and I ended up shooting 277. I suck.