Another One Bites the Dust

I think I'm back in the game. My score is now 74.

Project Euler Status Report

Today I cracked not one, but two Project Euler problems: numbers 76 and 63. Woo-hoo! For the longest time I was stuck, but persistence finally paid off. My score is now 72.  I should not have been stuck for so long, but it is what it is. I'm not the best Project Euler competitor by a very long shot. I don't have great knowledge of  number theory and algorithms, but I'm working on it. Now, at least I know what "partition" means in number theory.

Knowing the correct math terminology makes it much easier to research solutions. I need to spend some more time with a number theory text, pencil and paper. I never thought I would spend time on this kind of math...

By the way, yes, the "private email" listed in the image will connect to me. It's not the best way, but it will work. 

CA project status

The cellular automata project continues.  It is currently working in a bare-bones, command line manner. You can load start files in plaintext (.cells) format, start in single step mode, toggle on/off single step mode while the program is running and select fixed plane or toroid modes on startup. It's now actually usable.

The toroidal surface took longer than expected, which seems to be the norm for me. (I had changed the code for countNeighbors() in the C++ version and  I had some incorrect code to handle cells on the edges. It took me a while to sort it out.) The code is up on launchpad.

Features to work on:

• Save a snapshot of the current state to a plaintext (.cells) file.
• Input rulesets from the command line.
• Set the global constants from a configuration file.

Hey, it works!

Earlier, I determined that I would need to implement just a few more functions in C++ to get a bare-bones version of my cellular automaton (CA) program working. Here's a list of the necessary functions:

• countNeighbors
• cellNextgen
• updateCAMatrix
• a 2D vector to hold the ruleset information

 I wrote out the functions using pencil and paper. True to my past performance, none of them ran as written on paper. One of these days, I'll get it right from the get-go. Whatever. At least I was correct in that these were the functions required get the job done. At the end of a small hack-a-thon, I was left with a working, bare-bones version of Conway's Game of life. I decided not to fill the blog up with too much source code. If you're interested, the source code is available here on launchpad. I'll only add code snippets as necessary, or when I just feel like it.

Next on the agenda is implementing:

• Toroidal surface version.
• Single step mode.
• Start pattern file input.

The nice thing about C++ is that it is faster than Python. In this case, the C++ version of the CA program is much, much faster than the Python version. It's so much faster that I want to take another look at my Python code to see if there's something amiss. I think C++  is my new language of choice for sound and graphics.

The downside is that C++ is more painful for me to code in. Part of it is my ignorance, and part of it is just the nature of C++. I studied things like "pass by reference", "pass by value" and "dynamic memory allocation" in school, and I quickly left them behind because I was an electrical engineering student, studying other topics. Now that I've started writing more code, and I'm beginning to use C++, I have to start paying attention to these things.

Python is free and easy language. Python has automatic memory management (garbage collection), while in C++ the programmer must take out the trash. C++ has static typing; Python has dynamic typing. C++ is compiled; Python is interpreted. These differences make Python much easier to use, which means it is much faster to write code in. C++ is more painful to code in, but it sure runs fast. The C++ CA program runs so fast compared to Python version that I think it's worth the trouble of climbing the C++ learning curve. And what a steep curve it is! This is going to take a while.

One problem that I notice when asking Google how to do things with C++ is the widespread use of C idioms and libraries to solve problems in C++. While C++ was developed from C, and can run almost everything just like C, it also has a number of distinctly C++ ways of handling tasks. It seems that so many C coders segued into C++ they carried many of their C solutions into C++ code. For example, I wanted to convert some text into an integer. Google shows that many people would use a C method:

...

#include <stdlib.h>

...

...

int myint;

char *mystring;

...

myint = atoi(mystring)

...

which works just fine in C++. It's just that C++ has another way, a native C++ way to do the same thing.
        ...
        #include <string>
        #include <sstream>

        using namespace std;
        ...
        ...
        int myint;
        string mystring;
        stringtream ss;
        stringstream ss;
        ...
        ...
        ss << mystring;
        ss >> myint;

