Skip to content

Instantly share code, notes, and snippets.

memo = {}
def p(n,k):
if (n,k) in memo: return memo[n,k]
if (n,k) == (0,0): return 1
if n < k or (n > 0 and k == 0): return 0
memo[n,k] = p(n-k,k) + p(n-1,k-1)
return memo[n,k]
@niklasb
niklasb / tlds_to_js_regex.py
Created January 15, 2012 20:56
Extract TLDs from Chrome's effective_tld_names.dat and dump as a Javascript regex
import re
import sys
import codecs
def js_str_chunks(l, n):
tmp = []
size = 0
for x in l:
char_size = len(repr(x)) - 3
if size + char_size > n:
@niklasb
niklasb / convert-to-mp4.sh
Created January 29, 2012 18:45
Convert video to MP4 for Android
#!/bin/bash
if [[ $# != 2 ]]; then
echo >&2 "Syntax: $0 infile outfile"
fi
ffmpeg -i "$1" -s 480x320 -vcodec mpeg4 -acodec libfaac -ac 1 -ar 16000 -r 15 -ab 32000 -aspect 3:2 -threads 12 "$2"
@niklasb
niklasb / googlers_minimal.py
Created April 19, 2012 01:43
Codejam 2012 - Dancing with the Googlers
def acc(p, total):
best, rest = divmod(total + 2, 3)
return (1, 0) if best >= p else (0, total and rest and best + 1 == p)
for i, line in enumerate(input() for _ in range(int(input()))):
_, S, p, *totals = map(int, line.split())
a, s = map(sum, zip(*(acc(p, total) for total in totals)))
print("Case #%d: %d" % (i + 1, a + min(s, S)))
@niklasb
niklasb / gist:3318976
Created August 10, 2012 23:40
More from Savon
require 'savon'
url = 'http://kim-cm-bts01.scc.kit.edu/HeadingTreeService/HeadingTreeService.svc?wsdl'
client = Savon::Client.new do
wsdl.document = url
http.proxy = "http://dtun.de:9999"
http.auth.basic "heroku", "XXX"
end
@niklasb
niklasb / pow.sage
Last active October 18, 2015 16:17
pow pow
import random
import socket
import subprocess
import hashlib
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
g = pow(2, 2*4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941, p)
gens = [pow(g,3**(336-i),p) for i in range(336)]
@niklasb
niklasb / primegen.cpp
Last active December 17, 2015 18:29
Generate primes < 10^9
#include <iostream>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
@niklasb
niklasb / whiteout.cpp
Last active September 5, 2016 20:13
Computational "proof" for solution of "whiteout" from Tokyo Westerns/MMA CTF 2016
// We want to prove that 5618427494400 is the maximum sigma in range 1..10^12
//
// The following algorithm will explore the entire search space and prune it
// using an upper bound for sigma, while considering the lower bound given by
// our example of sigma(995886571680) = 5618427494400
//
// We consider only primes up to sqrt(10^12). A single prime p is obviously
// not the solution because the sum of its divisors is
// p + 1 < 10^12 < 5618427494400
tenpows = [10**i for i in range(1000)]
def cantor(hi):
res = 0
iters = 0
while hi > 0:
if iters % 100 == 0: print 'Progress: %d' % hi
iters += 1
hi_s = str(hi)
memo = {}
@niklasb
niklasb / gist:3318047
Created August 10, 2012 21:16
Savon + Proxy
require 'savon'
require 'pry'
url = 'http://kim-cm-bts01.scc.kit.edu/HeadingTreeService/HeadingTreeService.svc?wsdl'
client = Savon::Client.new do
wsdl.document = 'http://kim-cm-bts01.scc.kit.edu/HeadingTreeService/HeadingTreeService.svc?wsdl'
http.proxy = "http://dtun.de:9999"
end