Skip to content

Instantly share code, notes, and snippets.

View ashleyholman's full-sized avatar

Ashley Holman ashleyholman

  • Sydney, Australia
View GitHub Profile
@ashleyholman
ashleyholman / tsp.cpp
Created October 6, 2013 06:58
This program solves TSP instances, input as a series of points. The points are represented as x, y floating point co-ordinates. The edge costs are calculated using the euclidian distance between the points. There are no heuristics used in the algorithm, so it should correctly solve general instances in the same amount of time. To modify it to wo…
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
#include <limits>
using namespace std;
using dist = float;
const dist INF = numeric_limits<dist>::max();
@ashleyholman
ashleyholman / johnson.cpp
Created October 2, 2013 13:01
This code implements Johnson's algorithm to solve the "all pairs shortest path" problem, ie. given an input graph with general edge weights (can be negative) with no negative cycles, find the shortest (u, w) path for all pairs of vertices (u, w). If the input graph has any negative cycles, the program will report this and halt (since there is no…
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <exception>
#include <set>
using namespace std;
struct Edge {
@ashleyholman
ashleyholman / fingerprint.pl
Created August 17, 2013 05:36
This is a proof-of-concept fingerprinting tool for testing Bitcoin issue #2757. It attempts to fingerprint a node with a difficulty-1 block. For up-to-date nodes, a higher difficulty block would be required (but still very feasable to mine even on one GPU machine). See further information on https://github.com/bitcoin/bitcoin/issues/2757.
#!/usr/bin/perl -w
use strict;
use IO::Socket;
use Digest::SHA qw(sha256);
$SIG{ALRM} = sub {print "Timed out waiting for response... no fingerprint detected.\n";exit(1)};
# this is an orphaned difficulty-1 block at height 1001, with a timestamp in
# October 2013. in practice you could generate a unique block for each
# individual peer you wanted to fingerprint. this block will successfully
@ashleyholman
ashleyholman / fac.erl
Created August 1, 2013 01:59
This is some code I wrote when I was playing around with Erlang and trying to learn it. I decided to tackle a problem of calculating factorials. As in, fac(n) is the product of n * (n-1) * ... * 2 * 1. For n < 1000, the code does this one a single core using the "condense terms" loop, which simply multiplies pairs of numbers together, and then r…
-module(fac).
-export([fac/1, multiply_terms/1, condense_terms/1, shuffle/1, fac_multi_actor/3]).
% when N >= 1000, partition into 3 sublists and distribute work amongst 3 processes
fac(N) when N >= 1000 ->
L = shuffle(lists:seq(1, N)),
D = trunc(N / 3),
FirstPart = lists:sublist(L, 1, D),
SecondPart = lists:sublist(L, D, D),
LastPart = lists:sublist(L, D*2, N),
@ashleyholman
ashleyholman / radixsort.c
Created February 28, 2013 10:30
In http://www.youtube.com/watch?v=k4RRi_ntQc8, Schmidt asks Obama "What is the most efficient way to sort a million 32-bit integers?". After doing some research (and getting some clues from the youtube comments), it appears that this can be achieved in O(n) time using a non-comparison-based sort. I decided to implement a radix sort as a proof of…
#include <stdio.h>
#include <stdlib.h>
struct Numlist {
// size of the list
unsigned long size;
// the array of integers
unsigned int *arr;
};
@ashleyholman
ashleyholman / gist:5055567
Created February 28, 2013 09:48
Here is the code to generate 1 million random integers for testing radixsort.c. Note that rand() will only output up to RAND_MAX which on my system is defined as 0x7fffffff, so I don't fully get the whole spectrum of possible 32 bit integers. I didn't bother fixing this, but perhaps 1 solution would be to generate two random 16-bit numbers and j…
#include <stdlib.h>
#include <stdio.h>
// Generate 1 million random 32-bit integers.
int main (int argc, char **argv) {
sranddev();
int i;
for (i = 0; i < 1000000; i++) {
unsigned x = (unsigned)rand();
@ashleyholman
ashleyholman / algo_q3.cpp
Created February 25, 2013 12:20
This is an implementation of Karger's Min Cut algorithm. The probability of any given attempt successfully finding the min cut is lower bounded by P >= 1/n^2. So, n^2*log(n) attempts are made which makes the overall probability of failure P <= 1/n. In practice, this does way more attempts than required to find the min cut on most graphs. On a te…
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <cmath>
struct Vertex;
struct Edge {
int v1;