ラングトンのループ

ラングトンにはもうひとつ、ループというものがあります。

永久に自己増殖を繰り返していくセル・オートマトンです。

ルールはなんと219個！、しかも初期状態がかなり複雑です。

詳しくはこちら、もしくはこちら。

またまた、ルールだけを参考に、ncursesを利用して自前で組んでみました。

無限増殖とはいえ、画面には限りがあるので、上辺と下辺、左辺と右辺がそれぞれ繋がっているトーラス状の世界としてみました。

無限に続くので、終了はCtrl-Cによるものとし、シグナルをキャッチして終わるようにしました。

毎世代、画面の全セルごとに、ルールを検索することになるのですが、最初は甘く見て普通のリニアサーチにしてみたら、ループが増殖するに従い、目に見えて画面更新が遅くなっていきます。これは、最初の黒が多い状態ではルールテーブルの最初のあたりで検索が済むのに対し、色のついたセルのルールはテーブルの下方にあるので、検索に時間がかかるためでした。

Linuxではともかく、Cygwinでは待てないほど遅くなります。それに進むにしたがって遅くなる、というのもカッコ悪いです。

そこで、stdlibにあるバイナリサーチbsearchを使ってみました。バイナリサーチはテーブルがソートされていることが前提なので、これまたstdlibにあるクイックソートqsortを使いました。

効果てきめん！　安定して超高速になりました。

//
// langton's loop
//  make: gcc lloop.c -lncurses -o lloop
//

#include    <stdio.h>
#include    <stdlib.h>
#include    <ctype.h>
#include    <string.h>
#include    <ncurses.h>
#include    <unistd.h>
#include    <signal.h>

#define     LLOOP_TABLE         "lloop.table"
#define     TABLE_SIZE          256
#define     RULE_SIZE           10
#define     BUF_SIZE            256
#define     Q_W                 15
#define     Q_H                 10
#define     USLEEP              1000
#define     VALUE_AT_NO_RULE    0

int     **prev, **post;
char    table[TABLE_SIZE*4][RULE_SIZE];
int     num_of_table = 0;
int     width, height;
int     debug = 0;
int     num_of_search;

void    finalizer( void );
void    sig_catch( int );
void    rotate_rule( char *, char *, int );
int     comp( const void *, const void * );
int     comp2( const void *, const void * );
void    load_table( void );
int     search_table( int, int, int, int, int );
void    alloc_mem( void );
void    def_color( void );
void    init_array( void );
void    print_usage( void );

// finalizer
void    finalizer() {
    int i;

    // free
    for ( i = 0; i < width; i++ ) free( prev[i] );
    free( prev );
    for ( i = 0; i < width; i++ ) free( post[i] );
    free( post );

    attrset( COLOR_PAIR(0) );
    mvprintw( 1, 0, "Hit any key" );
    getch();
    endwin();
    exit( EXIT_SUCCESS );
}

// signal handler
void    sig_catch( int sig ) {
    finalizer();
}

// rotate rule
void    rotate_rule( char *in, char *out, int rot ) {
    int i;

    out[0] = in[0];
    for ( i = 1; i <= 4; i++ ) {
        out[i] = in[(i-1+rot)%4+1];
    }
    out[5] = in[5];
}

// compare for qsort
int comp( const void *c1, const void *c2 ) {
    return strcmp( (char *)c2, (char *)c1 );
}

// compare for bsearch
int comp2( const void *c1, const void *c2 ) {
    return strncmp( (char *)c2, (char *)c1, 5 );
}

// load table
void    load_table() {
    FILE    *fp;
    char    buf[BUF_SIZE];

    if ( (fp = fopen( LLOOP_TABLE, "r" )) == NULL ) {
        printf("faile open error\n");
        exit( EXIT_FAILURE );
    }
    while ( fgets( buf, BUF_SIZE, fp ) != NULL ) {
        if ( isdigit( buf[0] ) ) {
            strncpy( table[num_of_table], buf, 6 );
            table[num_of_table][6] = '\0';
            num_of_table++;
            // expand rule
            rotate_rule( buf, table[num_of_table++], 1 );
            rotate_rule( buf, table[num_of_table++], 2 );
            rotate_rule( buf, table[num_of_table++], 3 );
        }
    }
    // sort for bsearch
    qsort( table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp );
    if ( debug ) {
        for ( int i = 0; i < num_of_table; i++ ) {
            printf("rule: %d %s\n", i, table[i] );
        }
    }
}

// search table
int search_table( int c, int n, int e, int s, int w ) {
    int     i;
    char    *result;
    char    key[RULE_SIZE];

    sprintf( key, "%d%d%d%d%d", c, n, e, s, w );
    result = bsearch( key, table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp2 );
    if ( result == NULL ) {
        return( VALUE_AT_NO_RULE );
    } else {
        return( atoi( result+5 ) );
    }
}

