Skip to content

Instantly share code, notes, and snippets.

@mudge
mudge / README.md
Last active May 11, 2021 19:45
Compiling & installing cloudflared for DNS-over-HTTPS on a Raspberry Pi Model B
@mudge
mudge / dijkstra_with_fibonacci_heap.rb
Last active July 15, 2018 16:14
Implementing Dijkstra's algorithm with Fibonacci Heap
require 'fibonacci_heap'
# Assuming `graph` is an object with the following interface that stores vertices as `FibonacciHeap::Node`
# instances and `source` is a `FibonacciHeap::Node`:
#
# * `graph.vertices`: return an Enumerable of all vertices in the graph
# * `graph.neighbours(u)`: return an Enumerable of all vertices that neighbour a given vertex `u`
# * `graph.length(u, v)`: return the numeric weight of the edge between two given vertices `u` and `v`
def dijkstra(graph, source)
dist = Hash.new(Float::INFINITY)
@mudge
mudge / fibonacci_heap.rb
Last active June 24, 2018 19:56
A Ruby implementation of a Fibonacci heap
class CircularDoublyLinkedList
include Enumerable
class Node
include Comparable
attr_accessor :key, :next, :prev
alias right next
alias left prev
@mudge
mudge / dijkstra.rb
Last active June 22, 2018 15:41
An implementation of Dijkstra's algorithm in Ruby
# A pure Ruby implementation of https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#
# Takes a graph in hash form, e.g. { 'A' => ['B', 'C'], 'B' => ['D'], 'C' => ['D'] },
# and a source node, e.g. 'A', and returns the distances to every reachable node and a hash of "next hops" for each node.
def dijkstra(graph, source)
q = graph.keys
prev = {}
dist = Hash.new(Float::INFINITY)
dist[source] = 0
@mudge
mudge / snitch.rb
Last active February 17, 2018 13:56
A wrapper class for reporting on method calls useful for reverse engineering
# snitch = Snitch.new('A string')
#=> #<Snitch:0x00007fe53a1964b0 @obj="A string">
# snitch.empty?
# Calling empty? on A string with []
#=> false
class Snitch
attr_reader :obj
def initialize(obj)
@mudge
mudge / best_fit.rb
Last active July 28, 2017 21:32
Applying bin packing techniques to GNIP PowerTrack rules
domains = ARGF.readlines.map(&:chomp)
queries = domains.map { |domain| %[url_contains:"/#{domain}" OR url_contains:".#{domain}"] }
queries.sort_by!(&:size)
rule_limit = 1024
operator_limit = 30
rules = [queries.pop]
queries.reverse_each do |query|
enum Error {
NoRuleApplies,
}
enum Term {
TmTrue,
TmFalse,
TmIf(Box<Term>, Box<Term>, Box<Term>),
TmZero,
TmSucc(Box<Term>),
@mudge
mudge / nginx.conf
Last active February 6, 2017 20:34
Handling Fastly TLS termination in nginx with map: http://nginx.org/en/docs/http/ngx_http_map_module.html
# Declares a new variable, $forwarded_scheme, that contains the URL scheme
# used by a user even if Fastly terminates your TLS connections.
#
# Will use the scheme extracted from the request URI by default or return
# "https" if the Fastly-SSL HTTP header is found.
map $http_fastly_ssl $forwarded_scheme {
default $scheme;
"1" "https";
}
@mudge
mudge / hooks.rb
Created October 26, 2016 11:38
Run every Cucumber scenario with a separate Capybara session
Around do |scenario, block|
Capybara.using_session(scenario.object_id) do
block.call
end
end