Skip to content

Instantly share code, notes, and snippets.

Angel System quantumelixir

  • Zurich
View GitHub Profile
@quantumelixir
quantumelixir / josephus.py
Created Nov 7, 2018
The famous Josephus problem
View josephus.py
# There are n men numbered 1 through n standing in a circle. Starting
# from the first, every m-th man is killed, continuing the process
# from the next man in the circle. Who is the last to be killed?
# recursive
def l(n, m):
if n == 1: return 0
f = (m-1) % n
k = l(n-1, m)
if k <= n-1-(f+1): return k+f+1
@quantumelixir
quantumelixir / division.py
Created Oct 18, 2018
Reducing integer division to integer multiplication.
View division.py
# Reducing integer division to integer multiplication.
#
# Let M(n) denote the time it takes to multiply two n-bit
# integers. Say we want to find the quotient of the division a/b for
# two integers a and b. The simplest reduction is a binary search for
# the answer in the range [0, a], leading to a O(M(n)*n) algorithm for
# division. How can we do better?
#
# Here's an idea. Suppose we find 1 / b = 0.uvwxyz... accurately up to
# some precision (in, say, base 10) then we can just multiply
@quantumelixir
quantumelixir / copies-and-moves.cc
Created Dec 4, 2017
Understand the semantics of moves vs. copies in C++
View copies-and-moves.cc
// Study to understand the semantics of moves vs. copies in C++.
//
// * These operations are different only for reference types like the
// String class defined below. Unlike value types, a literal bitwise
// copy does not make sense for reference types. Instead, a copy
// typically involves a heap allocation followed by a bitwise copy
// from the object(s) being pointed to.
//
// * The goal of a move operation is to avoid unnecessary copying (and
// the associated heap allocations) when possible. For instance, in
@quantumelixir
quantumelixir / alt-poly.cc
Last active Dec 4, 2017
Alternative Runtime Polymorphism
View alt-poly.cc
// This code presents an alternate style of runtime polymorphism
// fleshed out in Sean Parent's talk on the subject
// (https://www.youtube.com/watch?v=QGcVXgEVMJg). The goal is to treat
// different collections of types polymorphically based on their uses
// in different contexts without requiring client-side inheritance of
// those types depending on each of the uses.
#include <iostream>
#include <memory>
#include <string>
@quantumelixir
quantumelixir / temporaries.cc
Created Nov 26, 2017
Lifetime of C++ Temporaries
View temporaries.cc
// A little exercise to demonstrate the lifetime of temporaries in
// C++. Inspired by the comment in this video
// https://youtu.be/xu7q8dGvuwk?t=3156 at CppCon2017 by Titus Winters.
//
// Two things to note:
//
// - Temporaries (rvalues) can have their lifetimes extended by
// binding them to a const reference. But the lifetime is extended
// only to the lifetime of the const reference itself, no more (see
// the Split(..) function below).
@quantumelixir
quantumelixir / reverse.cc
Created Nov 25, 2017
Reversing a linked list
View reverse.cc
// This is just an instructive exercise using pointers. The goal is to
// reverse a linked list, which is not difficult but this solution
// illustrates a particular idea that I first came across in a talk by
// Linus Torvalds.
//
// The idea is simply that holding a pointer to pointer allows
// changing what is being pointed to, and that this can be used in a
// neat way in the context of linked lists. Take the example of
// inserting an item in a list. Here, the role played by the `head`
// pointer is similar to the role played by the `next` pointer of some
View rotation_matrix_3d.nb
In[79]:= Rz[x_] := ( {
{Cos[x], -Sin[x], 0},
{Sin[x], Cos[x], 0},
{0, 0, 1}
} );
Ry[x_] := ( {
{Cos[x], 0, Sin[x]},
{0, 1, 0},
{-Sin[x], 0, Cos[x]}
} );
@quantumelixir
quantumelixir / kmp_string_matching.cpp
Created Jan 25, 2017
The Knuth Morris Pratt algorithm for string matching
View kmp_string_matching.cpp
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
// find all occurrences of pattern in the text as a vector of indices
// using the knuth morris pratt algorithm in time O(|text| + |pattern|)
vector<int> kmp_find_all(const string &t, const string &p) {
@quantumelixir
quantumelixir / markdownlatex
Created Feb 10, 2011
Turn Latex code between $..$ and $$..$$ in markdown into images
View markdownlatex
#!/usr/bin/python
import subprocess
import sys
import os
import re
# output directory for generated png files
global basedir
basedir = '.'
@quantumelixir
quantumelixir / ulamspiral.go
Created Jan 15, 2011
Print the ulam spiral
View ulamspiral.go
package main
import (
"os"
"fmt"
"flag"
"strconv"
)
You can’t perform that action at this time.