Skip to content

Instantly share code, notes, and snippets.

View sirupsen's full-sized avatar
🐡

Simon Eskildsen sirupsen

🐡
2.8k followers · 200 following
View GitHub Profile
@sirupsen
sirupsen / balanced.rb
Last active December 22, 2015 13:48
Benchmarks for a variety of ways to search through an array of strings for a prefix match.
class BBT
def initialize(array)
@set = array.sort
end
def lower_bound(element)
lower, upper = 0, @set.size - 1
while lower != upper
middle = (lower + upper) / 2
@sirupsen
sirupsen / gist:6480217
Last active December 22, 2015 13:38
Quick and dirty way to check whether a string of parentheses are balanced.
def balanced?(string)
string.each_char.inject(0) { |open, char|
return false if open < 0
char == '(' ? open + 1 : open - 1
} == 0
end
p balanced?("()((()))")
p balanced?("())))")
p balanced?("()(((())")
@sirupsen
sirupsen / gist:6479740
Last active April 5, 2019 16:28
Implementation of a trie in Ruby.
class Trie
attr_accessor :word, :trie
def initialize
@trie = {}
@word = false
end
def <<(string)
node = string.each_char.inject(self) { |node, char| node.trie[char] ||= Trie.new }
@sirupsen
sirupsen / posix-mqueue-receive.c
Last active December 22, 2015 04:18
Extraction from the posix-mqueue gem of how it receives messages from the queue.
VALUE
posix_mqueue_receive(VALUE self)
{
// Contains any error returned by the syscall
int err;
// Buffer data from the message queue is read into
size_t buf_size;
char *buf;
@sirupsen
sirupsen / gist:6225767
Last active December 21, 2015 01:09
Ruby 2.0.0 coerce incompatibility.
# The issue here, is that when Ruby encounters an expression like:
#
# 5 < Mass.new(10)
#
# The Fixnum doesn't know how to compare itself to a Mass. However, a Mass object knows
# how to compare itself with a Fixnum. Ruby calls #coerce on 5, to switch the parameters
# around, so now we have:
#
# Mass.new(10) > 5
#
@sirupsen
sirupsen / gist:5787227
Last active December 18, 2015 12:59
Simple example of finding the lowest common ancestor. The range minimum query is done in O(n) time, but can be done in O(log(n)) time with a O(n*log(n)) precomputation, with a e.g. a segment tree.
#include <vector>
#include <climits>
using namespace std;
int iteration = 0;
vector<size_t> h, l, e;
vector<vector<size_t> > adj;
void lca_dfs(size_t v, size_t depth)
{
@sirupsen
sirupsen / gist:5776242
Last active December 18, 2015 11:29
Well-known algorithmic competition hack to represent points in euclidean space as complex numbers to get the distance between them by subtracting the two complex numbers.
#include<complex>
#include<cmath>
#include<iostream>
using namespace std;
typedef complex<double> Point;
#define x imag()
#define y real()
@sirupsen
sirupsen / gist:5745187
Last active December 18, 2015 07:18
You have an infinite binary tree where each vertex is labeled: the left child has the label `2n`, right child `2n + 1`, with the root node having the label 1. The input is a walking sequence containing L (go to the left child), R (go to the right child), P (stay), and * (all of these). Output the sum of all the labels you can end up at following…
s = gets.strip
m = {
?L => ->(z) { z + z.real },
?R => ->(z) { z + Complex(z.real, z.real) },
?P => ->(z) { z },
?* => ->(z) { m[?L][z] + m[?R][z] + z }
}
z = s.reverse.each_char.inject(Complex(1)) { |z, c| m[c][z] }
@sirupsen
sirupsen / gist:5326168
Last active December 15, 2015 21:29
Simple implementation of a naive Bayesian classifier.
class Bayes
def initialize
@frequency = {}
@categories = Hash.new 0
end
# Prob(Category|Features) = Prob(Category) Prob(Features|Category)
def probability(features, category)
features_probability(features, category) * category_probability(category)
end
@sirupsen
sirupsen / palindrome.cpp
Created March 21, 2013 10:16
Given a string, print the minimum number of insertions to make it a palindrome with O(n) memory usage and O(n^2) complexity.
#include<iostream>
#include<cstring>
using namespace std;
string s1, s2;
int n;
int lcs()
{