Repair Roads (Codesprint problem)

March 3, 2012, 8:36 pm

I was looking though the old codesprint problems and came across this one:

The country of Byteland contains of N cities and N – 1 bidirectional roads between them such that there is a path between any two cities. The roads in Byteland were built long ago and now they are in need of repair. You have been hired to repair all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then move to one of the adjacent unrepaired roads. After repairing that, he will move to another adjacent unrepaired road, repair that and so on.
Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will can ever repair the same road, and no road can be visited twice. What is the least number of robots needed to accomplish the task?

here

The solution is described here. But it wasn’t so clear to me. I’d like to work through the problem to compilation, unfortunately I need to get hold of the paper he references. Anyway, I fundamentally understand the method now and thought I’d write up my notes so far:

1. The first step is to recognise that representation we want is the line graph of roads connecting towns. Paths on this graph represent valid transitions between edges. The problem is then to find a set of paths that visit each vertex once, and only once. Clearly if there is a Hamiltonian path, only one path is required. And only one robot is therefore required.

2. The second thing to recognise is that the number we are looking for is the minimal number of edges to add to allow a Hamiltonian path to exist. See here. Why is that? It’s because each edge we add to the graph to make it Hamiltonian connects a previously disconnected path. Each of those disconnected paths requires its own robot.

3. The next thing to recognise is that because there are N cities and N-1 edges, the graph is always a tree.

So we need to find a Hamiltonian completion of the line graph of a tree. And it turns out that there’s a linear time algorithm for doing this (though I’m unable to download the paper). This paper.

If I can dig out the paper (if you’re feeling kind and would like to help me get a copy, let me know) I might have a go at implementing the algorithm.

Category: Uncategorized  |  Comment

Langford Pairs – a silly hill climber

March 3, 2012, 12:22 am

Langford pairs are sequences if numbers where each number less than n occurs twice, and each occurrence of a value (i) is separated by i other numbers. For example for n=3:

3 1 2 1 3 2

So there you go. It’s a largely theoretical problem, though I think such sequences could have practical applications. For example, say you have a black box, caesar cypher encoder. You can feed it strings and look at the output in order to determine the substitution matrix being used… However the encoder embeds the message with a random amount of padding, and randomly discards parts of you message… Feeding the encoder a Langford pair may be an efficient way to determine the substitution matrix. Once encoded you can simply see which pairs are a given distance apart, the distance gives you the symbol number…

Anyway.

This is a silly hill climber for finding Langford pairs. There are surely better algorithms for doing this, and hill climbers don’t work particularly well! (solutions were at best 1 off for langford pairs beyond n=3. But I wonder what it is about the landscape that makes hill climbers perform badly here. As it’s almost a toy problem it might be interesting to play with a little.

import random

size = 7

def langfordscore(l):
  
  score = 0

  for i in range(1,size):
    idx = []
    for j in range(len(l)):
      if(l[j] == i):
        idx.append(j)

    if (abs(idx[0]-idx[1]) != (i+1)):
      score = score+1

  return score

def swap(l):
  i = random.randint(0,len(l)-1)
  j = random.randint(0,len(l)-1)

  nl = list(l)
  nl[i] = l[j]
  nl[j] = l[i]

  return nl

langford = []

for i in range(1,size):
  langford.append(i)
  langford.append(i)

print langford

score = 1000
ittr = 0
lastmove = 0
mutrate = 0
while ((score != 0) and (ittr < 200000)):

  nlangford = swap(langford)

  for i in range(mutrate):
    nlangford = swap(nlangford)

  if (lastmove > 500):
    lastmove = 0
    mutrate = mutrate + 1
  
  if (mutrate > 5):
    mutrate = 0


  nscore = langfordscore(nlangford)
  
  if(nscore < score):
    langford = nlangford
    score = nscore
    print score
    print langford
  else:
    lastmove = lastmove + 1

  ittr = ittr + 1
Category: Uncategorized  |  Comment

How to get a digital copy of “The Art of Computer Programming”

February 23, 2012, 7:07 pm

It’s the year 2012 and this is the only way to get a legitimate digital copy of the seminal work in Computer Science, The Art of Computer Programming:

Shame really, let face it we pretty much know there’s a postscript file sitting on Donald Knuth’s PC somewhere…

see here

Category: Uncategorized  |  1 Comment

Scanning books with a MFC-5895CW

February 19, 2012, 1:08 pm

I found a MFC-5895CW in Ryman’s today, discounted to 95 pounds. The MFC-5895CW is a multifunction printer/scanner/fax machine. What attracted me though is that it has a document feeder for scanning. I’ve been looking for a way to scan in my books (even if the process is destructive). As an aside, I’m told that book scanning services are common (and cheap) in Japan, it’s a shame it’s such a pain to get them there…

For my first effort I decided to use a book I was planning to throw out anyway “Digital System Design with VHDL” by Mark Zwolinski (sorry Mark, you were a great lecturer but I just don’t find myself doing much VHDL these days…).

To start with, I removed the front and back cover.

I then cut along the spine using a Stanley Knife:

Unfortunately, as I cut into the book I seem to have moved the knife nearer to the spine (something to avoid next time).

After slicing the whole thing up, it’s ready to scan!

The scanner can cope with about 60pages at a time. However it’s not a duplexing scanner. So once you’ve scanned one side you need to reinsert the stack of pages to scan the other side.

The MFC-5895CV scans directly to pdf. It creates files with a basename followed by a two digit number (01,02,03 etc.). It will also scan directly to a USB stick, which is rather neat.

So, after scanning you’re felt with a series of pdf files on a USB stick. Odd and Even numbered files form a pair of front and back sides of pages. You now need to join all these together.

I used pdftk on Linux to do this. Here’s my bash script (you’ll probably need to change the basename if you use it). It assumes it’s being run in the same directory as the input files.

basename="010111"

for ((i=1; i<=99; i++))
do
  mkdir join
  cd join
  file1=../$basename`printf "%02d" $i`.PDF
  fileout=../$basename`printf "%02d" $i`join.pdf
  i=$((i+1))
  file2=../$basename`printf "%02d" $i`.PDF
  echo "file1: " $file1
  echo "file2: " $file2
  cp $file1 ./first.pdf
  cp $file2 ./second.pdf
  pdftk ./second.pdf cat end-1 output second1.pdf
  rm second.pdf
  mv second1.pdf second.pdf
  pdftk first.pdf burst output %04d_A.pdf
  pdftk second.pdf burst output %04d_B.pdf
  rm first.pdf
  rm second.pdf
  pdftk *.pdf cat output out.pdf
  cp out.pdf $fileout
  cd ..
  rm -rf join
done

pdftk *join.pdf cat output complete.pdf

It all works pretty well for the most part. Some of the pages came out a little askew:

This maybe due to my poor cutting, not having set the feeder correctly, or the generally dog-eared nature of the book.

Diagrams came out pretty well:

Though, you can see some compression artifacts. It could also do with some post processing to increase the contrast perhaps. I might try the next book at 300dpi (I should also probably uses the black and white scanning mode).

Category: Uncategorized  |  3 Comments
« Previous Entries
Next Entries »