Skip to content

Instantly share code, notes, and snippets.

Chillu Annamalai quantumelixir

  • Zurich
Block or report user

Report or block quantumelixir

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
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.