Author Archives: jasongi

Linux.conf.au: Day 1

So today was the first day of my first Linux (or any) conference, linux.conf.au. Apparently blogging about these things is a thing (well at least according to Delan and Kye) so here we go.

Registrations were yesterday as well as the newcomer seminar about the conference by Rusty Russell (I hope this is his actual name.) who is a pretty cool guy and even bought all the newcomers a beer. We also got a whole bunch of merch which sadly didn’t include deodorant (see: Sysadmin miniconf) but was pretty decent for the $99 student ticket. We were also warned that the miniconfs over the first two days were independently run and could be a bit ‘rough’, as you’ll soon discover.

The first miniconf I attended was the Sysadmin miniconf where everyone was packed into the Woolnough lecture theater at UWA which is one of those ones where they try to cram as many seats into a room as possible. This combined with the hot Perth weather and a whole bunch of Linux enthusiasts did not make for a pleasant atmosphere to the point of where it was almost uncomfortable. To be honest, Sysadmin-ing bores me to tears and most of the talks either flew straight over my head or the speaker fumbled through slides, sometimes both. I feel like today’s miniconfs were slim pickings and I’m much more excited for tomorrow’s Open Programming conf. One gem in the rough for me was  ‘Quality of Service’, a common misconception (10 mins) – Julien Goodwin [ Video ] one of the talks which I felt would be accessible to all of the audience and the speaker actually new his stuff, as someone who was tried to mess with QoS before studying CS, this ten minute talk made me understand it in a way that I previously hadn’t.

After getting sick of the Sysadmin conf I went to see the Open Government lightning talks and I wish I had gone their sooner. It was much less congested which really made it feel like more of  a dialogue than the other talks. It was headed by Pia Waugh who seemed really passionate and knowledgeable about the subject (which you would hope she would be as the person in charge of data.gov.au, something I found out about today which I had never heard of and is amazing).

Lastly I went to a Crypto BoF (Birds of Feather, a concept which is new to me which I gather so far is a sort of informal discussion group). I’ve been a bit of a crypto enthusiast (Oh hey ASIO, I didn’t see you there) since doing some study on it at Curtin. One of the interesting topics which came up was the traditional security being at odds with usability and increasing usability may be a good thing regardless, because if enough people use PGP it may stop the people who use PGP from going on a list.

So that was linux.conf.au so far, it’s going to be an interesting week and I’m pumped for the proper talks to begin Wednesday-Friday. Hopefully I’ll be up in time for tomorrow’s keynote.

My linux.conf.au adventure is continued here.

Play audio or song when a certain device connects to your network

I got robbed recently in the middle of the night and they stole a phone and my keys. Obviously it was difficult to sleep that night knowing someone out there had access to my house, so remembering the phone automatically connected to my router when it was in range, I wrote this bash script to play The Final Countdown when it reconnected. It assumes you have VLC media player installed.

#!/bin/bash
PINGVAL=""
#PINGVAL will be null except when the phone pings back
while [ -z "$PINGVAL" ]; do
echo "pinging"
#change 10.1.1.5 to local ip address of phone, ping only outputs ttl when ping is successful
PINGVAL=$(ping 10.1.1.5 -c 1 | grep ttl) 
done
#dah dah DAH DAH, dah dah DAH DAH DAH, dah dah DAH DAH...
cvlc Europe.mp3 --start-time=13 --volume 1024

Solving a machinarium puzzle using recursion

I was procrastinating studying for my exams about a month ago, so I started playing Machinarium on the Playstation. It’s a cool little point and click adventure where you play a robot when needs to beat some other robots and get his girl-robot friend back. For those who don’t play adventure games, they tend to have some really really frustrating puzzles. Machinarium was no exception. One I got particularly stuck on in the greenhouse. It involved a 5×5 grid which you have to completely light up. The catch is that you picked a starting square, which lights up, and then you can only pick a direction after that. The squares then light up  in that direction until they hit a lit square or the edge of the grid. If you are surrounded by lit squares/edges and the grid isn’t lit, you have to start again. here is a video of someone playing it:

Well, I would have rather died playing this game before looking up a walk-through (the worst possible thing one can do while playing adventure games, such a slippery slope), so I decided screw it, that looks like it could be fairly easily implemented in a recursive algorithm. So I spent the next while doing it. At least it was good exam revision, I guess. I did it in C because that is what my exam was in. If you have thought of a better more efficient way to solve this puzzle (which I’m sure there is considering I’ve been only studying CS for a year), please tell me! I haven’t studied path solving type algorithms so far, but I plan to. This program can also solve bigger than 5×5 grids, but I haven’t really tested that yet – I would be interested to see how far this shoddy brute-force attempt will actually go as it gets exponentially more difficult. The code outputs the instructions back to front and at the bottom says the square you need to start at.

