Skip to content

Instantly share code, notes, and snippets.

@dobrokot
dobrokot / gccg.py
Last active August 29, 2015 14:04
import sys, re
# convert lispy-like language to 'lambda-man' ICFP2014 assembler.
# output is JavaScript, loaded in browser
def parse(s, i):
node = []
while 1:
while i < len(s) and (s[i] == ' ' or s[i] == '\n' or s[i] == '\r' or s[i] == '\t'):
i = i+1
докажите что в последовательности [2/sqrt(2)], [2^2/sqrt(2)], ... [2^n/sqrt(2)] .... , где [] - операция взятия целой части бесконечно много нечетных чисел
---------------------------------------------------
Для определёности, две последовательности (вторая - целые части первой):
An = (2^n)/sqrt(2)
Bn = [An] = [ (2^n)/sqrt(2) ]
Метод решения: посмотрел на картинке, что происходит с числами последовательности An "по модулю 2" в промежутке [0..2), там сразу видно: если число нечётное, то каждый раз удваивается расстояние от правой границы отрезка [0..2)
---------------------------------------------------
Формальные логические шаги:
Если четных Bn - конечное число, то бесконечно много нечетных Bn.
@dobrokot
dobrokot / dobro_backup.py
Last active August 29, 2015 14:02
dobro_backup.py - fast incremental backup
#!/usr/bin/env python
USAGE = '''
Incremental backup program
Usage: python "prog_name" destination_dir path1/source1 ... pathN/sourceN'
Copied result will be in the destination_dir/DATE_TIME/source1 ... destination_dir/DATE_TIME/sourceN'
Also there will be created files pathN/sourceN/hash_dir_info.txt (write access to source is needed now)'
When backup is complete, destination_dir/DATE_TIME/backup.complete is created, with timestamp info.
@dobrokot
dobrokot / write_png_to_memory_with_libpng.cpp
Created April 11, 2014 17:37
encode and write PNG to memory (std::vector) with libpng on C++
#include <png.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
//encode and write PNG to memory (std::vector) with libpng on C++
typedef unsigned char ui8;
#define ASSERT_EX(cond, error_message) do { if (!(cond)) { std::cerr << error_message; exit(1);} } while(0)
@dobrokot
dobrokot / sshcp.sh
Created March 13, 2014 10:33
copy directory fron host to (local or other) host
#!/usr/bin/env bash
set -eu
if [ "." == "$2" ]; then
CMD="tar -xvzf -";
else
case "$2" in
"dev") H="kotic.dev.zla.net" ;;
"gen") H="kotic-gen.proto.zla.net" ;;
*) H="$2" ;;
@dobrokot
dobrokot / tzset_slow_test.cpp
Created February 27, 2014 20:56
Slow tzset + localtime
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <string>
std::string tzs[] = {
"Africa/Accra", "Africa/Addis_Ababa", "Africa/Algiers", "Africa/Asmera", "Africa/Bamako", "Africa/Bangui", "Africa/Banjul", "Africa/Bissau", "Africa/Brazzaville", "Africa/Bujumbura", "Africa/Cairo", "Africa/Casablanca", "Africa/Conakry", "Africa/Dakar", "Africa/Dar_es_Salaam", "Africa/Djibouti", "Africa/Douala", "Africa/El_Aaiun", "Africa/Freetown", "Africa/Gaborone", "Africa/Harare", "Africa/Johannesburg", "Africa/Kampala", "Africa/Khartoum", "Africa/Kigali", "Africa/Kinshasa", "Africa/Lagos", "Africa/Libreville", "Africa/Lome", "Africa/Lusaka", "Africa/Malabo", "Africa/Maputo", "Africa/Maseru", "Africa/Mbabane", "Africa/Mogadishu", "Africa/Monrovia", "Africa/Nairobi", "Africa/Ndjamena", "Africa/Niamey", "Africa/Nouakchott", "Africa/Porto-Novo", "Africa/Sao_Tome", "Africa/Tripoli", "Africa/Tunis", "Africa/Windhoek", "America/Anchorage", "America/Anguilla", "America/An
@dobrokot
dobrokot / auto_differentiate.cpp
Created January 12, 2014 11:51
auto_differentiate.cpp
#include <math.h>
#include <stdio.h>
template <class Number>
Number f(Number x) {
Number z = x;
for (int i = 0; i < 4; ++i) {
z = z*z - 0.1 + sin(z*3);
}
if (z < 1) {
import sympy
def make_id(size):
return sympy.Matrix([[int(i==j) for j in xrange(size)] for i in xrange(size)])
def add_absorb(k, m):
size = len(m)
assert size == len(m[0])
return [row + [0] for row in m] + [ [0]* (size-1) + [k,1] ]
@dobrokot
dobrokot / count_random_words.py
Created January 1, 2014 22:21
substring probability, n successes in a row
#!/usr/bin/env python
import random
def id_mat(n):
return [[int(i == j) for j in xrange(n)] for i in xrange(n)]
def my_pow(x, n, mul_fun, one):
r = one
assert n >= 0 and int(n) == n
@dobrokot
dobrokot / fast_grep_patch3.diff
Last active December 21, 2015 16:59
faster state sets merge in grep utility, dfa.c (avoid O(N^2) algorithms)
Index: dfa.c
===================================================================
--- dfa.c (revision grep-2.14-faster-dfa)
+++ dfa.c (revision grep-2.14)
@@ -1992,6 +1992,133 @@
s->elems[i] = s->elems[i + 1];
}
+/* Merge implementation of sorted sets, then number of sets smore than 2.
+ Priority queue aka 'heap' data structure used to select maximum of