Wednesday, December 31, 2014

Maze Generating in C (like Lumosity Penguin Pursuit)

Playing lumosity is fun. Among one of their games, there is a cute maze game.
lumosity game
In that game, however, the goal is not about solving the maze, but about adjusting the direction when the screen flips or rotates.  The point is, generating this kind of maze has computer science theories.  Wikipedia has a great reference (Maze_generation_algorithm).  This fun algorithmic problem is implemented using C.  I used back-trace method, and here it is.
sample output



#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#define WIDTH   6
#define HEIGHT  6

struct node {
    int north_wall;
    int west_wall;
    int visited;
    int x;
    int y;
};

void printMaze(int cnt, struct node *cells)
{
    int y,x;
    for (y=0; y<HEIGHT; ++y) {
        for (x=0; x<WIDTH; ++x) {
            struct node *c = cells + ( x + y*WIDTH );
            printf("+");
            if (c->north_wall) {
                if (c->x == 0 && c->y == 0) 
                    printf("  ");
                else
                    printf("--");
            }
            else 
                printf("  ");
        }
        printf("+\n");

        for (x=0; x<WIDTH; ++x) {
            struct node *c = cells + (x + y*WIDTH) ;
            if (c->west_wall) 
                printf("|  ");
            else
                printf("   ");
        }
        printf("|\n");
    }
    
    for (x=0; x<WIDTH-1; ++x) {
        printf("+--");
    }
    printf("+  +\n\n");
}

// rtn is a pointer array.  NWES.
int neibor(struct node *cells, struct node *cur, struct node **rtn)
{
    int x = cur->x;
    int y = cur->y;
    rtn[0] = rtn[1] = rtn[2] = rtn[3] = NULL;

    if (y-1 >= 0) rtn[0] = cells + (x + (y-1)*WIDTH);
    if (x-1 >= 0) rtn[1] = cells + ((x-1) + y*WIDTH);
    if (x+1 < WIDTH)  rtn[2] = cells + ((x+1) + y*WIDTH);
    if (y+1 < HEIGHT) rtn[3] = cells + (x + (y+1)*WIDTH);

    return rtn[0] != NULL || rtn[1] != NULL ||
           rtn[2] != NULL || rtn[3] != NULL;
}

void shuffle(struct node **array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);

    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            struct node  *t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}

void punchWall(struct node *node1, struct node *node2)
{
    int x1 = node1->x;
    int y1 = node1->y;
    int x2 = node2->x;
    int y2 = node2->y;

    if (x1 < x2 && y1 == y2)
        node2->west_wall =0;
    if (x2 < x1 && y1 == y2)
        node1->west_wall =0;

    if (y1 > y2 && x1 == x2)
        node1->north_wall =0;
    if (y2 > y1 && x1 == x2)
        node2->north_wall =0;
        
}

void genMaze(struct node *cells, struct node *cur)
{
    int i;
    if (cur->visited == 0) {
        struct node *nei[4];

        cur->visited = 1;
        if (neibor( cells, cur, nei)) {
            shuffle(nei, 4);
            for (i=0; i<4; ++i) {
                if (nei[i] && nei[i]->visited==0) {
                    punchWall(cur, nei[i]);
                    genMaze(cells, nei[i]);
                }
            }
        }
    }
}

int main(int argc, char **argv) {
    int i;
    struct node cells[ WIDTH * HEIGHT ];

    // Initialize Cells
    for (i=0; i < WIDTH*HEIGHT; ++i) {
        cells[i].north_wall = cells[i].west_wall = 1;
        cells[i].visited = 0;
        cells[i].x = i % WIDTH;
        cells[i].y = i / WIDTH;
    }
    genMaze(cells, &cells[0]);
    printMaze(WIDTH * HEIGHT, cells);
    return 0;
}

Thursday, December 25, 2014

Quick Example of Red Black Tree.

