Extreme Whitewater Canoeing You are paddling a canoe down a fairly fast whitewater river. Suddenly, your paddles explode, and you find yourself in a dangerous situation hurtling down a river rapid without any paddles. Luckily, you still have your programming skills, so you decide to carve a program on the side of your canoe to help you survive the rapids. However, there is not much surface area on the side of the canoe to write your program with, so you must make the program as short as possible.

The river can be represented as an 8 by 16 grid. We will label the columns with the numbers 0 to 7 and the rows with the numbers 0 to 15.

        y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x


Above: A completely calm, ordinary river with no obstructions. Naturally, this is not the river you are on.

You begin at the coordinate (4, 0) and from there move uncontrollably up the river (i.e. the vector (0,1)) until you hit a rock (represented by an o in these examples). When you hit a rock, you will have a 55% chance of moving past the rock to the left (i.e. the vector (-1,1)) and a 45% chance of moving past the rock to the right (i.e. the vector (1,1)). If the canoe is on the far left or right columns, it will always move towards the centre. If there are no rocks, it will move straight upwards. 

        y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567


Above: A possible route the canoe might take, represented using the character x

Given the map of the river, write a program that will output the probability of the canoe finishing at a given column. 

Accept input in whichever method is convenient for your program (e.g. STDIN, command line argument, raw_input(), reading from a file, etc). The first part of the input is a single integer from 0 to 7, representing the column the program will find the probability for. Following that is a list of tuples in the form x,y representing the position of the stones.

An example:

Input:

4 4,1 5,5 3,5


This would indicate a river with rocks at the positions (4,1), (5,5), and (3,5), and asks for the probability of the canoe ending at the 4th column.

Output:

0.495


Note that in this example, the positions of the rocks were symmetrical, allowing the problem to be solved with a binomial distribution. This won't always be the case!

Also, the river will always be crossable. That is, there will never be two rocks that are positioned adjacent to each other horizontally. See Glenn's comment for an example of an impossible case.

This is code golf, so lowest number of characters wins. Feel free to ask questions in the comments if the specification isn't clear.
Ruby, 204 191 172 characters

c,*r=gets.split
o=[0]*8
s=-&gt;x,y,p{y&gt;14?o[x]+=p :(r.index("#{x},#{y+=1}")?(x&lt;1?s[x+1,y,p]:(x&gt;6?s[x-1,y,p]:(s[x-1,y,p*0.55]+s[x+1,y,p*0.45]))):s[x,y,p])}
s[4,0,1]
p o[c.to_i]


It recursively simulates all possibly outcomes while keeping track of each individual outcome's probability, then it adds that probability to a cumulative counter when y == 15.

Fancy tricks:


c,*r=gets.split - the "splat" operator (*) takes all the remaining elements of gets.split and sticks them in the r array
next {something} if {condition}: essentially equivalent to

if {condition}
    {something}
    return
end


"Discovered" by evolving from if condition; something; return; end to return something if condition to break something if condition, and then I figured I would try a shorter "loop operator" to see if it would work (which it did, of course).
Thanks to @MartinBüttner for suggesting to use chained ternary operators (which ended up becoming the enormous third line in the golfed code above) and eliminating the above point (which saved 19 (!) characters).

I did use a somewhat fancy trick with those, though: I realized that s[foo],s[bar] doesn't work in Ruby for two method calls in one statement. So at first I changed it to (_=s[foo],s[bar]) (a dummy variable), but then I realized I could just add and throw away the return values: s[foo]+s[bar]. This only works because calls to s will only ever "return" other calls to s or a number (o[x]+=p), so I don't have to worry about checking for nil.
Other various optimizations: p instead of puts for printing numbers, &lt;1 instead of ==0 (since the canoe never leaves the river) and similar comparisons elsewhere, [0]*8 for initial probabilities as Ruby's numbers are always "pass by value"


Ungolfed:

column, *rocks = gets.chomp.split
outcomes = Array.new(8, 0)
simulate = -&gt; x, y, probability {
    if y == 15
        outcomes[x] += probability
    elsif rocks.index("#{x},#{y + 1}")
        case x
        when 0 then simulate[x + 1, y + 1, probability]
        when 7 then simulate[x - 1, y + 1, probability]
        else
            simulate[x - 1, y + 1, probability * 0.55]
            simulate[x + 1, y + 1, probability * 0.45]
        end
    else
        simulate[x, y + 1, probability]
    end
}
simulate[4, 0, 1.0]
p outcomes
puts outcomes[column.to_i]