Category Archives: Programming

Linux.conf.au: Day 3

Wow. I now realise the last two days were just a warmup. The Conference really came into it’s own today. With talks going about twice as long as the previous two days, we really got some in-depth information from some top notch speakers.

This is a continuation of this post here about my first Linux.conf.au, here.

It started off with the lightning talks in lieu of a keynote speaker. I was a bit disappointed that there weren’t more of them (they finished well before scheduled) but the ones that were there were very well spoken about things ranging from Raising Geek Girls to Password Storage best-practices.

Next up I attended the Python 3: Making the Leap! by Tim Leslie tutorial. This was a great tutorial where Tim went through the nuances of the differences between the two versions of python and how the -3 flag and the 2to3.py tool can be used to convert a 2.xx script to python 3. I found this particularly helpful as someone who recent started having a go at python with my (disclaimer: linking to horrible, horrible code) blackboard scraper I recently wrote. For some reason despite all my dependencies working with python 3 I wrote it in 2.7. Learning to write pretty much depreciated code was probably not the most intelligent thing to do, but at least now I have a good explanation on what is different when writing code for 3 in the future.

Next up was Building Effective Alliances around the Trans-Pacific Partnership Agreement by Sky Croeser [ Video ]. The great thing about this talk is that it went beyond saying why the TPPA is bad, which is all we ever seem to hear from tech news sites, and actually delved into strategies of how to effectively combat. The strategies were diverse with no possibility left unturned, from writing letters to politicians to 1999 Seattle WTO Protest tactics – fun for the whole family! I thought the way she approached the topic was terrific, as a person who is not in the slightest bit interested in radical activism, but a strong interest in political issues such as this, it was nice to be acknowledged as somebody who can still contribute. If you’re at all worried about TPPA, I would strongly recommend watching the talk when it’s uploaded on Monday.

Bringing MoreWomen to Free and Open Source Software by Karen Sandler [ Video ] was a really eye opening talk on the strategies used at the GNOME Foundation the bring their amount of female contributors up to par with the rest of the Computing sector (3% compared to 18%, still a woefully small number). The lack of women in computing is quite a serious problem which I think is overlooked (and sometimes even perpetuated) by many computer scientists and programmers, and perhaps society in general. I’m fairly certain (and very hopeful) this is a changing statistic I’ve met many people who are committed to the issue.

Opening up government data by Pia Waugh [ Video ] continued from Monday’s open government miniconf about making government datasets available freely to the public. As I mentioned on Monday, Pia Waugh is definitely someone who is “on our side” in the government sector relating to open data and is in charge of the great data.gov.au website where you can request and vote for certain datasets to be release. She talked about certain issues related to open government data including ways to automate data collection and uploading (which would always provide up-to-date-data) and issues with the format in which data is provided. I love playing to datasets so this talk was very interesting to me, I would recommend giving it a watch when it’s online.

Reverse engineering vendor firmware drivers for little fun and no profit by Matthew Garrett [ Video ]* would have to be the best talk of the day (and possibly the week). In this talk we follow the protagonist Garrett as he embarks on a journey to reverse engineer a vendor tool for modifying servers which doesn’t quite go as expected. I won’t go any further because you have to watch it to really appreciate. The thing I really like about Garrett’s talk is not only the sprinkles of humor paced throughout, but the fact that whenever he says anything that isn’t basic computer/Linux knowledge, he stops and gives a short explanation of what that is. One mistake I feel like many speakers have is that they assume every attendee is as knowledgeable as they are in the domain they are speaking about when in reality there are people of all different types of skillsets. By not stopping to explain things you run the risk of having half your audience feel stupid and switch off. As a student these kinds of explanations are much appreciated and help me achieve my goal of learning more about the kernel.

*for those with a keen eye, you might notice that two Garrett and the Open Data talk overlapped. I watched one on video after the end of today’s conference.

That was all for today, looking very forward to tomorrow with a keynote by Matthew Garrett who will hopefully be beating his own record of “Best Talk so Far”. If you can’t make it but want to watch, tune in at http://timvideos.us/octagon at 9AM tomorrow.

My linux.conf.au adventure is continued here.

Linux.conf.au: Day 2

Continuing from this post here, I’m going to continue blogging my experiences at linux.conf.au being held this year in Perth and UWA as a newcomer.

I actually managed to make the keynotes for this day, which was Kate Chapman’s talk on OpenStreetMap [ Video ]. The cool thing about linux.conf.au is that everything is being livestreamed at timvideos.us so when I was a little late, I could still stream audio in the car. Sweet! The keynote was really warm and fuzzy about open source doing great things around the world using OpenStreetMaps. It was a very accessible talk and has even inspired me to eventually try to contribute to OSM in some way, which is what a talk should do!

I spent most of the day at the Kernel UnConference. I know nothing about the Linux kernel, my general kernel knowledge spans only what was taught in the introductory university course however I, like a bunch of other students attending from Curtin, want to know more about what drives our favorite OSes. Most of what was being said went over my head and at times it seemed like the participants were speaking another language but I still think I managed to get something out of it. I think the idea of UnConferences is really great and definitely improves audience engagement though.

During lunch a bunch of us decided to go to Cafe Biscotti for lunch. This is relevant because it’s the first cafe in Perth to accept Bitcoin. Ironically, it’s a tiny cafe situated on the ground floor of Bankwest, which is part of the largest banking group (Commonwealth Bank) in Australia. Props to them for being the trendsetter in Perth (and for giving a 5% discount).

Taken at Cafe Biscotti, 300 Murray St, Perth

Taken at Cafe Biscotti, 300 Murray St, Perth

Returning to the conference, I took a break from kernel hackerspeak to see A Pseudo-Random Talk on Entropy by Jim Cheetham. As an introduction to the history and current techniques for random number generation this talk was pretty good, however it was a bit short (at only ten minutes) and I would have loved a more in depth look. Such is life with the miniconfs though.

Finally returning to the Kernel UnConference after afternoon tea, I got to see the highlight of my day as a panel of kernel developers answered questions from the audience including Linus Torvalds. It’s really cool to have one of your idols talking nonchalantly a few meters away from you, and is something I’ll definitely remember this conference by.

Credit - Andrew Cooks

Credit – Andrew Cooks

My linux.conf.au adventure is continued here.

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.