In previous articles, FreeBSD AVL tree is ported to Linux and a usage example is presented.
Linux uses red-black tree instead of AVL.  Just searching for rbtree.h in Linux kernel returned so many components such as ext4.  But, rbtree can't be used in user space in kernel source form.  Luckily there is user-space ported rbtree in here.

That code contains a test code.  Here, I post one more example.  My example is the same test written in AVL test code (here).

By the way, using these codes have advantage of efficiency.
Enjoy.



#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include "rbtree.h"
#include "rbtree_test.h"


void printTree(RBRootType *root)
{
 int count = 0;
 Person *data, *rootdata;
 RBNodeType *cur;

 rootdata = container_of( root->rb_node, Person, node);
 printf("Root node: %s\n", rootdata->name);
 
 cur = rb_first(root);
 while (cur) {
  data = container_of( cur, Person, node);
  printf("%d : %s(%s)\n", count, data->name, data->phone);
  cur = rb_next(cur);
  count++;
 }
 printf("Total nodes in tree: %d\n", count);
 printf("---------------------------------------------------------------------\n");

}

Person* searchPerson(RBRootType *root, char *name)
{
 RBNodeType *curnode = root->rb_node;
 while (curnode) {
  Person *data = container_of(curnode, Person, node);
  int result;

  result = strcmp(name, data->name);

  if (result < 0)
   curnode = curnode->rb_left;
  else if (result > 0)
   curnode = curnode->rb_right;
  else
   return data;
 }
 return NULL;
}

int insertPerson(RBRootType *root, Person *data)
{
 RBNodeType **new = &(root->rb_node), *parent = NULL;
 while (*new) {
  Person *cur = container_of(*new, Person, node);
  int result = strcmp(data->name, cur->name);
  
  parent = *new;
  if (result < 0)
   new = &((*new)->rb_left);
  else if (result > 0)
   new = &((*new)->rb_right);
  else 
   return 0;
 }
 
 // New node
 rb_link_node(&(data->node), parent, new);
 rb_insert_color(&(data->node), root);

 return 1;
}


