Skip to content

Instantly share code, notes, and snippets.


Ashley Holman ashleyholman

  • Sydney, Australia
View GitHub Profile
ashleyholman / tsp.cpp
Created Oct 6, 2013
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…
View tsp.cpp
#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 / johnson.cpp
Created Oct 2, 2013
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…
View johnson.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <exception>
#include <set>
using namespace std;
struct Edge {
ashleyholman /
Created Aug 17, 2013
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
#!/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 / fac.erl
Created Aug 1, 2013
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…
View fac.erl
-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 / radixsort.c
Created Feb 28, 2013
In, 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…
View radixsort.c
#include <stdio.h>
#include <stdlib.h>
struct Numlist {
// size of the list
unsigned long size;
// the array of integers
unsigned int *arr;
ashleyholman / gist:5055567
Created Feb 28, 2013
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…
View gist:5055567
#include <stdlib.h>
#include <stdio.h>
// Generate 1 million random 32-bit integers.
int main (int argc, char **argv) {
int i;
for (i = 0; i < 1000000; i++) {
unsigned x = (unsigned)rand();
ashleyholman / algo_q3.cpp
Created Feb 25, 2013
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…
View algo_q3.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <cmath>
struct Vertex;
struct Edge {
int v1;