I don't have a big problem with using C idioms in C++; it's just that while studying Python I found it best to write Python code in Python, not translated Scheme or C. I suspect that this will hold true in C++ as well.  While it's true for this example the C code is nice and concise, the C++ version is pretty flexible and can do some interesting things. For example, it could parse a long string of whitespace separated items, and deposit each item into a separate variable. The variables could have varying types, if desired. The infrastructure is already there. I'm just learning this C++ stuff, but it seems to me that you might not always want to immediately just grab a tool from C to tackle a problem in C++.

Another problem is C++ has changed over the years. If in searching for C++ wisdom you see something like #include in sample code, go somewhere else. That does not work anymore, and hasn't for a while.

I've been working through Lazy Foo's Beginning Game Programming tutorials. These tutorials are using Simple Directmedia Layer  so they are of great interest to me. I highly recommend them. I got a copy of Programming Linux Games:  Building Multimedia Applications with SDL, OpenAL(tm), and Other APIs by Loki Software, Inc. with John R. Hall. These days I don't buy too many computer books because they are expensive, often quickly obsolete and just do not give you a lot of bang for your buck. I mean, Google is pretty good at answering questions about computing, and my local library has beau coup books on the subject, as well as a subscription to Safari Books Online. I made an exception for this book, because it's from the people who developed SDL, and the excerpts looked pretty good. Now that I have it in my hands, I glad I spent the money. It's a little old (I think some things have changed with SDL since the book was written), but it's still pretty solid.

Sadly, the author, John R. Hall, is now blessed memory. He died way too young. My condolences to his family and friends.

Pseudo-Life

Nothing much to report here. I worked a bit on the cellular automata program; now it generates screen after screen of random patterns. This is not the final goal, but it is a step in the right direction. A game of pseudo-life, instead of Conway's life. When I first compiled and ran this bit of code, I saw something strange. In just a few moments the screen would fill up with green blocks. It took me a little while to figure out what the problem was. D'oh! I neglected to clear the cells vector, which would keep on magically growing. This gives you a minty green screen o' blocks.

I kept pouring over the SDL sections of the code. There was no problem with SDL code, just the plain vanilla C++ code. Happy cells.clear(); to all.

I went through the Python version of this program and figured out what functions would have to be ported to get a bare bones working version of the program. It looks like just a few:

• countNeighbors
• cellNextgen
• updateCAMatrix
• a 2D vector to hold the ruleset information.

No I haven't posted them yet -- they're still vaporware. They will all be showing up as I go along. I actually coded them using pencil and paper, but to date I have a poor track record of writing down working code with pencil and paper. I will code and debug them, then post.

One thing I learned after writing the paper and pencil code is that using c++ vector <bool> is probably not a good idea. Too bad, it looks so good on paper.

#include <iostream>
#include <vector>
#include <cstdlib>
#include "SDL/SDL.h"

using namespace std;

// Globals
const int XRES = 1024;
const int YRES = 768;
const int BLOCKSIZE = 4;
const int DELTA_T = 250;
const int FCOLOR = 0x0000FF00;
const int BCOLOR = 0x00000000;
const int ROWS = YRES / BLOCKSIZE;
const int COLS = XRES / BLOCKSIZE;

int randomStart(vector & cells, vector > & world) {
        srand(time(NULL));

        SDL_Rect p;
        int pct;

        for (int row = 0; row < ROWS; ++row)
        {
            for (int col = 0; col < COLS; ++col)
            {
                pct  = rand() % 1000;
                if (pct < 200)
                {
                    p.x = col * BLOCKSIZE;
                    p.y = row * BLOCKSIZE;
                    p.w = BLOCKSIZE;
                    p.h = BLOCKSIZE;
                    cells.push_back(p);
                    world[row][col] = 1;
                }
                else
                    world[row][col] = 0;
            }
        }
    return 0;
}

