Skip to content

Instantly share code, notes, and snippets.

View CMCDragonkai's full-sized avatar

Roger Qiu CMCDragonkai

View GitHub Profile
CMCDragonkai / dynamic_fibonnaci.php
Created October 27, 2014 09:07
PHP: Dynamic Fibonnaci O(n)
// O(n) time complexity with constant space complexity
function fibonacci_dynamic($n){
if($n == 0){
return 0;
}elseif($n == 1 OR $n == 2){
return 1;
CMCDragonkai / dynamic_fibonnaci.nix
Created October 27, 2014 09:08
Nix: Dynamic Fibonnaci in Functional Style O(n)
fib = number: fib' number 1 1;
fib' = number: first: second:
if number == 0
then first
else fib' (number - 1) second (first + second);
# the second becomes the new first, the (first + second) becomes the new second
fib 5
CMCDragonkai / bitstring_to_integer.exs
Created October 27, 2014 09:21
Elixir: Converting a bitstring to integer. Basically converting base 1 to base 2.
# Note that you can also do things like for << b::2 <- <<1::1, 1::1, 1::1, 0::1>> >>, do: b
# It's pretty cool, it makes sure the b variable is composed of 2 bits. So it will segment the bitstring to represent and have create a b for every 2 bits.
# Binary Comprehension over a bitstring of size 1 bits
list = for << b::1 <- <<1::1, 1::1, 1::1, 0::1>> >>, do: b
# The Goal is the turn <<1::1, 1::1, 1::1, 0::1>> into a base 2 integer, which would be 14
# POWER is like 2^2 which means 2*2. So if x^y. Then there y recursions of x * x.
defmodule Math do
CMCDragonkai / linked_list.nix
Created October 27, 2014 09:28
Nix: Lazy Linked List Implementation using Nested Attribute Sets. This example specifically reifies the fibonnaci sequence into a lazy linked list.
# nix lists are not lazy linked lists
# we can however create lazy linked list using nested attribute sets, where the head is the node value and the tail is the nested cons
# we've basically created a recursive union type:
# type stream a = nil | { head = a; tail = stream a; }
# it's basically a lazy linked list!!!!
# O(n) access of the linked list, it needs to unwrap the linked list as it goes deeper into the list
streamElemAt = s: i:
CMCDragonkai / append.m
Created October 27, 2014 09:32
Mercury: Append Predicate - this demonstrates argument unification
%% this is a linked list append, which is O(n), because it needs to break up the list until the end, then add the list to be appended at the very end, then build up the list again by consing them!
%% unlike loops, each step is a recursion, and I guess there might some sort of tail call optimisation that makes sure that a stack doesn't grow forever in functional languages
:- pred append(list(T), list(T), list(T)).
:- mode append(in, in, out) is det.
:- mode append(out, out, in) is multi.
append(Xs, Ys, Zs) :-
Xs = [], Zs = Ys %% conjunction
CMCDragonkai /
Created October 27, 2014 09:51
Python: Depth First Search on a Adjacency List - returns a list of nodes that can be visited from the root node.
def depth_first_search(neighbour_list, root_node):
visited_nodes = set()
stack = [root_node]
while stack:
node = stack.pop()
if node not in visited_nodes:
stack.extend(set(neighbour_list[node]) - visited_nodes)
return list(visited_nodes)
CMCDragonkai / equal_segregation.php
Last active August 29, 2015 14:08
PHP: Equal Needle Segregation. Given an array containing Xs and Ys, find they key index in which the number of Xs on the left is equal to the number of Ys on right, where X is some arbitrary needle and Y is any element that is not X. The key position is inclusive of Xs.
* Equal needle segregation
* Given an zero-indexed array of values
* Find the index where there is a equal number of X on the left hand side
* To an equal number of Y on the right hand side.
* X is the an arbitrary search needle.
* Y is anything that is not the arbitrary search needle.
* Example: [1, 2, 2, 3, 4]; X = 2
CMCDragonkai / turtle.php
Created November 2, 2014 11:58
PHP: Does the turtle cross a point that it has already visited? (Possibly useful in a snake games)
* Logo Turtle Challenge
* A turtle starts at (0,0).
* You have an array of movements, where each element represents the distance of a single move.
* Directions are cycled every four elements going through north, east, south, west.
* Find the move where the turtle crosses through a point that it has passed through before.
* This solution is somewhat space inefficient, and could become time inefficient if the distance range for a particular move is huge!
* There is probably a solution that allows you to persist only the corner coordinates and then using line equations to figure out if they intersect.
CMCDragonkai / fizzbuzz.js
Last active August 29, 2015 14:09
OMetaJS: FizzBuzz Compiler
// our FizzBuzz language
var code =
"for every number from 1 to 100\
if the number is a multiple of 3 and it is a multiple of 5 then\
print \"FizzBuzz\"\
else if it is a multiple of 3 then\
print \"Fizz\"\
else if it is a multiple of 5 then\
print \"Buzz\"\
CMCDragonkai / list_of.js
Last active August 29, 2015 14:09
OMetaJS: List Of Higher Order
ometa List {
listOf :p = apply(p):head (',' apply(p))*:tail -> [head].concat(tail),
listOfDigits = listOf('digit'):l -> l,
var result = List.matchAll(