Skip to content

Instantly share code, notes, and snippets.

View PRotondo's full-sized avatar

Pablo Rotondo PRotondo

9 followers · 9 following
View GitHub Profile
@PRotondo
PRotondo / look_and_say.sage
Created August 13, 2014 15:30
Fast look-and-say computation (for the binary case, starting with 0), implemented in Sage.
import itertools
M = {}
def look_and_say(atom,n) :
global M
a = atom
if n == 0 :
return 0
b = ""
@PRotondo
PRotondo / shellsort.cpp
Created October 16, 2014 19:37
Dyadic shellsort
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cassert>
using namespace std;
int count; // to experiment a bit...
// divide and conquer shellsort with powers of two...
@PRotondo
PRotondo / in_order_iterate.py
Last active November 9, 2017 12:46
Iterate over each element of a set in order. It is well-known that one can easily do it in reverse order by doing i = (i-1)&superset (see https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/)
def binary(x) :
return format(x,'b')
def print_binary(x) :
print binary(x)
def iterate(superset,f) :
i = 0
while True :
f(i)
@PRotondo
PRotondo / lua-timed-iterations.lua
Last active April 5, 2023 15:02
Model simulation in Lua : probabilistic model with insertions that are uniform on the array of the hashtable and deletions
math.randomseed(2151) -- (2151)
n = 1<<23
iterations = 100
pow = 1<<31
pow2 = pow>>1
m = 15
offset = 1<<m
it = offset
@PRotondo
PRotondo / worst-case-insertions-deletions-deterministic.lua
Created May 10, 2023 15:09
Worst case scenarios for the Lua hybrid tables
k = 15
m = 1<<k
tab = {}
pow2 = m<<2 -- any power of two larger works
for i=1,m do
tab[pow2+i] = 1 -- insert big elements
end