## One mile South, one mile West, one mile North

July 22nd, 2014

This is another puzzle I found to be an interesting variation from the original that I have heard previously.

Basic puzzle: how many places are there on Earth (if any) that you can you walk one mile South, one mile West and one mile North and be back in your original position.

Answer A: 1 — right at the North pole, so you form a geodesic triangle.

“True” answer B: infinitely many – one mile above the the slice of earth that is one mile in circumference.

Scale is all wrong yada yada but the visual concept should be clear enough (I hope, and such is the intent).

## 8, 9, 12 balls problem

July 21st, 2014

Lately I’ve been reading some common interview puzzle problems and came across the 8-ball problem. I’ve come across this problem before, along with some more complex variations. In particular, http://learntofish.wordpress.com/2008/11/30/solution-of-the-12-balls-problem/ already gives a very good explanation of the solution. My only complaint is that I found it a bit difficult to keep track of the numbering. Thus, this post is not much more than my personal rendition of the problem and solution, using colour rather than labels.

The most basic variation is that you are given 8 balls but one is heavier than the rest. You are asked to find the minimum number of times you would use a balancing scale such that you would definitely find the heavier one.

basic 8 balls problem

I think it helps when you know that the solution is two times and you get to work that out. Here’s a visual solution:

Solution to basic problem

This is the same solution for 9 balls, one heavy — the only difference is the second weighing is always the bottom case. However, a more interesting variation is of the same practical scenario but this time you are not told whether the one ball is heavier or lighter, just that it is different.

Less knowledge: one ball weighs differently

This time solution to this is three times — this is somewhat straightforward for the 8 or 9 balls case, as an extension to above. But for the 12 ball case, the reasoning is much more subtle.

Addendum: It has been almost a year since I’ve last visited this post, I might one day finish with the visual version of the 12 ball case, but for now, I’ll just have to leave published as is. The original link‘s explanation will have to do.

## Handy command line thingies

December 23rd, 2013

A compilation of handy commands I use when working remotely and/or on command line.

#### File sharing from remote server

I used to use scp a bunch for transferring files between my local machine and some server. However, I found that ssh file share is waaay handier.

Essentially, you define a local folder from which you mount a directory in a remote server by typing the following:

So, for example, here I’d use sshfs sammi@nonado.net: MyNonadoFiles/ in the location where my MyNonadoFiles/ folder is.

#### Search previous commands

Another handy shortcut I use a lot since learning to use the command line is reusing previous commands. Pressing the ‘up’ scrolling button is fine but if I’ve been typing a lot of cd here and there or running scripts repeatedly then it can take a while to find a specific command (such as the sshfs above) which I use seldomly but is super useful. Here’s a couple of shortcuts:

• Ctrl-r + “what you’re searching for”
• e.g. pressing Ctrl and r, and then ssh would find your most recent command that has ssh in it.
• To look further back, keep pressing Ctrl+r
• history -“number of lines”
• e.g. history -100 returns your most recent 100 commands

## Code snippet: all paths between two nodes in a graph

January 13th, 2013

An adapted version (of code found at Python patterns) for finding all the paths between two given nodes in a NetworkX graph, with the additional limit of length k (where k is the maximum number of edges in the path).

```def find_all_paths_lim(graph, start, end, k, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
if len(path) < k+1:
newpaths = find_all_paths_lim(graph, node, end, k, path)
for newpath in newpaths:
paths.append(newpath)
return paths```

So, for example:

```import networkx as nx
G=nx.Graph()
`find_all_paths_lim(G,"beans","black pudding",3)`

gives you

`[['beans', 'egg', 'spam', 'black pudding']]`

and

`find_all_paths_lim(G,"beans","black pudding",4)`
gives you
`[['beans', 'egg', 'spam', 'white pudding', 'black pudding'],`
`['beans', 'egg', 'spam', 'black pudding']]`

Note: loops are omitted and works on MultiDiGraphs (i.e. directed and multi-labeled NetworkX graphs).

December 18th, 2012

“Error during update

A problem occurred during the update. This is usually some sort of network problem, please check your network connection and retry.”

I haven’t upgraded my Ubuntu distribution since Lucid Lynx (10.04) and didn’t want to do a fresh install to get the current Precise Pangolin (12.04). This requires upgrading Lucid one intermediate distro at a time to get to my final goal. But, since nearly all the intermediate distros have become unsupported in the meantime, this means the standard way of asking the Update Manager do this all for me was a moot point. After a bunch of googling and lots of waiting (I had to go 10.04 -> 10.10 -> 11.04 -> 11.10 -> 12.04) I finally got there, despite some errors along the way.

1. First, download the “Alternate Install CD” for the distribution version you want. Then:

2. (i) You can either burn the ISO onto a CD and upgrade by booting from it

or

2. (ii) Type in the terminal (don’t literally copy + paste the italics!):

Remember to choose the upgrade without getting updates from the internet or there will likely be errors because it can’t find the no longer supported distribution.

I also ran into other errors that wouldn’t allow me to update but I can’t remember the precise details so I won’t bother trying to  dig it up. Something along the lines of removing unsupported software did the trick, I think.

## Network Data sources

July 19th, 2012

Data data data, it’s so much easier (and reassuring) to use data that is preprocessed and previously analysed. Here are some nice sources of them:

• KONECT – The Koblenz Network Collection. These are proper big networks ranging from few ten thousands of nodes to a few ten million. The page layout is broken down by types of networks e.g. Authorship, Lexical, Ratings etc. with neat symbols beside the name of them to show what type of graphs they are, bipartite, directed, weighted, temporal etc.
• Social network datasets – a page with datasets associated with some social network analysis course. Most of the datasets were originally collected by sociologists studying the behaviour of animals/people so are understandably small (<100 nodes). However, very useful as well-studied and ground truth is, well, well-grounded XD Format is less pretty – it’s pretty old-school in layout, links that are names of authors/collectors of datasets that goes to the section of the page that describes it.
• Clique Datasets – a list of links to datasets that have been created by Clique researchers, which have been made available for academic use. A smaller collection of datasets, but well-documented with links to related publication and blog posts (when there is one).
• Stanford Large Network Dataset Collection as well as their Web and Blog datasets – of which a bunch are part of the KONECT datasets. They are mostly large (again ranging from ten thousands to ten millions nodes) datasets from Jure Leskovec‘s page for their Stanford Network Analysis Package (SNAP).

## Webcomics and other miscellany (to keep me sane)

May 9th, 2012

Some miscellaneous comics which summarise:

## List of European Airports and their City Codes

March 1st, 2012

(Resource entry)

List of International Air Transport Association airport codes with their associated City or Airport name for geographically-defined European countries:

Albania, Armenia, Austria, Azerbaijan, Belarus, Belgium, Bosnia and Herzegovina, Bulgaria, Croatia, Cyprus, Czech Republic, Denmark, Estonia, Finland, France, Georgia, Germany, Greece, Hungary, Iceland, Ireland, Italy, Latvia, Liechtenstein (not in database), Lithuania, Luxembourg, Macedonia, Malta, Moldova, Monaco, Montenegro, Netherlands, Norway, Poland, Portugal, Romania, Serbia, Slovakia, Slovenia, Spain, Sweden, Switzerland, Turkey, Ukraine, United Kingdom, Jersey, Guernsey, Isle of Man, and the Faroe Islands; Russia was omitted as its landmass spanned further East than was required.

These were taken from the database provided by OpenFlights.org in December 2010.

## Plotting Heatmaps in R

January 24th, 2012

I had recently had to create a heatmap visualisation as a part of our results in a paper we had submitted for a conference and as it took way more time than I had anticipated, I figured it’s something worth documenting. My first point of call was obviously Sgt. Google and the first hit given was How to Make a Heatmap – a Quick and Easy Solution, which I naturally liked since the sample dataset was a basketball stats one 😀 However, I quickly realised that this was not enough for what I wanted – my x-axis showed time and instead of nice, fat blocks, my heatmap/graph showed thin, coloured lines. Another problem I ran into was interpretation. I initially had something like this:

n = 50
matrix_to_be_plotted <- rnorm(n*n) # generate 50 x 50 = 2500 random numbers
dim(matrix_to_be_plotted) <- c(n,n) # change vector to matrix of dimension 50 x 50

heatmap(matrix_to_be_plotted, # as name suggests, the matrix of the data to be plotted
scale = “row”, # this is important; I did not realise this at first and spent an evening wondering why data values did not match with what I was describing in the heatmap (I’d assumed the darker the shade, the higher the value). Basically, you can control colour scaling by row or column, default is row. This is so important in my opinion that I’ll quote the documentation: “character indicating if the values should be centered and scaled in either the row direction or the column direction, or none. The default is “row” if symm false, and “none” otherwise.”
main = “Greyscale heatmap – squares”, # name/title of figure
Colv=NA, Rowv=NA, # set to NA or columns/rows of matrix would be rearranged into hierarchical clusters according to R’s dendrogram function
margins=c(3,3), # column/row margin space, the higher the number, the more space you get
cexCol=1, cexRow=1, # size of column/row labels, 1 is default
col=grey(seq(1,0,-0.01)) # colour is greyscale, sequence from 1 (black) to 0 (white) in steps of 0.01
)

which was a grey-scale version of what I wanted. You can read the documentation of the parameters of R heatmap, but my own explanation/interpretation of the parameters in the context of what I’ve given is written.

Here’s a picture of what should come out (tips on Saving Plots in R):

Not bad: Example of Greyscale heatmap, square matrix

This doesn’t look so bad, and if this is all you need, great. However, here’s a rectangular matrix, i.e. more similar to what I had in originally, which can be emulated by changing the dimensions like so:

dim(matrix_to_be_plotted_thin) <- c(n/2,2*n)
colnames(matrix_to_be_plotted_thin) <- rep(” “, 2*n)
colnames(matrix_to_be_plotted_thin)[seq(1,2*n,3)] <- paste(“Wk”, seq(1,2*n,3))

The column names are changed so they don’t get so squished on the x-axis:

Kind of Ugly: Example of Greyscale heatmap, rectangular matrix

This is less visually appealing. Moreover, it didn’t suit my graph because looked like this:

Yuck: My own graph, Greyscale insufficient

Part of the problem was that I didn’t realise I hadn’t the scaling properly – by default it was row-scaled, I was describing it as it were column-scaled. However, in retrospect, it still wouldn’t have worked if I had the correct scaling because this, as a figure taking up about barely one-sixth of a page, it was fairly difficult to read when printed. (I couldn’t figure out how to get a border around the graphic either so if anyone knows, please comment and let me know!) Anyway, my Saturday morning thus became an online google image and documentation hunt with keywords of R, heatmap, image, matrix image, visualisation,  <what have you>, and finally I converged to using an upgraded package of heatmap (library being heatmap.plus) with gplots – to prettify the graph with custom colours.

This apparently Easy Guide To Drawing Heat Maps To PDF With R (With Color Key) was a great starting point, but ultimately, I found that the full heatmap.2 documentation combined with this colorRamp pdf most useful as they actually explained what you needed to do to customise.

A slight detour – colour

I am a bit particular about my colours, both from an explanatory viewpoint and from an aesthetic one. I utterly despise bad graphs and badly-coloured ones even more so. In academia (or any good documentation that requires printing out), the best thing to do is to have graphs free of colour, such that it still makes perfect sense when printed in greyscale, and I do prefer that. However, when needs be for colour, I think it’s important to get it right, e.g. the most common type of colour blindness is red-green, so avoid using those two for distinguishing.

This arbitrary compulsive requirement of mine lead me to actually create my own palette for my heatmap…(Yay, as if I don’t have enough ways to spend my time.) More importantly, graphs are supposed to be a more efficient way of explaining data, not made just for the sake of them. If I am going to use colour in my graph, there should be a reason for it, and it shouldn’t require more text to explain why. (Picture – a thousand words – that sort of thing.)

A useful resource for creating your own palette is to look at this R colour chart. Here are a few examples:

TestPalette <- colorRampPalette( c(‘aliceblue’,’aquamarine1′,’azure3′,’blue’,’blueviolet’, ‘darkcyan’,’darkblue’,’darkgreen’,’darkmagenta’,’darkolivegreen’, ‘darkmagenta’,’darkviolet’,’black’))
CoolPalette <- colorRampPalette(c(‘lavender’,’mediumslateblue’,’blue’,’turquoise4′,’seagreen2′,’seagreen4′,’black’))
BluesPalette <- colorRampPalette(brewer.pal(9,”Blues”))(100)

brewer.pal is the in-built palette (as described in detail in the colorRamp pdf I linked earlier) – the handiest query for me was:

display.brewer.all()

which shows the name of the palette (like “Blues”) and the range of colours in it. Also, (100) in the BluesPalette example gives how fine you want the shading to be. So, if you had (3) then there’d be three varying shades of blue of something like Dark Blue, Blue, Light Blue, (100) gives you on hundred shades varying from dark to light.

Finally…

The code for my final plot and comments for explanation of new things:

library(gplots) # for colour panel of heatmap
library(heatmap.plus)

heatmap.2(MyMatrix,
Rowv=FALSE, Colv=FALSE, dendrogram= c(“none”),
cexCol=1, cexRow=1,
key=TRUE, keysize=0.1, # display colour key
density.info=c(“none”), # options of different plots to be drawn in colour key
trace=”none”, # character string indicating whether a solid “trace” line should be drawn across ‘row’s or down ‘column’s, ‘both’ or ‘none’.
margins=c(5,9),
lmat=rbind( c(0,3), c(2,1), c(0,4) ), lhei=c(0.2, 8.5, 2), # where to display colour key
col=CoolPalette # custom colours for colour key
)

….and the result:

Much nicer: Heatmap with Cool Palette colours

My only and final annoyance with this is the “Value” which floats a bit too near the displayed numbers, but I don’t think it impedes on the readability so much that it’s worth unnecessary tweaking.

Funnily enough, the greyscale versions don’t look as bad on screen as a blog post. But trust me, it makes one hell of a difference on paper.

## Web Science Doctoral Summer School 2011 (belated)

August 26th, 2011

Here’s a somewhat very belated post on the Web Science Summer School I attended over a month ago (July 6, 2011 – July 13, 2011).

My thoughts? It was great! Fortunately, there were also enough others who felt compelled to write about it so that I don’t feel a huge urge to have a massive brain squeeze of whatever memories I have of it. That said, there’s always room for a few (short) thoughts.

It was an intense week of lectures/tutorials, often starting at 9am and finishing at 6pm, which meant many of us were very much drained at the end. Tiredness aside, the highlight for me (minus the social bits) was the mini-project. Over the course of a few days, we collected different types of communication data (specifically, face-to-face communication, facebook & twitter) and pretended to be web-social scientists and tried to make as much sense of it (until silly hours). With a bit of help of compewters and algorisms to make it all sound legit, of course. (Actual details on it can be found at Aaron’s post, which I’ve linked below.)

Here’s one example of what coordinated collective action at this school resulted in:

Some other people’s posts (thoughts) on the school:

• Clare Hooper’s personal perspective on it, as well as the start of it (with subsequent posts on the attended lectures – well worth a read as summaries to decide if you want to watch the allotted ~1.5 hours for each talk).
• Aaron McDaid and Owen Phelan‘s posts on the school – the former has more details of our team’s mini-project.

Resources:

• Here are some links to the lecture/tutorial videos and the corresponding slides.
• Here are also some flickr photos of the school.
• In particular, very useful supporting material to the tutorial given by Derek Greene, post-doc at UCD. (Not just promoting a colleague 😉 It really is a good intro. to important concepts in social network analysis and relevant software (networkx, gephi), with concrete examples and datasets.)

Oh, and my favourite quote of the week (and aspire to partially be – i.e. automate as much ‘trivial’ stuffs as a I can so that what I am is the creator/storyteller rather than command follower (explanation especially for Ursula, even I’m not usually this pedantic!) ):

“You are what you do not automate” — Marc Smith