// allocate memory
void    alloc_mem() {
    int i;

    prev = (int **)malloc( sizeof(int *)*width );
    if ( prev == NULL ) {
        printf("memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    for ( i = 0; i < width; i++ ) {
        prev[i] = (int *)malloc( sizeof(int)*height );
        if ( prev[i] == NULL ) {
            printf("memory allocation failed.\n");
            exit(EXIT_FAILURE);
        }
    }
    post = (int **)malloc( sizeof(int *)*width );
    if ( post == NULL ) {
        printf("memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    for ( i = 0; i < width; i++ ) {
        post[i] = (int *)malloc( sizeof(int)*height );
        if ( post[i] == NULL ) {
            printf("memory allocation failed.\n");
            exit(EXIT_FAILURE);
        }
    }
}

// define color
void    def_color() {
    start_color();
    init_pair( 0, COLOR_BLACK,  COLOR_BLACK );
    init_pair( 1, COLOR_BLACK,  COLOR_BLUE );
    init_pair( 2, COLOR_BLACK,  COLOR_RED );
    init_pair( 3, COLOR_BLACK,  COLOR_GREEN );
    init_pair( 4, COLOR_BLACK,  COLOR_YELLOW );
    init_pair( 5, COLOR_BLACK,  COLOR_MAGENTA );
    init_pair( 6, COLOR_BLACK,  COLOR_WHITE );
    init_pair( 7, COLOR_BLACK,  COLOR_CYAN );
}

// init array
void    init_array() {
    int i, j;
    int init_q[Q_H][Q_W] = {
        { 0,2,2,2,2,2,2,2,2,0,0,0,0,0,0 },
        { 2,1,7,0,1,4,0,1,4,2,0,0,0,0,0 },
        { 2,0,2,2,2,2,2,2,0,2,0,0,0,0,0 },
        { 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
        { 2,1,2,0,0,0,0,2,1,2,0,0,0,0,0 },
        { 2,0,2,0,0,0,0,2,1,2,0,0,0,0,0 },
        { 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
        { 2,1,2,2,2,2,2,2,1,2,2,2,2,2,0 },
        { 2,0,7,1,0,7,1,0,7,1,1,1,1,1,2 },
        { 0,2,2,2,2,2,2,2,2,2,2,2,2,2,0 } };

    for ( i = 0; i < width; i++ ) {
        for ( j = 0; j < height; j++ ) {
            if (    i >= (width-Q_W)/2 &&
                    i <  (width+Q_W)/2 &&
                    j >= (height-Q_H)/2 &&
                    j <  (height+Q_H)/2 ) {
                prev[i][j] = init_q[j-(height-Q_H)/2][i-(width-Q_W)/2];
            } else {
                prev[i][j] = 0;
            }
        }
    }
}

// print usage
void    print_usage() {
    printf( "usage: lloop [-dh]\n" );
}

// main
int main( int argc, char **argv ){
    int     i, j;
    int     x, y;
    int     generation = 0;
    int     c, n, e, s, w;
    int     opt;
    int     change = 0;

    // option
    while ( (opt = getopt( argc, argv, "dh" )) != -1 ) {
        switch ( opt ) {
            case 'd':
                debug = 1;      // debug mode
                break;
            case 'h':
            case '?':
            default:
                print_usage();
                exit(EXIT_SUCCESS);
        }
    }

    // set signal handler
    if ( SIG_ERR == signal( SIGINT, sig_catch ) ) {
        fprintf( stderr, "cannot set signal handler.\n" );
        exit( EXIT_FAILURE );
    }

    // load rule table
    load_table();

    // init screen
    if ( !debug ) {
        initscr();
        getmaxyx( stdscr, height, width );
    } else {
        width = 80; height=51;
    }

    // define color
    if ( !debug ) def_color();

    // allocate memory
    alloc_mem();

    // init prev
    init_array();
    // init position
    for ( i = 0; i < width; i++ ) {
        for ( j = 0; j < height; j++ ) {
            if ( !debug ) {
                attrset( COLOR_PAIR( prev[i][j] ));
                mvaddstr( j, i, " " );
            }
        }
    }
    if ( !debug ) {
        mvprintw( 0, 0, "Hit any key" );
        refresh();
    }
    getch();
    if ( !debug ) erase();

    // endless loop
    for (;;) {
        for ( i = 0; i < width; i++ ) {
            for ( j = 0; j < height; j++ ) {
                // set next generation
                c = prev[i][j];
                if ( j == 0 ) {
                    n = prev[i][height-1];
                } else {
                    n = prev[i][j-1];
                }
                e = prev[(i+1)%width][j];
                if ( i == 0 ) {
                    w = prev[width-1][j];
                } else {
                    w = prev[i-1][j];
                }
                s = prev[i][(j+1)%height];
                post[i][j] = search_table( c, n, e, s, w );
                if ( post[i][j] < 0 ) {
                    printf("search faild.\r\n");
                    exit( EXIT_FAILURE );
                }
            }
        }

        // draw
        change = 0;
        for ( i = 0; i < width; i++ ) {
            for ( j = 0; j < height; j++ ) {
                if ( !debug ) {
                    attrset( COLOR_PAIR( post[i][j] ));
                    mvaddstr( j, i, " " );
                }
                if ( prev[i][j] != post[i][j] ) change++;
                prev[i][j] = post[i][j];
            }
        }

        // not changed
        if ( change == 0 ) {
            finalizer();
        }

        // print generation
        if ( !debug ) {
            attrset( COLOR_PAIR(6) | A_REVERSE );
            mvprintw( 0, 0, "%d", generation );
            num_of_search = 0;
            refresh();
        } else {
            printf( "%d %d\n", generation, num_of_search );
            num_of_search = 0;
            if ( generation >= 500 ) exit(EXIT_SUCCESS);
        }
        generation++;
        //usleep( USLEEP );
    }

    // finalize
    finalizer();
}

実行するとこんな感じ。 カラーでにぎやか。わっかがぐるぐる回りながら上下左右に増えていきます。

真っ暗な世界を増殖する場合はいいんですが、自分の残骸などに衝突すると、ルールに記載のないパターンになることがあるみたいで、その場合は死ぬ（黒くなる）ようにしてみたら、最後に残骸だけ残って停止します。