Skip to content

Instantly share code, notes, and snippets.

View jamespayor's full-sized avatar

James Payor jamespayor

View GitHub Profile
@jamespayor
jamespayor / bracket_matching_compress.py
Created April 28, 2022 17:18
Compress N elements into N-1 elements via bracket matching.
from sys import byteorder
from hashlib import sha256
uint256 = int
uint256_minus_1 = uint256
def source_parity(i: uint256) -> bool:
return (i & 1) != 0
def target_parity(i: uint256) -> bool:
@jamespayor
jamespayor / tournament.py
Last active April 23, 2022 19:26
An example invertible hash function on 256-bit numbers based on a single-elimination tournament.
"""
I define a collision-free hash function, forward : uint256 -> uint256, that is invertible on
most values, but for which it is infeasible to find preimages of large hashes.
We also give an inverse, backward : uint256 -> uint256, that runs quickly for small hashes, but
becomes too slow to use at the extreme end.
For instance, backward(2^256 - 1) needs to run 2^256 playoffs amongst all numbers. This is a
feature, not a bug, as it provides an initial answer to Vitalik's puzzle:
https://twitter.com/VitalikButerin/status/1516317085290446848
@jamespayor
jamespayor / BFS.hs
Last active January 13, 2022 00:06
BFS vs DFS as differences in lazy evaluation order
{-# LANGUAGE BlockArguments #-}
-- Setup
when :: (a -> Bool) -> a -> [a]
when f a = if f a then [a] else []
newtype Zip a = Zip { getZip :: [a] }
deriving (Eq, Ord, Show)
@jamespayor
jamespayor / maxWeightBipartiteMatching.cpp
Last active December 13, 2017 20:50
Competition-style O(N^4) implementation of the Hungarian algorithm, for weighted bipartite perfect matching.
#include <iostream>
#include <algorithm>
using namespace std;
#define fo(i,n) for(int i=0,_n=(n);i<_n;i++)
int n,delta,w[300][300],l[300],r[300],rm[300];
bool ul[300], ur[300], m[300][300];
const int oo = 2000000;
void relax() {
@jamespayor
jamespayor / viewer_signing.py
Last active April 6, 2017 20:48
Draftable Compare API - Signing viewer URLs walkthrough
import json
import hashlib
import hmac
from collections import OrderedDict
def get_viewer_url_signature(account_id, auth_token, identifier, valid_until_timestamp):
# type: (str, str, str, int) -> str
# First, we generate our policy, which is an object giving the account_id and