int main(int argc, char **argv)
{
 RBRootType mytree = RB_ROOT;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 insertPerson(&mytree, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 insertPerson(&mytree, &b);
 
 
 Person *srch = NULL;
 printTree(&mytree);
 
 if ( (srch = searchPerson(&mytree, "Micheal Smith")) != NULL ) 
  printf("Micheal found: %s\n", srch->phone);
 else
  printf("Micheal not found.\n");

 if ( (srch = searchPerson(&mytree, "Jack Stuart")) != NULL ) 
  printf("Jack found: %s\n", srch->phone);
 else
  printf("Jack not found.\n");
 printf("--------------------------------------------------\n");
 
 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 insertPerson(&mytree, &c);

 //traverse!!  root must be Jack.
 printTree(&mytree);

 
 return 0;
}

Monday, December 8, 2014

Sample Usage of AVL, quick and dirty.

So, previous article ported FreeBSD AVL into Linux AVL. (AVL Tree in C )
Here is quick and dirty way of how to use it.
It will be straightforward, except one thing.

Your data struct must be divided into two pieces.  Data part and avl_node_t part.  The Data part size must be multiple of 8.  If not, there will be a puzzling assert((offset & 0x7) == 0).  Here is the usage.  For convinience, I put the link part the first.  This will easy to cast type between (avl_node_t) and (struct person) with the same pointer.


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <stdint.h>
#include "avl.h"

#define NAME_LEN 36
#define PHONE_LEN 10

// assuming dtype has a link member as node type (avl_node_t)
#define OFFSETOF(data) 0

typedef struct person {
 avl_node_t  my_link; 
 char name[ NAME_LEN + 1];
 char phone[ PHONE_LEN + 1];
} Person;

int comparePerson(const void *a, const void *b) 
{
 Person *_a = (Person *)a;
 Person *_b = (Person *)b;
 if ( strncmp(_a->name, _b->name, NAME_LEN) < 0 )
  return -1;
 else if ( strncmp(_a->name, _b->name, NAME_LEN) > 0 )
  return 1;
 return 0;
}

Person* searchByName(avl_tree_t *tree, const char *name)
{
 Person *cur = AVL_NODE2DATA(tree->avl_root, tree->avl_offset);
 avl_node_t *p;
 while (cur) {
  if (strcmp(cur->name, name) == 0)
   return cur;
  else if (strcmp(name, cur->name) <0) {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[0];
  }
  else {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[1];
  }
  cur = p ? AVL_NODE2DATA( p, tree->avl_offset) : NULL;
 }
 return NULL;
}

void printTree(avl_tree_t *tree)
{
 int i = 0;
 Person *cur;

 printf("Total nodes in tree: %ld\n", avl_numnodes(tree));
 printf("Root: %s\n", ((Person *)(AVL_NODE2DATA( tree->avl_root, tree->avl_offset)))->name);

 cur = avl_first(tree);
 while (cur) {
  printf("%d : %s(%s)\n", i, cur->name, cur->phone);
  cur = AVL_NEXT(tree, cur);
  i++;
 }
 printf("---------------------------------------------------------------------\n");
}

int main(int argc, char **argv)
{
 avl_tree_t avl;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 avl_create(&avl, comparePerson, sizeof(Person), OFFSETOF(&a));
 avl_add(&avl, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 avl_add(&avl, &b);

 //traverse 
 printTree(&avl);

 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 avl_add(&avl, &c);

 //traverse!!  root must be Jack.
 printTree(&avl);

 // Searching.
 Person *search;
 search = searchByName(&avl, "Jack Stuart");
 if (search) 
  printf("Jack found: %s\n", search->name);
 else
  printf("Jack not found\n");

 search = searchByName(&avl, "lalalalala");
 if (search)
  printf("lala found:\n");
 else
  printf("lala not found\n");

 return 0;
}

AVL Tree in C

I ported FreeBSD avl implementation into Linux users pace version.
Code is here(github link).

Practically speaking, we don't need AVL tree these days in high level languages like Python.  There are good alternatives in general.  In algorithm perspective, there is a Red Black Tree, the rival of AVL tree.  They mostly serve for the similar purpose.  RBTree is easier to implement, but size is factor of 2 vs. AVL is 1.4.  Linux uses RBTree internally, and FreeBSD had AVL.  (Linux RBTree article)

Well, in day to day life, modern languages provide their own version of "List".  In Python case, we just stuff data into the list, and later call it by index.  For efficient search, we use bisect module.  If we need sort, Python list takes very "Intelligent" approach to be efficient.  I will discuss this later, but listsort.txt in Python source can be referenced.

But, then, why bother AVL tree?
First, it's mentioned more in different algorithm books probably thanks to BST (Binary Search Tree).  And, AVL is a good subject to introduce concepts of algorithm, "let's cover the weakness of a given algorithm."  Second, it's personal.  I just like it with no reason.

When I searched AVL written in C, I found many pages.  First, GNU libavl is an overkill.  Other small projects are not mature enough.  Either it's "not generic", or data allocation logic is "malloc".  This will cost performance.  Modern days, C is chosen by performance in many cases.  So, too many or individual malloc is a bigger penalty.

Interestingly, FreeBSD has avl implementation and they still include it even today.  Probably, former SunOS used avl for kernel data.  This is small.  This only implements AVL algorithm, but comparator is a function pointer which I can attach.  AVL node does not bother the data, but my data suppose to embed avl_node_t.  And, AVL algorithm doesn't do high-level search.  So, I have to provide the high level search, like searchByName(const char *key).  I liked the design  because it is more flexible.  Unfortunately, it's not directly usable in Linux.  So, I tweaked and made it usable in Linux.  There are two files (avl.h and avl.c).  Enjoy.


Friday, December 27, 2013

Wednesday, October 30, 2013

Pushing scale practice doesn't help improvising.

I used to have this problem in my first year playing guitar.  My first ultimate goal was "Far beyond the sun" by Yngwie Malmsteen.  Pretty ambitious for a beginner.  Accomplishing song by song, picking speed went up, left finger maneuver became fluent.  However, Yngwie Malmsteen style is pretty challenging.  If I remember that time, I practiced different scales in metronome.  One day, I could play "far beyond the sun."  However, the speed I play for Yngwie Malmsteen didn't help other songs.  I was puzzled.

Big Question. "I could cover fastest genre of the music, but other than his music, I am still struggling with other pieces.  Why? "

Having 10 years of gap without playing guitar, I can't play Yngwie Malmsteen as I did.  But, I can enjoy more music than back then I used to play.  Here is my answer about the question.

Improvising has two modes.  "Controlled progression" and "Shredding".  Controlled progression relies on current musical context.  What is the key signature/main scale?  What is the beat signature/and main rhythm? More importantly, controlled progression much relies on the brain, the most important tool for music.  Muscle movement works together with the brain.  Do you see that the limiter is "the brain"?
On the other hand, shredding depends less on the brain.  It heavily relies on muscle memory.  Brain just sets up basic information like "what code/what sclae" and "what major beat", then finger works all.  In here, detail is less important, such as order of notes  as long as notes are in scale, and diatonically working.

When playing in band, these come out somewhat mixed.  For example, Yngwie Malmsteen, many phrases are roughly 20% controlled, 80% shredded.  So, brain tells "From now, 4 measures will be diminished rooted 20th fret C down."  Then, during 4 measures fingers improvise without help of brain.  In the meanwhile, brain accepts the next phase, "stop at 8th C vibration, for the 4 beats, and then the last half beat will Bm harmonic minor in pulling manner."  After executing 4 measure, this should end at C, and pulling Bm harmonic scale comes up.  Sure while this finger is working, Brain just thinks the next, not the one fingers are playing.

When in shredding mode, accidentals are not common.  Because accidental is a big brain work.  "We make irregular note X, which is not in scale, but produces effects of A,B,C, and some alpha of tention.  It will be resolved by in scale tonic Y or 5th of Y, etc. "  These need lots of controlled work.  Fingers can't just dance on their own.  They will pay attention to the brain.

Now the key point here.  Increasing maneuverability in controlled work is the foundation to play variety of music.  At the same time, brain should have more tools to provide good signals to the fingers.  I will explain this further.
Here is a simple test how fast I can maneuver in controlled.
Simply pentatonic through 6 strings.(Low A(5th fret 6th string) to high C(8th fret 1st string).  Try beginning with down picking. Change the same play with beginning with up picking.  This is one example of controlled picking.
There are different patterns of controls like 3rd down (C-A, B-G, A-F, G-E, F-D, .... ), alternate/3 string sweep, etc.
If these maneuver is fluent, many things will be easier.  Plus, shredding speed will also increase.

At the same time, don't forget to listen to more good musics.  And catch ideas from the music.  Eventually, collection of these ideas will make brain lucrative to utilize, and improvising will be cool and sound.




Monday, October 28, 2013

Guitarists...

So, my favorite instrument is the guitar.  Practically, I only can play the guitar.  Many great musicians inspires me, but due to my limited time, when I get a chance to play it, I have to concentrate for just one thing.

Anyway, my favorite guitarist is "Jason Becker."  He is the god and the most fluent guitarist.  At the same time, he had many brilliant ideas.  Considering all of his work, which ended at his age of 29, he didn't have his best time, unfortunately.

Then, my favorite "active" guitarist is "Guthrie Govan".  He is very special, to tell the truth.  Most of guitarists have own color, specializing handful of genre, Guthrie doesn't have specialty.  He is really all-rounder.  Rock, Blues, Jazz (Classic, Beebop, fusion, plus some brilliant covers with different colors), and Country.  Picking, finger style, slap, tapping, arpegio, ...  He also plays very good acoustic.  His theory is very strong.

I recommend his videos in youtube.  None have disappointed me, so far.