Skip to content

Instantly share code, notes, and snippets.

View PRotondo's full-sized avatar

Pablo Rotondo PRotondo

5 followers · 9 following
View GitHub Profile
@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
@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 / 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 / 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 / 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 / look_and_say.py
Created August 13, 2014 14:07
look-and-say in binary
import itertools
def look_and_say(n) :
a = "0"
for i in xrange(n) :
b = ""
for c,l in itertools.groupby(a) :
b += bin(len(list(l)))[2:] + c
yield a
a = b
@PRotondo
PRotondo / AAAAAA.cpp
Created December 8, 2013 21:21
My solutions to the problems from Facebook Hackercup 2014 Round 1.
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define oo (1<<28)
int solve(vector <string> m)
{
int N = m.size(), M = m[0].length();
@PRotondo
PRotondo / basketball.rb
Created November 25, 2013 10:12
My solutions to the problems from Facebook Hackercup 2014 Qualification Round.
gets.to_i.times do |i|
n, m, ps = gets.split.map(&:to_i)
players = (1..n).map do
name, sp, h = gets.split
sp, h = sp.to_i, h.to_i
[sp,h,name]
end
players.sort!
players.reverse!
team1, team2 = [], []
@PRotondo
PRotondo / CodeForces.rb
Last active December 16, 2015 18:19
My gedit external tool for compiling and testing in CodeForces problems (C++). Filenames should be formatted like {contest-number}{problem-code}.cpp , for example 294A.cpp
#!/usr/bin/env ruby
# [Gedit Tool]
# Name=CodeForces
# Shortcut=<Control>F6
# Languages=cpp
# Applicability=all
# Output=output-panel
# Input=nothing
# Save-files=document
@PRotondo
PRotondo / colors.rb
Created April 21, 2013 17:47
PNG: from colour to black-and-white.
require 'cairo'
#input and output come as arguments
input, output = ARGV
surface = Cairo::ImageSurface.from_png input
goal_data = surface.data
HEIGHT, WIDTH = surface.height, surface.width