Tuesday 20 May 2008

Google Treasure Hunt Question 2

After solving question 1 successfully I decided to plod on and answer question 2 as well. It was, for me at least, far less challenging than the first question.

This time, you are generated a set of files with random directories and file names that you are asked to download and process. Once I got passed the immediate suspicion of downloading a zip file (for fear of viruses) it took no time at all to whip up a solution. My question was:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_15866755520722619948.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing BCD and ending in .pdf
Sum of line 5 for all files with path or name containing mno and ending in .rtf
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)


Again, my solution was Perl based and generated a correct answer of 364264342 for my particular zip file:
#!/usr/bin/perl -w
use strict;
use File::Find;
use FileHandle;
my $total1 = 0;
my $total2 = 0;
find(\&wanted, ("/home/gwhite/GoogleTreasureHunt08_15866755520722619948"));
print $total1*$total2."\n";
sub wanted {
return if (-d $File::Find::name);
if (($File::Find::name=~m!BCD!i) && ($File::Find::name=~m!\.pdf$!i)) {
my $fh = new FileHandle;
$fh->open($File::Find::name) || die ($File::Find::name." Oops: $!\n");
while (<$fh>) {
last if ($fh->input_line_number>4);
chomp($_);
$total1+=$_ if ($fh->input_line_number==4);
}
$fh->close();
}
elsif (($File::Find::name=~m!mno!i) && ($File::Find::name=~m!\.rtf$!i)) {
my $fh = new FileHandle;
$fh->open($File::Find::name) || die ($File::Find::name." Oops: $!\n");
while (<$fh>) {
last if ($fh->input_line_number>5);
chomp($_);
$total2+=$_ if ($fh->input_line_number==5);
}
$fh->close();
}
}

Monday 19 May 2008

Google Treasure Hunt

I've just discovered today (rather late I know) that Google have released a treasure hunt which is quite interesting. It's not what you might think. Given the name, I would have guessed it involved using the google search engine to find things on the Internet. However, it's actually a problem solving challenge where they pose questions and you submit your answer. I think question 2 is due out today (they obfuscate when the next question will be released), nobody seems to know how many questions there are, exactly how long this will go on for, etc. But there is a prize for "the first person to answer all the questions correctly" whatever that means.

A word of warning, don't read the rest of this if you want to work out the answer yourself!!!

My question number 1:
Google Treasure Hunt Q1
A robot is located at the top-left corner of a 65 x 61 grid (marked 'Start' in the diagram above)*.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the not to scale diagram below).

How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number.)


The problem here is the vast number of different routes that can be taken, which would overflow 32 bit computers for numbers this size. My (correct) answer was 1426507627253102510231886503468838531 which I calculated using the formula (x+y-2)! / ((x-1)! (y-1)!)

A few simple lines of Perl later and I had the answer:
#!/usr/bin/perl -w
use strict;
use Math::BigInt;
# change these to match your X & Y grid size
my $xgrid = 61;
my $ygrid = 65;
my $x = Math::BigInt->new($xgrid-1)->bfac();
my $y = Math::BigInt->new($ygrid-1)->bfac();
my $z = Math::BigInt->new($xgrid+$ygrid-2)->bfac();
print $z->bdiv($x->bmul($y))."\n";

Friday 16 May 2008

In with the new

Related to my previous post "Out with the old" I have been thinking about what's next for me in terms of a home media solution. I've also been spurred on by my recent purchase of a Current Cost meter which I can hook up to a computer, but more about that another time. Similar to my old system, I'm not bothered about video so this is purely an audio solution.

There are some things I took into consideration when building the old system that I don't consider to be so important this time around. I'm not bothered about browsing the Internet on my TV and I'm prepared to spend a bit more cash, for example. But rather than concentrate on those points, here's a list of things I would like to include in the new system:

  • Switchable speakers in different rooms (kitchen and living room)
  • Connection to my stereo amplifier
  • Access to my mp3 collection without leaving my PC powered on
  • Access to Internet music (podcasts, radio, etc)
  • Remotely controlled
  • Separate screen (from the TV)


After much research, here's what I've come up with:
Setup Diagram Click to enlarge.

I'm going to use a Linksys NSLU2 (a.k.a. a SLUG) which can be modified to run Linux so I can hack it into submission to be my low powered music server. The SLUG will provide my music collection over my wireless network to a Slim Devices Squeezebox Duet system. The Squeezebox is also able to access all the Internet services I want and similar to the SLUG runs open source software so has a fantastic community of users. The Duet comes with a wifi remote control with built-in LCD screen so I can interact with the system from anywhere in the house. From the Squeezebox is an audio connection to the amplifier which, similarly to my old system, is connected to a speaker switcher box.

