Archive for March 2012

Next Entries »

Another Pretty HTML5 thing

March 6, 2012, 3:53 am

I remember writing ARM assembler code to make these pretty things about 15 years ago. Anyway, now in html5!

Click Here to open in new window.

And here’s the JS for reference:


<script type="text/javascript">

  var ittr=10;
  var delta=-0.05;

  function draw_thing(ctx,ox,oy,sx,sy,ds,ex,ey,de) {

      var mins=0;
      var maxs=0;
      if(ds < 0) {mins=-200; maxs=0;} else {mins=200; maxs=0;}

      for(sy=maxs;Math.abs(sy) < Math.abs(mins);sy=sy+ds) {
        ctx.beginPath();
        ctx.moveTo(ox+sx,oy+sy);
        ctx.lineTo(ox+ex,oy+ey);
        ctx.closePath();
        ctx.stroke();
        ex=ex+de;
      }

      ctx.beginPath();
      ctx.moveTo(ox,oy);
      ctx.lineTo(ox,oy+mins);
      ctx.closePath();
      ctx.stroke();

  }

  function draw_frame() {
    var canvas = document.getElementById("m_canvas");
    if(canvas.getContext) {

      var ctx = canvas.getContext("2d");
      ctx.clearRect(0, 0, canvas.width, canvas.height);
      ctx.lineWidth  = 1;

      ctx.fillStyle = "rgb(0,0,0)";
      var size=1;
      var offset=0;

      draw_thing(ctx,200,200,0,0,  ittr, 200,0,0-ittr);
      draw_thing(ctx,200,200,0,0,0-ittr, 200,0,0-ittr);
      draw_thing(ctx,200,200,0,0,  ittr,-200,0,  ittr);
      draw_thing(ctx,200,200,0,0,0-ittr,-200,0,  ittr);

      ittr = ittr + delta;
      if(ittr<2 ) {delta = 0-delta; ittr=2;}
      if(ittr>10) {delta = 0-delta;}
    }
  }

</script>
Category: Uncategorized  |  1 Comment

Pretty HTML Canvas thing from a 30 year old magazine

March 5, 2012, 1:06 am

I was looking through an old copy of Beebug from 1982 and came across a review for “Practical Programs for the BBC Computer and Acorn Atom”:

The review contains a code listing from the book to draw a “very nice 3D object”. I decided it might be fun to port the program to HTML5 using a canvas. I also modified it slightly to animate the rendering. It’s a direct port, I just ported it line for line and then added code to vary YS to animate the object. Click below to take a look:


CLICK TO OPEN ANIMATION

opens in new window

The basic html5 implementation was pretty straightforward, however getting it to animate without a horrible amount of flickering was harder. It doesn’t look like canvas has support for double buffering, the only option being to use 2 canvas objects and hide one while you’re drawing to it. Blanking the whole canvas resulted in a horrible flicker for me, so instead I opted to black vertical lines during the rendering of each frame, this seems to work pretty well.

If you liked this thing, there’s another one here.

Notes

Here’s the full text of the article:

Title: Practical Programs for the BBC Computer and Acorn Atom
By: David Johnson-Davis Price £5.95
Reviewer: David Graham

As its title suggests, this book is not concerned with teaching you to program, or with teaching you to use the computer, but with the presentation of a number of programs. The range of programs offered is good, and includes games, graphics, number and word handling, and rather surprisingly an SPL compiler. With each program there is a discussion of the objects and principles involved (though nothing on the programming principles). The program listings are also broken down into useful subsections with boxed functional headings. This makes them relatively easy to follow.

The final section of the book, chapter 5, introduces the subject of compilers, and gives a listing for an experimental Simple Programming Language compiler for the BBC machine, plus a number of SPL programs that may be run on it. This all looks very interesting, and well worth some closer study. But if you are not interested in compilers, you are left with only 65 pages of the book; and since some of that space is taken up with the Acorn Atom version of each program presented, the book becomes a little expensive per useable page. It does, however, contain some good ideas, such as the brief program given below which plots the very nice 3D object in the photograph.

 10 REM FROM:
 20 REM PRACTICAL PROGRAMS FOR THE
 30 REM BBC COMPUTER AND ACORN ATOM
 40 REM BY DAVID JOHNSON-DAVIS
 50 MODE4:VDU29,640,512;:XS=4:YS=4
 60 A=640:B=A*A:C=512
 70 FORX=0TOA STEPXS:S=X*X:P=SQR(B-S)
 80   FORI=-P TO P STEP 6*YS
 90     R=SQR(S+I*I)/A
100     Q=(R-1)*SIN(24*R)
110     Y=I/3+Q*C
120     IFI=-P THEN M=Y:GOTO150
130     IFY>M M=Y: GOTO160
140     IFY>=N GOTO170
150     N=Y
160     PLOT69,-X,Y:PLOT69,X,Y
170     NEXT:NEXT
180 END

The Javascript:

  function draw_frame() {
    var canvas = document.getElementById("m_canvas");
    if(canvas.getContext) {
      var ctx = canvas.getContext("2d");
      ctx.lineWidth  = 0;

      ctx.fillStyle = "rgb(0,0,0)";
      var size=1;
      var offset=0;

      ctx.scale(1,-1);

      var xs=2;
      var ys=ittr;
      var a=640;
      var b=a*a;
      var c=512;

      for(var x=0;x<=a;x=x+xs) {
        s = x*x;
        p = Math.sqrt(b-s);

        ctx.clearRect(((  x+640)/2)+offset,0,2,canvas.height);
        ctx.clearRect(((0-x+640)/2)+offset-1,0,2,canvas.height);

        // size=0.5; offset=0;
        for(var i=0-p;i<=p;i+=6*ys) {
          var r = Math.sqrt(s+i*i)/a;
          var q = (r-1)*Math.sin(24*r);
          y = i/3 + q*c;
          if(i==0-p) {m=y; n=y; ctx.fillRect(((0-x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); ctx.fillRect(((x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); }
          if(y>m)    {m=y;      ctx.fillRect(((0-x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); ctx.fillRect(((x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); }
          if(!(y>=n)){n=y;      ctx.fillRect(((0-x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); ctx.fillRect(((x+640)/2)+offset,(512-(y+512)/2)+offset,size,size); }
        }
      }
      ittr = ittr + delta;
      if(ittr < 0.6) delta = 0-delta;
      if(ittr > 100) delta = 0-delta;
    }
  }

The function is then triggered by a setInterval on the page load as follows:

<body  onload="setInterval(draw_frame,10);" >
Category: Uncategorized  |  1 Comment

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
Next Entries »