text:
Equilibrium index of a sequence
Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:
A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:
A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:
A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.
The idea is to create a program that given a sequence (array), returns its equilibrium index (any) or -1 if no equilibrium indexes exist.

Golfscript 17 16
Since the form of the input isn't specified, this takes a string in Golfscript array format from stdin.
~0\{1$+.@+\}/])?

So run as e.g.
golfscript.ry eqindex.gs <<<"[-7 1 5 2 -4 3 0]"

The idea is very simple: it takes an array of A_i and maps to an array of A_i + 2 SUM_{j<i} A_j and then looks for the first index which is equal to the sum of the whole array.

For @mellamokb's challenge I offer:
~0\{1$+.@+\}/:S;]:A,,{A=S=},`

for 29 chars.

Since you easily have the shortest solution, I proclaim you must return all of the indexes, not just the first one :)

@mellamokb, with my compliments.

Cool!  Now I've got some more GolfScript learning to do...

Haskell (95 83)
e l=[n|n<-[0..length l-1],sum(take n l)==sum(drop(n+1)l)]
main=interact$show.e.read

Reads a list in Haskell style from stdin, eg.
[-7,1,5,2,-4,3,0]

and returns a Haskell style list of the indices, eg.
[3,6]

The result is [], if there is no index.
Please tell me, if your spec wants a different behavior.
Edits:

(95 → 83): list comprehension is more breve

Python - 72 chars
A=input()
print[i for i in range(len(A))if sum(A[:i])==sum(A[i+1:])]or-1

Takes comma separated input

Awesome... this one returns all the equilibrium indexes... really cool.

@Christian: Mine does so, too.

I see :) I actually don't know how to run haskell code... will have to study.

Christian: There is ghc, a compiler and hugs, an interpreter. I'd suggest downloading hugs. It's better then downloading ghc, because hugs is about 7 MiB, while the whole ghc distribution is about 300 MiB. Using hugs, you can just type runhugs FILE.hs to run program FILE.hs.

C - 96
a[99],*p=a,s;main(){for(;scanf("%d",p)>0;s+=*p++
);for(;p>a;s-=*p)(s-=*--p)||printf("%d\n",p-a);}

Note that this prints the equilibrium indices in reverse order.
Sample usage:
$ ./equilibrium <<< "-7 1 5 2 -4 3 0"
6
3

Ruby (83 77)
a=*$<.map(&:to_i)
p (0...a.size).select{|x|a[0..x].reduce(:+)==a[x..-1].reduce(:+)}

Edit: Shorter version as suggested by Ventero:
a=$<.map &:to_i
p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"}

Input is one number per line, output is comma separated list of indexes in square brackets.

You don't need the parentheses in the first line, and you can save a few chars by using join + eval to get the sums: p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"} (note that this is for Ruby 1.9, since it uses character literals as strings)

Great suggestions, thanks! Kind of annoying that Array#sum isn't in Ruby core.

If I remove the parantheses in the first line, I get: "SyntaxError: (irb):17: syntax error, unexpected tAMPER, expecting $end"

There has to be a space between map and the ampersand. And you don't need the splat operator in front of the $< either, so all in all the line would look like this: a=$<.map &:to_i. ;)

Ah, thanks again, it was the splat that ruined the syntax.

JavaScript (161)
P=parseInt;L=prompt().split(',');S=function(A)A.reduce(function(a,b)P(a)+P(b),0);R=[i for(i in L)if(S(L.slice(0,i))==S(L.slice(P(i)+1)))];alert(R.length>0?R:-1);

http://jsfiddle.net/6qYQv/1/

scala, 108
val l=readline().split(" ").map(w=>w.toInt)
for(i<-0 to l.length-1
if l.take(i).sum==l.drop(i+1).sum)yield i

J (12 characters)
A monadic verb in tacit notation that returns a vector of equilibrium indices. Spaces inserted for legibility only.
[: I. +/\. = +/\

To explain this, first observe its explicit definition; y is the formal parameter:
3 : 'I. (+/\. y) = (+/\ y)'

+ adds its arguments. / is an adverb that inserts the verb left of it between the members of its right argument, e.g. +/ 1 2 3 4 is the same as 1 + 2 + 3 + 4.
\ is an adverb that applies the verb to its left to all prefixes prefixes of its right argument. For instance, with < drawing a box around its argument, <\ 1 2 3 4 produces
┌─┬───┬─────┬───────┐
│1│1 2│1 2 3│1 2 3 4│
└─┴───┴─────┴───────┘

Thus, +/\ computes for each prefix of its right argument the sum.
\. is like \ but operates on suffixes instead of prefixes. Thus, +/\. computes a vector of sums of suffixes.
= performs item-wise comparison of its arguments. For instance, 1 1 3 3 = 1 2 3 4 yields 1 0 1 0.
Thus, (+/\. y) = (+/\ y) yields one for all indices at which the suffix sum is equal to the prefix sum, or, an equilibrium is created.
For vectors of zeroes and ones, I. returns a vector of the indices at which the vector contains a one.

Python 2, 70
A=input()
e=i=s=0
for x in A:e=[e,~i][s*2==sum(A)-x];s+=x;i+=1
print~e

The idea is to track the running sum s and check whether it is half of the sum of array without the current element, and therefore equal to the sum of the array after the current element. If so, we update the equilibrium index to the current index. The last equilibrium index is printed, or the initial value -1 if there's none.
Actually, we store the bit-complement of the equilibrium index so that we can initialize it to 0 instead.

Python - 114
i=map(lambda x:int(x),raw_input().split(" "));x=0
print map(lambda x:(sum(i[0:x])==sum(i[x+1::])),range(0,len(i)))

Python - 72
i=input()
print map(lambda x:sum(i[0:x])==sum(i[x+1::]),range(0,len(i)))

Prints whether or not the given index is an equilibrium index, does not print the integer indecies at which the array is balanced.

What do you mean it breaks?  6 is an equilibrium index because the items before it sum to zero, there are no items after it, and 50 is ignored.

AH. Thanks for the clarification joey, I didn't realize that the value at x was supposed to be ignored.

PHP, 134 chars
<?for($a=explode(",",fgets(STDIN));++$i<($c=count($a));$o.=$s==0?$i:"")for($n=$s=0;$n<$c;)$s+=$n<$i?$a[$n++]:-$a[++$n];echo$o?$o:"-1";

I have an itch that this is far from optimal PHP golfing, but just ran out of steam (brains). At least it's shorter than with array_sum and array_splice :-)

PHP (81)
for($i=count($a)-1,$c=0;$i+1&&$c!=(array_sum($a)-$a[$i])/2;$c+=$a[$i--]);echo $i;
http://3v4l.org/qJvhO
Since no input was specified, this needs to be initialised with the array as the variable $a.


text:
Pirate Treasure
Finding a treasure hidden by pirates is really easy. Everything you need for this is a map. It is widely known that pirates draw maps by hand and describe the algorithm to find a place in the following way: "Stand near a lone palm tree, do 30 steps towards the forest, 15 towards the lake, ..."
A journey through such route is usually a great opportunity to see the scenery... However, nowadays nobody has time for that. That's why treasure seekers have asked you to write a program that would determine the exact location of a treasure using a given map.

Input
The input consists of multiple instructions <Direction> <Distance>, separated with commas (that are followed by one whitespace each).
Direction is one of the following:
N - North, S - South, E - East, W - West,
NE - Northeast, NW - Northwest, SE - Southeast, SW - Southwest.
Distance is an integer (1 to 1000).
Output
The result is the coordinates where you end up after finishing the instructions, with three decimal places, separated with a comma and a whitespace. Start location has zero coordinates (0, 0).
The first coordinate is X (East means coordinates larger than zero, West means less than zero).
The second coordinate is Y (North means more than zero, South means less than zero).

Examples
1. N 3, E 1, N 1, E 3, S 2, W 1
    3.000, 2.000
2. NW 10
    -7.071, 7.071
3. NE 42, NW 42, SE 42, SW 42
    0.000, 0.000

Source (in Ukrainian). Input format is different there.

Bonus points for doing it in Logo? ;)

@Peter The output format is strict... But we will see whether people like the picture :D

The first example output should be -3.000, 2.000.

with UCB Logo the output format can be obtained as (print (word (form xcor 4 3) ",) (form ycor 4 3)). But I'm not sure how easy parsing the input would be.

@Lowjacker Yes, thanks. Actually, the input was wrong.

Ruby 1.9, 175 171 162 153 130 120 117
l=0
gets.scan(/(\w+) (\d+)/){|d,n|l+=n.to_i*?i.to_c**%w[E NE N NW W SW S SE].index(d).quo(2)}
puts'%.3f, %.3f'%l.rect

?i.to_c can be shortened to 1.i for -4 bytes.

Python, 158 154 150 chars
p=0j
for s in raw_input().split(','):c,d=s.split();v=sum(dict(N=1j,E=1,S=-1j,W=-1)[x]for x in c);p+=v*int(d)/abs(v)
print'%.3f, %.3f'%(p.real,p.imag)

You actually have 157 chars, not 158.

I guess I don't need to, but I usually count the trailing newline.

[157] Line 1: D=dict(N=1j,E=1,S=-1j,W=-1) [153] Line 2: is j really needed? [152] Lines 3-4: If you switch to Python 3, raw_input→input, and even though you have to use parentheses after print, you save 2 characters [150]

@BlaXpirit: Thanks for the dict optimization.  The j is needed in line 2 in case all the directions are E and W.  The resulting p needs to be complex for .real and .imag to work.

@Keith: It is not necessary to even declare the dict. You can just put it instead of D inside the code to save 4 more characters. Just saying...

int class has both imag and real attrs...

@JBernardo: well, not in my python version (2.4.4).

@Keith: there is really no reason to use that version of Python.

Haskell (291)
import Text.Printf
d=sqrt(0.5)
f"N"n(x,y)=(x,y+n)
f"S"n(x,y)=(x,y-n)
f"E"n(x,y)=(x+n,y)
f"W"n(x,y)=(x-n,y)
f[a,b]n(x,y)=(s,t)where(s,_)=f[b](d*n)(x,y);(_,t)=f[a](d*n)(x,y)
p[]=(0,0)
p(a:b:c)=f a(read b::Float)$p c
s(a,b)=printf"%.3f, %.3f"a b
main=getLine>>=putStrLn.s.p.words.filter(/=',')

How about changing the defintion of f to use pattern guards? They have the nice property to not require a line break and should be more breve in this case. Also, use interact.

C99 (319 chars)
#define B ;break;
#include<math.h>
#include<stdio.h>
float x,y,w,z,j;int
main(void){int
k;char
c[3];while(scanf("%s%d,",c,&k)==2){j=k;w=1;switch(c[1]){case'E':w=3;default:w-=2;j=sqrt(k*k/2)B
case
0:w=z=0;}switch(*c){case'N':z=1
B
case'S':z=-1
B
case'E':w=1
B
default:w=-1;}x+=w*j;y+=z*j;}printf("%5.3f, %5.3f\n",x,y);}

input in stdin, test run at ideone :)

JavaScript, 179 164 170 168 158 156 153 chars
prompt(X=Y=0).replace(/(N|S)?(.)? (\d+)/g,
        function(m,y,x,n){
            n/=x&&y?Math.SQRT2:1
            Y+=y?y<'S'?n:-n:0
            X+=x?x<'W'?n:-n:0
        })
alert(X.toFixed(3)+', '+Y.toFixed(3))

170: fixed accuracy issue
168: replaced (E|W) in regex with (.)
158: replaced repetitive logic in function with variable d
156: reused n instead of a new variable d
153: Personally, I think this edit makes it ten times uglier, but it's three characters shorter. It's based on the non-standard behavior that you can call RegExp objects as functions: /./g('string') is the same as /./g.exec('string'):
for(p=prompt(X=Y=0),R=/(N|S)?(.)? (\d+)/g;[,y,x,n]=R(p)||0;X+=x?x<'W'?n:-n:0)n/=x&&y?Math.SQRT2:1,Y+=y?y<'S'?n:-n:0;alert(X.toFixed(3)+', '+Y.toFixed(3))

Unfortunately, q=.707 fails the "NW 10" input due to rounding errors; I think you need "q=Math.SQRT1_2" which adds 8 chars. On the other hand, you can replace "(E|W)?" with "(.)?" since you have already established north/south/neither and the input is well-formed, saving 2 chars.

Thanks for the regex bit. As for the accuracy issue, I used SQRT2 instead and switched the multiplication to division.

Haskell, 199 characters
import Text.Printf
import Complex
i=0:+(1::Float)
e 'S'= -i
e d=i^mod(fromEnum d-1)4
g p(d:s:t)=g(p+(signum.sum.map e)d*(fst(reads s!!0):+0))t
g(x:+y)[]=printf"%.3f, %.3f"x y
main=interact$g 0.words

Scala (367, 332)
var (x,y,s)=(.0,.0,.7071);args.mkString(" ").split(",").foreach{m=>val a=m.trim.split(" ");var (n,u,v)=(a(1).toInt,.0,.0);a(0) match{case "N"=>v=1;case "S"=>v= -1;case "E"=>u=1;case "W"=>u= -1;case "NW"=>{u= -s;v=s};case "NE"=>{u=s;v=s};case "SW"=>{u= -s;v= -s};case "SE"=>{u=s;v= -s}};x += n*u;y += n*v};printf("%1.3f %1.3f\n",x,y)

Java (459) (445) (402) (382) (363) (352)
import java.util.*;class
M{public
static void main(String[]a){double
x=0,y=0;Scanner
s=new
Scanner(System.in);s.useDelimiter("\\W+");while(s.hasNext()){String
d=s.next();double
z=Math.sqrt(d.length());int
w=s.nextInt();y+=(d.contains("N")?w:d.contains("S")?-w:0)/z;x+=(d.contains("E")?w:d.contains("W")?-w:0)/z;}System.out.format("%1.3f %1.3f",x,y);}}

stdin input

PowerShell, 178
$input-split','|%{,@{N=0,1
NE=($s=.707106781186548),$s
E=1,0
SE=$s,-$s
S=0,-1
SW=-$s,-$s
W=-1,0
NW=-$s,$s}[($a=-split$_)[0]]*$a[1]}|%{$x+=$_[0]
$y+=$_[1]}
'{0:N3}, {1:N3}'-f$x,$y

This can probably lose up to 10 characters by reducing the accuracy of √2/2.

C (gcc), 155 152 bytes
-3 bytes thanks to ceilingcat
float x,y,l;D;main(d){for(;scanf("%s%f,",&d,&l)>0;y+=d^78?d^83?0:-l:l)D=d,l/=D>99?D/=256,d&=255,sqrt(2):1,x+=D^87?D^69?0:l:-l;printf("%.3f, %.3f",x,y);}

Try it online!

Groovy (215)
x=0.0;y=0.0;args.join(' ').split(', ').each{d=it.split(' ');c=d[0]==~/../?Math.sqrt(2):1;s=d[1] as int;a=['N':1,'S':-1,'E':1,'W':-1];m=d[0]=~/N|S/;y+=m?a[m[0]]*(s/c):0;m=d[0]=~/E|W/;x+=m?s/c*a[m[0]]:0};print "$x,$y"

reads input as program arguments. Example:
groovy golf.groovy NW 10, SW 10, W 10

Perl 5 -n, 122 bytes
s,(N|S)?(E|W)? (\d+),$d=$3/($1&$2?2**.5:1);$x+=$2&&$d*(-1)**($2gt F);$y+=$1&&$d*(-1)**($1gt O),ge;printf"%.3f, %.3f",$x,$y

Try it online!

J, 93 bytes
[:0j3&":@+.@(1#.".@>@{:*(0j1^2%~i.8){~<;._1@' E NE N NW W SW S SE'i.{.)@|:[:(<;._1);._1', ',]

Try it online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Implement QuickSort in BrainF***
As discussed in the Lounge room on Stack Overflow:

if you can't implement the Quicksort algorithm given en.wikipedia.org/wiki/Quicksort in any language you have minimal knowledge of, you might want to consider a different profession. @sbi

but SBI also noted that maybe BrainF*** was an exception.
So, here's the puzzle/challenge: implement QuickSort in BrainF***. The implementation must

be interpreted by this and/or by the interpreter(s) here (for large scripts)
implement the algorithm as described on Wikipedia - if possible as an in-place sort
sort the following list of integers: [0,4,6,4,2,3,9,2,3,6,5,3] and print the result

Searching around a bit I'm able to find one implementation, but it's 6kB (and compiled from Haskell).

@Peter actually the brainfuck implementation is 474.2 K inside the archive - which is a bit bigger than I expected (and too big for the on-line interpreter). Maybe I should change the target interpreter.. (but I would love to see something hand-written)

Actually, I got an error on that one: an underflow at byte 484109 (using the bcci interpreter)

@Ronald, yes, oops. Looked at the wrong component of the output of wc.

Quick question: can I assume that all the integers are only one digit? It would make things so much simpler. And if not, can I at least assume that they can be stored in a single byte (i.e. in the interval [0,255])? Can the number be negative?

Also, are we allowed to use procedural brainf***?

@Peter Yes, integers will be single-digit. No procedural BrainFuck though.

I bet I could do bubble sort instead and nobody looking at the code would know the difference...

something like >>,[>>,]<<[[-<+<]>[>[>>]<[.[-]<[[>>+<<-]<]>>]>]<<] (by Daniel B Cristofani) perhaps?

If the elements are only 0-9, counting sort would work pretty well also...

@Keith the idea is to really implement QuickSort, not just any sort that'll work... :-)

@Peter Of The Corn: We would discover a bubble-sort by the bad performance.

I can try to code a merge sort, but since the quick sort requires recursion, coding a quick sort is impossible for me. (I admire every brainfucker who implemented functions and recursions in BF - like C2BF)

I'm gonna do this. By hand. I have a data model that I think will work, but holy cow it may take a miracle.

BrainF* (697 bytes)
>>>>>>>>,[>,]<[[>>>+<<<-]>[<+>-]<+<]>[<<<<<<<<+>>>>>>>>-]<<<<<<<<[[>>+
>+>>+<<<<<-]>>[<<+>>-]<[>+>>+>>+<<<<<-]>[<+>-]>>>>[-<->]+<[>->+<<-[>>-
<<[-]]]>[<+>-]>[<<+>>-]<+<[->-<<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+>>>>]>[-<
<+[-[>+<-]<-[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<]<<[>>+<<-]>[>[>+>
>+<<<-]>[<+>-]>>>>>>[<+<+>>-]<[>+<-]<<<[>+>[<-]<[<]>>[<<+>[-]+>-]>-<<-
]>>[-]+<<<[->>+<<]>>[->-<<<<<[>+<-]<[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]
<<]>[[-]<<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-]>>>>>[-[>>[<<<+>>>-]<[>+<-]
<-[>+<-]>]<<[[>>+<<-]<]]>]<<<<<<-]>[>>>>>>+<<<<<<-]<<[[>>>>>>>+<<<<<<<
-]>[<+>-]<+<]<[[>>>>>>>>+<<<<<<<<-]>>[<+>-]<+<<]>+>[<-<<[>+<-]<[<]>[[<
+>-]>]>>>[<<<<+>>>>-]<<[<+>-]>>]<[-<<+>>]>>>]<<<<<<]>>>>>>>>>>>[.>]

Below is an annotated version.  In order to keep track of what was supposed to be happening while developing it, I used a comment notation that looks like this: |a|b=0|c=A0|@d|A0|A1|```|
|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)

