// 18_algorithms.ruchy - Common algorithms and data structure operations
fn main() {
println("=== Algorithms ===\n")
// Sorting algorithms
println("=== Sorting Algorithms ===")
// Bubble sort
fn bubble_sort(mut arr) {
let n = arr.len()
for i in 0..n {
for j in 0..(n - i - 1) {
if arr[j] > arr[j + 1] {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
arr
}
// Quick sort
fn quick_sort(arr) {
if arr.len() <= 1 {
return arr
}
let pivot = arr[arr.len() / 2]
let left = arr.filter(x => x < pivot)
let middle = arr.filter(x => x == pivot)
let right = arr.filter(x => x > pivot)
quick_sort(left) + middle + quick_sort(right)
}
// Merge sort
fn merge_sort(arr) {
if arr.len() <= 1 {
return arr
}
let mid = arr.len() / 2
let left = merge_sort(arr.slice(0, mid))
let right = merge_sort(arr.slice(mid))
merge(left, right)
}
fn merge(left, right) {
let mut result = []
let mut i = 0
let mut j = 0
while i < left.len() && j < right.len() {
if left[i] <= right[j] {
result.append(left[i])
i += 1
} else {
result.append(right[j])
j += 1
}
}
result + left.slice(i) + right.slice(j)
}
let unsorted = [64, 34, 25, 12, 22, 11, 90]
println(f"Original: {unsorted}")
println(f"Bubble sorted: {bubble_sort(unsorted.clone())}")
println(f"Quick sorted: {quick_sort(unsorted.clone())}")
println(f"Merge sorted: {merge_sort(unsorted.clone())}")
// Searching algorithms
println("\n=== Searching Algorithms ===")
// Binary search
fn binary_search(arr, target) {
let mut left = 0
let mut right = arr.len() - 1
while left <= right {
let mid = (left + right) / 2
if arr[mid] == target {
return Some(mid)
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
None
}
let sorted = [11, 12, 22, 25, 34, 64, 90]
let target = 34
match binary_search(sorted, target) {
Some(index) => println(f"Found {target} at index {index}"),
None => println(f"{target} not found")
}
// Graph algorithms
println("\n=== Graph Algorithms ===")
// Breadth-first search (BFS)
fn bfs(graph, start) {
let mut visited = set()
let mut queue = [start]
let mut result = []
while queue.len() > 0 {
let node = queue.remove(0)
if !visited.contains(node) {
visited.add(node)
result.append(node)
for neighbor in graph[node] {
if !visited.contains(neighbor) {
queue.append(neighbor)
}
}
}
}
result
}
// Depth-first search (DFS)
fn dfs(graph, start, visited = set()) {
let mut result = []
visited.add(start)
result.append(start)
for neighbor in graph[start] {
if !visited.contains(neighbor) {
result = result + dfs(graph, neighbor, visited)
}
}
result
}
let graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
println(f"BFS from A: {bfs(graph, 'A')}")
println(f"DFS from A: {dfs(graph, 'A')}")
// Dynamic programming
println("\n=== Dynamic Programming ===")
// Fibonacci with memoization
fn fibonacci_memo(n, memo = {}) {
if n in memo {
return memo[n]
}
if n <= 1 {
return n
}
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
memo[n]
}
println(f"Fibonacci(10): {fibonacci_memo(10)}")
// Longest common subsequence
fn lcs(str1, str2) {
let m = str1.len()
let n = str2.len()
let dp = [[0 for _ in 0..=n] for _ in 0..=m]
for i in 1..=m {
for j in 1..=n {
if str1[i - 1] == str2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
dp[m][n]
}
println(f"LCS('ABCDGH', 'AEDFHR'): {lcs('ABCDGH', 'AEDFHR')}")
// Tree algorithms
println("\n=== Tree Algorithms ===")
struct TreeNode {
value: int,
left: Option<TreeNode>,
right: Option<TreeNode>
}
// Tree traversals
fn inorder(node) {
if node == None {
return []
}
match node {
Some(n) => {
inorder(n.left) + [n.value] + inorder(n.right)
},
None => []
}
}
fn preorder(node) {
if node == None {
return []
}
match node {
Some(n) => {
[n.value] + preorder(n.left) + preorder(n.right)
},
None => []
}
}
fn postorder(node) {
if node == None {
return []
}
match node {
Some(n) => {
postorder(n.left) + postorder(n.right) + [n.value]
},
None => []
}
}
// String algorithms
println("\n=== String Algorithms ===")
// KMP pattern matching
fn kmp_search(text, pattern) {
let n = text.len()
let m = pattern.len()
if m == 0 {
return []
}
let lps = compute_lps(pattern)
let mut matches = []
let mut i = 0 // index for text
let mut j = 0 // index for pattern
while i < n {
if pattern[j] == text[i] {
i += 1
j += 1
}
if j == m {
matches.append(i - j)
j = lps[j - 1]
} else if i < n && pattern[j] != text[i] {
if j != 0 {
j = lps[j - 1]
} else {
i += 1
}
}
}
matches
}
fn compute_lps(pattern) {
let m = pattern.len()
let lps = [0 for _ in 0..m]
let mut length = 0
let mut i = 1
while i < m {
if pattern[i] == pattern[length] {
length += 1
lps[i] = length
i += 1
} else {
if length != 0 {
length = lps[length - 1]
} else {
lps[i] = 0
i += 1
}
}
}
lps
}
let text = "ABABDABACDABABCABAB"
let pattern = "ABABCABAB"
println(f"Pattern '{pattern}' found at indices: {kmp_search(text, pattern)}")
// Mathematical algorithms
println("\n=== Mathematical Algorithms ===")
// Sieve of Eratosthenes
fn sieve_of_eratosthenes(n) {
let is_prime = [true for _ in 0..=n]
is_prime[0] = false
is_prime[1] = false
for i in 2..=sqrt(n).to_int() {
if is_prime[i] {
for j in (i * i..=n).step_by(i) {
is_prime[j] = false
}
}
}
[i for i in 2..=n if is_prime[i]]
}
println(f"Primes up to 30: {sieve_of_eratosthenes(30)}")
// GCD using Euclidean algorithm
fn gcd(a, b) {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
println(f"GCD(48, 18): {gcd(48, 18)}")
}