// 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)}")
}