int main() {
    vector cells;
    vector< vector > world(ROWS, vector(COLS,0));

    // initialize SDL
    SDL_Init(SDL_INIT_VIDEO);

    // populate the world
    //randomStart(cells, world);   // pass by reference

    // set the title bar
    SDL_WM_SetCaption("Cellular Automata", "Cellular Automata");

    // create window
    SDL_Surface* screen = SDL_SetVideoMode(XRES, YRES, 0, SDL_DOUBLEBUF);

    // Create background and block
    SDL_Surface* bg = SDL_CreateRGBSurface(SDL_SWSURFACE,XRES, YRES, 32, 0, 0, 0, 0);
    SDL_FillRect(bg, NULL, BCOLOR);

    // Display the bank screen
    SDL_BlitSurface(bg, NULL, screen, NULL);
    SDL_Flip(screen);

    // creak the block image for a live cell
    SDL_Surface* block = SDL_CreateRGBSurface(SDL_SWSURFACE, BLOCKSIZE - 2, BLOCKSIZE - 2, 32, 0, 0, 0, 0);
    SDL_FillRect(block, NULL, FCOLOR);

    SDL_Event event;
    bool gameover = false;

    // message pump
    while (!gameover)
    {
        // look for an event
        if (SDL_PollEvent(&event)) {
            // an event was found
            switch (event.type) {
                // close button clicked
                case SDL_QUIT:
                    gameover = true;
                    break;

                // handle the keyboard
                case SDL_KEYDOWN:
                    switch (event.key.keysym.sym) {
                        case SDLK_ESCAPE:
                        case SDLK_q:
                            gameover = true;
                            break;
                    }
                    break;

            }
        }

        randomStart(cells, world);

        // draw the background
        SDL_BlitSurface(bg, NULL, screen, NULL);

        // blit the blocks
        for (unsigned int i = 0; i < cells.size(); ++i)
            SDL_BlitSurface(block, NULL, screen, &cells[i]);

        // empty the vector of cells
        cells.clear();

        // update screen
        SDL_Flip(screen);

    }

    // free the background surface
    SDL_FreeSurface(bg);

    // cleanup SDL
    SDL_Quit();

    return 0;
}

Adding SDL

Now that I have the basic data structure representing the cellular automata "world", it's time to start hacking in the graphics code. I'm using Simple DirectMedia Layer (SDL) to make the magic here. Why SDL? Well, I started doing this stuff in Python, where I used pygame to make the magic, and SDL is the magic behind pygame.

SDL was the library that Loki Games used to port commercial games from Windows to Linux. I even purchased one. Sadly, Loki is gone, but SDL is still here and is even still under development. Ignorant as I am, it seems as good a choice as any.

The magic so far

The display portions of the code were copied from a demo that I found somewhere on the net. Sorry, I don't remember where.  Ask Google -- the code is out there. Most of the comments are from that source. Originally the program displayed a bitmap; I hacked it to my bidding. I won't say much more about the code, although I could go on until the cows come home.

One tweak that come to mind is to change the world vector's data type, which is currently a C++ int, which is 4 bytes on my machine. I really don't need 4294967296 different values to hold 2 states, 0 or 1. A bool would do nicely, or maybe a shorter king of unsigned integer type, if I decide to encode more information about the cell. It's on the TODO list.

#include <iostream>
#include <vector>
#include <cstdlib>
#include "SDL/SDL.h"

using namespace std;

const int XRES = 1024;
const int YRES = 768;
const int BLOCKSIZE = 8;
const int DELTA_T = 250;
const int FCOLOR = 0x00FF00;
const int BCOLOR = 0x000000;
const int ROWS = YRES / BLOCKSIZE;
const int COLS = XRES / BLOCKSIZE;

int randomStart(vector<SDL_Rect> & cells, vector<vector <int> > & world) {
        srand(time(NULL));

        SDL_Rect p;
        int pct;

        for (int row = 0; row < ROWS; ++row)
        {
            for (int col = 0; col < COLS; ++col)
            {
                pct  = rand() % 1000;
                if (pct < 375)
                {
                    p.x = col * BLOCKSIZE;
                    p.y = row * BLOCKSIZE;
                    p.w = BLOCKSIZE;
                    p.h = BLOCKSIZE;
                    cells.push_back(p);
                    world[row][col] = 1;
                }
                else
                    world[row][col] = 0;
            }
        }
    return 0;
}

