Julia samples (egonSchiele#108)

coditori · egonSchiele · commit 9dc7611411dc · 2019-11-12T09:19:21.000-06:00
* Add julialang binary search sample

* Add unit test

* Add julialang selection sort sample

* Change julia suffix to jl

* Add recursion and quick sort with tests

* add quick sort

* Add hash table samples

* Add BFS

* Changed file names

* Add dijkstras

* Add Dijkstras test
diff --git a/01_introduction_to_algorithms/julia/01_binary_search.jl b/01_introduction_to_algorithms/julia/01_binary_search.jl
diff --git a/02_selection_sort/julia/01_selection_sort.jl b/02_selection_sort/julia/01_selection_sort.jl
@@ -0,0 +1,26 @@
+using Test
+
+function find_smallest(arr)
+    smallest = arr[1]
+    smallest_index = 1
+    for i = 1:length(arr)
+        if arr[i] < smallest
+            smallest = arr[i]
+            smallest_index = i
+        end
+    end
+    return smallest_index
+end
+
+function selection_sort(arr)
+    new_arr = Array{Int64}(undef,0)
+    for i = 1:length(arr)
+        smallest = find_smallest(arr)
+        append!(new_arr,arr[smallest])
+        deleteat!(arr,smallest)
+    end
+    return new_arr
+end
+
+arr = [5,3,6,2,10]
+@test selection_sort(arr) == [2,3,5,6,10]
diff --git a/03_recursion/julia/01_countdown.jl b/03_recursion/julia/01_countdown.jl
@@ -0,0 +1,24 @@
+using Test
+using Suppressor
+
+function countdown(i)
+    println(i)
+    if i <= 0
+        return
+    end
+    countdown(i-1)
+end
+
+result = @capture_out(countdown(10)) # return stdout result
+@test result == "10
+9
+8
+7
+6
+5
+4
+3
+2
+1
+0
+"
diff --git a/03_recursion/julia/02_greet.jl b/03_recursion/julia/02_greet.jl
@@ -0,0 +1,24 @@
+using Test
+using Suppressor
+
+function greet2(name)
+    println("how are you, ",name,"?")
+end
+
+function bye()
+    println("ok bye!")
+end
+
+function greet(name)
+    println("hello, ",name,"!")
+    greet2(name)
+    println("getting ready to say bye...")
+    bye()
+end
+
+result = @capture_out greet("adit")
+@test result == "hello, adit!
+how are you, adit?
+getting ready to say bye...
+ok bye!
+"
diff --git a/03_recursion/julia/03_factorial.jl b/03_recursion/julia/03_factorial.jl
@@ -0,0 +1,10 @@
+using Test
+
+function factorial(x)
+    if x == 1
+        return 1
+    end
+    return x * factorial(x-1)
+end
+
+@test factorial(5) == 120
diff --git a/04_quicksort/julia/01_loop_sum.jl b/04_quicksort/julia/01_loop_sum.jl
@@ -0,0 +1,11 @@
+using Test
+
+function sum(arr)
+    total = 0
+    for x in arr
+        total += x
+    end
+    return total
+end
+
+@test sum([1,2,3,4]) == 10
diff --git a/04_quicksort/julia/02_recursive_sum.jl b/04_quicksort/julia/02_recursive_sum.jl
@@ -0,0 +1,10 @@
+using Test
+
+function sum(arr)
+    if isempty(arr)
+        return 0
+    end
+    return arr[1] + sum(arr[2:end])
+end
+
+@test sum([1,2,3,4]) == 10
diff --git a/04_quicksort/julia/03_recursive_cout.jl b/04_quicksort/julia/03_recursive_cout.jl
@@ -0,0 +1,10 @@
+using Test
+
+function count(arr)
+    if isempty(arr)
+        return 0
+    end
+    return 1 + count(arr[2:end])
+end
+
+@test count([1,2,3,4]) == 4
diff --git a/04_quicksort/julia/04_recursive_max.jl b/04_quicksort/julia/04_recursive_max.jl
@@ -0,0 +1,11 @@
+using Test
+
+function max_(arr)
+    if length(arr) == 1
+        return arr[1]
+    end
+    sub_max = max_(arr[2:end])
+    return arr[1] > sub_max ? arr[1] : sub_max
+end
+
+@test max_([1,5,8,20,9,10]) == 20
diff --git a/04_quicksort/julia/05_quick_sort.jl b/04_quicksort/julia/05_quick_sort.jl
@@ -0,0 +1,11 @@
+using Test
+
+function quick_sort(arr)
+    if length(arr) < 2 return arr end
+    pivot = arr[1]
+    less = [i for i in arr[2:end] if i <= pivot]
+    greater = [i for i in arr[2:end] if i > pivot]
+    return vcat(quick_sort(less), [pivot], quick_sort(greater))
+end
+
+@test quick_sort([3,5,2,1,4]) == [1,2,3,4,5]
diff --git a/05_hash_tables/julia/01_price_of_groceries.jl b/05_hash_tables/julia/01_price_of_groceries.jl
@@ -0,0 +1,2 @@
+book = Dict("apple"=> 0.67, "milk"=> 1.49, "avocado"=> 1.49)
+println(book)
diff --git a/05_hash_tables/julia/02_check_voter.jl b/05_hash_tables/julia/02_check_voter.jl
@@ -0,0 +1,13 @@
+function check_vote(name)
+	if voted.get(name)
+		println("kick them out!")
+	else
+		voted[name] = true
+		println("let them vote!")
+	end
+end
+
+voted = Dict()
+check_vote("tom")
+check_vote("mike")
+check_vote("mike")
diff --git a/06_breadth-first_search/julia/01_breadth-first_search.jl b/06_breadth-first_search/julia/01_breadth-first_search.jl
@@ -0,0 +1,39 @@
+using DataStructures, Test, Suppressor
+
+graph = Dict()
+graph["you"] = ["alice","bob","claire"]
+graph["bob"] = ["anuj","peggy"]
+graph["claire"] = ["thom","jonny"]
+graph["alice"] = ["peggy"]
+graph["anuj"] = []
+graph["peggy"] = []
+graph["thom"] = []
+graph["jonny"] = []
+
+function person_is_seller(name)
+	return name[end] == 'm'
+end
+
+function search(name)
+	search_queue = Deque{String}()
+	map(n -> push!(search_queue,n),graph[name])
+	searched = []
+	while isempty(search_queue) == false
+		person = popfirst!(search_queue)
+		if (person in searched) == false
+			if person_is_seller(person)
+				println(person , " is a mango seller")
+				return true
+			else
+				map(n -> push!(search_queue,n),graph[person])
+				push!(searched,person)
+			end
+		end
+	end
+	return false
+end
+
+
+result = @capture_out search("you")
+@test result == "thom is a mango seller
+"
diff --git a/07_dijkstras_algorithm/julia/01_dijkstras_algorithm.jl b/07_dijkstras_algorithm/julia/01_dijkstras_algorithm.jl
@@ -0,0 +1,64 @@
+# Julia version: LTS (v1.0.3)
+using Test
+
+graph = Dict()
+graph["start"] = Dict()
+graph["start"]["a"] = 6
+graph["start"]["b"] = 2
+
+graph["a"] = Dict()
+graph["a"]["fin"] = 1
+
+graph["b"] = Dict()
+graph["b"]["a"] = 3
+graph["b"]["fin"] = 5
+
+graph["fin"] = Dict()
+
+# the costs table
+infinity = Inf
+costs = Dict()
+costs["a"] = 6
+costs["b"] = 2
+costs["fin"] = infinity
+
+# the parents table
+parents = Dict()
+parents["a"] = "start"
+parents["b"] = "start"
+parents["fin"] = nothing
+
+processed = []
+
+function find_lowest_cost_node(costs)
+    lowest_cost = Inf
+    lowest_cost_node = nothing
+    for node in keys(costs)
+        cost = costs[node]
+        if cost < lowest_cost && node ∉ processed
+            lowest_cost = cost
+            lowest_cost_node = node
+        end
+    end
+    return lowest_cost_node
+end
+
+node = find_lowest_cost_node(costs)
+while node != nothing
+    global node
+    cost = costs[node]
+    neighbors = graph[node]
+    for n in keys(neighbors)
+        new_cost = cost + neighbors[n]
+        if costs[n] > new_cost
+            costs[n] = new_cost
+            parents[n] = node
+        end
+    end
+    push!(processed,node)
+    node = find_lowest_cost_node(costs)
+end
+
+println("Cost from the start to each node:")
+println(costs)
+@test costs == Dict("fin"=>6,"b"=>2,"a"=>5)