The memory is laid out with a left-growing stack of partitions to process  on the left, a scratch space in the center, and the array being sorted to the right.   Array indexing is handled by moving a "data bus" containing the index and working space through the array.
So for instance a 3-wide bus of |i|data|0|A0|A1|A2, will become |A0|i-1|data|0|A1|A2 after shifting by one.  The partitioning is performed by keeping the bus between the high and low elements.
Here's the full version:
Get input
>>>>>>>> ,[>,]                      |A0|A1|```|An|@0|
Count items
<[ [>>>+<<<-]>[<+>-]<+ <]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
>[<<<<<<<<+>>>>>>>>-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
<<<<<<<<[
  Copy K1 to a&c via Z
  [>>+>+>>+<<<<<-]>>[<<+>>-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&d via Z
  <[>+>>+>>+<<<<<-]>[<+>-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  >>>>[-<->]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +<[>- >+<<-[>>-<<[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  >[<+>-]>[<<+>>-]<+<      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [->-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    <<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  >>>>]>[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    <<+[ -[>+<-]<-[>+<-]>>>>>>>>      (dec J as we move)
      [<<<<<<<<+>>>>>>>>-]<<<<<< ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    <<[>>+<<-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    >[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      >[>+>>+<<<-]>[<+>-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      >>>>>>[<+<+>>-]<[>+<-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g
      <<<[ >+>[<-]<[<]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g
        >>[<<+>[-]+>-]>-<<-]
      set g to 1; if d: set f
      >>[-]+<<< [->>+<<]
      If Aq LT Ap move Aq across Bus
      >>[->- <<<<<[>+<-] <[>+<-] >>>>>>>>
        [<<<<<<<<+>>>>>>>>-] <<]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq
      >[[-] <<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      >>>>>[-
        & While J shuttle right
        [>>[<<<+>>>-]<[>+<-]<-[>+<-]>] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        <<[ [>>+<<-] < ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]>]
    Either bus moved or last element swapped; reduce J in either case
    <<<<<<-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    >[>>>>>>+<<<<<<-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    <<[ [>>>>>>>+<<<<<<<-]>[<+>-]<+ <]
    <[ [>>>>>>>>+<<<<<<<<-]>>[<+>-]<+ <<] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    >+>[<-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      <<[>+<-] <[<]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p|
      shift left until return to 0 at K0;
      >[ [<+>-] >]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      >>>[<<<<+>>>>-]<<[<+>-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty)
    >>]<[- <<+>>]
  >>>]  End if !empty
<<<<<<] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
>>>>>>>>>>>[.>]

I was working on a similar solution but couldn't quite get it working. Awesome idea to do the partitioning that way. I was pulling out one element at a time and replacing it, and it got quite cumbersome quite quickly. I was also 1.5k into it, so you destroyed me on efficiency too.

Everything in BF gets cumbersome quite quickly :)  Even seemingly simple things like how to do an efficient if (i<j) {} else {} took several tries to get right.  And the edge cases are killers.  I don't know how many times I thought "just this one little thing left..." and then discovered a test case which caused another several hours work to handle.    I think I can reduce it by a few dozen characters, but I'm not sure I want to put in the effort.

One word: wow! I honestly didn't think it was humanly possible. I'm going to run a few inputs through it just to see how it works :-)

Epic! Just epic!

the only thing to say is "holy f*ck!"

What is the input format?

User input.  Asks for integers until it gets a 0. If you want to skip that step,  make the data look like the comment on the 4th line,  and start with the 5th.

brainfuck (178 bytes)
Even if brainfuck is cumbersome, it helps to work with the grain of the language. Ask yourself "Do I have to store this value explicitly in a cell?" You can often gain speed and concision by doing something more subtle. And when the value is an array index (or an arbitrary natural number), it may not fit in a cell. Of course, you could just accept that as a limit of your program. But designing your program to handle large values will often make it better in other ways.
As usual, my first working version was twice as long as it needed to be—392 bytes. Numerous modifications and two or three major rewrites produced this comparatively graceful 178-byte version. (Though amusingly a linear-time sort is only 40 bytes.)
>+>>>>>,[>+>>,]>+[--[+<<<-]<[[<+>-]<[<[->[<<<+>>>>+<-]<<[>>+>[->]<<[<]
<-]>]>>>+<[[-]<[>+<-]<]>[[>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]<<[<<<]>[>>[>>
>]<+<<[<<<]>-]]+<<<]]+[->>>]>>]>[brainfuck.org>>>]

The input values are spaced every three cells: for every (V)alue cell, there is a (L)abel cell (used for navigation) and one more cell for (S)cratch space. The overall layout of the array is
0 1 0 0 0 S V L S V L ... S V L 0 0 0 0 0 0 ...
Initially all the L cells are set to 1, to mark portions of the array that still need sorting. When we're done partitioning a subarray, we divide it into smaller subarrays by setting its pivot's L cell to 0, then locate the rightmost L cell that's still 1 and partition that subarray next. Oddly, this is all the bookkeeping we need to properly handle the recursive processing of subarrays. When all L cells have been zeroed, the whole array is sorted.
To partition a subarray, we pull its rightmost value into an S cell to act as pivot, and bring it (and the corresponding empty V cell) left, comparing it to each other value in the subarray and swapping as needed. At the end the pivot gets swapped back in, using the same swap code (which saves 50 bytes or so). During partitioning, two extra L cells are kept set to 0, to mark the two cells that may need to be swapped with each other; at the end of partitioning, the left 0 will fuse with the 0 to the left of the subarray, and the right 0 will end up marking its pivot. This process also leaves an extra 1 in the L cell to the right of the subarray; the main loop begins and ends at this cell.
>+>>>>>,[>+>>,]>+[                      set up; for each subarray:
    --[+<<<-]<[                         find the subarray; if it exists:
        [<+>-]<[                        S=pivot; while pivot is in S:
            <[                          if not at end of subarray
                ->[<<<+>>>>+<-]         move pivot left (and copy it)
                <<[>>+>[->]<<[<]<-]>    move value to S and compare with pivot
            ]>>>+<[[-]<[>+<-]<]>[       if pivot greater then set V=S; else:
                [>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]     swap smaller value into V
                <<[<<<]>[>>[>>>]<+<<[<<<]>-]        swap S into its place
            ]+<<<                       end else and set S=1 for return path
        ]                               subarray done (pivot was swapped in)
    ]+[->>>]>>                          end "if subarray exists"; go to right
]>[brainfuck.org>>>]                    done sorting whole array; output it

Awesome. It's so much cleaner when you work with BF's idioms, instead of trying to force it to act like a procedural language, like I did.

It is; but version 4 at 392 bytes was idiomatic brainfuck too. This is version 39 or so. :)

authors: Bob Jarvis - Слава Україні

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Airplane Navigation
You are tasked with planning a flying route for a local airplane delivery company.  You need to route an airplane from point A to point B.  You just can't start at A, point the airplane at B, and go, however, as the prevailing winds will blow you off course.  Instead you need to figure out which direction you should point the airplane so that it will fly directly to B, taking the wind into account.
input
7 floating-point numbers, encoding A_x, A_y, B_x, B_y, S, W_x, W_y.  These are the coordinates of your start and destination, the airspeed of your airplane, and the strength of the wind along the x and y axes (the direction the wind blows to, not from).
output
You should print the angle in degrees (rotating counterclockwise from the positive x axis) that the plane should point to reach B in a straight line.  Print GROUNDED if the wind is so strong as to make the trip impossible.
You may round to the nearest degree, and do so with any method you would like (up/down/nearest/...).
examples
inputs
0 0 10 0 100 0 -50
0 0 10 0 50 -55 0
3.3 9.1 -2.7 1.1 95.0 8.8 1.7

outputs
30
GROUNDED
229

Shortest code wins.

flat earth? or small fuel tank :-)

Wait... the earth isn't flat?

(Xb-Xa)(V·sinα+Wy)=(Yb-Ya)(V·cosα+Wx) ... Great.

@BlaXpirit: What if the two vectors are in opposite directions?

@BlaXpirit: Search for a sin x + b cos x = c on Google for some methods of solving your equation.  Direct solving may not be the best way to go here, though...

Actually the earth IS flat. Learn your geography.

J - 155 chars
h=:3 :0
'c w s'=.(([:j./[:-~/2 2$4{.]),([:j./5 6{]),4{])0".y
'T X'=.+.w*+c%|c
C=.-_1 o.X%s
>((s>|w)*.(-T)<s*2 o.C){'GROUNDED';360|<.360+(C+{:*.c)*180%o.1
)

For example:
   h '0 0 10 0 100 0 -50'
30
   h '0 0 10 0 50 -55 0'
GROUNDED
   h '3.3 9.1 -2.7 1.1 95.0 8.8 1.7'
229

Remove the 0". ahead of y if you don't mind J numeric syntax (_ for unary negation):
   h 0 0 10 0 100 0 _50
30

As I mentioned in my Perl answer, I'm only learning J, but liking its power.

Perl - 222 chars
use Math::Trig;($A,$a,$B,$b,$s,$W,$w)=split' ',<>;$c=atan2($b-$a,$B-$A);$A=atan2($w,$W);$S=sqrt($W*$W+$w*$w);$X=$S*sin($A-$c);$T=$S*cos($A-$c);$C=asin($X/$s);print((-$T>$s*cos($C))?"GROUNDED":(360+rad2deg($c-$C))%360,"\n")

Straighforward algorithm, and really only golfed by squeezing whitespace and variable name length, but I thought we needed a first answer here.  I've been learning some J for golfing; I suspect simply translating to J (or Ruby) will readily beat this.  Off to try those.
$X = crosswind component, $T = tailwind component.
We're grounded if the tailwind is actually a headwind (i.e., negative) and stronger than our airspeed.
Otherwise, $C is the wind correction angle that we subtract from our course $c to get our heading.  We need to turn far enough to balance the crosswind with the cross-track component of our velocity.

Perl: 193
Admittedly this is (mostly) DCharness's Perl code: but who doesn't like self-rewriting source?
use Math::Trig;$/=' ';@i=<>;$_='1=atan2(3-1,2-0);0=atan2(6,5);2=sqrt(6*6+5*5);5=2*sin(0-1);3=2*cos(0-1);6=asin(5/4);print-3>4*cos 6?GROUNDED:int rad2deg(1-6),"\n"';s/((?<!\w)\d)/\$i[$1]/g;eval

Also it will output degrees out of spec (i.e. <0 or >360), but did I mention self-rewriting source?


text:
File access redirection
This one ought to be a little more of a challenge than your normal "compute these numbers" or "print this sequence of text" puzzles:
Write a program that launches another program and when that other program tries to access a certain file the program causes it to open a different file.
Example:
The program launches Notepad.
Notepad attempts to open "orange.txt"
The program detects it and makes notepad open "green.txt" instead.
Rules:
WinAPI is allowed, but your code will stand out better if you can get this some other way.
You can use any language, but it must be able to run on either Windows or Linux

Since your post doesn't mention the winning criterion being shortest code length, I'm removing the [code-golf] tag. Feel free to readd the tag if you want to add such a criterion.

@Chris ok ty. i mostly wanted to see what kind of creative answers people would come up with, so i probably shouldn't have added that tag in the first place :)

C - 146
This is based on an answer to the StackOverflow question "how could I intercept linux sys calls?".
#define r(s)int s(int p,int f,int m)
#define c(s)r(s){return((r((*)))dlsym(-1,#s))(strcmp(p,getenv("OLD"))?p:getenv("NEW"),f,m);}
c(open)c(open64)

This has been tested on Linux/x86, and is unlikely to be portable.
Usage:
$ echo orange > orange.txt
$ echo green > green.txt
$ gcc -fPIC -shared -ldl intercept-open.c -o intercept-open.so
$ cat orange.txt
orange
$ LD_PRELOAD="./intercept-open.so" OLD="orange.txt" NEW="green.txt" cat orange.txt
green

This works with some programs (e.g. cat, less, wc, vim) but not others (e.g. nano, gedit).

gdb, 108 chars
star
b open if !(int)strcmp(((char**)$esp)[1],"orange.txt")
comm
set((char**)$esp)[1]="green.txt"
c
end
c
q

Save as the file redirect and run like this:
gdb -x redirect <program you want to redirect>

Works on x86 (linux at least, and probably Windows/Mac also).  Here's what the lines do:
star = start gets to the beginning of main (needed so open is defined for the next step).
b open if... = break if we're calling open on orange.txt
comm = command the code up to the next end is executed when the breakpoint fires.
set ((char*))... = replace the open argument with green.txt
c=continue
q=quit

It only works on x86-32. On x86-64 the first argument is stored in a register.


text:
Most optimized algorithm for incrementing squares
Write the "fastest" program to print an incrementing series of squares from a given input to a given input.
Example input:
-2
7

Example output:
4, 1, 0, 1, 4, 9, 16, 25, 36, 49

When using a "cryptic" language, please post the pseudocode, in addition to your program.
The entries will be judged on the most efficient algorithm.

Oh, come on. Code challenge to write a loop or comprehend a list. Whoop dee doo!

This was the dumbest question I've ever asked.

The tag says "code-challenge", but I don't see any challenge. Just some mathematics we studied when I was about 12.
import java.util.*;

public class IncSquares
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int min = in.nextInt();
        int max = in.nextInt();

        int sq = min * min;
        System.out.print(sq);
        while (min < max) {
            sq += (min << 1) + 1;
            min++;
            System.out.print(", " + sq);
        }
        System.out.println();
    }
}

+1 Technically, the fastest...the multiply will be optimized by the compiler to a single shift operation. so zero Multiplication (unlike the other answers)

Actually that's a good point - I was aiming to avoid multiplication, so I may as well be explicit about the shift.

If in doubt, the compiler probably knows best whether to represent a multiplication by 2 by a shift, a multiply or an add. The usual rule is to state your intent and let those optimize who do that for a living ;-)

@Joey, it gets complicated with Java. javac would emit an imul and leave it to the JIT to turn it into a shift.

Of course, that's what a JIT is for. It's still a compiler ;-)

@Peter, why don't you throw in a sq += (min << 1) | 1

@Peter, or maybe just calculate k = 2*min + 1 and do a k+=2 each time, wouldn't that be faster?

@st0le, depends how many registers there are.

Python
print ", ".join(`x*x` for x in range(int(raw_input()), int(raw_input())+1))

C
Since my usual language interpreter has a one-second startup time already, I chose not to use it here.
#include <stdio.h>

int main(void) {
    int start, end, i;
    scanf("%d\n%d", &start, &end);
    for (i = start; i <= end; i++) {
        printf("%d", i*i);
        if (i != end)
            printf(", ");
    }
    return 0;
}

Ruby
a,b=*$<.map(&:to_i)
p (a+1..b).reduce([a**2]){|m,x|m<<m[-1]+x+x-1;m}*?,

Jelly 12 bytes
+³’µ²
_N‘RÇ€

Explanation
+³’µ²
 ³’    -Decrement the first argument
+      -Sum it
   µ   -Groups the functions prior to this
    ²  -Square the result

_N‘RÇ€
_      -Subtract the two arguments
 N     -Negate the difference
  ‘    -Increment the difference
   R   -Generate Range from Difference
    Ç€ -Map range with above function

Try it online!

Jelly can do this in 2 bytes: r². Now I know this isn't code golf, but I do wonder how/why your program is more efficient than that.

(z + 1)^2 = z^2 + (2z + 1)

We already know z^2, and 2z is simply z<<1.
(z + 1)^2 = (z^2) + (z << 2 + 1)

Now just memorize this trick if you want to list squares in your head.
If you've got an arbitrary [two-digit] square (to do in your head), z^2, do this:
z^2 = (z-n)*(z+n) + n^2

Or:
23^2 = (23-3)*(23+3) + 3^2
23^2 = 20*26 + 9
23^2 = 520 + 9
23^2 = 529

Works even "faster" with larger numbers, relative to you doing 97*97 in your head. Have fun showing off.

So basically it's the same as mine but with added bugs?

@Peter Oh yes. :)

2z != z << 2. 2z = z << 1, always.


text:
1P5: Word Changer
This was written as part of the First Periodic Premier Programming Puzzle Push.
The Game
A starting and ending word of the same length are provided.  The objective of the game is to change one letter in the starting word to form a different valid word, repeating this step until the ending word is reached, using the fewest amount of steps.  For example, given the words TREE and FLED, the output would be:
TREE
FREE
FLEE
FLED
2

Specifications

The Wikipedia articles for the OWL or SOWPODS might be a useful starting point as far as word lists go.
The program should support two ways of selecting the start and end words:

Specified by the user via command-line, stdin, or whatever is suitable for your language of choice (just mention what you're doing).
Selecting 2 words at random from the file.

The starting and ending words, as well as all interim words should be the same length.
Each step should be printed out on its line.
The final line of your output should be the number of interim steps that were required to get between the starting and ending words.
If a match cannot be found between the starting and ending words, the output should consist of 3 lines:  the beginning word, the ending word, and the word OY.
Include the Big O Notation for your solution in your answer
Please include 10 unique starting and ending words pairs (with their output, of course) to show the steps your program produces.  (To save space, while your program should output these on individual lines, you can consolidate these into a single line for posting, replacing new lines with spaces and a comma between each run.

Goals / Winning Criteria

The fastest/best Big O solution producing the shortest interim steps after one week will win.
If a tie results from the Big O criteria, the shortest code will win.
If there is still a tie, the first solution to reach its fastest and shortest revision will win.

Tests / Sample Output
DIVE
DIME
DAME
NAME
2

PEACE
PLACE
PLATE
SLATE
2

HOUSE
HORSE
GORSE
GORGE
2

POLE
POSE
POST
PAST
FAST
3

Validation
I am working on a script that can be used to validate the output.
It will:

Ensure that each word is valid.
Ensure that each word is exactly 1 letter different from the previous word.

It will not:

Check that the shortest number of steps were used.

Once I've gotten that written, I will of course update this post. (:

Do the intermediate words have to be the same length as the start and end word?

@PeterTaylor, yes - I'll edit that clarification in.

I would have guessed that if only one letter can be changed per step that that is implied ;)

@Joey, often puzzles of this kind allow the change to be a deletion or insertion.

@Rebecca, does your dictionary not have GORSE? HOUSE HORSE GORSE GORGE is optimal.

Peter: I guess optimality will be judged from the word list.

@PeterTaylor, that's what I get for copying from a random website I found a few examples from. |:

It seems strange to me that performing 3 operations to get from HOUSE to GORGE is reported as 2.  I realize there are 2 intermediate words, so it does make sense, but # of operations would be more intuitive.

@Rebecca, can we assume that the alphabet is A-Z and that the longest words required are no longer than 13 letters? (I don't think it makes much difference to the complexity, which will be dominated by the number of edges in the graph in the worst case, but it allows some convenient hackery).

@Peter, according to sowpods wikipedia page there are ~15k words longer than 13 letters

I don't mean to be a know it all, but the puzzle actually has a Name, it was invented by Lewis Carroll  http://en.wikipedia.org/wiki/Word_ladder

You have an undecidable goal in the question: The fastest/best Big O solution producing the shortest interim steps after one week will win. Since you can't guarantee, that the fastest solution is meanwhile the one, which uses the fewest steps, you should provide a preference, if one solution uses fewer steps, but reaches the goal later.

I just want to confirm BAT and CAT will have zero steps, right?

@gnibbler, there are longer words but they're boring. There are 9116 14-letter words, so 41546170 pairs of 14-letter words, and only 2258 of those pairs have a solution. If you pick a random pair of 7-letter words the chances of a solution are about 1 in 7. With 8-letter words it's about 1 in 240, and then it gets worse. So I don't think it unreasonable to ask whether we can neglect words longer than a threshold.

If anyone wants a nasty test case with SOWPODS, try ENROBING LINCHETS.

@userunknown, using the shortest path possible is a basic part of the game.

@Rebecca: I see - shortest path is mandatory, to be a solution at all. Thanks.

This reduces itself to the Six Degrees of Wikipedia problem. While a heuristic can be developed based upon the Levenshtein Distance of the source and target, the most correct approach for single source, single destination appears to be a breadth-first search based upon the connectivity of all words in, for example, the Oxford English dictionary. Extra credit: because OED is small, run Floyd-Warshall to create a lookup table of all solutions when caching is desired. :)

Since length is listed as a criterion, here's the golfed version at 1681 characters (could probably still be improved by 10%):
import java.io.*;import java.util.*;public class W{public static void main(String[]
a)throws Exception{int n=a.length<1?5:a[0].length(),p,q;String f,t,l;S w=new S();Scanner
s=new Scanner(new
File("sowpods"));while(s.hasNext()){f=s.next();if(f.length()==n)w.add(f);}if(a.length<1){String[]x=w.toArray(new
String[0]);Random
r=new Random();q=x.length;p=r.nextInt(q);q=r.nextInt(q-1);f=x[p];t=x[p>q?q:q+1];}else{f=a[0];t=a[1];}H<S>
A=new H(),B=new H(),C=new H();for(String W:w){A.put(W,new
S());for(p=0;p<n;p++){char[]c=W.toCharArray();c[p]='.';l=new
String(c);A.get(W).add(l);S z=B.get(l);if(z==null)B.put(l,z=new
S());z.add(W);}}for(String W:A.keySet()){C.put(W,w=new S());for(String
L:A.get(W))for(String b:B.get(L))if(b!=W)w.add(b);}N m,o,ñ;H<N> N=new H();N.put(f,m=new
N(f,t));N.put(t,o=new N(t,t));m.k=0;N[]H=new
N[3];H[0]=m;p=H[0].h;while(0<1){if(H[0]==null){if(H[1]==H[2])break;H[0]=H[1];H[1]=H[2];H[2]=null;p++;continue;}if(p>=o.k-1)break;m=H[0];H[0]=m.x();if(H[0]==m)H[0]=null;for(String
v:C.get(m.s)){ñ=N.get(v);if(ñ==null)N.put(v,ñ=new N(v,t));if(m.k+1<ñ.k){if(ñ.k<ñ.I){q=ñ.k+ñ.h-p;N
Ñ=ñ.x();if(H[q]==ñ)H[q]=Ñ==ñ?null:Ñ;}ñ.b=m;ñ.k=m.k+1;q=ñ.k+ñ.h-p;if(H[q]==null)H[q]=ñ;else{ñ.n=H[q];ñ.p=ñ.n.p;ñ.n.p=ñ.p.n=ñ;}}}}if(o.b==null)System.out.println(f+"\n"+t+"\nOY");else{String[]P=new
String[o.k+2];P[o.k+1]=o.k-1+"";m=o;for(q=m.k;q>=0;q--){P[q]=m.s;m=m.b;}for(String
W:P)System.out.println(W);}}}class N{String s;int k,h,I=(1<<30)-1;N b,p,n;N(String S,String
d){s=S;for(k=0;k<d.length();k++)if(d.charAt(k)!=S.charAt(k))h++;k=I;p=n=this;}N
x(){N r=n;n.p=p;p.n=n;n=p=this;return r;}}class S extends HashSet<String>{}class H<V>extends
HashMap<String,V>{}

The ungolfed version, which uses package names and methods and doesn't give warnings or extend classes just to alias them, is:
package com.akshor.pjt33;

import java.io.*;
import java.util.*;

// WordLadder partially golfed and with reduced dependencies
//
// Variables used in complexity analysis:
// n is the word length
// V is the number of words (vertex count of the graph)
// E is the number of edges
// hash is the cost of a hash insert / lookup - I will assume it's constant, but without completely brushing it under the carpet
public class WordLadder2
{
    private Map<String, Set<String>> wordsToWords = new HashMap<String, Set<String>>();

    // Initialisation cost: O(V * n * (n + hash) + E * hash)
    private WordLadder2(Set<String> words)
    {
        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException
    {
        // Cost: O(filelength + num_words * hash)
        Map<Integer, Set<String>> wordsByLength = new HashMap<Integer, Set<String>>();
        BufferedReader br = new BufferedReader(new FileReader("sowpods"), 8192);
        String line;
        while ((line = br.readLine()) != null) add(wordsByLength, line.length(), line);

        if (args.length == 2) {
            String from = args[0].toUpperCase();
            String to = args[1].toUpperCase();
            new WordLadder2(wordsByLength.get(from.length())).findPath(from, to);
        }
        else {
            // 5-letter words are the most interesting.
            String[] _5 = wordsByLength.get(5).toArray(new String[0]);
            Random rnd = new Random();
            int f = rnd.nextInt(_5.length), g = rnd.nextInt(_5.length - 1);
            if (g >= f) g++;
            new WordLadder2(wordsByLength.get(5)).findPath(_5[f], _5[g]);
        }
    }

    // O(E * hash)
    private void findPath(String start, String dest) {
        Node startNode = new Node(start, dest);
        startNode.cost = 0; startNode.backpointer = startNode;

        Node endNode = new Node(dest, dest);

        // Node lookup
        Map<String, Node> nodes = new HashMap<String, Node>();
        nodes.put(start, startNode);
        nodes.put(dest, endNode);

        // Heap
        Node[] heap = new Node[3];
        heap[0] = startNode;
        int base = heap[0].heuristic;

        // O(E * hash)
        while (true) {
            if (heap[0] == null) {
                if (heap[1] == heap[2]) break;
                heap[0] = heap[1]; heap[1] = heap[2]; heap[2] = null; base++;
                continue;
            }

            // If the lowest cost isn't at least 1 less than the current cost for the destination,
            // it can't improve the best path to the destination.
            if (base >= endNode.cost - 1) break;

            // Get the cheapest node from the heap.
            Node v0 = heap[0];
            heap[0] = v0.remove();
            if (heap[0] == v0) heap[0] = null;

            // Relax the edges from v0.
            int g_v0 = v0.cost;
            // O(hash * #neighbours)
            for (String v1Str : wordsToWords.get(v0.key))
            {
                Node v1 = nodes.get(v1Str);
                if (v1 == null) {
                    v1 = new Node(v1Str, dest);
                    nodes.put(v1Str, v1);
                }

                // If it's an improvement, use it.
                if (g_v0 + 1 < v1.cost)
                {
                    // Update the heap.
                    if (v1.cost < Node.INFINITY)
                    {
                        int bucket = v1.cost + v1.heuristic - base;
                        Node t = v1.remove();
                        if (heap[bucket] == v1) heap[bucket] = t == v1 ? null : t;
                    }

                    // Next update the backpointer and the costs map.
                    v1.backpointer = v0;
                    v1.cost = g_v0 + 1;

                    int bucket = v1.cost + v1.heuristic - base;
                    if (heap[bucket] == null) {
                        heap[bucket] = v1;
                    }
                    else {
                        v1.next = heap[bucket];
                        v1.prev = v1.next.prev;
                        v1.next.prev = v1.prev.next = v1;
                    }
                }
            }
        }

        if (endNode.backpointer == null) {
            System.out.println(start);
            System.out.println(dest);
            System.out.println("OY");
        }
        else {
            String[] path = new String[endNode.cost + 1];
            Node t = endNode;
            for (int i = t.cost; i >= 0; i--) {
                path[i] = t.key;
                t = t.backpointer;
            }
            for (String str : path) System.out.println(str);
            System.out.println(path.length - 2);
        }
    }

    private static <K, V> void add(Map<K, Set<V>> map, K key, V value) {
        Set<V> vals = map.get(key);
        if (vals == null) map.put(key, vals = new HashSet<V>());
        vals.add(value);
    }

    private static class Node
    {
        public static int INFINITY = Integer.MAX_VALUE >> 1;

        public String key;
        public int cost;
        public int heuristic;
        public Node backpointer;

        public Node prev = this;
        public Node next = this;

        public Node(String key, String dest) {
            this.key = key;
            cost = INFINITY;
            for (int i = 0; i < dest.length(); i++) if (dest.charAt(i) != key.charAt(i)) heuristic++;
        }

        public Node remove() {
            Node rv = next;
            next.prev = prev;
            prev.next = next;
            next = prev = this;
            return rv;
        }
    }
}

As you can see, the running cost analysis is O(filelength + num_words * hash + V * n * (n + hash) + E * hash). If you'll accept my assumption that a hash table insertion/lookup is constant time, that's O(filelength + V n^2 + E). The particular statistics of the graphs in SOWPODS mean that O(V n^2) really dominates O(E) for most n.
Sample outputs:
IDOLA, IDOLS, IDYLS, ODYLS, ODALS, OVALS, OVELS, OVENS, EVENS, ETENS, STENS, SKENS, SKINS, SPINS, SPINE, 13
WICCA, PROSY, OY
BRINY, BRINS, TRINS, TAINS, TARNS, YARNS, YAWNS, YAWPS, YAPPS, 7
GALES, GASES, GASTS, GESTS, GESTE, GESSE, DESSE, 5
SURES, DURES, DUNES, DINES, DINGS, DINGY, 4
LICHT, LIGHT, BIGHT, BIGOT, BIGOS, BIROS, GIROS, GIRNS, GURNS, GUANS, GUANA, RUANA, 10
SARGE, SERGE, SERRE, SERRS, SEERS, DEERS, DYERS, OYERS, OVERS, OVELS, OVALS, ODALS, ODYLS, IDYLS, 12
KEIRS, SEIRS, SEERS, BEERS, BRERS, BRERE, BREME, CREME, CREPE, 7
This is one of the 6 pairs with the longest shortest path:
GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WALIEST, WANIEST, CANIEST, CANTEST, CONTEST, CONFEST, CONFESS, CONFERS, CONKERS, COOKERS, COOPERS, COPPERS, POPPERS, POPPETS, POPPITS, POPPIES, POPSIES, MOPSIES, MOUSIES, MOUSSES, POUSSES, PLUSSES, PLISSES, PRISSES, PRESSES, PREASES, UREASES, UNEASES, UNCASES, UNCASED, UNBASED, UNBATED, UNMATED, UNMETED, UNMEWED, ENMEWED, ENDEWED, INDEWED, INDEXED, INDEXES, INDENES, INDENTS, INCENTS, INCESTS, INFESTS, INFECTS, INJECTS, 56
And one of the worst-case soluble 8-letter pairs:
ENROBING, UNROBING, UNROPING, UNCOPING, UNCAPING, UNCAGING, ENCAGING, ENRAGING, ENRACING, ENLACING, UNLACING, UNLAYING, UPLAYING, SPLAYING, SPRAYING, STRAYING, STROYING, STROKING, STOOKING, STOOPING, STOMPING, STUMPING, SLUMPING, CLUMPING, CRUMPING, CRIMPING, CRISPING, CRISPINS, CRISPENS, CRISPERS, CRIMPERS, CRAMPERS, CLAMPERS, CLASPERS, CLASHERS, SLASHERS, SLATHERS, SLITHERS, SMITHERS, SMOTHERS, SOOTHERS, SOUTHERS, MOUTHERS, MOUCHERS, COUCHERS, COACHERS, POACHERS, POTCHERS, PUTCHERS, PUNCHERS, LUNCHERS, LYNCHERS, LYNCHETS, LINCHETS, 52
Now that I think I've got all the requirements of the question out of the way, my discussion.
For a CompSci the question obviously reduces to shortest path in a graph G whose vertices are words and whose edges connect words differing in one letter. Generating the graph efficiently isn't trivial - I actually have an idea I need to revisit to reduce the complexity to O(V n hash + E). The way I do it involves creating a graph which inserts extra vertices (corresponding to words with one wildcard character) and is homeomorphic to the graph in question. I did consider using that graph rather than reducing to G - and I suppose that from a golfing point of view I should have done - on the basis that a wildcard node with more than 3 edges reduces the number of edges in the graph, and the standard worst case running time of shortest path algorithms is O(V heap-op + E).
However, the first thing I did was to run some analyses of the graphs G for different word lengths, and I discovered that they're extremely sparse for words of 5 or more letters. The 5-letter graph has 12478 vertices and 40759 edges; adding link nodes makes the graph worse. By the time you're up to 8 letters there are fewer edges than nodes, and 3/7 of the words are "aloof". So I rejected that optimisation idea as not really helpful.
The idea which did prove helpful was to examine the heap. I can honestly say that I've implemented some moderately exotic heaps in the past, but none as exotic as this. I use A-star (since C provides no benefit given the heap I'm using) with the obvious heuristic of number of letters different from the target, and a bit of analysis shows that at any time there are no more than 3 different priorities in the heap. When I pop a node whose priority is (cost + heuristic) and look at its neighbours, there are three cases I'm considering: 1) neighbour's cost is cost+1; neighbour's heuristic is heuristic-1 (because the letter it changes becomes "correct"); 2) cost+1 and heuristic+0 (because the letter it changes goes from "wrong" to "still wrong"; 3) cost+1 and heuristic+1 (because the letter it changes goes from "correct" to "wrong"). So if I relax the neighbour I'm going to insert it at the same priority, priority+1, or priority+2. As a result I can use a 3-element array of linked lists for the heap.
I should add a note about my assumption that hash lookups are constant. Very well, you may say, but what about hash computations? The answer is that I'm amortising them away: java.lang.String caches its hashCode(), so the total time spent computing hashes is O(V n^2) (in generating the graph).
There is another change which affects the complexity, but the question of whether it is an optimisation or not depends on your assumptions about statistics. (IMO putting "the best Big O solution" as a criterion is a mistake because there isn't a best complexity, for a simple reason: there isn't a single variable). This change affects the graph generation step. In the code above, it's:
        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }

That's O(V * n * (n + hash) + E * hash). But the O(V * n^2) part comes from generating a new n-character string for each link and then computing its hashcode. This can be avoided with a helper class:
    private static class Link
    {
        private String str;
        private int hash;
        private int missingIdx;

        public Link(String str, int hash, int missingIdx) {
            this.str = str;
            this.hash = hash;
            this.missingIdx = missingIdx;
        }

        @Override
        public int hashCode() { return hash; }

        @Override
        public boolean equals(Object obj) {
            Link l = (Link)obj; // Unsafe, but I know the contexts where I'm using this class...
            if (this == l) return true; // Essential
            if (hash != l.hash || missingIdx != l.missingIdx) return false;
            for (int i = 0; i < str.length(); i++) {
                if (i != missingIdx && str.charAt(i) != l.str.charAt(i)) return false;
            }
            return true;
        }
    }

Then the first half of the graph generation becomes
        Map<String, Set<Link>> wordsToLinks = new HashMap<String, Set<Link>>();
        Map<Link, Set<String>> linksToWords = new HashMap<Link, Set<String>>();

        // Cost: O(V * n * hash)
        for (String word : words)
        {
            // apidoc: The hash code for a String object is computed as
            // s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
            // Cost: O(n * hash)
            int hashCode = word.hashCode();
            int pow = 1;
            for (int j = word.length() - 1; j >= 0; j--) {
                Link link = new Link(word, hashCode - word.charAt(j) * pow, j);
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
                pow *= 31;
            }
        }

By using the structure of the hashcode we can generate the links in O(V * n). However, this has a knock-on effect. Inherent in my assumption that hash lookups are constant time is an assumption that comparing objects for equality is cheap. However, the equality test of Link is O(n) in the worst case. The worst case is when we have a hash collision between two equal links generated from different words - i.e. it occurs O(E) times in the second half of the graph generation. Other than that, except in the unlikely event of a hash collision between non-equal links, we're good. So we've traded in O(V * n^2) for O(E * n * hash). See my previous point about statistics.

I believe 8192 is the default buffer size for BufferedReader (on SunVM)

@st0le, I omitted that parameter in the golfed version, and it doesn't harm in the ungolfed one.

Java
Complexity : ?? (I don't have a CompSci Degree, so i'd appreciate help in this matter.)
Input : Provide Pair of words  (more than 1 pair if you wish)  in the command line. If no Command line is specified 2 distinct random words are chosen.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class M {

    // for memoization
    private static Map<String, List<String>> memoEdits = new HashMap<String, List<String>>();
    private static Set<String> dict;

    private static List<String> edits(String word, Set<String> dict) {
        if(memoEdits.containsKey(word))
            return memoEdits.get(word);

        List<String> editsList = new LinkedList<String>();
        char[] letters = word.toCharArray();
        for(int i = 0; i < letters.length; i++) {
            char hold = letters[i];
            for(char ch = 'A'; ch <= 'Z'; ch++) {
                if(ch != hold) {
                    letters[i] = ch;
                    String nWord = new String(letters);
                    if(dict.contains(nWord)) {
                        editsList.add(nWord);
                    }
                }
            }
            letters[i] = hold;
        }
        memoEdits.put(word, editsList);
        return editsList;
    }

    private static Map<String, String> bfs(String wordFrom, String wordTo,
                                           Set<String> dict) {
        Set<String> visited = new HashSet<String>();
        List<String> queue = new LinkedList<String>();
        Map<String, String> pred = new HashMap<String, String>();
        queue.add(wordFrom);
        while(!queue.isEmpty()) {
            String word = queue.remove(0);
            if(word.equals(wordTo))
                break;

            for(String nWord: edits(word, dict)) {
                if(!visited.contains(nWord)) {
                    queue.add(nWord);
                    visited.add(nWord);
                    pred.put(nWord, word);
                }
            }
        }
        return pred;
    }

    public static void printPath(String wordTo, String wordFrom) {
        int c = 0;
        Map<String, String> pred = bfs(wordFrom, wordTo, dict);
        do {
            System.out.println(wordTo);
            c++;
            wordTo = pred.get(wordTo);
        }
        while(wordTo != null && !wordFrom.equals(wordTo));
        System.out.println(wordFrom);
        if(wordTo != null)
            System.out.println(c - 1);
        else
            System.out.println("OY");
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader scan = new BufferedReader(new FileReader(new File("c:\\332609\\dict.txt")),
                                                 40 * 1024);
        String line;
        dict = new HashSet<String>(); //the dictionary (1 word per line)
        while((line = scan.readLine()) != null) {
            dict.add(line);
        }
        scan.close();
        if(args.length == 0) { // No Command line Arguments? Pick 2 random
                               // words.
            Random r = new Random(System.currentTimeMillis());
            String[] words = dict.toArray(new String[dict.size()]);
            int x = r.nextInt(words.length), y = r.nextInt(words.length);
            while(x == y) //same word? that's not fun...
                y = r.nextInt(words.length);
            printPath(words[x], words[y]);
        }
        else { // Arguments provided, search for path pairwise
            for(int i = 0; i < args.length; i += 2) {
                if(i + 1 < args.length)
                    printPath(args[i], args[i + 1]);
            }
        }
    }
}

I've used Memoization, for quicker results. The Dictionary path is hardcoded.

@Joey, it used to be but not any more. It now has a static field which it increments each time and adds to System.nanoTime().

@Joey, aah, ok, but i'll leave it for now, don't want to increment my revisions :P

oh, btw, i'm at work and those scrabble websites are apparently blocked so i don't have access to the dictionaries...will generate those 10 unique words best by tomorrow morning. Cheers!

You could reduce the (computational) complexity by doing a bidirectional bfs, i.e. search from both sides and stop when you encounter a node visited from the other side.

@Nabb, will look into it, Actually, I already had this program in my archive just modified to suit the OP's requirements.

@Nabb, does that reduce the complexity? Surely the worst case  requires visiting all edges.

@Peter: Depends on how you look at it. It's possible to even construct cases where a bidirectional bfs is inferior (e.g. S--x--x--x--F--x). If we consider the number of edges from edge node to be a constant C, then I think we expect about C^H(S,F) for single direction bfs and 2*C^(H(S,F)/2) for bidirectional, with H(S,F) being the hamming distance between S and F.

@Nabb, the worst case is when there is no solution. I agree that bidirectional search done well can improve the average running time for some graphs (probably up to 5-letter words, given the actual statistics).

c on unix
Using dijkstra algorithm.
A large fraction of the code is a costume n-ary tree implementation, which serves to hold

The wordlist (thus minimizing the number of times the input file is read (twice for no arguments, once for other cases) on the assumption that file IO is slow
The partial trees as we build them.
The final path.

Anyone interested in seeing how it works should probably read findPath, process, and processOne (and their associated comments). And maybe buildPath and buildPartialPath. The rest is bookkeeping and scaffolding. Several routines used during testing and development but not in the "production" version have been left in place.
I'm using /usr/share/dict/words on my Mac OS 10.5 box, which has so many long, esoteric entries that letting it run completely at random generates a lot of OYs.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getline.h>
#include <time.h>
#include <unistd.h>
#include <ctype.h>

const char*wordfile="/usr/share/dict/words";
/* const char*wordfile="./testwords.txt"; */
const long double RANDOM_MAX = (2LL<<31)-1;

typedef struct node_t {
  char*word;
  struct node_t*kids;
  struct node_t*next;
} node;

/* Return a pointer to a newly allocated node. If word is non-NULL,
 * call setWordNode;
 */
node*newNode(char*word){
  node*n=malloc(sizeof(node));
  n->word=NULL;
  n->kids=NULL;
  n->next=NULL;
  if (word) n->word = strdup(word);
  return n;
}
/* We can use the "next" links to treat these as a simple linked list,
 * and further can make it a stack or queue by
 *
 * * pop()/deQueu() from the head
 * * push() onto the head
 * * enQueue at the back
 */
void push(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  n->next = (*list);
  (*list) = n;
}
void enQueue(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  if ( *list==NULL ) {
    *list=n;
  } else {
    enQueue(n,&((*list)->next));
  }
}
node*pop(node**list){
  node*temp=NULL;
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  temp = *list;
  if (temp != NULL) {
    (*list) = temp->next;
    temp->next=NULL;
  }
  return temp;
}
node*deQueue(node**list){ /* Alias for pop */
  return pop(list);
}

/* return a pointer to a node in tree matching word or NULL if none */
node* isInTree(char*word, node*tree){
  node*isInNext=NULL;
  node*isInKids=NULL;
  if (tree==NULL || word==NULL) return NULL;
  if (tree->word && (0 == strcasecmp(word,tree->word))) return tree;
  /* prefer to find the target at shallow levels so check the siblings
     before the kids */
  if (tree->next && (isInNext=isInTree(word,tree->next))) return isInNext;
  if (tree->kids && (isInKids=isInTree(word,tree->kids))) return isInKids;
  return NULL;
}

node* freeTree(node*t){
  if (t==NULL) return NULL;
  if (t->word) {free(t->word); t->word=NULL;}
  if (t->next) t->next=freeTree(t->next);
  if (t->kids) t->kids=freeTree(t->kids);
  free(t);
  return NULL;
}

void printTree(node*t, int indent){
  int i;
  if (t==NULL) return;
  for (i=0; i<indent; i++) printf("\t"); printf("%s\n",t->word);
  printTree(t->kids,indent+1);
  printTree(t->next,indent);
}

/* count the letters of difference between two strings */
int countDiff(const char*w1, const char*w2){
  int count=0;
  if (w1==NULL || w2==NULL) return -1;
  while ( (*w1)!='\0' && (*w2)!='\0' ) {
    if ( (*w1)!=(*w2) ) count++;
    w1++;
    w2++;
  }
  return count;
}

node*buildPartialPath(char*stop, node*tree){
  node*list=NULL;
  while ( (tree != NULL) &&
      (tree->word != NULL) &&
      (0 != strcasecmp(tree->word,stop)) ) {
    node*kid=tree->kids;
    node*newN = newNode(tree->word);
    push(newN,&list);
    newN=NULL;
    /* walk over all all kids not leading to stop */
    while ( kid &&
        (strcasecmp(kid->word,stop)!=0) &&
        !isInTree(stop,kid->kids) ) {
      kid=kid->next;
    }
    if (kid==NULL) {
      /* Assuming a preconditions where isInTree(stop,tree), we should
       * not be able to get here...
       */
      fprintf(stderr,"Unpossible!\n");
      exit(7);
    }
    /* Here we've found a node that either *is* the target or leads to it */
    if (strcasecmp(stop,kid->word) == 0) {
      break;
    }
    tree = kid;
  }
  return list;
}
/* build a node list path
 *
 * We can walk down each tree, identfying nodes as we go
 */
node*buildPath(char*pivot,node*frontTree,node*backTree){
  node*front=buildPartialPath(pivot,frontTree);
  node*back=buildPartialPath(pivot,backTree);
  /* weld them together with pivot in between
  *
  * The front list is in reverse order, the back list in order
  */
  node*thePath=NULL;
  while (front != NULL) {
    node*n=pop(&front);
    push(n,&thePath);
  }
  if (pivot != NULL) {
    node*n=newNode(pivot);
    enQueue(n,&thePath);
  }
  while (back != NULL) {
    node*n=pop(&back);
    enQueue(n,&thePath);
  }
  return thePath;
}

/* Add new child nodes to the single node in ts named by word. Also
 * queue these new word in q
 *
 * Find node N matching word in ts
 * For tword in wordList
 *    if (tword is one change from word) AND (tword not in ts)
 *        add tword to N.kids
 *        add tword to q
 *        if tword in to
 *           return tword
 * return NULL
 */
char* processOne(char *word, node**q, node**ts, node**to, node*wordList){
  if ( word==NULL || q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"ProcessOne called with NULL argument! Exiting.\n");
    exit(9);
  }
  char*result=NULL;
  /* There should be a node in ts matching the leading node of q, find it */
  node*here = isInTree(word,*ts);
  /* Now test each word in the list as a possible child of HERE */
  while (wordList != NULL) {
    char *tword=wordList->word;
    if ((1==countDiff(word,tword)) && !isInTree(tword,*ts)) {
      /* Queue this up as a child AND for further processing */
      node*newN=newNode(tword);
      enQueue(newN,&(here->kids));
      newN=newNode(tword);
      enQueue(newN,q);
      /* This might be our pivot */
      if ( isInTree(tword,*to) ) {
    /* we have found a node that is in both trees */
    result=strdup(tword);
    return result;
      }
    }
    wordList=wordList->next;
  }
  return result;
}

/* Add new child nodes to ts for all the words in q */
char* process(node**q, node**ts, node**to, node*wordList){
  node*tq=NULL;
  char*pivot=NULL;
  if ( q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"Process called with NULL argument! Exiting.\n");
    exit(9);
  }
  while (*q && (pivot=processOne((*q)->word,&tq,ts,to,wordList))==NULL) {
    freeTree(deQueue(q));
  }
  freeTree(*q);
  *q=tq;
  return pivot;
}

/* Find a path between w1 and w2 using wordList by dijkstra's
 * algorithm
 *
 * Use a breadth-first extensions of the trees alternating between
 * trees.
 */
node* findPath(char*w1, char*w2, node*wordList){
  node*thePath=NULL; /* our resulting path */
  char*pivot=NULL; /* The node we find that matches */
  /* trees of existing nodes */
  node*t1=newNode(w1);
  node*t2=newNode(w2);
  /* queues of nodes to work on */
  node*q1=newNode(w1);
  node*q2=newNode(w2);

  /* work each queue all the way through alternating until a word is
     found in both lists */
  while( (q1!=NULL) && ((pivot = process(&q1,&t1,&t2,wordList)) == NULL) &&
     (q2!=NULL) && ((pivot = process(&q2,&t2,&t1,wordList)) == NULL) )
    /* no loop body */ ;

  /* one way or another we are done with the queues here */
  q1=freeTree(q1);
  q2=freeTree(q2);
  /* now construct the path */
  if (pivot!=NULL) thePath=buildPath(pivot,t1,t2);
  /* clean up after ourselves */
  t1=freeTree(t1);
  t2=freeTree(t2);

  return thePath;
}

/* Convert a non-const string to UPPERCASE in place */
void upcase(char *s){
  while (s && *s) {
    *s = toupper(*s);
    s++;
  }
}

/* Walks the input file stuffing lines of the given length into a list */
node*getListWithLength(const char*fname, int len){
  int l=-1;
  size_t n=0;
  node*list=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) == len) {
      node*newN = newNode(line);
      upcase(newN->word);
      push(newN,&list);
    }
  }
  fclose(f);
  return list;
}

/* Assumes that filename points to a file containing exactly one
 * word per line with no other whitespace.
 * It will return a randomly selected word from filename.
 *
 * If veto is non-NULL, only non-matching words of the same length
 * wll be considered.
 */
char*getRandomWordFile(const char*fname, const char*veto){
  int l=-1, count=1;
  size_t n=0;
  char *word=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) < 2) continue; /* Single letters are too easy! */
    if ( (veto==NULL) || /* no veto means chose from all */
     (
      ( strlen(line) == strlen(veto) )  && /* veto means match length */
      ( 0 != strcasecmp(veto,line) )       /* but don't match word */
       ) ) {
      /* This word is worthy of consideration. Select it with random
         chance (1/count) then increment count */
      if ( (word==NULL) || (random() < RANDOM_MAX/count) ) {
    if (word) free(word);
    word=strdup(line);
      }
      count++;
    }
  }
  fclose(f);
  upcase(word);
  return word;
}

void usage(int argc, char**argv){
  fprintf(stderr,"%s [ <startWord> [ <endWord> ]]:\n\n",argv[0]);
  fprintf(stderr,
      "\tFind the shortest transformation from one word to another\n");
  fprintf(stderr,
      "\tchanging only one letter at a time and always maintaining a\n");
  fprintf(stderr,
      "\tword that exists in the word file.\n\n");
  fprintf(stderr,
      "\tIf startWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tIf endWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tconsistent with the length of startWord\n");
  exit(2);
}

int main(int argc, char**argv){
  char *startWord=NULL;
  char *endWord=NULL;

  /* intialize OS services */
  srandom(time(0)+getpid());
  /* process command line */
  switch (argc) {
  case 3:
    endWord = strdup(argv[2]);
    upcase(endWord);
  case 2:
    startWord = strdup(argv[1]);
    upcase(startWord);
  case 1:
    if (NULL==startWord) startWord = getRandomWordFile(wordfile,NULL);
    if (NULL==endWord)   endWord   = getRandomWordFile(wordfile,startWord);
    break;
  default:
    usage(argc,argv);
    break;
  }
  /* need to check this in case the user screwed up */
  if ( !startWord || ! endWord || strlen(startWord) != strlen(endWord) ) {
    fprintf(stderr,"Words '%s' and '%s' are not the same length! Exiting\n",
        startWord,endWord);
    exit(1);
  }
  /* Get a list of all the words having the right length */
  node*wordList=getListWithLength(wordfile,strlen(startWord));
  /* Launch into the path finder*/
  node *theList=findPath(startWord,endWord,wordList);
  /* Print the resulting path */
  if (theList) {
    int count=-2;
    while (theList) {
      printf("%s\n",theList->word);
      theList=theList->next;
      count++;
    }
    printf("%d\n",count);
  } else {
    /* No path found case */
    printf("%s %s OY\n",startWord,endWord);
  }
  return 0;
}

Some output:
$ ./changeword dive name
DIVE
DIME
DAME
NAME
2
$ ./changeword house gorge
HOUSE
HORSE
GORSE
GORGE
2
$ ./changeword stop read
STOP
STEP
SEEP
SEED
REED
READ
4
$ ./changeword peace slate
PEACE
PLACE
PLATE
SLATE
2
$ ./changeword pole fast
POLE
POSE
POST
PAST
FAST
3
$ ./changeword
QUINTIPED LINEARITY OY
$ ./changeword sneaky
SNEAKY WAXILY OY
$ ./changeword TRICKY
TRICKY
PRICKY
PRINKY
PRANKY
TRANKY
TWANKY
SWANKY
SWANNY
SHANNY
SHANTY
SCANTY
SCATTY
SCOTTY
SPOTTY
SPOUTY
STOUTY
STOUTH
STOUSH
SLOUSH
SLOOSH
SWOOSH
19
$ ./changeword router outlet
ROUTER
ROTTER
RUTTER
RUTHER
OUTHER
OUTLER
OUTLET
5
$ ./changeword
IDIOM
IDISM
IDIST
ODIST
OVIST
OVEST
OVERT
AVERT
APERT
APART
SPART
SPARY
SEARY
DEARY
DECRY
DECAY
DECAN
DEDAN
SEDAN
17

Complexity analysis is non-trivial. The search is a two-sided, iterative deepening.

For each node examined I walk the entire word list (though limited to words of the right length). Call the length of the list W.
The minimum number of steps is S_min = (<number of different letter>-1) because if we are only one letter apart we score the change at 0 intermediate steps. The maximum is hard to quantify see the TRICKY--SWOOSH run above. Each half of the tree will be S/2-1 to S/2
I have not done an analysis of the branching behavior of the tree, but call it B.

So the minimum number of operations is around  2 * (S/2)^B * W, not really good.

Maybe this is naive of me, but I don't see anything in your design or implementation that requires edge weights. While Dijkstra's indeed works for unweighted graphs (edge weight is invariably "1"), wouldn't a simple breadth-first search apply here to improve your bounds to O(|V|+|E|) instead of O(|E|+|V| log |V|)?


text:
The Prime Grid Game
I had fun solving this, so I offer this golf challenge.
The objective of this golf is to find the largest prime number that can be constructed using the given instructions.
You should accept 3x3 grid of single digits as input. (It's up to you how you want to do that, but specify that in your program.)
You can move along the grid orthogonally (left, right, up or down), and as you move, you keep appending the digits you walk across.
E.g.
1 2 3
3 5 6
1 8 9

Say we start at 1,
we can form the number 1236589 but cannot form 15.
You have to evaluate every starting position.
If a prime cannot be found, print -1, else print the prime itself.
Shortest code wins, make sure it runs within 10 secs.
Have Fun!
Edit: Use one position exactly once, in the entire number.
Here's a test case
Input:
1 2 3
4 5 6
7 8 9

Output:
69854123

I presume we can't repeat positions?

No, You cannot. Otherwise it'll be an infinite search :) Sorry, forgot to mention that. Editing.

I can haz test cases?

@MtnViewMark, i haz postd testcase, and confirmed your answer aswell. Cheers! :)

Haskell, 239 characters
p=2:q[3..]
q=filter(#p)
n#(x:y)=n==x||n`mod`x/=0&&(n`div`x<x||n#y)
(n§m)q=n:maybe[](\i->[q-4,q-1,q+1,q+4]>>=(n*10+i)§filter(/=(q,i))m)(lookup q m)
i=[0,1,2,4,5,6,8,9,10]
main=getLine>>=print.maximum.(-1:).q.(i>>=).(0§).zip i.map read.words

Input is given as a single line of nine numbers:
$> echo 1 2 3  3 5 6  1 8 9 | runhaskell 2485-PrimeGrid.hs
81356321
$> echo 1 2 3  4 5 6  7 8 9 | runhaskell 2485-PrimeGrid.hs
69854123
$> echo 1 1 1  1 1 1  1 1 1 | runhaskell 2485-PrimeGrid.hs
11
$> echo 2 2 2  2 2 2  2 2 2 | runhaskell 2485-PrimeGrid.hs
2
$> echo 4 4 4  4 4 4  4 4 4 | runhaskell 2485-PrimeGrid.hs
-1

I can confirm your answer :)

Python, 286 274 chars
I=lambda:raw_input().split()
m=['']
G=m*4+I()+m+I()+m+I()+m*4
def B(s,p):
 d=G[p]
 if''==d:return-1
 G[p]='';s+=d;n=int(s)
 r=max(n if n>1and all(n%i for i in range(2,n**.5+1))else-1,B(s,p-4),B(s,p+4),B(s,p-1),B(s,p+1))
 G[p]=d;return r
print max(B('',i)for i in range(15))

This does give a deprecation warning for the float argument to range.  Ignore it, or spend 5 more chars to wrap int() around it.


text:
Find sum of odd numbers
Write a program to find the sum of all odd numbers between a given range [a,b]. Input consists of a single line containing two integers a and b separated by a space. 0 ≤ a,b ≤ 1,000,000,000,000. Your program should not take more than 10 secs.
Sample Inputs
1 5
4 8
1 8
0 5

Sample Outputs
9
12
16
9

sigh ... ... ...

I've closed this as a duplicate of Sum of primes between given range. The fundamental challenge is the same (generate a range from $a$ to $b$, filter elements that meet a criteria, then sum), and, in my opinion, the two are the same task

@Dudecoinheringaahing I strongly disagree. Brute force is not allowed in this challenge because of the time limit.

Ruby, 43 characters
p eval"-(%d/2)**2+((%d+1)/2)**2"%gets.split

Example for largest input:
$ time echo "1 10000000000000000" | ruby oddsum.rb
25000000000000000000000000000000

real    0m0.006s
user    0m0.000s
sys     0m0.000s

You misspelled evil there. Otherwise, nice work!

You can replace (%d+1) with just -%d to save 3 bytes

Funciton
Not a language particularly suitable for golfing, but I gave it my best shot to cram everything together in best code-golf tradition. Near the end I was making rearrangements that gave net savings of a single character until I could find no more ways to improve it :)
This is 398 characters (or 786 bytes in UTF-16). I challenge anyone to find a way to make it smaller :)
 ┌───┐    ┌──────────┐
╔╧╗┌─┴╖┌─╖│╔═╗┌──╖┌─╖│
║ ║│>>╟┤_╟┘║1╟┤>>╟┤♯╟┘
╚═╝╘╤═╝╘═╝ ╚═╝╘═╤╝╘═╝
    └┐ ┌─┐ ╔══╗┌┴───┐
╔══╗┌┴╖│┌┴╖║32║│ ┌─╖│
║21╟┤×╟┘│♯║╚╤═╝└─┤×╟┘
╚══╝╘═╝ ╘╤╝┌┘ ┌─┐╘╤╝
┌──────┬─┘┌┘ ┌┴╖└─┘
│╔═╗  ┌┴╖┌┘  │−╟┐┌───────╖
│║0║ ┌┤ʘ╟┘┌─┐╘╤╝└┤int→str╟
│╚╤╝ │╘═╝┌┴╖└─┘  ╘═══════╝
│┌┴╖╔╧╗┌─┤×╟┐
└┤ʃ╟╢ ║│ ╘═╝│
 ╘╤╝╚═╝└┬───┘
  │┌─╖┌─┴╖╔═╗╓─╖┌───────╖
  └┤_╟┤>>╟╢1║║_╟┤str→int╟
   ╘═╝╘══╝╚═╝╙─╜╘═══════╝

What about BOCU-1 or SCSU? Wouldn't those make it quite a bit smaller?

@Joey: Certainly not the character count.

Ah, but the byte count ;-). Ok, I only now understood how you meant that.

Windows PowerShell, 84 61 55
$a,$b=-split"$input+1"|iex|%{($_-band-2)/2}
$b*$b-$a*$a

O(1) runtime.

Golfscript - 12 chars
~)2/2?\2/2?-

can be done in 11 chars if the order of the inputs is reversed
~)]{2/2?}/-

Python, 32 bytes
As unnamed lambda function:
lambda a,b:((b+1)/2)**2-(a/2)**2

Did some math to get a direct formula. Proof will follow.

Vyxal s, 7 bytes
›"2ḭ²Ḃ¯

Try it Online!
STACK = [4,8]
›               Increment, [5, 8]
"               Pair  [[5, 8]]
2              Push 2 [[5, 8], 2]
ḭ               Integer Division [[2, 4]]
²               Square [[4, 16]]
Ḃ              Reverse [[16, 4]]
¯               Deltas    [[12]]
                 Implicit Sum [12]

Does not work within the time limit.

@Bubbler edited

this doesn't meet the problems I/O requirements (which are overly strict but you still must follow them)

I see that Vyxal has commands for split on spaces, convert string to int, and mapping functions, so I'm sure there's some way to combine those to fulfill the requirements


text:
Rational Counting Function
Create a function that takes a natural number (starting from 0 inclusive), and returns a pair of positive integers, which are the numerator and denominator respectively.
Use the diagonal traversal. Previous-counted numbers must be skipped. (you can memorize the set of skipped values)
Diagram:

Red are skipped values
Values:

f(0) = 1, 1
f(1) = 2, 1
f(2) = 1, 2
f(3) = 1, 3
f(4) = 3, 1 (notice the skip)
f(5) = 4, 1
f(6) = 3, 2
f(7) = 2, 3
f(8) = 1, 4
f(9) = 1, 5
f(10) = 5, 1 (notice the skip)

You may use the Rational data structure and their operations if they exist.
Shortest code wins.

The number of counted rational numbers in each diagonal is the totient function of that diagonal's common sum.

I know this challenge is old, but there exists a shorter answer than the accepted one, so you might want to re-accept.

J, 41 36 characters
Takes an integers and returns a vector comprising two integers. My first solution that is neither entirely tacit nor entirely explicit.
{3 :'~.;<`(<@|.)/.(,%+.)"0/~1+i.1+y'

