physbuzz

// Timing  different permutation algorithms 1-5, RCR's code, and the reference implementation, respectively.
//
// g++ -O3 -o permutations permutations.cpp
// ./permutations	
// Passed! Time elapsed: 4.14582s
// Passed! Time elapsed: 0.014193s
// Passed! Time elapsed: 0.105983s
// Passed! Time elapsed: 0.015864s
// Passed! Time elapsed: 0.003905s
// Passed! Time elapsed: 0.046937s

physbuzz

/*A frog has 100 lily pads arranged in a circle. Each one has a distinct number 0,1,…,99 on it, arranged in 
increasing order counter-clockwise starting from 0. The frog starts at lily pad 0 and hops to the closest lily 
pad on the left or right of its current position with equal probability per hop. Find the probability that when 
the frog lands on lily pad 50 for the first time, it has visited every other lily pad not labeled 50.
 * 
This has a clever solution that the answer is 1/(NUM_LILLYPADS-1). But let's brute force it! 
I use OpenMP to cheaply speed stuff up and get a 95% confidence interval.

This feels slower than it should be... but I am using mersenne twister. 

physbuzz

#include <iostream>
#include "math.h"
#include <vector>
#include <cstdlib> 

using namespace std;

class BresenhamLine {
    int x1,y1,x2,y2, dx,dy, step;
    //philosophically the same as Bresenham, but we cheat by using floats.