int main() {
    vector<SDL_Rect> cells;
    vector< vector<int> > world(ROWS, vector<int>(COLS,0));

    // initialize SDL
    SDL_Init(SDL_INIT_VIDEO);

    // populate the world
    randomStart(cells, world);   // pass by reference

    // set the title bar
    SDL_WM_SetCaption("Cellular Automata", "Cellular Automata");

    // create window
    SDL_Surface* screen = SDL_SetVideoMode(XRES, YRES, 0, SDL_DOUBLEBUF);

    // Create background and block
    SDL_Surface* bg = SDL_CreateRGBSurface(SDL_SWSURFACE,XRES, YRES, 32, 0, 0, 0, 0);
    SDL_Surface* block = SDL_CreateRGBSurface(SDL_SWSURFACE, BLOCKSIZE - 2, BLOCKSIZE - 2, 32, 0, 0, 0, 0);
    SDL_FillRect(block, NULL, FCOLOR);

    // blit a block
    for (unsigned int i = 0; i < cells.size(); ++i)
        SDL_BlitSurface(block, NULL, bg, &cells[i]);

    SDL_Event event;
    bool gameover = false;

    // message pump
    while (!gameover)
    {
        // look for an event
        if (SDL_PollEvent(&event)) {
            // an event was found
            switch (event.type) {
                // close button clicked
                case SDL_QUIT:
                    gameover = true;
                    break;
                // handle the keyboard
                case SDL_KEYDOWN:
                    switch (event.key.keysym.sym) {
                        case SDLK_ESCAPE:
                        case SDLK_q:
                            gameover = true;
                            break;
                    }
                    break;
            }
        }
        // draw the background
        SDL_BlitSurface(bg, NULL, screen, NULL);

        // update the screen
        SDL_UpdateRect(screen, 0, 0, 0, 0);
    }
    // free the background surface
    SDL_FreeSurface(bg);

    // cleanup SDL
    SDL_Quit();

    return 0;
}

Coding in C++, or Why I like Python

I've been working on converting my cellular automata program from Python
using pygame to C++ using SDL. Now I remember why I like Python so much more than C++.

Admittedly, my C++ is rusty. I studied C++ back in the days of #include <iostream.h>, and I liked it so much that as soon as class was over, I started looking for another language to hack in. Almost anything else. Seriously. While I was away, I missed the whole namespace thing, which was just waiting to bite me.  I flirted with Java, but it reminds me way too much of C++. (I found Java to be kind of like C++, only slower and without pointers. I realize that some will take issue with the "slower" label, but that was my experience.) Then I turned to the Dark Side and used Visual Basic for a while, because I was running windows anyway on my fully operational Death Star computer. Eventually. I came to my senses and repented my sins, and switched to freeBASIC, and Ubuntu Linux, which are both pretty darn good.

Then I decided I needed to stop coding in BASIC. Cold turkey. Why? I'm not really sure. Possible reasons include:

• My Commodore 64 is long gone. (True, but freeBasic is a long way from C64 BASIC. A very, very long way.) 

 

(Photo by:  Bill Bertram)

• BASIC programmers get no respect. (True that.)

• BASIC programmers are brain dead. (OK, I am brain dead by design, not because my first programming language was BASIC. This must be a feature, and not a bug. For the record, my first programming language was FORTRAN.  I hacked code using an IBM keypunch at Oakton Community College, back when OCC was located at Oakton & Nagle. Let me tell you, IBM manufactured a solid keypunch. Hanging chad was not a problem.) 

• There's something better out there? (Maybe. I still don't know.)

• It's lonely out there, in BASIC but-not-Visual-Basic land. Most of the kids are playing somewhere else. Who can you plagiarize learn from? 

• The prolix syntax of BASIC was giving me writer's cramp.

I'm still not exactly sure why I left freeBASIC behind; I do remember that I wasn't happy with it. The grass must be greener on the other side, right? For whatever frivolous reason, I decided that I needed a new formal language, stat. I looked around, and decided on Python. I'm pretty happy with it. It's easy peasy, clean, and it generally runs fast enough. There are many people out there to learn from, although some of them speak in tongues.

So why the return to C++?

Well, pygame is using SDL to do its magic, and to better understand pygame I want to learn more about SDL, which "is written in C, but works with C++ natively." [1] I want to learn more about making pretty moving pictures and sound on my computer, and I want to be a bit closer to the hardware. I will be doing that, for now, using Simple DirectMedia Layer (SDL). It looks like C++ will help me with that, so it's time for me to re-confront the beast.  


