Skip to content

Instantly share code, notes, and snippets.

View sirupsen's full-sized avatar
🐡

Simon Eskildsen sirupsen

🐡
2.6k followers · 200 following
View GitHub Profile
@sirupsen
sirupsen / gist:2164021
Last active February 26, 2018 14:28
An extremely simple dynamic programming fibonacci implementation in Ruby using hashes.
# fibonacci
h = Hash.new { |hash,key| hash[key] = hash[key-1] + hash[key-2] }
h[1] = 0
h[2] = 1
@sirupsen
sirupsen / gist:3317833
Last active October 8, 2015 10:18
Simple program to schedule a reminder on OS X.
#!/bin/bash
at $2 << !!
say $1
osascript -e 'tell app "System Events" to display dialog "Reminder: $1"'
!!
exit 0
@sirupsen
sirupsen / gist:3736027
Last active October 10, 2015 18:58
Implementation of a logarithmic time segment tree tree to update an interval, instead of a single key.
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
struct Tree {
vector<ll> tree;
ll n;
@sirupsen
sirupsen / fast.cpp
Created October 18, 2012 19:24
Code for my competitive programming talk in C++ and Javascript. It solves the "Mega Inversion" problem from NCPC 2011: http://ncpc.idi.ntnu.no/ncpc2011/ncpc2011problems.pdf
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll n;
vector<int> numbers;
struct Tree {
@sirupsen
sirupsen / gist:4178574
Last active October 13, 2015 09:58
Implementation of a faster linear search, by sparing a single comparison.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int sought = 4e8;
vector<int> vec;
for(size_t i = 0; i < sought + 20; i++)
@sirupsen
sirupsen / hosts.focus
Created March 13, 2013 10:43
My /etc/hosts and the accompanying crontab.
##
# Host Database
#
# localhost is used to configure the loopback interface
# when the system is booting. Do not change this entry.
##
127.0.0.1 localhost
255.255.255.255 broadcasthost
::1 localhost
fe80::1%lo0 localhost
@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()
{
@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 / 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: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()