Archive

Author Archive

Halloween Pumpkins

November 11, 2010 Leave a comment

With lots of time on my hands, I decided that I would do something special with my pumpkin for Halloween. The idea was simple… Would I be able to carve my own face onto a pumpkin? This post tells the story of my endeavour, and by the end of it I’ll let you be the judge as to whether I was successful.

In order to get any sort of design onto the pumpkin, the main job is to create a template of the design that you want. The first challenge is to chose what design you want, which was easy for me as I had already decided that I would carve a picture of my own face. The next step was to find a suitable picture that could be used to make a good template. Keeping in mind that the final design can only use three shades, it is necessary to find a picture that can be converted into a three level grey-scale and still keep its features. In the final carving, the lightest areas will be made by carving out complete holes, the medium areas will be made by removing just the skin of the pumpkin, and the darkest areas will be left with their skin on. The main thing to keep in mind, is that the final pumpkin is only likely to work when lit from within by a candle, and sat in a dark room.

After a little bit of searching, the best hints I could find were to use a photo that is well lit from the front, but with a plain dark background. Luckily for me, I had a recent photograph that fulfilled that role: the professional photography from my graduation. So, cropping the picture so as just to show my face, I was left with the following starting point for creating my template.

Alex PhD Graduation

Now comes the Photoshop skills, or in my case GIMP skills. You need to convert the image into grey-scale, and then “posterize” it down to only 3 levels of grey. If the resulting image isn’t very good, then playing around with the contrast and brightness of the image, before posterisation, can help. You also have to remember that the template will have to be carved into a pumpkin, so you cannot have any dark or medium areas “floating” within light areas. I have changed my 3-level grey-scale image into a 3-level orange-scale image, to add a pumpkin colour theme to the template.

pumpkin template

So, with template in hand, I only had to choose a pumpkin from the green grocer’s, attach a print out of the template, and transfer the layout onto the pumpkin. Then the relevant parts of the design could be cut out or skinned.

PumpkinsPumpkin with TemplateTemplate Transferred to PumkpinHoles Cut OutAreas SkinnedPumpkin lit

I’ll end this post with a photo of the finished pumpkin, lit up with a candle, and placed in a dark room, and a photo of it sat amongst its Halloween pumpkin peers.

Final OutcomeFinished Pumpkins

Comments welcome.

Advertisements
Categories: Life

GPS tracks in Saas Fee

November 10, 2010 Leave a comment

One thing that I like to do these days is to log my whereabouts using the GPS device in my phone. I have a HTC Hero, and the My Tracks application for Android, which is made by Google, does exactly what I want in this respect. I used to have a Bluetooth GPS device, and log the tracks on an IPAQ in raw NMEA format, but the GPX and KML formats that are created in My Tracks are much more widely used these days.

I do plan to go through all my old logs and post any interesting results that I come across, but for now I shall just give a simple example of the type of thing I like to do.

Earlier this year, I went skiing in Saas Fee, which is in Switzerland, and carried my phone with me to log my skiing tracks. Over the whole week I tried to do all the pistes that were available, and enjoyed using the logs to see where I’d been, and how fast I’d been able to ski etc. As an aside, my max speed over the whole week was 54 mph, which made me pleased that I have started to wear a helmet!

Once I was back in the UK, I was able to load all the logs from the week into Google Earth, and plot them in 3D by having the Terrain layer on. I do plan to split the tracks into the various pistes and lifts that are in the resort, and colour them accordingly, but for now the plot of all my tracks can already be compared with the piste map.

My GPS Tracks from Skiing in Saas FeeThe Piste Map for the Saas Fee resort

Bonus points for any comments on which pistes must have been closed while I was there!

Update – November 2010

I have now gone through all the GPS data available, and collated it into a single KMZ file. I have split all the tracks into the respective pistes; and lifts, and coloured them accordingly. A screen shot of this data shown in Google Earth is as follows.

Saas Fee - Piste Map

If you would like to view the KMZ file using the Google Earth browser plug-in, or download the KMZ directly, then please head over to the relevant page on my webiste:

Saas Fee – Piste Map – http://www.drinkupthyzider.co.uk/ge.html#map

 