That little lot should keep me busy for a while and give me all I want from music at home. As I mentioned, a lot of research went into deciding which components to choose. The weak link here will likely be the SLUG because it's such a small box with only 32Mb RAM and a relatively slow processor (just 264 bogomips) but it should do for the time being. Here's my component list:

Tuesday 13 May 2008

Out with the old

I moved house pretty much spot on 6 months ago now and we're still settling into the new house. Aside from decorating, emptying boxes and all the other things you have to do at the time, it's also an opportunity for re-thinking some of the technology used in our previous house. To that end, one of the things I want to update is my audio solution. I shy away from saying media centre as that seems to brew up ideas of full on PVR systems for most people which would include recording television; something I don't care about as I have a commercial hard disk recorder I'm very happy with.

My current solution was documented at the time on Eight Bar as a description using an IBM Thinkpad built as a media centre with more details of the process, also on Eight Bar. This solution worked extremely well while having its problems at the same time. My requirements for putting the solution together were cost (it was experimental and needed a good wife acceptance factor so price was all important), fast start-up, easy and remotely controllable, and integrated with my current home stereo and speaker arrangement. I think I achieved this, it cost about 20 quid for the cables and keyboard, the Thinkpad was borrowed from work, I used the Amarok music player which made things very easy, hooked up my stereo remote control to the Thinkpad and integrated it nicely. See the no-expense-spared diagram below...

diagram Click to enlarge.
It's running Fedora Linux on the Thinkpad, with a KDE desktop and Amarok as I mentioned. I don't have a huge music collection so all my mp3s fit on the Thinkpad hard disk. I configured Linux to suspend to RAM and thus boot extremely quickly with auto-login to the KDE desktop and auto-start of various programs including the music player should a cold boot be required. The thinkpad has a serial port so I was able to hook up a serial IR receiver using LIRC to receive signals, with the audio cables going to my stereo using the minidisk port. With no minidisk attached I had spare keys on the remote control (such as play/pause/stop/next/previous) that had no effect when pointed at the stereo while other controls (such as volume) function as expected. This means I can program the spare keys to be picked up by the laptop IR receiver instead, in order to operate Amarok, and with no interference with normal operation of my stereo (so only one remote control needed for the whole solution). A nice bonus of this set up was the ability to display the screen on the television via the thinkpad s-video port. With a radio controlled keyboard and built-in mouse it's easy to sit on your sofa browsing the Internet or e-mailing with the convenience of your TV and wireless broadband.

This is all sounding marvelous and when described like that I wonder why I think about replacing it, but it does have issues. Browsing the web on your TV is great, but it's not particularly convenient when someone else wants to use the TV for its main purpose in life. Niether is it convenient browsing the Internet in 800x600 which is the highest resolution my CRT TV can cope with, then there's the wireless keyboard which is slightly fiddly but I'm just being picky now. The next major problem is a bug with the thinkpad firmware that causes the wireless to stay disconnected after a certain amount of uptime, which is unresolvable and requires a full reboot to temporarily fix until the next time it goes down. Another slight usability issue is user feedback. Browsing songs, playlists, podcasts and all in Amarok is stupidly easy, but controlling from a remote control when you can't see the screen (that was another idea for putting it on the TV) is not easy. It's great you've got the secondary screen you can use if necessary, but if you're trying to do something else or not in the same room it becomes much more difficult.

So, all these little niggles to what is in theory quite a nice setup have got me thinking of a better way to solve my requirements.

Monday 12 May 2008

Welcome

I'm sitting here having just started a new blog and wondering whether to write a this is my first post entry or not, cheesy as it may be, here it is...

I've been involved with various blogs over the years but never set one up externally to the company I work for that my overlap with my professional interests. There are, of course, external blogs I've written for including Eight Bar and the blog I write with Beth about our allotment. My personal interests regularly overlap those I have at work, I intentionally use the term professional interests having recently been certified by the British Computer Society as a Chartered IT Professional; I usually describe myself informally at work as A Professional Linux Geek. I currently have some ideas I wanted to write about that don't really fit in any of the places I not-so-regularly write, I hope to log these here and continue to do so in the future.

Picture of GrahamA quick intro to me then. I've already given away I have technical interests and the name of my current employer. I left Exeter University with a degree in Computer Science and Management Science to work at the Hursley location where I established an interest in Linux. This has since been broadened into open source software generally, and open standards and the web. All this has been through a number of interesting positions working in internal support, super computing, and customer facing consulting. I'm currently working for an organisation called Emerging Technology Services that offer great skills to our customers interested in all things new and trendy.

Away from work I like to get out and about. Whether that's playing badminton (I do that a lot), or out with Beth Geocaching, general walking, or working down at our allotment. I like a lot of sports to both play and watch (except football/soccer). I have an interest in music, listening to as much as I get time for and having played the piano since just before I was 5 I think. When all else fails I can usually be found playing the odd computer game on the PC or the Wii, or around the house somewhere doing some DIY.