Skip to content

Instantly share code, notes, and snippets.

View rgrig's full-sized avatar

Radu Grigore rgrig

View GitHub Profile
@rgrig
rgrig / a.py
Created December 7, 2020 15:39
import sys
M = 10
cache = [[None for k in range(2**b+1)] for b in range(M)]
def maxo(a, b):
if b is None:
return a
if a is None:
return b
@rgrig
rgrig / foo.hs
Last active November 24, 2020 14:41
import Data.Array.IArray (Array, array, (!), elems)
imap :: (Int -> a -> b) -> [a] -> [b]
imap = m 1
where
m _ _ [] = []
m i f (x : xs) = (f i x) : m (i + 1) f xs
solve :: [Int] -> Int
solve xs = n - cyclesCount

Questions: https://github.com/regehr/assert_quiz/blob/master/assert_quiz.md

  1. bad, should handle error sensibly
  2. bad, debug builds don't even alloc
  3. bad, should handle error sensibly
  4. ?, assert ok, but code around clearly bad: the hash_function has no idea what lenght is, and no modulo done after
  5. bad, should handle error sensibly
  6. kinda ok. You probably want a way to turn off expensive assertions, though. This way you can run prog with all asserts on small tests, and with cheap asserts on big tests (an with no asserts in release -- if you so fancy).
include <stdio.h>
int main() {
const int n = 200;
int data[n];
data[0]=0; data[1]=2;
int i, j;
i = j = 0;
int state = 0;
while (j < n) {
printf("%d\n",data[j]);
@rgrig
rgrig / fib.hs
Created April 25, 2015 18:08
memoization in Haskell
import Data.Array
import Debug.Trace
tabulate :: (Ix a) => (a,a) -> (a -> b) -> Array a b
tabulate bounds f = array bounds [(i,f i) | i <- range bounds]
dp :: (Ix a) => (a,a) -> ((a->b) -> a -> b) -> a -> b
dp bounds f = (memo!) where
memo = tabulate bounds (f (memo!))
@rgrig
rgrig / Median.py
Last active August 29, 2015 14:11
computing the median for a list of integers
# NOTES:
# - I didn't pay attention to what happens for lists of even length
# - Since the data is random, the algorithms need not be randomized. I put
# randomization in because calls to randrange/sample/etc might take
# significant time, and it's not really OK to ignore that time.
# - Since the data is random, Python's sort should be disadvantaged, at least
# when M >> N. (The main idea of Timsort is that it exploits patterns
# in data.)
# - As expected, Timsort does better when N>M than when M>N. I didn't expect it
# to bo _so_ much better, though.
@rgrig
rgrig / tsp_long.py
Created September 22, 2014 07:03
some rather bad euclidean tsp solver
#!/usr/bin/env python3
from copy import copy
from math import atan2, pi, sqrt
from random import randrange, seed, shuffle
from sys import exit, stderr
from time import time
eps = 1e-9
from sys import stdin, stdout
import random, math
def tour_length(G, xs):
s = sum(G[xs[i-1]][xs[i]] for i in range(len(xs)))
n = len(xs)
return s + min(G[0][xs[i]] - max(G[xs[i]][xs[(i+1)%n]], G[xs[i]][xs[(i-1)%n]])
for i in range(n))
int power(int x, unsigned int y) {
if (y == 0) return 1;
if (y == 2) return x * x;
if (y&1) return x * power(power(x, y/2),2);
return power(power(x, y/2),2);
}
@rgrig
rgrig / A.java
Created July 3, 2014 07:45
getOnlyElement
import com.google.common.base.Optional;
import com.google.common.collect.Lists;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class A {
public static <T> T getOnlyElement(Iterable<T> xs, Optional<T> e, Optional<T> xx) {
Iterator<T> i = xs.iterator();
if (!i.hasNext()) {
if (e.isPresent()) return e.get();