This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
// 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let | |
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 | |
in | |
fib 5 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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!!!! | |
let | |
# O(n) access of the linked list, it needs to unwrap the linked list as it goes deeper into the list | |
streamElemAt = s: i: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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: | |
visited_nodes.add(node) | |
stack.extend(set(neighbour_list[node]) - visited_nodes) | |
return list(visited_nodes) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* 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. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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\"\ | |
else\ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
ometa List { | |
listOf :p = apply(p):head (',' apply(p))*:tail -> [head].concat(tail), | |
listOfDigits = listOf('digit'):l -> l, | |
END | |
} | |
var result = List.matchAll( | |
'1,2,3,4,5', | |
'listOfDigits' | |
); |
OlderNewer