A programming challenge all up in your face.

[H_TeXMeX_H]

Hmmm ... yeah, this is too damn hard.

[worker201]

Why am I unable to post my code?

Not Acceptable

 An appropriate representation of the requested resource /forums/editpost.php could not be found on this server.

[mobrien_12]

There's some stupid bug in the system if you have a couple of characters one right after the other the whole post gets borked.  I can't remember the sequence... we had a thread on it last year, but it never got fixed.

Try posting chunks of it with edit to find out what is crashing the system.  That's what I had to do last time one of my posts triggered this bug.

Alternatatively you could compress and upload it as a tgz or bz2 file.

Please do it, I want to see the code

[TheQuirk]

Wow, this thread has taken off.

Re: vertical lines, since we have this:

[(y2 - y1)/(x2 - x1)]x + k = y

We could multiply both sides by (x2 - x1) and see what that gets us (there won't be division by 0).

Re: Matlab, I was always under the impression that Matlab could actually do lots of computations faster than compiled C.

[H_TeXMeX_H]

Why am I unable to post my code?

The keyword you can't post is:

f  open

So why can I post it ? Because there are two spaces between f and open instead of one

[mobrien_12]

The keyword you can't post is:

f  open

So why can I post it ? Because there are two spaces between f and open instead of one

But I could post fopen??

f opan
f op
f ope
f opep
g open

but f with a space followed by open barfs the system.

WTF kind of bug is this?

[piratePenguin]

mobrien: put a space between the f and open. Using two spaces works, ala: f  open

Not Acceptable
An appropriate representation of the requested resource /forums/editpost.php could not be found on this server.

That is a classy error message if ever I saw one.

[mobrien_12]

OK this bug needs to be a sticky somewhere.

[mobrien_12]

Re: Matlab, I was always under the impression that Matlab could actually do lots of computations faster than compiled C.

Certain matrix calculations yes, because it has optimized compiled libraries that take care of them.  It has superior support or complex numbers as well.

In general, however, for very large codebases, it's slow as a basset hound on a hot summer day after eating a steak.  It is a scripting language.  

You need to be a pretty experienced Matlab or Octave coder to be able to take advantage of the vector/matrix nature of the languages properly, and that will help, but if you want to speed up the calculations you need to either recode in C or Fortran 9x or take the slowest parts of the code base and turn those into C.  You can link compiled C code into Matlab or Octave, and that speeds things up a hell of a lot, but that requires you to not be a lazy bastard.

There is a Matlab compiler now... not sure how its performance compares to C.

[piratePenguin]

just testing.
testing

[worker201]

I didn't understand M_Obrien's geometry, so I used the Law of Cosines.  As displayed in the following image:


I can't deal with tangent lines, vertical lines, or datfiles with more than 16 circles.  Otherwise, it seems to work fine.

http://www.triple-bypass.net/download/circleline.txt

[mobrien_12]

Updated solution to fix the problem mentioned before.  

Code: [Select]


## Solution to Quirk's challenge problem Version 2
## Written by M O'Brien.  Copyright 2006.
## Licenced to others under GPL.
## Language is GNU Octave (http://www.octave.org)

## READ DATA FILE
fileid=fopen("data.dat","rt");
[x1,count]=fscanf(fileid,"%f",1);
[y1,count]=fscanf(fileid,"%f",1);
[x2,count]=fscanf(fileid,"%f",1);
[y2,count]=fscanf(fileid,"%f",1);
[numcircles,count]=fscanf(fileid,"%d",1);
for k=1:numcircles
  [circledat,count]=fscanf(fileid,"%f %f %f",3);
  circx(k)=circledat(1);
  circy(k)=circledat(2);
  radius(k)=circledat(3);
endfor
fclose(fileid);

##  Start the interesting stuff

linelength=sqrt( (x2-x1)**2 + (y2-y1)**2 );

totalpathlength=linelength;
numcirclesintersected=0;
for k=1:numcircles
 
  ## calculate distace from the line to the center of circle
  ## formula is from vector analysis but can be found with web
  ## search
 
  numerator=abs((x2-x1)*(y1-circy(k)) - \
(x1-circx(k))*(y2-y1) );
  disttoline=numerator/linelength;
 
  ## define some intermediate variables to make later equations readable
  ## s1 is distance from line endpoint 1 to center circle
  s1=sqrt( (circx(k)-x1)**2 + (circy(k)-y1)**2 );
  ## s2 is distance from line endpoint 2 to center circle
  s2=sqrt( (circx(k)-x2)**2 + (circy(k)-y2)**2 );
  ## p1 is the projection of s1 along the line (vector component)
  p1=sqrt( s1**2 - disttoline**2 );
  ## p2 is the projection of s2 along the line (vector component)
  p2=sqrt( s2**2 - disttoline**2 );
 
 
  ## these are boolean, true or false
  ## check to see if a line endpoint is inside the circle
  EndInCircle= ( ( s1 < radius(k) ) | ( s2 < radius(k) ) );
  LineInRange= (disttoline < radius(k));
  LineLongEnough = ( ( p1 < linelength ) & ( p2 < linelength ) );

  if ( (!EndInCircle) & (LineInRange) & (LineLongEnough) )
    ## the line is intersecting the current circle, forming a chord.
    ## Only use less than because if it is equal, it is a tangent line
    ## and will not affect the path extension at all
    numcirclesintersected=numcirclesintersected+1;
    halfangle=acos(disttoline/radius(k));
    chordlength=2*radius(k)*sin(halfangle);
    arclength=2*halfangle*radius(k);
    pathdifference=arclength-chordlength;
  else
    ## Line does not interesect the circle.
    pathdifference=0;
  endif
 
  totalpathlength=totalpathlength+pathdifference;

endfor

## final output comes now
disp("total number of circles intersected"),disp(numcirclesintersected);
disp("length of line w/o circles factored in"), disp(linelength);
disp("final path length after circles"), disp(totalpathlength);

fileid=fopen("output.dat","wt");
fprintf(fileid,"%f",totalpathlength);
fclose(fileid)

## end program


Tested with the following data.

Code: [Select]


0
0
10
10
2
5 5 1
20 20 2


With the following results

total number of circles intersected
 1
length of line w/o circles factored in
 14.142
final path length after circles
 15.284

Actual answer is 15.28372827

Final answer is rounded off to 3 decimal places so the answer is fully correct.

[mobrien_12]

Worker, I tried to compile your code but get errors.... it says sqrt and acos is undefined.  

I just did gcc circleline.c, and I do have math.h on my system.  Do I need a special library?

EDIT:  nevermind... forgot about the -lm to link to the math library....

[mobrien_12]

Output from Worker's program.

15.282185

Actual answer is 15.28372827

Looks good!

[worker201]

I noticed that too.  At what stage do our calculation differences come from?