/**
* mach.h
*/
#define GRIDSIZE 5
void solveStart(int **array);
int gridFull(int **array);
int** solve(int **array, int position);
void freeA(int **a);
void aCopy(int **a1, int **a2);
int** iterate(int** array, int xDir, int yDir, int pos, char* direction);

 

/**
* mach.c
**/#include <stdlib.h>
#include <stdio.h>
#include "mach.h"

int main()
{
    /*declarations*/
    int **array;
    int ii, jj, input;

    /*allocate starting array*/
    array = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++) /*allocate array*/
    {
        array[ii] = (int*)calloc(GRIDSIZE,sizeof(int));
    }

    /*input the dead squares (grid is labeled starting at 0 going to GRIDSIZE moving across horizontally*/
    input = 0;
    while(input != 1234)
    {
        /*input the coordinate*/
        printf("\n input dead squres or enter 1234 to start solving: ");
        scanf("%4d", &input);

        /*if already dead, reverse, other wise make dead*/
        if ( (input < GRIDSIZE*GRIDSIZE) && (input >= 0) )
            if(array[input/GRIDSIZE][input%GRIDSIZE])
                array[input/GRIDSIZE][input%GRIDSIZE] = 0;
            else array[input/GRIDSIZE][input%GRIDSIZE] = 1;

        /*if out of bounds and not the exit key, dispaly error*/
        else if (input != 1234) 
        {
        printf("\n value entered is out of bounds, check your value or change #DEFINE GRIDSIZE value\n");
        }

        /*print the grid as it stands*/
        printf("\nCurrent grid (X for dead squares, O for live)\n");
        for(ii = 0; ii < GRIDSIZE; ii++)
        {
            for (jj = 0; jj < GRIDSIZE; jj++)
            {
                if(array[ii][jj] == 0)
                    printf("0");
                else printf("X");
            }
            printf("\n");
        }
    }

    /*start the algorithm*/
    solveStart(array);

    /*clean up*/
    freeA(array);
    return 0;
}

void solveStart(int **array)
{
    /*declarations*/
    int ii, exit;
    int **successArray, **tempArr;

    /*allocate array*/
    tempArr = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++)
    {
        tempArr[ii] = (int*)calloc(GRIDSIZE, sizeof(int));      
    }

    /*initialisations*/
    exit = 0;
    ii=0;

    /*main loop*/
    while (!exit)
    {
        /*can't start on dead squares*/
        while( (ii < GRIDSIZE*GRIDSIZE) && array[ii/GRIDSIZE][ii%GRIDSIZE] == 1)
            ii++;
        if (ii < GRIDSIZE*GRIDSIZE)
        {
            /*make a copy of starting array to attempt to solve starting at location ii*/
            aCopy(array, tempArr);
            /*turn the start square dead*/
            tempArr[ii/GRIDSIZE][ii%GRIDSIZE] = 1;
            /*start the algorithm*/
            successArray = solve(tempArr, ii);
            /*print the starting square if the puzzle can be solved by starting on it*/
            if( (exit = gridFull(successArray)) )
                    printf("%d\n", ii);
            /*go to the next square*/
            ii++;
            /*set exit variable to true if you've run out of spots to try*/
        }
        else 
        {
            exit = 1;
            printf("\n Grid not solvable\n");
        }
    }
    /*clean up*/
    freeA(successArray);
}

int** iterate(int** array, int xDir, int yDir, int pos, char* direction)
{
    /*declarations*/
    int newPos, ii; 
    int** returnVal, **tempArr;

    /*allocate temporary array to try the next iterations*/
    tempArr = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++) /*allocate array*/
    {
        tempArr[ii] = (int*)calloc(GRIDSIZE, sizeof(int));
    }
    returnVal = NULL;

    /*copy the imported array into the temp array */
    aCopy(array, tempArr);

    /*next square we're hoping to conquer*/
    newPos  = pos+yDir*GRIDSIZE+xDir;

    /*check to see if it is in the bounds, and that it is alive*/
    if  ( ( (newPos < GRIDSIZE*GRIDSIZE) && ( newPos >= 0 ) && (tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] == 0 ) ) && ( (xDir == 0) ||  ( (pos%GRIDSIZE-newPos%GRIDSIZE) == 1) || ( (pos%GRIDSIZE-newPos%GRIDSIZE) == -1) ) )
        {
            do
            {
                /*make the square dead and set the next square we hope to conquer*/
                tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] = 1;
                pos = newPos;
                newPos = newPos+yDir*GRIDSIZE+xDir;
            }

            /*check to see if next square is in the bounds, and that it is alive, if not exit*/
            while ( ( ( (newPos) < GRIDSIZE*GRIDSIZE ) && ( newPos >= 0 ) && ( tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] == 0 ) ) && ( (xDir == 0) ||  ( (pos%GRIDSIZE-newPos%GRIDSIZE) == 1) || ( (pos%GRIDSIZE-newPos%GRIDSIZE) == -1) ) );

            /*find the next direction*/
            tempArr = solve(tempArr,pos);
            /*you should only get here if your grid is filled or if you've exhausted all posibilities for this node (and its children*/
            if (gridFull(tempArr))
            {
                /*if you're here, the problem is solved and program is unwinding*/
                printf("%s\n", direction);
                freeA(array);
                returnVal = tempArr;
            }
            else
                freeA(tempArr);
        }
        else freeA(tempArr);
    /*NULL if unsolved, contains the solved array if it isn't*/
    return returnVal;
}