Here is the solution with spaces inserted where appropriate:
{ 3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

An explanation:

x (, % +.) y–a vector of length 2 representing the fraction with numerator x and denominator y reduced to the smallest denominator
1 + i. 1 + y–a vector of integers from 1 to y + 1
(, % +.)"0/~ 1 + i. 1 + y–a matrix of all reduced fractions with unreduced denominator and numerator in the range from 1 to y + 1.
<`(<@|.)/. y–an array of the oblique diagonals of matrix y, each other diagonal flipped
~. ; y–an array of diagonals collapsed into a vector of elements with duplicates removed
x { y–the item at position x in y
(u v) y–the same as y u v y. In this particular use case, u is { and v is 3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

30 bytes

Haskell, 78 characters
q(r,f)=[(r-b,b)|b<-f[1..r-1],r`gcd`b==1]
d=reverse:id:d
f=((zip[2..]d>>=q)!!)

Sample run:
> map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
> f 100
(17,1)
> f 1000
(3,55)

Edit: (100 → 87) silly me, just testing the gcd is enough!
Edit: (87 → 85) clever trick with cycle and functions to alternate row order
Edit: (85 → 82) replace cycle with the hand-built infinite list d
Edit: (82 → 78) applied gcd identity as suggested by Matías

By definition, gcd (r-b) b == gcd r b and you can shave off four more characters.

Python, 144 chars
def F(i):
 r,d,z=[1],1,[]
 while z[:i]==z:z+=[(x,y)for x,y in zip(r[::d],r[::-d])if all(x%j+y%j for j in r[1:])];d=-d;r+=[r[-1]+1]
 return z[i]

Ruby 1.9, 109 106
F=->n{x=y=d=1
e=0
n.times{(x+=d).gcd(y+=e)>1&&redo
x<2?d<0?d=0:(d,e=1,-1):y<2?e<0?e=0:(d,e=-1,1):0}
[x,y]}

OCaml + Batteries, 182 168 characters
This is what would be natural in Haskell but is only barely possible in OCaml:
open LazyList
let rec r(i,j)=lazy(let a,b=if(i+j)mod 2=0then i,j else j,i in
Cons((a,b),filter(fun(c,d)->a*d<>c*b)(r(if j=1 then 1,i+1else i+1,j-1))))
let f=nth(r(1,1))

Edit: The diagonal is unnecessary

Perl 6, 75 bytes
{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique[$_]}

Test it
This basically generates the entire sequence of rational values, only stopping once the indexed value is generated.
(Based on my golf to another challenge.)
Expanded:
{  # bare block lambda with implicit parameter $_

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            …
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            …
            1      # finish at one
          )

        }
        … * # never stop generating values
      )

    Z/   # zip using &infix:« /  » (generates Rats)

      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            …
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            …
            1
          )
        }
        … * # never stop generating values
      )

  ).unique                # get only the unique values
  .[ $_ ]                 # index into the sequence
}

({1…($+=2)…1}…*) generates the infinite sequence of numerators (|(…) is used above to flatten)
(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)
…

(1,{1…(($||=1)+=2)…1}…*) generates the infinite sequence of denominators
1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
…


text:
1P5: Earthquake!
USGS's seismometers have just detected a major earthquake! Emergency response teams need a quick estimate of the number of people affected. Write a program to compute this estimate.
Your program receives 2 inputs. The first is the details of the earthquake itself. The earthquake modeled as a line segment along which the earth ruptured, along with the critical distance from the fault within which damage could be expected. The second input is a list of the location and population of cities in the area. Your program should compute the number of people living in the affected area, that is the sum of the population of all cities within the critical distance of the fault segment.
Input
First a line describing the earthquake, containing the x,y coordinates of the start and end points of the fault, plus the critical distance. The format is A_x A_y B_x B_y D. For example:
3.0 3.0 7.0 4.0 2.5

encodes the fault extending from (3.0,3.0) to (7.0,4.0) and a critical distance of 2.5.
Second, one line per city in the area, containing the x,y coordinates of the city and its population. For example:
1.0 1.0 2500
5.0 7.0 8000
3.0 4.0 7500
9.0 6.0 3000
4.0 2.0 1000

Output
The number of people living in the affected area. For the above example only the third and fifth cities are in the danger area, so the output would be
8500

Shortest code wins.
Example 2
0.0 0.0 10.0 0.0 5.0
5.0 4.0 10000
5.0 -4.0 1000
5.0 6.0 100
11.0 2.0 10
-4.0 4.0 1

generates
11010

Does the output have to be an integer, or would 8500.0 be ok for the example? And could we maybe get some more testcases?

Also, what is the type of the input? As in, how many decimal places could it have? This is relevant for languages which don't have floating point.

The output needs to be an integer, can't have fractional people.  Let's say the input is at most 2 decimal places.

Does the critical area extend in a semicircle around the endpoints, or is it just a rectangle?

@Peter: It ends in semicircles, so the whole thing is lozenge-shaped.

Ruby, 171 152 155 153
u,v,a,b,d=gets.split.map &:to_f
a-=u;b-=v
p eval$<.map{|l|"(x=%f-u;t=(a*x+b*y=%f-v)/(a*a+b*b);d*d<(x-a*t=t<0?0:t>1?1:t)**2+(y-t*b)**2?0:%d)"%l.split}*'+'

This is my first ruby submission and my first code-golf at all. Straight forward implementation of the task. Please give me some hints how to improve (there must be a shorter way to read floats...).

You can save a few characters by eliminating the parentheses around map and eval, and inlining t. And since you're already eval'ing, you can use format-strings instead of .to_f, so the last block can be shortened to p eval$<.map{|l|"(x=%f-u;t=(x*a+b*y=%f-v)/(a**2+b**2);d*d<(x-t=t<0?0:t>1?1:t)**2+(y-t*b)**2?0:%d)"%l.split}*'+'

@Ventero thank you. Inlining t again saves another two.

I can't get this to work on example #2 (just added), it errors with undefined method > for nil:NilClass (NoMethodError)

@Keith should work now on your input as well.

C# - 743 715
namespace System{using Linq;using m=Math;class P{public float X,Y;}class E{static void Main(){Func<string,float>p=s=>float.Parse(s);Func<P,P,double>d=(a,b)=>{return a.X*b.X+a.Y*b.Y;},c=(a,b)=>{return a.X*b.Y-a.Y*b.X;};Func<P,P,P>u=(a,b)=>{return new P{X=a.X-b.X,Y=a.Y-b.Y};};Func<P,P,P,double>g=(A,B,C)=>{return d(u(C,B),u(B,A))>0?m.Sqrt(d(u(B,C),u(B,C))):d(u(C,A),u(A,B))>0?m.Sqrt(d(u(A,C),u(A,C))):m.Abs(c(u(B,A),u(C,A))/m.Sqrt(d(u(B,A),u(B,A))));};var n=IO.File.ReadAllLines("i");var i=n[0].Split();var q=new{A=new P{X=p(i[0]),Y=p(i[1])},B=new P{X=p(i[2]),Y=p(i[3])},D=p(i[4])};Console.WriteLine((from l in n.Skip(1)let f=l.Split()let w=new P{X=p(f[0]),Y=p(f[1])}where g(q.A,q.B,w)<q.D select p(f[2])).Sum());}}}

Non-Golfed:
namespace System
{
    using Linq;
    using m = Math;
    class Point { public float X, Y;}
    class Earthquake
    {
        static void Main()
        {
            Func<string, float> parse = s => float.Parse(s);
            Func<Point, Point, double> dotProduct = (a, b) => { return a.X * b.X + a.Y * b.Y; },
                                       crossProduct = (a, b) => { return a.X * b.Y - a.Y * b.X; };
            Func<Point, Point, Point> subtract = (a, b) => { return new Point { X = a.X - b.X, Y = a.Y - b.Y }; };
            Func<Point, Point, Point, double> getDistance = (A, B, C) => {
                return dotProduct(subtract(C, B), subtract(B, A)) > 0 ?
                        m.Sqrt(dotProduct(subtract(B, C), subtract(B, C))) :
                        dotProduct(subtract(C, A), subtract(A, B)) > 0 ?
                            m.Sqrt(dotProduct(subtract(A, C), subtract(A, C))) :
                            m.Abs(crossProduct(subtract(B, A), subtract(C, A)) / m.Sqrt(dotProduct(subtract(B, A), subtract(B, A))));
            };
            var inputLines = IO.File.ReadAllLines("i");
            var quakeLine = inputLines[0].Split();
            var quake = new {
                PointA = new Point { X = parse(quakeLine[0]), Y = parse(quakeLine[1]) },
                PointB = new Point { X = parse(quakeLine[2]), Y = parse(quakeLine[3]) },
                Distance = parse(quakeLine[4])
            };
            var affectedPopulations = (from line in inputLines.Skip(1)
                                       let fields = line.Split()
                                       let location = new Point { X = parse(fields[0]), Y = parse(fields[1]) }
                                       let population = parse(fields[2])
                                       where getDistance(quake.PointA, quake.PointB, location) < quake.Distance
                                       select population);
            Console.WriteLine(affectedPopulations.Sum());
        }
    }
}

Something is wrong with the golfed version, I get an error when I compile it (quake.cs(1,254): error CS1525: Unexpected symbol ',', expecting 'from', 'group', 'join', 'let', 'orderby', 'select', or 'where').  The ungolfed version works fine.

@KeithRandall, oops - too much golfing!

Javascript (437)
This can probably be golfed significantly, but not enough to beat the Ruby solution.
p=$("#i").text().split("\n");for(i=0;i<p.length;i++){p[i]=p[i].split(" ")}
z=p[0];a=z[0];b=z[1];c=z[2];d=z[3];e=z[4];o=0;f=[a,b];g=[c,d];
function q(r,s){return Math.sqrt(Math.pow(s[0]-r[0],2)+Math.pow(s[1]-r[1],2))}
for(i=1;i<p.length;i++){w=p[i];u=((w[0]-a)*(c-a)+(w[1]-b)*(d-b))/Math.pow(q(f,g,2),2);
x=[(a*1)+u*(c-a),(b*1)+u*(d-b)];l=e;m=w[2]*1;u=w[0];w=w[1];v=[u,w];
o+=q(v,x)<l&&q(x,g)+q(x,f)==q(f,g)?m:q(v,f)<l?m:q(v,g)<l?m:0}alert(o);

You can see it in action here.

You can save 2 characters by using b-0 instead of (b*1), 1 character by removing the trailing semicolon. Finally, start with M=Math and replace all Maths with M, saving 6 characters. Using Prototype and .value saves 2 characters (the # and one parenthesis).

c  -- 471 characters
#include <stdio.h>
#define F float
#define G getline(&v,&l,stdin)
F a[2],b[2],c[2],d[2],e[2],r,t,y,z;char*v;size_t l,n,p;
F s(F u[2],F v[2]){y=u[0]-v[0];z=u[1]-v[1];return y*y+z*z;}
j(F g[2],F h[2],F i[2]){*i=*g-*h;i[1]=g[1]-h[1];}
int i(){j(b,a,d);j(c,a,e);t=*d**e+d[1]*e[1];
return s(a,c)<=r||s(b,c)<=r||t>0&&t/s(a,b)<=1&&s(a,c)-t*t/s(a,b)<=r;}
int main(){G;sscanf(v,"%f %f %f %f %f",a,a+1,b,b+1,&r);r*=r;
while(G!=-1)sscanf(v,"%f %f %i",c,c+1,&p),n+=p*i();printf("%d\n",n);}

It assumes your standard library has getline.
The method is clarified a bit in the comment to the ungolfed version:
#include <stdio.h>

float a[2],b[2],c[2],d[2],e[2],r,t,y,z;
char*v;
size_t l,n,p;
float s(float u[2],float v[2]){ /* returns the square of the distance
                   between two points */
  y=u[0]-v[0];
  z=u[1]-v[1];
  return y*y+z*z;
}
j(float g[2],float h[2],float i[2]){ /* sets i=g-h */
  i[0]=g[0]-h[0];
  i[1]=g[1]-h[1];
}
int i/*sCLose*/(){
  j(b,a,d); /* d=b-a */
  j(c,a,e); /* e=c-a */
  t=d[0]*e[0]+d[1]*e[1]; /* dot product */
  return
    (s(a,c)<=r) || /* near one end point */
    (s(b,c)<=r) || /* near the other */
    (
     (t>0) && /* C lies more "towards" B than away */
     (t/s(a,b)<=1) && /* Nearest point on AB to C lies between A and B */
     (s(a,c)-t*t/s(a,b)<=r) /* length of the altitude less than R */
       );
}
int main(){
  getline(&v,&l,stdin);
  sscanf(v,"%f %f %f %f %f",a,a+1,b,b+1,&r);
  r*=r; /* r is now r squared, as that is the only way we use it */
  printf("(%f, %f); (%f, %f): %f\n",a[0],a[1],b[0],b[1],r);
  while (getline(&v,&l,stdin) != -1){
    sscanf(v,"%f %f %i",c,c+1,&p);
    printf("\t (%f, %f): %d\n",c[0],c[1],p);
    n+=p*i/*sClose*/();
  }
  printf("%d\n",n);
}

scala: 660 chars:
object E extends App{
type I=Int
type D=Double
def b(h:D,i:D,x:I,y:I,d:D)=(x-h)*(x-h)+(y-i)*(y-i)<=d*d
def a(p:java.awt.Polygon,x:I,y:I,h:I,i:I,d:D,r:Array[String])={
val w=r(0).toDouble
val j=r(1).toDouble
val n=r(2).toInt
if (p.contains(w,j)||b(j,w,x,y,d)||b(j,w,i,h,d))n
else 0}
val s=new java.util.Scanner(System.in)
val b=s.nextLine.split(" ")
val c=b.map(_.toDouble)
val e=c.map(_.toInt)
val(x,h,y,i,d)=(e(0),e(2),e(1),e(3),c(4))
val f=List(x,h)
val g=List(y,i)
val p=new java.awt.Polygon((f:::f.reverse).toArray,(g.map(_-e(4)):::g.reverse.map(_+e(4))).toArray,4)
var r=0
while(s.hasNext){
val row=s.nextLine
r+=a(p,x,y,h,i,d,row.split(" "))}
println(r)}

ungolfed:
object Earthquake extends App {

  def bowContains (h: Double, i: Double, x:Int, y:Int, d: Double) : Boolean = {
    (x-h)*(x-h) + (y-i)*(y-i) <= d*d
  }

  import java.awt._

  def affected (polygon: Polygon, x:Int, y:Int, h: Int, i: Int, d: Double, row: Array[String]) : Int = {
    val w = row (0).toDouble
    val j = row (1).toDouble
    val population = row (2).toInt
    if (polygon.contains (w, j) || bowContains (j, w, x, y, d) || bowContains (j, w, i, h, d))
      population
    else 0
  }
  val sc = new java.util.Scanner (System.in)
  val line = sc.nextLine.split (" ")

  val li = line.map (_.toDouble)
  val ll = li.map (_.toInt)

  val (x, h, y, i, d) = (ll (0), ll (2), ll (1), ll (3), li(4))
  val xs = List (x, h)
  val ys = List (y, i)

  val polygon = new Polygon ((xs ::: xs.reverse).toArray, (ys.map (_ - ll(4)) ::: ys.reverse.map (_ + ll(4))).toArray, 4)
  var res = 0
  while (sc.hasNext) {
    val row = sc.nextLine
    println ("line: " + line)
    res += affected (polygon, x, y, h, i, d, row.split (" "))
  }
  println (res)
}