Categories: GPS Logs

Painting and Decorating

October 24, 2010 Leave a comment

I was recently asked to help out with some redecorating. This mainly involved a single bedroom, which needed a hole fixing in the ceiling, a few cracks filling in the walls, and a full repaint. I thought this blog post would be a good place to put a brief description of what we did, along with some before, during and after photos of the room.

Firstly the hole in the ceiling…

The original Artex ceiling was falling away from the actual ceiling beneath, and had left a large hole. This was fixed by preparing the surface with some watered-down PVA, onto which the new Artex could be applied. Finally the whole ceiling was painted in “Calm Breeze” so the patched hole would match the rest of the ceiling.

Then the biggest crack? in the wall…

One of the walls had got a little damp, probably due to the placing of furniture in front of the wall. The old plaster had come off in places, so it would require filling to give the wall a smooth surface. Once again, we prepared the surface with watered-down PVA and then filled the hole with Polyfilla. The “before” photo on the left is a little dark, but also shows the original dark blue colour of the room. Finally we finished the wall off by painting it with “Calm Breeze”.

The finished room…

I am pleased with the results. The room is now a lot lighter, and the work only took a few days.

Categories: Life

Prefix Trees in Haskell

September 13, 2010 1 comment

As part of an interview, I was recently challenged to define a data type to represent prefix trees, along with lookup and insert functions. I was allowed to use any language of my choice, so decided to use Haskell. This blog post will introduce what a prefix tree is, and then cover my implementation. There may well be better implementations of prefix trees, but I was quite pleased with the functional representation that I ended up using.

Prefix Trees
The best way to define a prefix tree may well be with the aid of the following small diagram:

A Sample Prefix Tree

It is a data structure that stores values associated with certain keys. The key is used to traverse a branch of the tree. Not all nodes of the tree have to contain data, and in this instance, a key is only associated with a single piece of data. For example, in the diagram above, the prefixes (which form the keys) are the lower case letters on each branch, and the data is represented by the capital letters at (some of) the nodes.

In this highlighted example, the key “a” has no data associated with it, the key “ab” is associated with the data ‘N’, the key “abc” has no data associated with it, and the key “abcd” is associated with the data ‘X’.

The Key "abcd" Highlighted

Haskell

The first thing to decide is the types that represent the keys and data in the tree. In fact, we can make this definition polymorphic, and use any arbitrary data types for each of these. However, we’ll see later that we need to be able to compare the elements that form a key in order to define the insert function. A key is then formed by a list of the relevant key data type.

type Key a = [a]

So the key “abcd” used in the example above would have the type: Key Char

Now we can define the actual type that forms the prefix tree. A tree can simply be thought of as a node which may contain some data, along with a function which takes the next prefix and returns the tree below that point (if there is any further tree below that point).

data PFTree a b = Node (Maybe b) (a -> Maybe (PFTree a b))

With this definition we can now define an empty tree. That is, a tree with no data at the root node, and for which any prefix returns no sub tree.

initialTree :: PFTree a b
initialTree = Node Nothing (\_ -> Nothing)

So, we’ve now defined the tree data type, but we want to be able to define the lookup and insert functions. The lookup function is used to see whether a given key has any data associated with it, within the given prefix tree.

lookup :: Key a -> PFTree a b -> Maybe b

If we have got to the end of a key, then the data associated with the current node is the data we are looking up (even if it is Nothing).

lookup [] (Node b _) = b

If we haven’t reached the end of a key, then we need to see whether the relevant sub tree exists, and if it does, we need to lookup the rest of the key within the subtree.

lookup (x:xs) (Node b f) = case f x of
                           Nothing -> Nothing
                           Just pt -> lookup xs pt

The code for the insert function is also very similar. It is used to insert data associated to a given key, into a given prefix tree. However, we now need that the type of the keys fulfils the Eq typeclass, or in other words it defines the function (==) :: a -> a -> Bool that checks for equality between two members of the type.

insert :: Eq a => Key a -> b -> PFTree a b -> PFTree a b

If we have traversed the tree up to the end of the given key, then we have reached the node at which we wish to insert the given data. In this instance, we just swap the new data for whatever was previously in the tree at the current node.