int** solve(int **array, int position)
{
    int **tempArr;

    /*base case: when the grid is full*/
    if (gridFull(array))
        tempArr = array;
    else
    {
        /*try going in each possible direction*/
        if ( (tempArr = iterate(array, 0, -1, position, "up") ) != NULL );
        else if ( (tempArr = iterate(array, 0, 1, position, "down") ) != NULL );
        else if ( (tempArr = iterate(array, 1, 0, position, "right") ) != NULL );
        else if ( (tempArr = iterate(array, -1, 0, position, "left") ) != NULL );
        else tempArr = array;
    }
    return tempArr;
}

/*helper function set the values in a2 to the values in a1*/
void aCopy(int **a1, int **a2)
{
    int ii;
    int jj;
    for (ii = 0; ii < GRIDSIZE; ii++)
    {
        for(jj=0;jj<GRIDSIZE; jj++)
            a2[ii][jj] = a1[ii][jj];
    }
}       

/*helper function to check if the grid is full (therefore complete), evil multi return to speed up false cases*/
int gridFull(int **array)
{
    int ii;
    int jj;
    for (ii=0;ii<GRIDSIZE;ii++)
    {
        for(jj = 0; jj<GRIDSIZE;jj++)
        {
            if (array[ii][jj] == 0)
                return 0;
        }
    }
    return 1;   
}

/*helper function to free a 2D malloc'd array of size [GRIDSIZE][GRIDSIZE]*/
void freeA(int **a)
{
    int ii;
    for (ii=0;ii<GRIDSIZE;ii++)
    {
        free(a[ii]);
    }
    free(a);
}
While making this little program, I wondered how many different solvable grids there were. So I decided to find out. It turns out the number of possible grids (but not necessarily solvable) you can get is equal to N = 2G2 where G is the height of the grid. I used this little piece of code as well as a slightly modified version of the above, shown here (I fixed up some memory errors too), piping the test program into the mach program to feed every possible grid for the specified gridsize and the program will tell me how many are solvable and save those to a file.
/**
* test.c
**
#include <stdlib.h>
#include <stdio.h>
#include "mach.h"

int plusOne(int *prev)
{
    int ii;
    ii = GRIDSIZE*GRIDSIZE-1;
    while(prev[ii] == 1)
    {
        if (ii == 0)
            return 0;
        prev[ii] = 0;
        ii--;
    }
    prev[ii] = 1;
    return 1; 
}
int main()
{
    int ii;
    int* array;
    array = (int*)calloc(GRIDSIZE*GRIDSIZE, sizeof(int));
    do
    {
        for(ii = 0; ii <GRIDSIZE*GRIDSIZE;ii++)
        {
            if (array[ii] == 1)
                printf("%d\r", ii);
        }
        printf("1234");
    }
    while (plusOne(array));
    free(array);
    return 0;
}
It turns out for the a 2×2 grid there are 16 possible but only 14 13 are solvable
For 3×3, there are 512 possible but only 171 are solvable

For 4×4, there are 65,536 possible but only 3503 are solvable

For a 5×5, there are 33,554,432 possible, but my computer so far has only calculated 4.7 million. It will probably take a couple of hours from now. After a couple of computing hours, it has 118481 solvable.
6×6 will probably take a very long time on my PC, 68,719,476,736 possibilities – likely more than a year, so thats where this algorithm’s usefulness wears out. I wonder how far it could be optimized.
Here are links to the outputted logs of every possible solvable grid:
2×2 This is lost now, sorry
Update: Looking through the 2×2 log, I notice that a grid that looks like this was in there

XO

OX
when it is clearly not solvable. I think the problem here is with how I detected whether you were at the edge of the grid by seeing if the difference between the next and current position mod the grid size was one. This is clearly a problem in a 2×2 grid, therefore the algorithm is definitely not suited to it.