(I'm not in the mood for doing C right now, thank you very much. I did study C in my night school career. I have even written a linked list in C. I don't feel the need to do it again, unless absolutely necessary. C++ means never having to implement another list ADT again, ever.)

The story so far:

Once I got over the whole "now it's

#include <iostream>

using namespace std;

thing" I ran smack into the I can't believe that I have forgotten the whole concept of "pass by value" vs " pass by reference" thing. How could I have forgotten what a big, fat, hairy deal it was to write beautiful code in C++? This here is one very good reason to like Python.

In Python, if you want to pass a list to a function, you just pass the list (which is an object)  to the function. If you want to return the list after the function is done with it, you can return the list (which is still the same object, only possibly somewhat changed) from the function. This appears to be passing by reference. This makes sense, because generally you would not want to deep copy a list, which is what you would have to do to pass a list by value.  If you want to pass a 2D array to a function, well, you do the same as you would with the list, because a 2D array in Python is a list of lists.  (Unless you're using numpy. Then a 2D array is... I dunno. Beats me.) No worries, and best of all, automagically handled.

Mind you, you have to remember which Python objects are immutable and which are mutable, but that's about it.

For example, the Python version has this function, which updates a 2D "array" (actually, a list of lists) named "ca_matrix". I can easily pass the ca_matrix object to the function, and even easily pass it to yet another function, cellNextgen.

def updateCA_MATRIX(ca_matrix, ruleset, mode):
    global COLS, ROWS
    tarray = makeCA_MATRIX()
    for row in range(ROWS):
        for col in range(COLS):
            tarray[row][col] = cellNextgen(row, col, ca_matrix, ruleset, mode)
    return tarray 

Note that I cannot change ca_matrix here because I need it unchanged to calculate the next generation's ca_matix. If you want to, you can easily pass a list to a function, modify it and the changes will be in the scope of the calling function. For example, in Python 2.6.4:

#! /usr/bin/env python

def change_list(s):
    s[0] = 2*s[0]

s = [1,2,3,4]
print s

change_list(s)

print s

Gives the following output:

[1, 2, 3, 4]
[2, 2, 3, 4]

No worries, just code it.

In the C programming language, there are no lists, unless you roll your own list type. If you ever take a decent class in C programming, the teacher will make you do so. In C++, there are these list-like things called vectors , as well as lists and some various other "containers". (Alas, none of them contain beer.) You just have to learn how to use and abuse them. They seem useful.

For the truely brave, you can also roll your list type, just like in C. Initially, I opted for vectors and a C style 2D array... and I should have been using just vectors. For the record, it was great sport, sorting out how to pass a an array by reference in C++. Now that I know how, they are gone from my code. I don't think they'll be back again, at least in my C++ stuff.

The simple truth is that in C++ you should use C++ code, not C code; you must learn not only when you want to pass by value or pass by reference but also how to pass by value or pass by reference. C++ compilers are finicky. In Python this stuff is just not a problem.

The C++ code so far:


#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>    // for random numbers

using namespace std;

// Globals
const int XRES = 1024;
const int YRES = 768;
const int BLOCK_SIZE = 4;
const int DELTA_T = 250;
const int FCOLOR = 0x00FF00;
const int BCOLOR = 0x000000;
const int ROWS = YRES / BLOCK_SIZE;
const int COLS = XRES / BLOCK_SIZE;

struct point {
        int x;
        int y;
};

int randomStart(vector<point> & cells, vector<vector <int> > & world) {
        srand(time(NULL));

        point p;
        int pct;

        for (int row = 0; row < ROWS; ++row)
        {
            for (int col = 0; col < COLS; ++col)
            {
                pct  = rand() % 1000;
                if (pct < 375)
                {
                    p.x = col;
                    p.y = row;
                    cells.push_back(p);
                    world[row][col] = 1;
                }
                else
                {
                    world[row][col] = 0;
                }
            }
        }

        cout << "During randomStart: cells.size() = " << cells.size() << endl;
    cout << "done randomStart" << endl;

    return 0;
}
Initially I used a vector and an array of arrays. I lost the array of arrays because arrays are are evil. I should have been using a vector of vectors instead of a C++ array of arrays. This is especially true because figuring out how to pass a 2D array to a function in C++ was painful. (References: http://www.parashift.com/c++-faq-lite/containers.html#faq-34.1, http://bytes.com/topic/c/answers/61931-passing-array-function-reference-pointers) 

Initially I used #define for magic global values when I should have been using const. I fixed that.

The idea here is to write C++ code using C++, not C. My goal is to write good Python code using the best Python practices; to write good C++ code using the best C++ practices.

I'm still working on it.

Notes:
[1] http://www.libsdl.org/

Back to C++

Replicators on a toroidal surface
(Ruleset: B36/S23 "HighLife")

Many have written cellular automaton programs.

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model studied in computability theory, mathematics, physics, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off".  [1]

Cellular automatons are often referred to as "Conways Game of Life", which is one type of cellular automaton. For exploring cellular automatons on your computer,  I can highly recommend both Golly (runs on Windows, OS X or Linux) or Mirek's Cellebration (Windows, and wherever Java applets can run.) They're both great programs. There are others available, too. Just ask your favorite search engine. Since I want to explore writing software, and cellular automatons seem like fun, I wrote my own cellular automation program, in Python. It's now working fairly well. I just cleaned up a few bugs features and added a toroidal surface mode, which is really cool. (I got that idea from Nathaniel Johnston's blog.) Now that the program is working well enough,  I want to convert it to C++, which is one of the languages that I studied in night school. It can't be that hard, right? It might even be fun.


I started coding in Python, because it's rather easy peasy compared to other programming languages I have used: interpreted, with a large standard library, yet still fast enough. Currently, Python is the main tool I use for programming. (I also started studying Scheme, initially to try to get a handle on recursion, later to learn functional programming. Still working on it.)

Now it's time to use a compiled language for a while, so C++ it is. Why a compiled language? Because I fell like it. Why C++? For a most excellent reason, namely I studied a few years back in night school and I'm already somewhat familiar with it.
`
People tend to favor what they are already familiar with.

I studied C++ a number of years ago, while the language standard was still evolving. I used to write C++ something like this:

#include <iostream.h>

void main()

{

    cout << "Hello, world!" << endl;

   

    return 0;

}

And it worked just fine. (Yes, it is odd for a function that returns void returning an integer. Yet I remember this working. Go figure. Some things in life just don't make sense.)[2]

This certainly does not work now. To be fair, the professor told us that would probably be the case, but not to worry, because it wouldn't change that much.) Well, what hat has changed? The C++ compiler I am using (GNU g++, gcc version 4.4.1), is supposed to mostly follow the current C++ standard. It supposedly is closer to the standard than many other compilers. Here's some changes that I noted: the current C++ standard now uses namespaces, iostream.h is now iostream and main must return an integer. Rewriting the code gives:

#include <iostream>

using namespace std;

int main()

{

    cout << "Hello, world!" << endl;

    return 0;

}

which works.

mikey@hatshepsut:~$ g++ -o hello hello.cpp
mikey@hatshepsut:~$ ./hello
Hello, world!
mikey@hatshepsut:~$

This works, too:

#include <iostream>

int main()
{
    std::cout << "Hello, world!" << std::endl;

    return 0;
}

Aside from this stuff, it's seems to be the same. I guess I'll find out as I go along.

My Python program uses pygame for displaying the graphics. Pygame is built on SDL (Simple DirectMedia Layer). SDL is " a cross-platform, free and open source software multimedia library written in C that presents a simple interface to various platforms' graphics, sound, and input devices."[3]  SDL also works with C++. I used Python's built-in list data type. C++ has the Standard Template Library, which provides both a vector and a list container, either of which should work for me. That's all the magic there is, at least for this project. Let's see how it goes.

Notes:
[1] Wikipedia article: Cellular automaton (Tue Feb  9 10:59:37 CST 2010)
[2] No, I am not imagining this. Track down a copy of How to think like a computer scientist  C++ Version First Edition by Allen B. Downey on the Internet if you don't believe me.
[3] Wikipedia article: Simple DirectMedia Layer (Tue Feb  9 10:26:16 CST 2010)