insert [] b (Node _ f) = Node (Just b) f

If we haven’t reached the end of the key, then we are in one of two situations. Either the next prefix will evaluate to Nothing and we can just construct the subtree with the remaining key and an empty tree, or we have to insert the data recursively into the subtree with the remaining key. In either case, we construct the relevant function using the equality function.

insert (x:xs) b (Node mb f) = case f x of
                            Nothing -> Node mb (\x' -> if x' == x then Just (insert xs b initialTree) else f x')
                            Just pt -> Node mb (\x' -> if x' == x then Just (insert xs b pt) else f x')

Everything is now defined such that we could use the prefix trees. The insert function can be used along with the empty tree to construct arbitrary trees, and the lookup function can be used to extract data from them.

I’ll leave it as an exercise for someone to define the tree given as an example above.

Categories: FUN

GPS tracks on Snowdon

September 1, 2010 Leave a comment

The weekend just gone was the end of August bank holiday weekend (28th, 29th and 30th of August, 2010), so Karen and I decided to spend the time visiting Wales. More specifically, we decided to spend the long weekend in Llanberis, at the foot of Mount Snowdon. The journey there would be a bit of adventure on the train, having to take three trains to get from Beeston in Nottinghamshire, to Bangor in Gwynedd. The route took in the delights of a change in both Derby and Crewe. Once in Bangor, we were able to catch a bus to Llanberis, with a stop off on the way to visit Caernarfon Castle.

We stayed in a B&B style hotel (the Dol Peris hotel), which was conveniently located on the high street in Llanberis. We chose to stay in Llanberis as it is home to the Snowdon Mountain Railway, for which we had booked tickets up the mountain on the Sunday morning. Our plan was to take in the views at the summit, and then walk down the Miner’s track to Pen-y-Pass, from where we could get the Sherpa bus back around to Llanberis.

The rest of this blog post will mainly be about this day trip up and back down Snowdon, for which I took my trusty HTC Hero, and logged a GPS track of the trip. We both had an excellent weekend in Snowdonia, and would very much like to go back for more walking in the mountains. For now though, I have split the rest of this post into three sections, one for the train journey up the mountain, and one for the walk back down the Miner’s path. The final section documents the whole journey through screen shots of the GPS track displayed in Google Earth.

The Snowdon Mountain Railway

The Snowdon Mountain Railway was constructed in the late 19th Century, and was first used to take tourists to the top of Snowdon in 1896. The original complement of three steam engines has now been added to by diesel locomotives, and although SMR can’t guarantee which type of train will take you up the mountain, we were lucky enough to be taken by one of the original steam locomotives, “Wyddfa”, built in 1895. The trains are all fitted with a “pinion” which engages with the “rack” to provide traction. One thing to note is that the boilers on the steam engines are also inclined so that the firebox is always submerged in water.

Snowdon Mountain Railway "Wyddfa"

The railway is apparently the only public rack and pinion railway in use within the British isles. The track has a double rack mounted between the rails, which can be clearly seen on the photo below. Without the rack and pinion the trains wouldn’t be able to make there way over the gradients of up to 1 in 5.5 (which is approximately 18.2%) to reach the summit.

Snowdon Mountain Railway tracks

There are three passing points on the track up the mountain, where the trains ascending the mountain are able to safely pass those descending it. The steam locomotives also take the opportunity to refill with water at the half way passing point on the ascent of the mountain. The journey up the mountain took about 55 minutes, and covers a total of 4.675 miles. For people taking the return journey on the train, you get a 30 minute stop off at the top, which gives you plenty of time to walk the last 50 or so meters to the actual summit (where the triangulation point sits).

Snowdon SummitSnowdon Summit Triangulation Point

As you can see, the summit was rather covered in cloud when we got there, so our plans to take in the views were a little optimistic. However, we were able to have lunch in the new visitor centre, and prepare ourselves for the walk down. I’m pretty sure the massive Original Welsh “Oggie” that I ate was a bit excessive, but it was delicious none the less.

After an hour and a bit at the summit, hoping the clouds would clear, we decided that we should head off to find the top of the Miner’s track, and head back down the mountain.

The Miner’s Track

The Miner’s track is one of the main paths used by people ascending and descending Snowdon. Most of the information online seems to describe the ascent of the Miner’s track, so this description will differ in that it describes our descent. As mentioned previously, the top of Snowdon was completely covered in cloud when we were up there, and we would definitely recommend that you prepare yourself with plenty of warm clothes, and practical footwear if you are going to attempt this yourself.

From the very summit, you can head back down towards the visitor centre, and then start to follow the path alongside the railway. This part of the path can be very busy as all the paths on Snowdon converge into this one path as you reach the last ridge before the summit. To get to the Miner’s track you simply follow this main path until you reach the first finger stone, as pictured below.

Snowdon Finger Stone 1

At the finger stone, you take the path off to the right hand side. This path is the top of both the Miner’s track and the Pyg track, and is a steep zig-zag. For us, it was a welcome turn off the main path as this part of the path was protected from the strong winds that had been coming up from the other side of the mountain. The path is pretty easy to follow, not least because of all the other hikers. We were told that on a clear day you would be able to get a view over the lakes below, but the cloud was still reducing the visibility, and carried on to do so until we were a little lower. Eventually though, the clouds parted and we were able to see the lakes below.

Snowdon Lakes

After the big zig-zag of this path, you reach another finger stone (a little smaller than the first). This is where the Miner’s track and the Pyg track diverge from one another.

Snowdon Finger Stone 2

Again, you take the right hand path at this finger stone, as the left hand path is the Pyg track. The path from this point down to Glaslyn was often described as a steep scree scramble, but we didn’t find it too challenging, especially as the visibility had improved dramatically. The path seems well trodden, and there are stair like stones placed to help at the steepest parts.

Once you reach Glaslyn, you can carry on the path down the valley to Llyn Llydaw, but we took the time to walk a little around the lake, and look at some of the disused mining buildings that are scattered around. It is the path from here back to Pen-y-Pass for which it is named, as it is the route that the miners would have taken.

View of Snowdon from GlaslynMining Building by Glaslyn

The rest of the path down to Pen-y-Pass is very easy going as you will have already done most of the decent. The path takes in two more lakes, including an impressive causeway over Llyn Llydaw, and the smaller Llyn Teyrn.

View of Snowdon from Llyn Llydaw

Altogether, the walk took us just under 3 hours, from the summit to Pen-y-Pass (which is about 4 miles), but we were slowed by the poor visibility at the top. I don’t think an estimate of a little over 2 hours would be far out on a good day. We were glad that we hadn’t driven as the Pen-y-Pass car park is £10 for parking (for over 4 hours), and the Sherpa bus back to Llanberis was only £1.

GPS log of the trip

The three separate parts of our trip make up the three sides of the triangle that can be seen on the GPS track. That is the ascent from Llanberis to the summit on the Snowdon Mountain Railway, the descent to Pen-y-Pass on the Miner’s track, and finally the return to Llanberis on the Sherpa bus.

The most impressive view of the GPS track is of the part which forms the Miner’s track down from the summit via Glaslyn and Llyn Llydaw.

Miner's Track GPS log

Another view of the entire track, also gives a good view of the walk down to Pen-y-Pass.

GPS log view of Miner's Track

The view of the track that best shows the ascent up the Snowdon Mountain Railway also shows that the railway goes up the least steep ridge of Snowdon.

GPS log view of Snowdon Mountain Railway

The last view of the GPS log that I shall put here is from the side of the bus journey back from Pen-y-Pass to Llanberis.

GPS log view of Sherpa Bus Route

The final diagram below shows a graph of altitude by distance travelled. Somehow the scales have been turned into percentages, but these aren’t too hard to change back in to the actual values.

Altitude by Distance Travelled

The altitude corresponding to 0 Elevation is 512 feet, and is approximately the altitude of Llanberis (GPS altitude is the least accurate part of the fix), and the altitude corresponding to 100 Elevation is 3756 feet. The actual height of Snowdon is only 3560 feet (or 1085 meters), so this does give an idea of the lack in accuracy of the altitude readings taken from the GPS.

The distance travelled scale starts at the hotel in Llanberis. The journey up the Snowdon Mountain Railway is from about 5 to just over 30. The walk down the Miner’s track is from just over 30 to just under 60. The Sherpa bus back to Llanberis is from just under 60 to around 95.

Categories: GPS Logs

GPS and Golf

I haven’t played much golf in my life. In fact, excluding a few rounds of pitch and putt, I’ve only played two rounds of golf. Both of these have been within the last few weeks at Ramsdale Park.

On the second of these occasions I decided to take a GPS log of my round. Here are two different views of the round as shown in Google Earth:

A round at Ramsdale Park Golf ClubA round at Ramsdale Park Golf Club

These pictures don’t quite give the course the justice it deserves. The front nine are nice and flat, but the the back nine start up on a big ridge which is only just visible above the green start marker in the first picture.

Anyway, my golfing may have improved very slightly, and I’m looking forward to my next round!

Categories: GPS Logs

Radix Sort in F#

August 13, 2010 1 comment

I have spent many years programming in Haskell, but have also recently started dabbling in F# and Ocaml. I would count myself as a big proponent of the Functional Programming paradigm.

Just as a practice I thought I would implement a Radix sort algorithm in F# for unsigned 32bit integers. Radix sort algorithms use a Radix in order to sort the elements in a list or array. This means that you must be able to define a Radix for the data type which you are trying to sort, but has the advantage that the time complexity of the algorithm is only linear in the number of elements to be sorted (multiplied by a constant that relates to the size of the radix), compared to O(n log n) for most partition sort algorithms.

For this implementation, I shall use the bits as the Radix. This means that each step of the sort algorithm splits the list into two, depending on the value of a single bit in each element, keeping all the elements in these sublists in the same order they appeared in the original list. The algorithm works by splitting the list depending on the least significant bit of each element, and then joining the resultant sublists, before repeating the process depending on the next least significant bit… this repeats until the last step where the splitting depends on the most significant bit of the elements, and the final joined list is ordered. I am sure there are much better definitions of a radix sort on the web, but I thought this would be an interesting initial experiment with F#.

Some of these functions my well be in the library, but my current knowledge of the library is lacking slightly, so I have implemented everything I don’t know about.

The first definition is a function that simply returns a Boolean value of whether the input integer is equal to zero. This achieved using pattern matching.

let is0 x =
  match x with
    0 -> true
  | n -> false

The next function defines how the list is split depending on the Radix. The first argument is the position of the bit which is the current Radix, and the second argument is the input list. The recursive sub-function actually does the work using a pair of accumulators.

// splits a list of integers in half depending on the value of the nth bit of the integers
let splitBy n xxs =
   let rec splitBy' n' xxs' (oz,iz) =
      match xxs' with
        [] -> (oz,iz)
      |  x :: xs -> splitBy' n' xs (if is0 ((x >>> n') &&& 1) then (x::oz,iz) else (oz,x::iz))
   splitBy' n xxs ([],[])

You’ve probably noticed that the lists returned by the previous function actually contain the elements in the reverse order in which they appear in the input list. So, we will need a function that reverses a list. This can also be achieved using an accumulator.

//simple reverse list implemented using an accumulator e.g. extra list to move elements into
let reverse ls =
   let rec reverse' (xs,scratch) =
      match xs with
        [] -> scratch
      | x :: xs -> reverse' (xs,x :: scratch)
   reverse' (ls,[])

We can use the reverse function when we want to join the two lists that are created at each step of the algorithm. I have used the list concatenation function from the library.

let join (oz,iz) = List.concat [reverse oz;reverse iz]

Each step of the algorithm can now be defined. The first argument still defines which bit you’re working with, and the second argument is the input list.

let sortBy n xs = join (splitBy n xs)

The algorithm is completed by running the algorithm recursively over all 32 bits in the unsigned 32 bit integers.

// recursive algorithm to sort depending on LSB upto MSB e.g. bits 0 to 31
let sort xs =
   let rec sort' n xs' =
      match n with
        0 -> xs'
      | i -> sortBy (i-1) (sort' (i-1) xs')
   sort' 32 xs

and that is it… An implementation of Radix sort in F#.
Comments Please.

Categories: FUN