Crystal Interview Questions with Answers

# Hello World in Crystal
puts "Hello, World!"

# Data Types in Crystal
age = 25
salary = 50000.50_f32
pi = 3.14159265358979
grade = 'A'
is_active = true
name = "Alice"
price = 99.99

puts "Age: #{age}"
puts "Salary: #{salary}"
puts "Pi: #{pi}"
puts "Grade: #{grade}"
puts "Active: #{is_active}"
puts "Name: #{name}"
puts "Price: #{price}"

# Variables, Constants, and Readonly
class Program
  PI = 3.14159
  MAX = 100

  def self.main
    x = 10
    MIN_VALUE = 0
    
    # Type inference
    val = 3.14
    str = "Hello"
    
    puts "x = #{x}"
    puts "PI = #{PI}"
    puts "val = #{val}"
    puts "str = #{str}"
  end
end

Program.main

# OOP - Classes and Objects
class Car
  getter brand : String
  getter year : Int32
  getter price : Float64

  def initialize(@brand : String, @year : Int32, @price : Float64)
  end

  def display
    puts "Brand: #{@brand}, Year: #{@year}, Price: $#{@price}"
  end

  def finalize
    puts "#{@brand} destroyed."
  end
end

c1 = Car.new("Toyota", 2022, 25000.0)
c2 = Car.new("BMW", 2023, 55000.0)

c1.display
c2.display
puts "Brand: #{c1.brand}"

# Constructors and Destructors
class Student
  property name : String
  property age : Int32

  def initialize
    @name = "Unknown"
    @age = 0
    puts "Default constructor called"
  end

  def initialize(@name : String, @age : Int32)
    puts "Parameterized constructor: #{@name}"
  end

  def initialize(other : Student)
    @name = other.name
    @age = other.age
    puts "Copy constructor: #{@name}"
  end

  def display
    puts "Name: #{@name}, Age: #{@age}"
  end

  def finalize
    puts "Destructor: #{@name}"
  end
end

s1 = Student.new
s2 = Student.new("Alice", 20)
s3 = Student.new(s2)

s1.display
s2.display
s3.display

# Inheritance in Crystal
class Animal
  property name : String
  property age : Int32

  def initialize(@name : String, @age : Int32)
  end

  def speak
    puts "#{@name} makes a sound."
  end

  def info
    puts "Name: #{@name}, Age: #{@age}"
  end
end

class Dog < Animal
  property breed : String

  def initialize(name : String, age : Int32, @breed : String)
    super(name, age)
  end

  def speak
    puts "#{@name} says: Woof!"
  end

  def display
    info
    puts "Breed: #{@breed}"
  end
end

class Cat < Animal
  def initialize(name : String, age : Int32)
    super(name, age)
  end

  def speak
    puts "#{@name} says: Meow!"
  end
end

dog = Dog.new("Rex", 3, "German Shepherd")
cat = Cat.new("Whiskers", 2)

dog.display
dog.speak
cat.speak

# Polymorphism via base reference
a = dog.as(Animal)
a.speak

# Polymorphism and Abstract Classes
abstract class Shape
  abstract def area : Float64
  abstract def perimeter : Float64

  def display
    puts "Area: #{area}, Perimeter: #{perimeter}"
  end
end

class Circle < Shape
  def initialize(@radius : Float64)
  end

  def area
    Math::PI * @radius * @radius
  end

  def perimeter
    2 * Math::PI * @radius
  end
end

class Rectangle < Shape
  def initialize(@width : Float64, @height : Float64)
  end

  def area
    @width * @height
  end

  def perimeter
    2 * (@width + @height)
  end
end

shapes = [
  Circle.new(5.0),
  Rectangle.new(4.0, 6.0)
]

shapes.each { |s| s.display }

# Operator Overloading
struct Vector2D
  property x : Float64, y : Float64

  def initialize(@x : Float64 = 0, @y : Float64 = 0)
  end

  def +(other : Vector2D)
    Vector2D.new(@x + other.x, @y + other.y)
  end

  def -(other : Vector2D)
    Vector2D.new(@x - other.x, @y - other.y)
  end

  def *(scalar : Float64)
    Vector2D.new(@x * scalar, @y * scalar)
  end

  def ==(other : Vector2D)
    @x == other.x && @y == other.y
  end

  def to_s
    "(#{@x}, #{@y})"
  end
end

v1 = Vector2D.new(3, 4)
v2 = Vector2D.new(1, 2)

puts "v1 = #{v1}"
puts "v2 = #{v2}"
puts "v1 + v2 = #{v1 + v2}"
puts "v1 - v2 = #{v1 - v2}"
puts "v1 * 2 = #{v1 * 2}"
puts "v1 == v2: #{v1 == v2}"

# Generics in Crystal
class Stack(T)
  @data = Array(T).new(100)
  @top = -1

  def push(val : T)
    @top += 1
    @data[@top] = val
  end

  def pop : T
    val = @data[@top]
    @top -= 1
    val
  end

  def peek : T
    @data[@top]
  end

  def empty?
    @top == -1
  end
end

def max(a : T, b : T) forall T
  a > b ? a : b
end

def swap(a, b)
  {b, a}
end

struct Pair(K, V)
  property key : K
  property value : V

  def initialize(@key : K, @value : V)
  end

  def print
    puts "#{@key} -> #{@value}"
  end
end

puts max(10, 20)
puts max(3.5, 2.1)
puts max("B", "A")

si = Stack(Int32).new
si.push(1)
si.push(2)
si.push(3)
puts "#{si.pop} #{si.pop}"

p = Pair(String, Int32).new("age", 25)
p.print

# Collections - Lists
list = [5, 2, 8, 1, 9, 3]

# Add elements
list << 7
list.insert(0, 0)

# Count and capacity
puts "Count: #{list.size}"
puts "Capacity: #{list.capacity}"

# Iterate
puts list.join(" ")

# Sort
list.sort!
puts list.join(" ")

# Find and remove
list.delete(8)

# 2D List
mat = Array.new(3) { Array.new(3, 0) }
mat[1][1] = 5
puts "mat[1][1] = #{mat[1][1]}"

# Filter
evens = list.select { |x| x.even? }
puts "Evens: #{evens.join(", ")}"

# Hash and Set
scores = {
  "Alice" => 95,
  "Bob" => 87,
  "Carol" => 92
}

scores.each { |k, v| puts "#{k}: #{v}" }

puts "Alice: #{scores["Alice"]}"
puts "Contains Bob: #{scores.has_key?("Bob")}"

# Set
set = Set{5, 2, 8, 2, 1, 9, 5}
puts set.to_a.join(" ")

set.add(6)
set.delete(2)
puts "Contains 5: #{set.includes?(5)}"

# SortedHash
sorted = SortedHash(String, Int32).new
sorted["banana"] = 3
sorted["apple"] = 5
sorted["cherry"] = 2
sorted.each { |k, v| puts "#{k}: #{v}" }

# Stack, Queue, and PriorityQueue
# Stack (LIFO)
stack = [] of Int32
stack.push(10)
stack.push(20)
stack.push(30)
puts "Stack top: #{stack.last}"
while !stack.empty?
  print "#{stack.pop} "
end
puts

# Queue (FIFO)
queue = Deque(Int32).new
queue.push(10)
queue.push(20)
queue.push(30)
puts "Queue front: #{queue.first}"
while !queue.empty?
  print "#{queue.shift} "
end
puts

# PriorityQueue
pq = PriorityQueue(String, Int32).new
pq.push("Low", 3)
pq.push("High", 1)
pq.push("Medium", 2)
while !pq.empty?
  item = pq.pop
  print "#{item} "
end
puts

# LinkedList
ll = Deque(Int32).new
ll.push(10)
ll.push(20)
ll.unshift(5)
puts ll.to_a.join(" ")

# Exception Handling
class ValidationError < Exception
  getter code : Int32

  def initialize(message : String, @code : Int32)
    super(message)
  end
end

def divide(a : Float64, b : Float64)
  raise ArgumentError.new("Division by zero!") if b == 0
  a / b
end

def get_age(age : Int32)
  if age < 0 || age > 150
    raise ValidationError.new("Invalid age: #{age}", 400)
  end
  age
end

begin
  puts divide(10, 2)
  puts divide(10, 0)
rescue ex : ArgumentError
  puts "Error: #{ex.message}"
end

begin
  get_age(200)
rescue ex : ValidationError
  puts "Validation [#{ex.code}]: #{ex.message}"
rescue ex : Exception
  puts "General: #{ex.message}"
end

begin
  puts "Processing..."
ensure
  puts "Cleanup always runs"
end

# IDisposable and Using Statement
class Resource
  include Disposable

  def initialize(@name : String)
    puts "Resource acquired: #{@name}"
  end

  def use
    puts "Using: #{@name}"
  end

  def dispose
    puts "Resource released: #{@name}"
  end
end

# Using statement (auto-dispose)
Resource.new("FileResource") do |r1|
  r1.use
end

# Manual disposal
r2 = Resource.new("DatabaseResource")
r2.use
r2.dispose

# Try-finally equivalent
r3 = Resource.new("NetworkResource")
begin
  r3.use
ensure
  r3.dispose if r3
end

# Lambdas and Functional Programming
# Basic lambda
greet = ->(name : String) {
  puts "Hello, #{name}!"
}
greet.call("Alice")

# Proc
add = ->(x : Int32, y : Int32) { x + y }
puts "Add: #{add.call(10, 20)}"

# Lambda with closures
x = 10
add_x = ->{ x + 5 }
puts "addX: #{add_x.call}"

# Functional with arrays
nums = [5, 1, 8, 3, 9, 2, 7]

# Sort
nums.sort!
puts nums.join(" ")

# Filter
evens = nums.select { |n| n.even? }
puts "Evens: #{evens.join(" ")}"

# Transform
squares = nums.map { |n| n * n }
puts "Squares: #{squares.join(" ")}"

# Reduce
sum = nums.reduce(0) { |acc, n| acc + n }
puts "Sum: #{sum}"

# Async/Await and Fibers
require "fiber"

def fetch_data(url : String, delay : Int32)
  Fiber.yield
  "Data from #{url}"
end

def compute(a : Int32, b : Int32)
  Fiber.yield
  a + b
end

# Basic async
fiber1 = Fiber.new do
  result = fetch_data("api.example.com", 500)
  puts result
end
fiber1.resume

# Parallel async tasks
fibers = [] of Fiber
["source1", "source2", "source3"].each do |url|
  fibers << Fiber.new { puts fetch_data(url, 200) }
end
fibers.each { |f| f.resume }

# Channel for communication
channel = Channel(String).new

spawn do
  channel.send "Data from channel"
end

puts channel.receive

# Parallel processing with channels
numbers = (1..10).to_a
results = [] of Int32

numbers.each do |n|
  spawn do
    Fiber.yield
    results << n * n
  end
end

Fiber.yield
puts "Squares: #{results.join(", ")}"

# File I/O in Crystal
# Write to file
File.write("students.txt", <<-TEXT
Alice 20 3.85
Bob 22 3.62
Carol 21 3.91
TEXT
)

# Read from file
content = File.read_lines("students.txt")
content.each { |line| puts line }

# Read/Write with File
File.open("output.txt", "w") do |file|
  file.puts "Hello, World!"
  file.puts "Line 2"
end

File.open("output.txt", "r") do |file|
  text = file.gets_to_end
  puts text
end

# File operations
File.delete("temp.txt") if File.exists?("temp.txt")

# Directory operations
Dir.mkdir("testdir")
Dir.rmdir("testdir")

# FileInfo
fi = File.info("students.txt")
puts "File size: #{fi.size} bytes"
puts "Created: #{fi.creation_time}"

# CSV parsing
csv = "Alice,Bob,Carol,Dave"
csv.split(',').each { |token| print "#{token} " }
puts

# LINQ and Functional Programming
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

# Unique and sort
unique = nums.uniq.sort
puts "Unique: #{unique.join(" ")}"

# Aggregation
puts "Sum: #{nums.sum}"
puts "Min: #{nums.min}"
puts "Max: #{nums.max}"
puts "Avg: #{nums.average}"

# Conditional counts
evens = nums.count { |x| x.even? }
puts "Evens: #{evens}"

first_greater = nums.find { |x| x > 4 }
puts "First > 4: #{first_greater}"

# Transform
doubled = nums.map { |x| x * 2 }
puts "Doubled: #{doubled.join(" ")}"

# Group by
grouped = nums.group_by { |x| x.even? ? "Even" : "Odd" }
grouped.each { |k, v| puts "#{k}: #{v.join(", ")}" }

# Zip
a = [1, 2, 3]
b = [4, 5, 6]
zipped = a.zip(b).map { |x, y| x + y }
puts "Zipped sum: #{zipped.join(", ")}"

# LinkedList Implementation
class Node(T)
  property data : T
  property next : Node(T)?

  def initialize(@data : T)
    @next = nil
  end
end

class LinkedList(T)
  @head : Node(T)? = nil

  def push_front(val : T)
    node = Node(T).new(val)
    node.next = @head
    @head = node
  end

  def push_back(val : T)
    node = Node(T).new(val)
    if @head.nil?
      @head = node
      return
    end
    curr = @head
    while !curr.next.nil?
      curr = curr.next.not_nil!
    end
    curr.next = node
  end

  def display
    curr = @head
    while !curr.nil?
      print "#{curr.data} -> "
      curr = curr.next
    end
    puts "null"
  end
end

list = LinkedList(Int32).new
list.push_back(10)
list.push_back(20)
list.push_back(30)
list.push_front(5)
list.display

# Binary Search and Sorting
def binary_search(arr : Array(Int32), target : Int32)
  left = 0
  right = arr.size - 1
  while left <= right
    mid = left + (right - left) // 2
    return mid if arr[mid] == target
    if arr[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  -1
end

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# Manual
puts "Index of 23: #{binary_search(arr, 23)}"

# Built-in binary search
puts "Index of 56: #{arr.bsearch_index { |x| x >= 56 }}"

# Contains
puts "Contains 56: #{arr.includes?(56)}"

# Find methods
found = arr.find { |x| x > 20 }
puts "First > 20: #{found}"

# Find all
greater = arr.select { |x| x > 30 }
puts " > 30: #{greater.join(", ")}"

# Sort
arr.sort!
puts "Sorted: #{arr.join(" ")}"

# Recursion in Crystal
def factorial(n : Int32) : Int32
  return 1 if n <= 1
  n * factorial(n - 1)
end

def fibonacci(n : Int32) : Int32
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

def hanoi(n : Int32, from : Char, to : Char, aux : Char)
  if n == 1
    puts "Move disk 1: #{from} -> #{to}"
    return
  end
  hanoi(n - 1, from, aux, to)
  puts "Move disk #{n}: #{from} -> #{to}"
  hanoi(n - 1, aux, to, from)
end

def power(base : Int32, exp : Int32) : Int32
  return 1 if exp == 0
  if exp.even?
    half = power(base, exp // 2)
    half * half
  else
    base * power(base, exp - 1)
  end
end

puts "5! = #{factorial(5)}"
puts "fib(8) = #{fibonacci(8)}"
puts "2^10 = #{power(2, 10)}"
puts "Tower of Hanoi (3 disks):"
hanoi(3, 'A', 'C', 'B')

# Sorting Algorithms in Crystal
def bubble_sort(arr)
  n = arr.size
  (n - 1).times do |i|
    swapped = false
    (0...n - i - 1).each do |j|
      if arr[j] > arr[j + 1]
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        swapped = true
      end
    end
    break unless swapped
  end
end

def merge_sort(arr)
  return arr if arr.size <= 1
  mid = arr.size // 2
  left = merge_sort(arr[0...mid])
  right = merge_sort(arr[mid..-1])
  merge(left, right)
end

def merge(left, right)
  result = [] of Int32
  i, j = 0, 0
  while i < left.size && j < right.size
    if left[i] <= right[j]
      result << left[i]
      i += 1
    else
      result << right[j]
      j += 1
    end
  end
  result.concat(left[i..-1]) if i < left.size
  result.concat(right[j..-1]) if j < right.size
  result
end

v1 = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(v1)
puts "Bubble: #{v1.join(" ")}"

v2 = [38, 27, 43, 3, 9, 82, 10]
v2 = merge_sort(v2)
puts "Merge: #{v2.join(" ")}"

# Built-in sort
v3 = [5, 3, 1, 8, 2, 7]
v3.sort!
puts "Built-in: #{v3.join(" ")}"

v3.sort! { |a, b| b <=> a }
puts "Descending: #{v3.join(" ")}"

# Dynamic Memory and Garbage Collection
class Matrix
  property rows : Int32
  property cols : Int32
  property data : Array(Array(Int32))

  def initialize(@rows : Int32, @cols : Int32)
    @data = Array.new(@rows) { Array.new(@cols, 0) }
  end

  def set(r : Int32, c : Int32, val : Int32)
    @data[r][c] = val
  end

  def get(r : Int32, c : Int32) : Int32
    @data[r][c]
  end

  def print
    @data.each do |row|
      puts row.join(" ")
    end
  end

  def finalize
    # Clean up resources if needed
  end
end

# Arrays
arr = [10, 20, 30, 40, 50]
puts arr.join(" ")

# Multi-dimensional array
matrix = Matrix.new(3, 3)
matrix.set(0, 0, 1)
matrix.set(1, 1, 5)
matrix.set(2, 2, 9)
matrix.print

# Jagged array
jagged = [
  [1, 2],
  [3, 4, 5],
  [6]
]

# Garbage Collection
puts "Total memory: #{GC.heap_size}"
GC.collect
puts "After GC: #{GC.heap_size}"

# String Operations in Crystal
s = "Hello, World!"

# Basic operations
puts "Length: #{s.size}"
puts "Substring: #{s[7, 5]}"
puts "Contains: #{s.includes?("World")}"
puts "Index of: #{s.index("World")}"

# StringBuilder (mutable string)
sb = String.build do |str|
  str << "Hello"
  str << ", World!"
  str.insert(6, " Crystal")
end
puts sb

# Case conversion
lower = s.downcase
upper = s.upcase
puts "Lower: #{lower}"
puts "Upper: #{upper}"

# Split and join
csv = "Alice,Bob,Carol,Dave"
tokens = csv.split(',')
puts tokens.join(" ")

# String interpolation
name = "Alice"
age = 25
puts "#{name} is #{age} years old"

# Trim and padding
padded = "  Hello  "
puts "Trimmed: '#{padded.strip}'"
puts "Padded: '#{padded.rjust(10)}'"

# Reverse and palindrome
pal = "racecar"
reversed = pal.reverse
puts "#{pal} is palindrome: #{pal == reversed}"

# Interfaces and Abstract Classes
module Drawable
  abstract def draw
  abstract def resize(factor : Float64)
  abstract def area : Float64
end

abstract class Shape
  include Drawable
end

class Circle < Shape
  def initialize(@radius : Float64)
  end

  def draw
    puts "Drawing Circle r=#{@radius}"
  end

  def resize(factor : Float64)
    @radius *= factor
  end

  def area
    Math::PI * @radius * @radius
  end
end

class Square < Shape
  def initialize(@side : Float64)
  end

  def draw
    puts "Drawing Square s=#{@side}"
  end

  def resize(factor : Float64)
    @side *= factor
  end

  def area
    @side * @side
  end
end

shapes = [
  Circle.new(5.0),
  Square.new(4.0)
]

shapes.each do |s|
  s.draw
  puts "Area: #{s.area}"
  s.resize(2.0)
  s.draw
  puts "New Area: #{s.area}"
end

# Multiple Inheritance via Modules
module Vehicle
  property speed : Int32

  abstract def move
end

module Electric
  property battery : Int32

  abstract def charge
end

class ElectricCar
  include Vehicle
  include Electric

  property model : String

  def initialize(@model : String, @speed : Int32, @battery : Int32)
  end

  def display
    puts "Model: #{@model}"
    puts "Speed: #{@speed} km/h"
    puts "Battery: #{@battery}%"
  end

  def move
    puts "#{@model} glides silently at #{@speed} km/h"
  end

  def charge
    puts "Charging battery: #{@battery}%"
  end
end

tesla = ElectricCar.new("Tesla Model 3", 250, 85)
tesla.display
tesla.move
tesla.charge

# Extension Methods
module StringExtensions
  def is_palindrome? : Bool
    cleaned = self.gsub(/[^a-zA-Z0-9]/, "").downcase
    cleaned == cleaned.reverse
  end

  def to_title_case : String
    self[0].upcase + self[1..-1].downcase
  end
end

struct String
  include StringExtensions
end

module ListExtensions
  def second
    raise "List has less than 2 elements" if size < 2
    self[1]
  end

  def last_or_default(default)
    empty? ? default : last
  end
end

class Array(T)
  include ListExtensions
end

# Extension methods on strings
text = "racecar"
puts "#{text} is palindrome: #{text.is_palindrome?}"

name = "alice"
puts "Title case: #{name.to_title_case}"

# Extension methods on lists
numbers = [10, 20, 30, 40]
puts "Second: #{numbers.second}"
puts "LastOrDefault(100): #{numbers.last_or_default(100)}"

empty = [] of Int32
puts "Empty LastOrDefault: #{empty.last_or_default(100)}"

# Chaining
result = numbers.select { |x| x > 15 }.map { |x| x * 2 }
puts "Chained: #{result.join(", ")}"

# Design Patterns - Singleton and Factory
# Singleton
class Config
  class_getter instance : Config = Config.new

  @db_url = "localhost:5432"

  private def initialize
  end

  def db_url
    @db_url
  end

  def db_url=(value)
    @db_url = value
  end
end

# Factory Pattern
interface Logger
  def log(message : String)
end

class ConsoleLogger
  include Logger

  def log(message : String)
    puts "[CONSOLE] #{message}"
  end
end

class FileLogger
  include Logger

  def log(message : String)
    puts "[FILE] #{message}"
  end
end

def create_logger(type : String) : Logger?
  case type.downcase
  when "console" then ConsoleLogger.new
  when "file" then FileLogger.new
  else nil
  end
end

cfg = Config.instance
puts cfg.db_url

logger = create_logger("console")
logger.try &.log("App started")

flog = create_logger("file")
flog.try &.log("Error occurred")

# Modules and Namespaces
module MathUtils
  PI = 3.14159265358979

  module Geometry
    def self.circle_area(r : Float64)
      PI * r * r
    end

    def self.rect_area(w : Float64, h : Float64)
      w * h
    end
  end

  module Advanced
    module Algebra
      def self.power(base : Float64, exp : Int32)
        result = 1.0
        exp.times { result *= base }
        result
      end
    end
  end
end

module Physics
  G = 9.81

  module Mechanics
    def self.kinetic_energy(m : Float64, v : Float64)
      0.5 * m * v * v
    end

    def self.weight(mass : Float64)
      mass * G
    end
  end
end

include MathUtils::Geometry
include MathUtils::Advanced::Algebra

puts "PI = #{MathUtils::PI}"
puts "Circle area = #{circle_area(5.0)}"
puts "2^8 = #{power(2.0, 8)}"
puts "Weight(70kg) = #{Physics::Mechanics.weight(70)} N"

# Using alias
Math = MathUtils::Geometry
puts "Rect area = #{Math.rect_area(4, 5)}"

# Two Sum Problem in Crystal
# Hash map approach O(n)
def two_sum(nums : Array(Int32), target : Int32)
  map = {} of Int32 => Int32
  nums.each_with_index do |num, i|
    complement = target - num
    return {map[complement], i} if map.has_key?(complement)
    map[num] = i
  end
  nil
end

# Two pointer (sorted input)
def two_sum_pairs(arr : Array(Int32), target : Int32)
  result = [] of Tuple(Int32, Int32)
  l = 0
  r = arr.size - 1
  while l < r
    sum = arr[l] + arr[r]
    if sum == target
      result << {arr[l], arr[r]}
      l += 1
      r -= 1
    elsif sum < target
      l += 1
    else
      r -= 1
    end
  end
  result
end

nums = [2, 7, 11, 15]
res = two_sum(nums, 9)
puts "Indices: [#{res[0]}, #{res[1]}]"

sorted = [1, 2, 3, 4, 6]
two_sum_pairs(sorted, 6).each do |a, b|
  puts "Pair: #{a} + #{b}"
end

# Kadane's Algorithm in Crystal
def max_subarray(arr : Array(Int32))
  max_sum = Int32::MIN
  curr_sum = 0
  start = 0
  temp_start = 0
  end_idx = 0

  arr.each_with_index do |val, i|
    curr_sum += val
    if curr_sum > max_sum
      max_sum = curr_sum
      start = temp_start
      end_idx = i
    end
    if curr_sum < 0
      curr_sum = 0
      temp_start = i + 1
    end
  end
  {max_sum, start, end_idx}
end

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sum, s, e = max_subarray(arr)

puts "Max Sum: #{sum}"
print "Subarray: "
(s..e).each { |i| print "#{arr[i]} " }
puts

# Binary Tree in Crystal
class TreeNode(T)
  property val : T
  property left : TreeNode(T)?
  property right : TreeNode(T)?

  def initialize(@val : T)
    @left = nil
    @right = nil
  end
end

class BinaryTree(T)
  @root : TreeNode(T)? = nil

  def insert(val : T)
    node = TreeNode(T).new(val)
    if @root.nil?
      @root = node
      return
    end
    queue = Deque(TreeNode(T)).new
    queue.push(@root.not_nil!)
    while !queue.empty?
      curr = queue.shift
      if curr.left.nil?
        curr.left = node
        return
      else
        queue.push(curr.left.not_nil!)
      end
      if curr.right.nil?
        curr.right = node
        return
      else
        queue.push(curr.right.not_nil!)
      end
    end
  end

  def inorder
    inorder_rec(@root)
    puts
  end

  def inorder_rec(node : TreeNode(T)?)
    return if node.nil?
    inorder_rec(node.not_nil!.left)
    print "#{node.not_nil!.val} "
    inorder_rec(node.not_nil!.right)
  end

  def height : Int32
    height_rec(@root)
  end

  def height_rec(node : TreeNode(T)?) : Int32
    return 0 if node.nil?
    1 + Math.max(height_rec(node.not_nil!.left), height_rec(node.not_nil!.right))
  end
end

bt = BinaryTree(Int32).new
[1, 2, 3, 4, 5, 6, 7].each { |v| bt.insert(v) }
bt.inorder
puts "Height: #{bt.height}"

# Binary Search Tree in Crystal
class BST
  property val : Int32
  property left : BST?
  property right : BST?

  def initialize(@val : Int32)
    @left = nil
    @right = nil
  end
end

def insert(root : BST?, val : Int32) : BST
  return BST.new(val) if root.nil?
  if val < root.val
    root.left = insert(root.left, val)
  elsif val > root.val
    root.right = insert(root.right, val)
  end
  root
end

def search(root : BST?, val : Int32) : Bool
  return false if root.nil?
  return true if root.val == val
  val < root.val ? search(root.left, val) : search(root.right, val)
end

def inorder(root : BST?)
  return if root.nil?
  inorder(root.left)
  print "#{root.val} "
  inorder(root.right)
end

root : BST? = nil
[50, 30, 70, 20, 40, 60, 80].each { |v| root = insert(root, v) }

inorder(root)
puts
puts "Search 40: #{search(root, 40) ? "Found" : "Not found"}"
puts "Search 99: #{search(root, 99) ? "Found" : "Not found"}"

# Graph BFS and DFS in Crystal
class Graph
  property v : Int32
  property adj : Array(Array(Int32))

  def initialize(@v : Int32)
    @adj = Array.new(@v) { [] of Int32 }
  end

  def add_edge(u : Int32, v : Int32)
    @adj[u] << v
    @adj[v] << u
  end

  def bfs(start : Int32)
    visited = Array.new(@v, false)
    queue = Deque(Int32).new
    visited[start] = true
    queue.push(start)
    print "BFS: "
    while !queue.empty?
      v = queue.shift
      print "#{v} "
      @adj[v].each do |u|
        if !visited[u]
          visited[u] = true
          queue.push(u)
        end
      end
    end
    puts
  end

  def dfs(start : Int32)
    visited = Array.new(@v, false)
    print "DFS: "
    dfs_rec(start, visited)
    puts
  end

  def dfs_rec(v : Int32, visited : Array(Bool))
    visited[v] = true
    print "#{v} "
    @adj[v].each do |u|
      dfs_rec(u, visited) if !visited[u]
    end
  end
end

g = Graph.new(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)
g.bfs(0)
g.dfs(0)

# Dijkstra's Algorithm in Crystal
def dijkstra(graph : Array(Array(Tuple(Int32, Int32))), src : Int32)
  v = graph.size
  dist = Array.new(v, Int32::MAX)
  visited = Array.new(v, false)
  dist[src] = 0

  v.times do
    # Find minimum distance vertex
    min_dist = Int32::MAX
    min_vertex = -1
    v.times do |i|
      if !visited[i] && dist[i] < min_dist
        min_dist = dist[i]
        min_vertex = i
      end
    end
    break if min_vertex == -1

    visited[min_vertex] = true
    graph[min_vertex].each do |w, neighbor|
      if !visited[neighbor] && dist[min_vertex] + w < dist[neighbor]
        dist[neighbor] = dist[min_vertex] + w
      end
    end
  end

  puts "Shortest distances from #{src}:"
  v.times do |i|
    puts "  To #{i}: #{dist[i] == Int32::MAX ? -1 : dist[i]}"
  end
end

v = 5
graph = Array.new(v) { [] of Tuple(Int32, Int32) }

def add_edge(graph, u, v, w)
  graph[u] << {w, v}
  graph[v] << {w, u}
end

add_edge(graph, 0, 1, 10)
add_edge(graph, 0, 3, 5)
add_edge(graph, 1, 2, 1)
add_edge(graph, 1, 3, 2)
add_edge(graph, 2, 4, 4)
add_edge(graph, 3, 4, 9)

dijkstra(graph, 0)

# Dynamic Programming - Classic Problems
# 0/1 Knapsack
def knapsack(weights : Array(Int32), values : Array(Int32), w : Int32)
  n = weights.size
  dp = Array.new(n + 1) { Array.new(w + 1, 0) }
  (1..n).each do |i|
    (0..w).each do |j|
      dp[i][j] = dp[i - 1][j]
      if weights[i - 1] <= j
        val = dp[i - 1][j - weights[i - 1]] + values[i - 1]
        dp[i][j] = Math.max(dp[i][j], val)
      end
    end
  end
  dp[n][w]
end

# Longest Common Subsequence
def lcs(s1 : String, s2 : String)
  m = s1.size
  n = s2.size
  dp = Array.new(m + 1) { Array.new(n + 1, 0) }
  (1..m).each do |i|
    (1..n).each do |j|
      if s1[i - 1] == s2[j - 1]
        dp[i][j] = dp[i - 1][j - 1] + 1
      else
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      end
    end
  end
  dp[m][n]
end

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
puts "Knapsack(W=7): #{knapsack(weights, values, 7)}"

s1 = "ABCBDAB"
s2 = "BDCAB"
puts "LCS: #{lcs(s1, s2)}"

# Hash Map - Custom Implementation
class HashMap(K, V)
  @capacity : Int32
  @table : Array(Array(Tuple(K, V)))

  def initialize(capacity : Int32 = 16)
    @capacity = capacity
    @table = Array.new(capacity) { [] of Tuple(K, V) }
  end

  private def hash(key : K) : Int32
    key.hash.abs % @capacity
  end

  def put(key : K, value : V)
    idx = hash(key)
    @table[idx].each_with_index do |kvp, i|
      if kvp[0] == key
        @table[idx][i] = {key, value}
        return
      end
    end
    @table[idx] << {key, value}
  end

  def get(key : K) : V
    idx = hash(key)
    @table[idx].each do |k, v|
      return v if k == key
    end
    raise "Key not found"
  end

  def has_key?(key : K) : Bool
    idx = hash(key)
    @table[idx].any? { |k, v| k == key }
  end

  def delete(key : K)
    idx = hash(key)
    @table[idx].reject! { |k, v| k == key }
  end
end

map = HashMap(String, Int32).new
map.put("alice", 90)
map.put("bob", 85)
map.put("carol", 92)
puts "alice: #{map.get("alice")}"
puts "Contains bob: #{map.has_key?("bob")}"
map.delete("bob")
puts "Contains bob after delete: #{map.has_key?("bob")}"

# Heap and Priority Queue in Crystal
# K largest elements
def k_largest(arr : Array(Int32), k : Int32)
  min_heap = [] of Int32
  arr.each do |x|
    min_heap << x
    min_heap.sort!
    if min_heap.size > k
      min_heap.shift
    end
  end
  min_heap
end

# Merge K sorted arrays
def merge_k_sorted(arrays : Array(Array(Int32)))
  pq = PriorityQueue(Tuple(Int32, Int32, Int32), Int32).new
  arrays.each_with_index do |arr, i|
    pq.push({arr[0], i, 0}, arr[0]) if arr.size > 0
  end

  result = [] of Int32
  while !pq.empty?
    val, i, j = pq.pop
    result << val
    if j + 1 < arrays[i].size
      next_val = arrays[i][j + 1]
      pq.push({next_val, i, j + 1}, next_val)
    end
  end
  result
end

arr = [3, 1, 5, 12, 2, 11, 9]
top3 = k_largest(arr, 3)
puts "Top 3: #{top3.join(" ")}"

k_arr = [
  [1, 4, 7],
  [2, 5, 8],
  [3, 6, 9]
]
merged = merge_k_sorted(k_arr)
puts "Merged: #{merged.join(" ")}"

# Trie Data Structure in Crystal
class TrieNode
  property children : Hash(Char, TrieNode)
  property is_end : Bool

  def initialize
    @children = {} of Char => TrieNode
    @is_end = false
  end
end

class Trie
  @root : TrieNode

  def initialize
    @root = TrieNode.new
  end

  def insert(word : String)
    curr = @root
    word.each_char do |c|
      if !curr.children.has_key?(c)
        curr.children[c] = TrieNode.new
      end
      curr = curr.children[c]
    end
    curr.is_end = true
  end

  def search(word : String) : Bool
    curr = @root
    word.each_char do |c|
      return false if !curr.children.has_key?(c)
      curr = curr.children[c]
    end
    curr.is_end
  end

  def starts_with(prefix : String) : Bool
    curr = @root
    prefix.each_char do |c|
      return false if !curr.children.has_key?(c)
      curr = curr.children[c]
    end
    true
  end
end

t = Trie.new
t.insert("apple")
t.insert("app")
t.insert("apply")
puts "Search apple: #{t.search("apple")}"
puts "Search app: #{t.search("app")}"
puts "Search ap: #{t.search("ap")}"
puts "StartsWith appl: #{t.starts_with("appl")}"
puts "StartsWith xyz: #{t.starts_with("xyz")}"

# Segment Tree in Crystal
class SegmentTree
  @tree : Array(Int32)
  @n : Int32

  def initialize(arr : Array(Int32))
    @n = arr.size
    @tree = Array.new(4 * @n, 0)
    build(arr, 1, 0, @n - 1)
  end

  def build(arr, node, l, r)
    if l == r
      @tree[node] = arr[l]
      return
    end
    mid = (l + r) // 2
    build(arr, node * 2, l, mid)
    build(arr, node * 2 + 1, mid + 1, r)
    @tree[node] = @tree[node * 2] + @tree[node * 2 + 1]
  end

  def update(idx : Int32, val : Int32)
    update(1, 0, @n - 1, idx, val)
  end

  def update(node, l, r, idx, val)
    if l == r
      @tree[node] = val
      return
    end
    mid = (l + r) // 2
    if idx <= mid
      update(node * 2, l, mid, idx, val)
    else
      update(node * 2 + 1, mid + 1, r, idx, val)
    end
    @tree[node] = @tree[node * 2] + @tree[node * 2 + 1]
  end

  def query(ql : Int32, qr : Int32) : Int32
    query(1, 0, @n - 1, ql, qr)
  end

  def query(node, l, r, ql, qr)
    return 0 if qr < l || r < ql
    return @tree[node] if ql <= l && r <= qr
    mid = (l + r) // 2
    query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr)
  end
end

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree.new(arr)
puts "Sum [1,3]: #{st.query(1, 3)}"
st.update(1, 10)
puts "Sum [1,3] after update: #{st.query(1, 3)}"

# Union-Find in Crystal
class UnionFind
  @parent : Array(Int32)
  @rank : Array(Int32)

  def initialize(n : Int32)
    @parent = (0...n).to_a
    @rank = Array.new(n, 0)
  end

  def find(x : Int32) : Int32
    if @parent[x] != x
      @parent[x] = find(@parent[x])
    end
    @parent[x]
  end

  def unite(x : Int32, y : Int32) : Bool
    px = find(x)
    py = find(y)
    return false if px == py
    if @rank[px] < @rank[py]
      px, py = py, px
    end
    @parent[py] = px
    if @rank[px] == @rank[py]
      @rank[px] += 1
    end
    true
  end

  def connected(x : Int32, y : Int32) : Bool
    find(x) == find(y)
  end
end

uf = UnionFind.new(6)
uf.unite(0, 1)
uf.unite(1, 2)
uf.unite(3, 4)
puts "0-2: #{uf.connected(0, 2)}"
puts "0-3: #{uf.connected(0, 3)}"
uf.unite(2, 3)
puts "0-4 after merge: #{uf.connected(0, 4)}"

# Sliding Window Maximum in Crystal
def max_sliding_window(nums : Array(Int32), k : Int32)
  dq = Deque(Int32).new
  result = [] of Int32

  nums.each_with_index do |num, i|
    # Remove out-of-window indices
    while !dq.empty? && dq.first < i - k + 1
      dq.shift
    end

    # Remove smaller elements from rear
    while !dq.empty? && nums[dq.last] < nums[i]
      dq.pop
    end

    dq.push(i)

    if i >= k - 1
      result << nums[dq.first]
    end
  end
  result
end

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
res = max_sliding_window(nums, k)
puts "Sliding window max: #{res.join(" ")}"

# KMP String Matching in Crystal
def build_lps(pattern : String)
  m = pattern.size
  lps = Array.new(m, 0)
  len = 0
  i = 1
  while i < m
    if pattern[i] == pattern[len]
      len += 1
      lps[i] = len
      i += 1
    elsif len > 0
      len = lps[len - 1]
    else
      lps[i] = 0
      i += 1
    end
  end
  lps
end

def kmp_search(text : String, pattern : String)
  positions = [] of Int32
  lps = build_lps(pattern)
  n = text.size
  m = pattern.size
  i = 0
  j = 0

  while i < n
    if text[i] == pattern[j]
      i += 1
      j += 1
    end
    if j == m
      positions << i - j
      j = lps[j - 1]
    elsif i < n && text[i] != pattern[j]
      if j > 0
        j = lps[j - 1]
      else
        i += 1
      end
    end
  end
  positions
end

text = "AABAACAADAABAABA"
pat = "AABA"
pos = kmp_search(text, pat)
puts "Pattern found at: #{pos.join(" ")}"

# N-Queens in Crystal
class NQueens
  @n : Int32
  @board : Array(Array(Int32))
  @solutions : Int32 = 0

  def initialize(@n : Int32)
    @board = Array.new(@n) { Array.new(@n, 0) }
  end

  def is_safe(row : Int32, col : Int32) : Bool
    # Check row
    (0...col).each do |j|
      return false if @board[row][j] == 1
    end
    # Check diagonal up-left
    i = row
    j = col
    while i >= 0 && j >= 0
      return false if @board[i][j] == 1
      i -= 1
      j -= 1
    end
    # Check diagonal down-left
    i = row
    j = col
    while i < @n && j >= 0
      return false if @board[i][j] == 1
      i += 1
      j -= 1
    end
    true
  end

  def solve(col : Int32)
    if col == @n
      @solutions += 1
      if @solutions == 1
        @board.each do |row|
          puts row.map { |x| x == 1 ? "Q" : "." }.join(" ")
        end
      end
      return
    end

    (0...@n).each do |row|
      if is_safe(row, col)
        @board[row][col] = 1
        solve(col + 1)
        @board[row][col] = 0
      end
    end
  end

  def run
    solve(0)
    puts "Total solutions: #{@solutions}"
  end
end

q = NQueens.new(8)
q.run

# LRU Cache in Crystal
class LRUCache(K, V)
  @capacity : Int32
  @cache : Deque({K, V})
  @map : Hash(K, Deque({K, V})::Node?)

  def initialize(@capacity : Int32)
    @cache = Deque({K, V}).new
    @map = {} of K => Deque({K, V})::Node?
  end

  def get(key : K) : V?
    return nil unless @map.has_key?(key)
    node = @map[key].not_nil!
    value = node.value[1]
    @cache.delete(node)
    @cache.push({key, value})
    @map[key] = @cache.last
    value
  end

  def put(key : K, value : V)
    if @map.has_key?(key)
      node = @map[key].not_nil!
      @cache.delete(node)
      @map.delete(key)
    end
    if @cache.size == @capacity
      first_key, _ = @cache.shift
      @map.delete(first_key)
    end
    @cache.push({key, value})
    @map[key] = @cache.last
  end
end

lru = LRUCache(Int32, Int32).new(2)
lru.put(1, 10)
lru.put(2, 20)
puts lru.get(1)
lru.put(3, 30)
puts lru.get(2)
puts lru.get(3)

# Graph - Topological Sort in Crystal
def topo_sort(v : Int32, adj : Array(Array(Int32)))
  in_degree = Array.new(v, 0)
  (0...v).each do |u|
    adj[u].each { |v| in_degree[v] += 1 }
  end

  queue = Deque(Int32).new
  (0...v).each do |i|
    queue.push(i) if in_degree[i] == 0
  end

  order = [] of Int32
  while !queue.empty?
    u = queue.shift
    order << u
    adj[u].each do |v|
      in_degree[v] -= 1
      queue.push(v) if in_degree[v] == 0
    end
  end

  order.size == v ? order : [] of Int32
end

v = 6
adj = Array.new(v) { [] of Int32 }

adj[5] << 2
adj[5] << 0
adj[4] << 0
adj[4] << 1
adj[2] << 3
adj[3] << 1

order = topo_sort(v, adj)
puts "Topological Order: #{order.join(" ")}"

# Bit Manipulation in Crystal
def is_bit_set(n : Int32, p : Int32) : Bool
  (n >> p) & 1 == 1
end

def set_bit(n : Int32, p : Int32) : Int32
  n | (1 << p)
end

def clear_bit(n : Int32, p : Int32) : Int32
  n & ~(1 << p)
end

def toggle_bit(n : Int32, p : Int32) : Int32
  n ^ (1 << p)
end

def count_bits(n : Int32) : Int32
  count = 0
  while n > 0
    n &= n - 1
    count += 1
  end
  count
end

def is_power_of_2(n : Int32) : Bool
  n > 0 && (n & (n - 1)) == 0
end

def find_unique(arr : Array(Int32)) : Int32
  result = 0
  arr.each { |x| result ^= x }
  result
end

n = 0b10110100
puts "Number: #{n}"
puts "Bit 2 set? #{is_bit_set(n, 2)}"
puts "Set bit 0: #{set_bit(n, 0)}"
puts "Clear bit 4: #{clear_bit(n, 4)}"
puts "Toggle bit 7: #{toggle_bit(n, 7)}"
puts "Count bits: #{count_bits(n)}"
puts "isPow2(16): #{is_power_of_2(16)}"

arr = [2, 3, 5, 4, 5, 3, 4]
puts "Unique: #{find_unique(arr)}"

# Number Theory in Crystal
def gcd(a : Int32, b : Int32) : Int32
  b == 0 ? a : gcd(b, a % b)
end

def lcm(a : Int32, b : Int32) : Int32
  a // gcd(a, b) * b
end

def is_prime(n : Int32) : Bool
  return false if n < 2
  (2..Math.sqrt(n).to_i).each do |i|
    return false if n % i == 0
  end
  true
end

def sieve(limit : Int32)
  not_prime = Array.new(limit + 1, false)
  not_prime[0] = true if limit >= 0
  not_prime[1] = true if limit >= 1
  (2..Math.sqrt(limit).to_i).each do |i|
    next if not_prime[i]
    (i * i..limit).step(i).each do |j|
      not_prime[j] = true
    end
  end
  (2..limit).select { |i| !not_prime[i] }
end

def mod_pow(base : Int64, exp : Int64, mod : Int64) : Int64
  result = 1_i64
  base %= mod
  while exp > 0
    result = (result * base) % mod if exp.odd?
    base = (base * base) % mod
    exp >>= 1
  end
  result
end

puts "GCD(48,18)=#{gcd(48, 18)}"
puts "LCM(4,6)=#{lcm(4, 6)}"
puts "isPrime(17)=#{is_prime(17)}"

primes = sieve(50)
puts "Primes: #{primes.join(" ")}"

puts "2^10 mod 1000 = #{mod_pow(2, 10, 1000)}"

# Tuple and NamedTuple in Crystal
# Tuple
t1 = {"Alice", 25, 3.85}
puts "#{t1[0]} age=#{t1[1]} gpa=#{t1[2]}"

# NamedTuple
t2 = {name: "Bob", age: 22, gpa: 3.62}
puts "#{t2[:name]} age=#{t2[:age]} gpa=#{t2[:gpa]}"

# NamedTuple deconstruction
n, a, g = t2.values
puts "Deconstructed: #{n}, #{a}, #{g}"

# Named tuple in method return
def get_min_max(nums : Array(Int32))
  {min: nums.min, max: nums.max}
end

result = get_min_max([5, 2, 8, 1, 9])
puts "Min=#{result[:min]}, Max=#{result[:max]}"

# Tuple in collections
students = [
  {"Alice", 90},
  {"Bob", 85},
  {"Carol", 92}
]
students.sort! { |a, b| b[1] <=> a[1] }
students.each do |name, score|
  puts "#{name}: #{score}"
end

# Two Pointers Technique in Crystal
# Container with most water
def max_water(height : Array(Int32))
  l = 0
  r = height.size - 1
  max_area = 0
  while l < r
    area = Math.min(height[l], height[r]) * (r - l)
    max_area = Math.max(max_area, area)
    if height[l] < height[r]
      l += 1
    else
      r -= 1
    end
  end
  max_area
end

# 3-sum
def three_sum(nums : Array(Int32))
  nums.sort!
  result = [] of Array(Int32)
  (0...nums.size - 2).each do |i|
    next if i > 0 && nums[i] == nums[i - 1]
    l = i + 1
    r = nums.size - 1
    while l < r
      sum = nums[i] + nums[l] + nums[r]
      if sum == 0
        result << [nums[i], nums[l], nums[r]]
        l += 1 while l < r && nums[l] == nums[l + 1]
        r -= 1 while l < r && nums[r] == nums[r - 1]
        l += 1
        r -= 1
      elsif sum < 0
        l += 1
      else
        r -= 1
      end
    end
  end
  result
end

h = [1, 8, 6, 2, 5, 4, 8, 3, 7]
puts "Max water: #{max_water(h)}"

nums = [-1, 0, 1, 2, -1, -4]
three_sum(nums).each { |triplet| puts triplet.join(" ") }

# Backtracking in Crystal
# Generate all subsets
def subsets(nums : Array(Int32))
  result = [] of Array(Int32)
  backtrack_subsets(nums, 0, [] of Int32, result)
  result
end

def backtrack_subsets(nums, idx, curr, result)
  result << curr.dup
  (idx...nums.size).each do |i|
    curr << nums[i]
    backtrack_subsets(nums, i + 1, curr, result)
    curr.pop
  end
end

# Generate permutations
def permute(nums : Array(Int32))
  result = [] of Array(Int32)
  permute_helper(nums, 0, result)
  result
end

def permute_helper(nums, start, result)
  if start == nums.size
    result << nums.dup
    return
  end
  (start...nums.size).each do |i|
    nums[start], nums[i] = nums[i], nums[start]
    permute_helper(nums, start + 1, result)
    nums[start], nums[i] = nums[i], nums[start]
  end
end

nums = [1, 2, 3]

subsets = subsets(nums)
puts "Subsets (#{subsets.size}):"
subsets.each { |s| puts "[#{s.join(" ")}]" }

perms = permute(nums)
puts "Permutations (#{perms.size}):"
perms.each { |p| puts p.join(" ") }

# Greedy Algorithms in Crystal
# Activity Selection
def activity_selection(activities : Array({Int32, Int32}))
  activities.sort! { |a, b| a[1] <=> b[1] }
  count = 1
  last_end = activities[0][1]
  (1...activities.size).each do |i|
    if activities[i][0] >= last_end
      count += 1
      last_end = activities[i][1]
    end
  end
  count
end

# Fractional Knapsack
def fractional_knapsack(items : Array({Int32, Int32}), w : Int32)
  items.sort! { |a, b| (b[0].to_f / b[1]) <=> (a[0].to_f / a[1]) }
  total = 0.0
  items.each do |value, weight|
    if w >= weight
      total += value
      w -= weight
    else
      total += (value.to_f / weight) * w
      break
    end
  end
  total
end

acts = [
  {1, 3}, {2, 5}, {4, 6}, {6, 8}, {5, 7}
]
puts "Max activities: #{activity_selection(acts)}"

items = [
  {60, 10}, {100, 20}, {120, 30}
]
puts "Max value (W=50): #{fractional_knapsack(items, 50)}"

# Events and Delegates in Crystal
# Delegate definition
abstract class PriceChangedEventHandler
  abstract def invoke(sender : Stock, e : PriceChangedEventArgs)
end

# Event args
class PriceChangedEventArgs
  getter old_price : Float64
  getter new_price : Float64

  def initialize(@old_price : Float64, @new_price : Float64)
  end
end

# Subject
class Stock
  getter symbol : String
  @price : Float64
  @event_handlers = [] of PriceChangedEventHandler

  def initialize(@symbol : String, @price : Float64)
  end

  def price
    @price
  end

  def price=(value)
    return if @price == value
    old = @price
    @price = value
    on_price_changed(old, @price)
  end

  def add_handler(handler : PriceChangedEventHandler)
    @event_handlers << handler
  end

  def remove_handler(handler : PriceChangedEventHandler)
    @event_handlers.delete(handler)
  end

  def on_price_changed(old_price : Float64, new_price : Float64)
    args = PriceChangedEventArgs.new(old_price, new_price)
    @event_handlers.each { |handler| handler.invoke(self, args) }
  end
end

# Observer
class Investor < PriceChangedEventHandler
  property name : String

  def initialize(@name : String)
  end

  def invoke(sender : Stock, e : PriceChangedEventArgs)
    puts "#{@name} notified: Price changed from $#{e.old_price} to $#{e.new_price}"
  end
end

apple = Stock.new("AAPL", 150.0)
alice = Investor.new("Alice")
bob = Investor.new("Bob")

apple.add_handler(alice)
apple.add_handler(bob)

apple.price = 155.0
apple.price = 160.0

# IDisposable and Resource Management
class FileHandler
  include Disposable

  @filename : String
  @file : File?

  def initialize(@filename : String)
    @file = File.open(@filename, "w")
    puts "File opened: #{@filename}"
  end

  def write(data : String)
    @file.try &.puts(data)
  end

  def dispose
    if file = @file
      file.close
      puts "File closed: #{@filename}"
    end
  end
end

# Using statement - auto dispose
FileHandler.new("test.txt") do |fh|
  fh.write("Hello RAII!")
  fh.write("Line 2")
end

# Manual disposal with try-finally
fh2 = FileHandler.new("test2.txt")
begin
  fh2.write("Data")
ensure
  fh2.dispose
end

# Async and Parallel Programming
require "concurrent"

# Parallel processing
def parallel_process(data : Array(Int32))
  channel = Channel({Int32, Int32}).new(data.size)

  data.each do |item|
    spawn do
      result = item * item
      channel.send({item, result})
    end
  end

  results = {} of Int32 => Int32
  data.size.times do
    item, result = channel.receive
    results[item] = result
  end
  results
end

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
results = parallel_process(numbers)
puts "Squares: #{results.values.join(", ")}"

# Concurrent jobs with fibers
fibers = [] of Fiber
(1..5).each do |i|
  fibers << Fiber.new do
    sleep 0.1
    puts "Task #{i} on fiber #{Fiber.current.object_id}"
  end
end
fibers.each { |f| f.resume }

# Channel for coordination
channel = Channel(String).new

spawn do
  3.times do |i|
    sleep 0.05
    channel.send "Message #{i}"
  end
  channel.close
end

while msg = channel.receive?
  puts "Received: #{msg}"
end

# Regular Expressions in Crystal
# Email validation
email_rx = /^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+.[a-zA-Z]{2,}$/
emails = ["user@example.com", "invalid-email", "hello@world.org"]
emails.each do |e|
  puts "#{e}: #{(email_rx =~ e) ? "Valid" : "Invalid"}"
end

# Search and replace
text = "The quick brown fox jumps over the lazy dog"
replaced = text.gsub(/w{4}/, "****")
puts "Replaced: #{replaced}"

# Find all matches
data = "Price: $100, Discount: $20, Total: $80"
num_rx = /$(d+)/
matches = data.scan(num_rx)
print "Numbers found: "
matches.each { |m| print "#{m[1]} " }
puts

# Named groups
date_rx = /(?<year>d{4})-(?<month>d{2})-(?<day>d{2})/
date_match = "2024-01-15".match(date_rx)
if date_match
  puts "Year: #{date_match["year"]}"
  puts "Month: #{date_match["month"]}"
  puts "Day: #{date_match["day"]}"
end

# Capture groups
word_rx = /(w+)s+(w+)/
sentence = "Hello World"
match = sentence.match(word_rx)
if match
  puts "Word 1: #{match[1]}"
  puts "Word 2: #{match[2]}"
end

# Attributes and Macros in Crystal
# Define a macro for attributes
macro author(name, version = "1.0")
  def author_name
    {{name}}
  end

  def author_version
    {{version}}
  end
end

class Calculator
  author "John Doe", "2.0"

  def add(a : Int32, b : Int32)
    a + b
  end

  def multiply(a : Int32, b : Int32)
    a * b
  end
end

# Get class attributes via macros
calc = Calculator.new
puts "Class Author: #{calc.author_name} (v#{calc.author_version})"

# Reflection - get methods
puts "
All methods:"
Calculator.methods.each { |m| puts "  #{m}" }

# Dynamic invocation
add_method = Calculator.method(:add)
result = add_method.call(calc, 5, 3)
puts "Add(5,3) = #{result}"

mult_method = Calculator.method(:multiply)
mult_result = mult_method.call(calc, 4, 5)
puts "Multiply(4,5) = #{mult_result}"

# Design Patterns - Observer and Command
# Observer Pattern
module Observer
  abstract def update(event_name : String, data : Int32)
end

class Subject
  @observers = [] of Observer
  @data : Int32 = 0

  def subscribe(observer : Observer)
    @observers << observer
  end

  def unsubscribe(observer : Observer)
    @observers.delete(observer)
  end

  def data
    @data
  end

  def data=(value : Int32)
    @data = value
    notify
  end

  def notify
    @observers.each { |o| o.update("Data Changed", @data) }
  end
end

class ConsoleObserver
  include Observer

  def initialize(@name : String)
  end

  def update(event_name : String, data : Int32)
    puts "#{@name} notified: #{event_name} = #{data}"
  end
end

# Command Pattern
interface Command
  def execute
  def undo
end

class Counter
  @value : Int32 = 0

  def increment(n : Int32)
    @value += n
  end

  def decrement(n : Int32)
    @value -= n
  end

  def value
    @value
  end
end

class IncrementCommand
  include Command

  def initialize(@counter : Counter, @amount : Int32)
  end

  def execute
    @counter.increment(@amount)
  end

  def undo
    @counter.decrement(@amount)
  end
end

# Observer
subject = Subject.new
subject.subscribe(ConsoleObserver.new("Observer1"))
subject.subscribe(ConsoleObserver.new("Observer2"))
subject.data = 42
subject.data = 100

# Command
counter = Counter.new
history = [] of Command
history << IncrementCommand.new(counter, 10)
history << IncrementCommand.new(counter, 5)
history.each { |cmd| cmd.execute }
puts "Counter: #{counter.value}"
history.last.undo
puts "After undo: #{counter.value}"

# Functional Programming in Crystal
# Higher-order functions
def map(list : Array(T), fn : T -> T) forall T
  list.map { |x| fn.call(x) }
end

def filter(list : Array(T), pred : T -> Bool) forall T
  list.select { |x| pred.call(x) }
end

def reduce(list : Array(T), init : R, fn : R, T -> R) forall T, R
  list.reduce(init) { |acc, x| fn.call(acc, x) }
end

# Function composition
def compose(f, g)
  ->(x : T) { f.call(g.call(x)) }
end

# Memoization
def memoize(fn)
  cache = {} of typeof(fn.call(0)) => typeof(fn.call(0))
  ->(x : Int32) {
    if !cache.has_key?(x)
      cache[x] = fn.call(x)
    end
    cache[x]
  }
end

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

doubled = map(nums, ->(x : Int32) { x * 2 })
puts "Doubled: #{doubled.join(" ")}"

evens = filter(nums, ->(x : Int32) { x.even? })
puts "Evens: #{evens.join(" ")}"

sum = reduce(nums, 0, ->(acc : Int32, x : Int32) { acc + x })
puts "Sum: #{sum}"

add_one = ->(x : Int32) { x + 1 }
double_it = ->(x : Int32) { x * 2 }
add_then_double = compose(double_it, add_one)
puts "Compose(double, +1)(5) = #{add_then_double.call(5)}"

# Memoized Fibonacci
fib = ->(n : Int32) {
  n <= 1 ? n : fib.call(n - 1) + fib.call(n - 2)
}
memo_fib = memoize(fib)
puts "fib(30) = #{memo_fib.call(30)}"

# Advanced Generics and Constraints in Crystal
# Generic class with constraints
class Repository(T)
  @items = [] of T

  def add(item : T)
    @items << item
  end

  def create
    T.new
  end

  def get_all
    @items
  end
end

class Entity
  property id : Int32
  property name : String

  def initialize(@id : Int32 = 0, @name : String = "")
  end
end

# Generic interface
interface RepositoryInterface(T)
  def add(item : T)
  def get(id : Int32) : T?
end

class GenericRepository(T)
  include RepositoryInterface(T)

  @items = {} of Int32 => T
  @next_id = 1

  def add(item : T)
    @items[@next_id] = item
    @next_id += 1
  end

  def get(id : Int32) : T?
    @items[id]?
  end
end

repo = Repository(Entity).new
e1 = repo.create
e1.name = "Alice"
repo.add(e1)
e2 = repo.create
e2.name = "Bob"
repo.add(e2)

repo.get_all.each { |e| puts e.name }

generic_repo = GenericRepository(Entity).new
generic_repo.add(Entity.new(name: "Carol"))
found = generic_repo.get(1)
puts "Found: #{found.try &.name}"

# Matrix Operations in Crystal
def multiply(a : Array(Array(Int32)), b : Array(Array(Int32)))
  r = a.size
  c = b[0].size
  k = b.size
  result = Array.new(r) { Array.new(c, 0) }
  (0...r).each do |i|
    (0...c).each do |j|
      (0...k).each do |p|
        result[i][j] += a[i][p] * b[p][j]
      end
    end
  end
  result
end

def transpose(a : Array(Array(Int32)))
  r = a.size
  c = a[0].size
  result = Array.new(c) { Array.new(r, 0) }
  (0...r).each do |i|
    (0...c).each do |j|
      result[j][i] = a[i][j]
    end
  end
  result
end

def rotate_90(m : Array(Array(Int32)))
  n = m.size
  # Transpose
  (0...n).each do |i|
    (i + 1...n).each do |j|
      m[i][j], m[j][i] = m[j][i], m[i][j]
    end
  end
  # Reverse each row
  (0...n).each do |i|
    m[i].reverse!
  end
  m
end

def print_matrix(m)
  m.each { |row| puts row.join(" ") }
end

a = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

b = [
  [9, 8, 7],
  [6, 5, 4],
  [3, 2, 1]
]

puts "A*B:"
print_matrix(multiply(a, b))
puts "T(A):"
print_matrix(transpose(a))
puts "A rotated 90CW:"
print_matrix(rotate_90(a))

# Trapping Rain Water in Crystal
def trap(height : Array(Int32))
  l = 0
  r = height.size - 1
  left_max = 0
  right_max = 0
  water = 0

  while l < r
    if height[l] < height[r]
      if height[l] >= left_max
        left_max = height[l]
      else
        water += left_max - height[l]
      end
      l += 1
    else
      if height[r] >= right_max
        right_max = height[r]
      else
        water += right_max - height[r]
      end
      r -= 1
    end
  end
  water
end

h1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
puts "Water trapped: #{trap(h1)}"

h2 = [4, 2, 0, 3, 2, 5]
puts "Water trapped: #{trap(h2)}"

# Longest Increasing Subsequence in Crystal
# DP O(n^2)
def lis_dp(arr : Array(Int32))
  n = arr.size
  dp = Array.new(n, 1)
  (1...n).each do |i|
    (0...i).each do |j|
      if arr[j] < arr[i]
        dp[i] = Math.max(dp[i], dp[j] + 1)
      end
    end
  end
  dp.max
end

# Binary Search O(n log n)
def lis_bs(arr : Array(Int32))
  tails = [] of Int32
  arr.each do |x|
    idx = tails.bsearch_index { |v| v >= x }
    if idx.nil?
      tails << x
    else
      tails[idx] = x
    end
  end
  tails.size
end

arr = [10, 9, 2, 5, 3, 7, 101, 18]
puts "LIS (DP): #{lis_dp(arr)}"
puts "LIS (BS): #{lis_bs(arr)}"

# Bellman-Ford in Crystal
struct Edge
  property u : Int32
  property v : Int32
  property w : Int32

  def initialize(@u : Int32, @v : Int32, @w : Int32)
  end
end

def bellman_ford(edges : Array(Edge), v : Int32, src : Int32)
  dist = Array.new(v, Int32::MAX)
  dist[src] = 0

  (1...v).each do
    edges.each do |e|
      if dist[e.u] != Int32::MAX && dist[e.u] + e.w < dist[e.v]
        dist[e.v] = dist[e.u] + e.w
      end
    end
  end

  # Check negative cycle
  edges.each do |e|
    if dist[e.u] != Int32::MAX && dist[e.u] + e.w < dist[e.v]
      puts "Negative cycle detected!"
      return
    end
  end

  puts "Distances from #{src}:"
  (0...v).each do |i|
    puts "  #{i}: #{dist[i]}"
  end
end

v = 5
edges = [
  Edge.new(0, 1, -1),
  Edge.new(0, 2, 4),
  Edge.new(1, 2, 3),
  Edge.new(1, 3, 2),
  Edge.new(1, 4, 2),
  Edge.new(3, 2, 5),
  Edge.new(3, 1, 1),
  Edge.new(4, 3, -3)
]

bellman_ford(edges, v, 0)

# Floyd-Warshall in Crystal
def floyd_warshall(dist : Array(Array(Int32)))
  v = dist.size
  (0...v).each do |k|
    (0...v).each do |i|
      (0...v).each do |j|
        if dist[i][k] != Int32::MAX && dist[k][j] != Int32::MAX
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
        end
      end
    end
  end

  puts "All-Pairs Shortest Paths:"
  (0...v).each do |i|
    (0...v).each do |j|
      print dist[i][j] == Int32::MAX ? "INF " : "#{dist[i][j]} "
    end
    puts
  end
end

inf = Int32::MAX
graph = [
  [0,   3,   inf, 7  ],
  [8,   0,   2,   inf],
  [5,   inf, 0,   1  ],
  [2,   inf, inf, 0  ]
]

floyd_warshall(graph)

# Kruskal's MST in Crystal
struct Edge
  property u : Int32
  property v : Int32
  property w : Int32

  def initialize(@u : Int32, @v : Int32, @w : Int32)
  end
end

class DSU
  @parent : Array(Int32)
  @rank : Array(Int32)

  def initialize(n : Int32)
    @parent = (0...n).to_a
    @rank = Array.new(n, 0)
  end

  def find(x : Int32) : Int32
    if @parent[x] != x
      @parent[x] = find(@parent[x])
    end
    @parent[x]
  end

  def unite(x : Int32, y : Int32) : Bool
    px = find(x)
    py = find(y)
    return false if px == py
    if @rank[px] < @rank[py]
      px, py = py, px
    end
    @parent[py] = px
    if @rank[px] == @rank[py]
      @rank[px] += 1
    end
    true
  end
end

v = 4
edges = [
  Edge.new(0, 1, 10),
  Edge.new(0, 2, 6),
  Edge.new(0, 3, 5),
  Edge.new(1, 3, 15),
  Edge.new(2, 3, 4)
]

edges.sort! { |a, b| a.w <=> b.w }

dsu = DSU.new(v)
cost = 0
puts "MST Edges:"
edges.each do |e|
  if dsu.unite(e.u, e.v)
    puts "#{e.u} -- #{e.v} (weight #{e.w})"
    cost += e.w
  end
end
puts "MST Cost: #{cost}"

# String Algorithms in Crystal
# Longest palindromic substring
def longest_palindrome(s : String)
  n = s.size
  start = 0
  max_len = 1

  expand = ->(l : Int32, r : Int32) {
    while l >= 0 && r < n && s[l] == s[r]
      l -= 1
      r += 1
    end
    if r - l - 1 > max_len
      max_len = r - l - 1
      start = l + 1
    end
  }

  (0...n).each do |i|
    expand.call(i, i)
    expand.call(i, i + 1)
  end
  s[start, max_len]
end

# Check anagram
def is_anagram(s1 : String, s2 : String)
  return false if s1.size != s2.size
  freq = {} of Char => Int32
  s1.each_char { |c| freq[c] = freq.get(c, 0) + 1 }
  s2.each_char do |c|
    return false if !freq.has_key?(c)
    freq[c] -= 1
    return false if freq[c] < 0
  end
  true
end

# Group anagrams
def group_anagrams(words : Array(String))
  map = {} of String => Array(String)
  words.each do |w|
    key = w.chars.sort.join
    map[key] = map.get(key, [] of String) << w
  end
  map.values
end

puts longest_palindrome("babad")
puts is_anagram("listen", "silent")

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
group_anagrams(words).each { |group| puts group.join(" ") }

# Coin Change and Subset Sum in Crystal
# Minimum coins
def coin_change(coins : Array(Int32), amount : Int32)
  dp = Array.new(amount + 1, Int32::MAX)
  dp[0] = 0
  (1..amount).each do |i|
    coins.each do |c|
      if c <= i && dp[i - c] != Int32::MAX
        dp[i] = Math.min(dp[i], dp[i - c] + 1)
      end
    end
  end
  dp[amount] == Int32::MAX ? -1 : dp[amount]
end

# Count ways
def count_ways(coins : Array(Int32), amount : Int32)
  dp = Array.new(amount + 1, 0)
  dp[0] = 1
  coins.each do |c|
    (c..amount).each do |i|
      dp[i] += dp[i - c]
    end
  end
  dp[amount]
end

# Subset sum
def subset_sum(arr : Array(Int32), target : Int32)
  n = arr.size
  dp = Array.new(n + 1) { Array.new(target + 1, false) }
  (0..n).each { |i| dp[i][0] = true }
  (1..n).each do |i|
    (1..target).each do |j|
      dp[i][j] = dp[i - 1][j]
      if arr[i - 1] <= j
        dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]]
      end
    end
  end
  dp[n][target]
end

coins = [1, 5, 6, 9]
puts "Min coins for 11: #{coin_change(coins, 11)}"
puts "Ways for 10: #{count_ways(coins, 10)}"

arr = [3, 34, 4, 12, 5, 2]
puts "Subset sum 9: #{subset_sum(arr, 9)}"
puts "Subset sum 30: #{subset_sum(arr, 30)}"

# Monotonic Stack Problems
# Next Greater Element
def next_greater(arr : Array(Int32))
  n = arr.size
  result = Array.new(n, -1)
  stack = [] of Int32
  (0...n).each do |i|
    while !stack.empty? && arr[stack.last] < arr[i]
      result[stack.pop] = arr[i]
    end
    stack << i
  end
  result
end

# Largest Rectangle in Histogram
def largest_rect(heights : Array(Int32))
  stack = [] of Int32
  max_area = 0
  h = heights + [0]
  (0...h.size).each do |i|
    while !stack.empty? && h[stack.last] > h[i]
      height = h[stack.pop]
      width = stack.empty? ? i : i - stack.last - 1
      area = height * width
      max_area = Math.max(max_area, area)
    end
    stack << i
  end
  max_area
end

arr = [4, 5, 2, 10, 8]
ng = next_greater(arr)
puts "Next Greater: #{ng.join(" ")}"

h = [2, 1, 5, 6, 2, 3]
puts "Largest Rect: #{largest_rect(h)}"

# Binary Search Variants in Crystal
# Search in rotated sorted array
def search_rotated(arr : Array(Int32), target : Int32)
  l = 0
  r = arr.size - 1
  while l <= r
    mid = (l + r) // 2
    return mid if arr[mid] == target
    if arr[l] <= arr[mid]
      if target >= arr[l] && target < arr[mid]
        r = mid - 1
      else
        l = mid + 1
      end
    else
      if target > arr[mid] && target <= arr[r]
        l = mid + 1
      else
        r = mid - 1
      end
    end
  end
  -1
end

# Find peak element
def find_peak(arr : Array(Int32))
  l = 0
  r = arr.size - 1
  while l < r
    mid = (l + r) // 2
    if arr[mid] > arr[mid + 1]
      r = mid
    else
      l = mid + 1
    end
  end
  l
end

# First and last position
def first_last(arr : Array(Int32), target : Int32)
  first = arr.index(target)
  return {-1, -1} if first.nil?
  last = arr.rindex(target)
  {first, last}
end

rotated = [4, 5, 6, 7, 0, 1, 2]
puts "Search 0: #{search_rotated(rotated, 0)}"

arr = [1, 2, 3, 1]
puts "Peak index: #{find_peak(arr)}"

v = [5, 7, 7, 8, 8, 10]
f, l = first_last(v, 8)
puts "First,Last of 8: #{f},#{l}"

# Product of Array Except Self in Crystal
def product_except_self(nums : Array(Int32))
  n = nums.size
  result = Array.new(n, 1)

  # Left pass
  (1...n).each do |i|
    result[i] = result[i - 1] * nums[i - 1]
  end

  # Right pass
  right = 1
  (n - 1).downto(0).each do |i|
    result[i] *= right
    right *= nums[i]
  end
  result
end

nums = [1, 2, 3, 4]
res = product_except_self(nums)
puts "Output: #{res.join(" ")}"

# Flood Fill and Number of Islands
# Flood Fill
def flood_fill(img, r, c, old_color, new_color)
  return if r < 0 || r >= img.size || c < 0 || c >= img[0].size
  return if img[r][c] != old_color || img[r][c] == new_color
  img[r][c] = new_color
  flood_fill(img, r + 1, c, old_color, new_color)
  flood_fill(img, r - 1, c, old_color, new_color)
  flood_fill(img, r, c + 1, old_color, new_color)
  flood_fill(img, r, c - 1, old_color, new_color)
end

# Number of Islands
def dfs(grid, r, c)
  return if r < 0 || r >= grid.size || c < 0 || c >= grid[0].size
  return if grid[r][c] == '0'
  grid[r][c] = '0'
  dfs(grid, r + 1, c)
  dfs(grid, r - 1, c)
  dfs(grid, r, c + 1)
  dfs(grid, r, c - 1)
end

def num_islands(grid)
  count = 0
  (0...grid.size).each do |r|
    (0...grid[0].size).each do |c|
      if grid[r][c] == '1'
        dfs(grid, r, c)
        count += 1
      end
    end
  end
  count
end

grid = [
  ['1', '1', '0', '0'],
  ['1', '1', '0', '0'],
  ['0', '0', '1', '0'],
  ['0', '0', '0', '1']
]
puts "Islands: #{num_islands(grid)}"

# Word Search in Grid
def dfs(board, word, r, c, idx)
  return true if idx == word.size
  return false if r < 0 || r >= board.size || c < 0 || c >= board[0].size
  return false if board[r][c] != word[idx]

  tmp = board[r][c]
  board[r][c] = '#'
  found = dfs(board, word, r + 1, c, idx + 1) ||
          dfs(board, word, r - 1, c, idx + 1) ||
          dfs(board, word, r, c + 1, idx + 1) ||
          dfs(board, word, r, c - 1, idx + 1)
  board[r][c] = tmp
  found
end

def word_search(board, word)
  (0...board.size).each do |r|
    (0...board[0].size).each do |c|
      return true if dfs(board, word, r, c, 0)
    end
  end
  false
end

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]

puts word_search(board, "ABCCED")
puts word_search(board, "SEE")
puts word_search(board, "ABCB")

# Spiral Matrix in Crystal
def spiral_order(matrix)
  result = [] of Int32
  top = 0
  bottom = matrix.size - 1
  left = 0
  right = matrix[0].size - 1

  while top <= bottom && left <= right
    (left..right).each { |i| result << matrix[top][i] }
    top += 1
    (top..bottom).each { |i| result << matrix[i][right] }
    right -= 1
    if top <= bottom
      (right).downto(left).each { |i| result << matrix[bottom][i] }
      bottom -= 1
    end
    if left <= right
      (bottom).downto(top).each { |i| result << matrix[i][left] }
      left += 1
    end
  end
  result
end

mat = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16]
]

puts "Spiral: #{spiral_order(mat).join(" ")}"

# Sudoku Solver in Crystal
def is_valid(board, r, c, num)
  (0...9).each do |i|
    return false if board[r][i] == num
    return false if board[i][c] == num
    box_r = 3 * (r // 3) + i // 3
    box_c = 3 * (c // 3) + i % 3
    return false if board[box_r][box_c] == num
  end
  true
end

def solve(board)
  (0...9).each do |r|
    (0...9).each do |c|
      if board[r][c] == '.'
        ('1'..'9').each do |num|
          if is_valid(board, r, c, num)
            board[r][c] = num
            return true if solve(board)
            board[r][c] = '.'
          end
        end
        return false
      end
    end
  end
  true
end

board = [
  ['5','3','.','.','7','.','.','.','.'],
  ['6','.','.','1','9','5','.','.','.'],
  ['.','9','8','.','.','.','.','6','.'],
  ['8','.','.','.','6','.','.','.','3'],
  ['4','.','.','8','.','3','.','.','1'],
  ['7','.','.','.','2','.','.','.','6'],
  ['.','6','.','.','.','.','2','8','.'],
  ['.','.','.','4','1','9','.','.','5'],
  ['.','.','.','.','8','.','.','7','9']
]

solve(board)
board.each { |row| puts row.join(" ") }

# Priority Queue Custom Comparator
class Task
  property name : String
  property priority : Int32
  property deadline : Int32

  def initialize(@name : String, @priority : Int32, @deadline : Int32)
  end
end

# Custom comparator
class TaskComparer
  include Comparator(Task)

  def compare(a : Task, b : Task)
    if a.priority != b.priority
      return b.priority <=> a.priority
    end
    a.deadline <=> b.deadline
  end
end

task_queue = PriorityQueue(Task, TaskComparer).new
task_queue.push(Task.new("Write Report", 3, 5))
task_queue.push(Task.new("Fix Bug", 5, 2))
task_queue.push(Task.new("Code Review", 4, 3))
task_queue.push(Task.new("Deploy Feature", 5, 1))
task_queue.push(Task.new("Write Tests", 3, 4))

puts "Task execution order:"
while !task_queue.empty?
  t = task_queue.pop
  puts "  [P=#{t.priority},D=#{t.deadline}] #{t.name}"
end

# Graph - Prim's MST in Crystal
def prim_mst(graph : Array(Array(Tuple(Int32, Int32))), v : Int32)
  key = Array.new(v, Int32::MAX)
  in_mst = Array.new(v, false)
  pq = PriorityQueue(Tuple(Int32, Int32), Int32).new

  key[0] = 0
  pq.push({0, 0}, 0)
  total_cost = 0

  while !pq.empty?
    weight, u = pq.pop
    next if in_mst[u]
    in_mst[u] = true
    total_cost += weight

    graph[u].each do |w, neighbor|
      if !in_mst[neighbor] && w < key[neighbor]
        key[neighbor] = w
        pq.push({w, neighbor}, w)
      end
    end
  end
  total_cost
end

v = 5
graph = Array.new(v) { [] of Tuple(Int32, Int32) }

def add_edge(graph, u, v, w)
  graph[u] << {w, v}
  graph[v] << {w, u}
end

add_edge(graph, 0, 1, 2)
add_edge(graph, 0, 3, 6)
add_edge(graph, 1, 2, 3)
add_edge(graph, 1, 3, 8)
add_edge(graph, 1, 4, 5)
add_edge(graph, 2, 4, 7)
add_edge(graph, 3, 4, 9)

puts "MST Cost (Prim's): #{prim_mst(graph, v)}"

# Custom Iterator Pattern in Crystal
# Custom Range iterator
struct RangeIterator
  include Iterator(Int32)

  def initialize(@start : Int32, @end : Int32, @step : Int32 = 1)
  end

  def next
    if @start < @end
      value = @start
      @start += @step
      value
    else
      stop
    end
  end
end

class Range
  include Enumerable(Int32)

  def initialize(@start : Int32, @end : Int32, @step : Int32 = 1)
  end

  def each
    i = @start
    while i < @end
      yield i
      i += @step
    end
  end
end

# Custom Fibonacci generator
class Fibonacci
  include Enumerable(Int64)

  def initialize(@count : Int32)
  end

  def each
    a = 0_i64
    b = 1_i64
    @count.times do
      yield a
      a, b = b, a + b
    end
  end
end

# Custom range
Range.new(1, 11).each { |x| print "#{x} " }
puts

Range.new(0, 20, 2).each { |x| print "#{x} " }
puts

# Custom fibonacci
Fibonacci.new(10).each { |x| print "#{x} " }
puts

# LINQ with custom iterator
evens = Range.new(1, 21).select { |x| x.even? }
puts "Evens: #{evens.to_a.join(" ")}"

# Yield return examples
def squares(start, end)
  (start..end).each { |i| yield i * i }
end

print "Manual squares: "
squares(1, 5) { |x| print "#{x} " }
puts

# Stack and Queue Implementations
# Custom Stack
class MyStack(T)
  @items = [] of T

  def push(item : T)
    @items << item
  end

  def pop : T
    raise "Stack is empty" if empty?
    @items.pop
  end

  def peek : T
    raise "Stack is empty" if empty?
    @items.last
  end

  def empty?
    @items.empty?
  end

  def size
    @items.size
  end
end

# Custom Queue
class MyQueue(T)
  @items = Deque(T).new

  def enqueue(item : T)
    @items << item
  end

  def dequeue : T
    raise "Queue is empty" if empty?
    @items.shift
  end

  def peek : T
    raise "Queue is empty" if empty?
    @items.first
  end

  def empty?
    @items.empty?
  end

  def size
    @items.size
  end
end

# Custom Stack
stack = MyStack(Int32).new
stack.push(10)
stack.push(20)
stack.push(30)
puts "Stack top: #{stack.peek}"
while !stack.empty?
  print "#{stack.pop} "
end
puts

# Custom Queue
queue = MyQueue(Int32).new
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
puts "Queue front: #{queue.peek}"
while !queue.empty?
  print "#{queue.dequeue} "
end
puts

# Counting Sort and Radix Sort in Crystal
def counting_sort(arr : Array(Int32))
  return arr if arr.empty?
  max_val = arr.max
  count = Array.new(max_val + 1, 0)
  arr.each { |x| count[x] += 1 }

  idx = 0
  (0..max_val).each do |i|
    while count[i] > 0
      arr[idx] = i
      idx += 1
      count[i] -= 1
    end
  end
  arr
end

def count_sort_by_digit(arr : Array(Int32), exp : Int32)
  n = arr.size
  output = Array.new(n, 0)
  count = Array.new(10, 0)

  arr.each { |x| count[(x // exp) % 10] += 1 }

  (1...10).each { |i| count[i] += count[i - 1] }

  (n - 1).downto(0).each do |i|
    digit = (arr[i] // exp) % 10
    output[count[digit] - 1] = arr[i]
    count[digit] -= 1
  end

  (0...n).each { |i| arr[i] = output[i] }
end

def radix_sort(arr : Array(Int32))
  max_val = arr.max
  exp = 1
  while max_val // exp > 0
    count_sort_by_digit(arr, exp)
    exp *= 10
  end
  arr
end

v1 = [4, 2, 2, 8, 3, 3, 1, 7, 5]
counting_sort(v1)
puts "Counting: #{v1.join(" ")}"

v2 = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(v2)
puts "Radix: #{v2.join(" ")}"

# Graph Cycle Detection in Crystal
# Directed graph - DFS with recursion stack
def dfs_cycle(v, adj, visited, rec_stack)
  visited[v] = true
  rec_stack[v] = true

  adj[v].each do |u|
    if !visited[u]
      return true if dfs_cycle(u, adj, visited, rec_stack)
    elsif rec_stack[u]
      return true
    end
  end
  rec_stack[v] = false
  false
end

def has_cycle_directed(v, adj)
  visited = Array.new(v, false)
  rec_stack = Array.new(v, false)
  (0...v).each do |i|
    return true if !visited[i] && dfs_cycle(i, adj, visited, rec_stack)
  end
  false
end

# Undirected graph - Union Find
def has_cycle_undirected(v, edges)
  parent = (0...v).to_a

  find = ->(x : Int32) {
    if parent[x] != x
      parent[x] = find.call(parent[x])
    end
    parent[x]
  }

  edges.each do |u, v|
    pu = find.call(u)
    pv = find.call(v)
    return true if pu == pv
    parent[pu] = pv
  end
  false
end

v = 4
adj = Array.new(v) { [] of Int32 }
adj[0] << 1
adj[1] << 2
adj[2] << 3
adj[3] << 1

puts "Directed cycle: #{has_cycle_directed(v, adj)}"

edges = [{0, 1}, {1, 2}, {2, 0}]
puts "Undirected cycle: #{has_cycle_undirected(3, edges)}"

# Advanced LINQ - GroupJoin, SelectMany, etc.
class Customer
  property id : Int32
  property name : String

  def initialize(@id : Int32, @name : String)
  end
end

class Order
  property customer_id : Int32
  property product : String
  property quantity : Int32

  def initialize(@customer_id : Int32, @product : String, @quantity : Int32)
  end
end

customers = [
  Customer.new(1, "Alice"),
  Customer.new(2, "Bob"),
  Customer.new(3, "Carol")
]

orders = [
  Order.new(1, "Laptop", 1),
  Order.new(1, "Mouse", 2),
  Order.new(2, "Keyboard", 1),
  Order.new(2, "Monitor", 3),
  Order.new(2, "Mouse", 1)
]

# GroupJoin (left outer join)
customer_orders = customers.map do |c|
  {c.name, orders.select { |o| o.customer_id == c.id }.map { |o| "#{o.product} (x#{o.quantity})" }}
end

puts "Customer Orders:"
customer_orders.each do |name, products|
  puts "#{name}: #{products.join(", ")}"
end

# SelectMany (flatten)
all_order_items = orders.flat_map { |o| [o.product] * o.quantity }
puts "All items: #{all_order_items.join(", ")}"

# ToLookup
order_lookup = orders.group_by { |o| o.customer_id }
order_lookup.each do |id, orders|
  puts "Customer #{id} has #{orders.size} orders"
end

# Aggregate
all_products = orders.map(&.product).join(", ")
puts "All products: #{all_products}"

# Expression Evaluation using Stack
# Evaluate Reverse Polish Notation
def eval_rpn(tokens : Array(String))
  stack = [] of Int32
  tokens.each do |t|
    case t
    when "+"
      b = stack.pop
      a = stack.pop
      stack << a + b
    when "-"
      b = stack.pop
      a = stack.pop
      stack << a - b
    when "*"
      b = stack.pop
      a = stack.pop
      stack << a * b
    when "/"
      b = stack.pop
      a = stack.pop
      stack << a // b
    else
      stack << t.to_i
    end
  end
  stack.pop
end

# Infix to Postfix
def infix_to_postfix(expr : String)
  ops = [] of Char
  result = [] of String

  precedence = ->(c : Char) {
    case c
    when '+', '-' then 1
    when '*', '/' then 2
    else 0
    end
  }

  expr.each_char do |c|
    if c.ascii_number?
      result << c.to_s
    elsif c == '('
      ops << c
    elsif c == ')'
      while ops.last != '('
        result << ops.pop.to_s
      end
      ops.pop
    else
      while !ops.empty? && precedence.call(ops.last) >= precedence.call(c)
        result << ops.pop.to_s
      end
      ops << c
    end
  end

  while !ops.empty?
    result << ops.pop.to_s
  end

  result.join(" ")
end

rpn = ["2", "1", "+", "3", "*"]
puts "RPN eval: #{eval_rpn(rpn)}"

puts "Infix to Postfix: #{infix_to_postfix("(2+3)*4")}"

# Design Patterns - Strategy and Template
# Strategy Pattern
interface SortStrategy
  def sort(data : Array(Int32))
  def name : String
end

class BubbleSortStrategy
  include SortStrategy

  def name
    "Bubble Sort"
  end

  def sort(data : Array(Int32))
    n = data.size
    (n - 1).times do |i|
      swapped = false
      (0...n - i - 1).each do |j|
        if data[j] > data[j + 1]
          data[j], data[j + 1] = data[j + 1], data[j]
          swapped = true
        end
      end
      break unless swapped
    end
  end
end

class BuiltInSortStrategy
  include SortStrategy

  def name
    "Built-in Sort"
  end

  def sort(data : Array(Int32))
    data.sort!
  end
end

class SortContext
  @strategy : SortStrategy

  def initialize(@strategy : SortStrategy)
  end

  def set_strategy(strategy : SortStrategy)
    @strategy = strategy
  end

  def sort(data : Array(Int32))
    puts "Using: #{@strategy.name}"
    @strategy.sort(data)
  end
end

# Template Method Pattern
abstract class DataProcessor
  def process
    load_data
    process_data
    save_result
  end

  abstract def load_data
  abstract def process_data
  abstract def save_result
end

class CSVProcessor < DataProcessor
  def load_data
    puts "Loading CSV data..."
  end

  def process_data
    puts "Processing CSV data..."
  end

  def save_result
    puts "Saving CSV result..."
  end
end

data = [5, 3, 8, 1, 9, 2]

context = SortContext.new(BubbleSortStrategy.new)
context.sort(data.dup)
puts data.join(" ")

context.set_strategy(BuiltInSortStrategy.new)
context.sort(data.dup)
puts data.join(" ")

puts "
Template Method:"
processor = CSVProcessor.new
processor.process

# String Matching - Rabin-Karp in Crystal
def rabin_karp(text : String, pattern : String)
  positions = [] of Int32
  n = text.size
  m = pattern.size
  base = 31
  mod = 1000000009_i64

  # Compute hash of pattern and first window
  pat_hash = 0_i64
  win_hash = 0_i64
  power = 1_i64

  (0...m).each do |i|
    pat_hash = (pat_hash + (pattern[i].ord - 'a'.ord + 1) * power) % mod
    win_hash = (win_hash + (text[i].ord - 'a'.ord + 1) * power) % mod
    if i < m - 1
      power = (power * base) % mod
    end
  end

  (0..n - m).each do |i|
    if pat_hash == win_hash
      if text[i, m] == pattern
        positions << i
      end
    end
    if i < n - m
      win_hash = (win_hash - (text[i].ord - 'a'.ord + 1)) % mod
      win_hash = (win_hash * (mod + 1 - base)) % mod
      win_hash = (win_hash + (text[i + m].ord - 'a'.ord + 1) * power) % mod
    end
  end
  positions
end

text = "aabaacaadaabaaba"
pattern = "aaba"
pos = rabin_karp(text, pattern)
puts "Rabin-Karp found at: #{pos.join(" ")}"

# Type Erasure with Dynamic in Crystal
# dynamic type
value = 42
puts "Int: #{value}"
value = "Hello, World!"
puts "String: #{value}"
value = 3.14159
puts "Double: #{value}"

# Dynamic object with Hash
person = {} of String => String | Int32
person["name"] = "Alice"
person["age"] = 25
puts "Hello, I'm #{person["name"]}"

# Dictionary to dynamic
dict = {
  "Name" => "Bob",
  "Age" => 30
}
puts "#{dict["Name"]} is #{dict["Age"]} years old"

# Type checking
puts "value is Int: #{value.is_a?(Int32)}"
puts "value is Float64: #{value.is_a?(Float64)}"

# Generic with type parameter
def print_type(t)
  puts "Type: #{t.class}, Value: #{t}"
end

print_type(42)
print_type("hello")
print_type(3.14)

# Advanced OOP - Mixins and Interfaces
# Interface for printable
module Printable
  abstract def print
end

# Interface for comparable
module Comparable
  abstract def compare_to(other : T) : Int32 forall T
end

# Mixin using module
module PrintableMixin
  def print_with_header
    puts "=== Print Start ==="
    print
    puts "=== Print End ==="
  end
end

# Implementation
class Point
  include Printable
  include PrintableMixin
  include Comparable(Point)

  property x : Float64
  property y : Float64

  def initialize(@x : Float64, @y : Float64)
  end

  def print
    puts "Point(#{@x}, #{@y})"
  end

  def compare_to(other : Point)
    d1 = @x * @x + @y * @y
    d2 = other.x * other.x + other.y * other.y
    d1 <=> d2
  end

  def distance
    @x * @x + @y * @y
  end
end

p1 = Point.new(3, 4)
p2 = Point.new(1, 1)
p3 = Point.new(3, 4)

p1.print
p1.print_with_header

puts "p1 == p3: #{p1.compare_to(p3) == 0}"
puts "p1 > p2: #{p1.compare_to(p2) > 0}"
puts "p2 < p1: #{p2.compare_to(p1) < 0}"

# With LINQ
points = [p1, p2, p3]
sorted = points.sort_by { |p| p.distance }
puts "Sorted by distance:"
sorted.each { |p| p.print }

# Concurrency - Producer-Consumer with Channel
# Producer-Consumer using Channel
buffer = Channel(Int32).new(3)

# Producer
spawn do
  (1..6).each do |i|
    buffer.send(i)
    puts "Produced: #{i} | Buffer size: #{buffer.size}"
    sleep 0.1
  end
  buffer.close
end

# Consumer
spawn do
  while item = buffer.receive?
    puts "Consumed: #{item} | Buffer size: #{buffer.size}"
    sleep 0.15
  end
end

# Wait for completion
sleep 2

# ConcurrentBag example (using Channel)
bag = Channel(Int32).new(10)
(0...10).each do |i|
  spawn { bag.send(i) }
end

count = 0
10.times do
  bag.receive
  count += 1
end
puts "ConcurrentBag count: #{count}"

# ConcurrentDictionary (using Hash with locks)
dict = {} of String => Int32
mutex = Mutex.new

spawn do
  mutex.synchronize { dict["one"] = 1 }
end

spawn do
  mutex.synchronize { dict["two"] = 2 }
end

spawn do
  mutex.synchronize do
    dict["three"] = dict.get("three", 0) + 3
  end
end

spawn do
  mutex.synchronize do
    dict["one"] = dict.get("one", 0) + 10
  end
end

sleep 0.5
mutex.synchronize do
  puts "ConcurrentDictionary: one=#{dict["one"]}, three=#{dict["three"]}"
end

# Crystal Features - Records and Pattern Matching
# Struct (similar to record)
struct Person
  property name : String
  property age : Int32

  def initialize(@name : String, @age : Int32)
  end
end

# Struct with methods
struct Student < Person
  property major : String

  def initialize(name : String, age : Int32, @major : String)
    super(name, age)
  end

  def display
    puts "#{@name} (#{@age}) studies #{@major}"
  end
end

# Positional struct with distance
struct Point
  property x : Float64
  property y : Float64

  def initialize(@x : Float64, @y : Float64)
  end

  def distance
    Math.sqrt(@x * @x + @y * @y)
  end
end

# Struct instantiation
p1 = Person.new("Alice", 25)
p2 = Person.new("Alice", 25)
p3 = Person.new(p1.name, p1.age + 1)  # With expression

puts "p1 == p2: #{p1 == p2}"
puts "p1: Person(@name="Alice", @age=25)"
puts "p3: Person(@name="Alice", @age=26)"

# Pattern matching
obj = 42
case obj
when Int32
  if obj > 10
    puts "Medium int"
  else
    puts "Small int"
  end
when String
  puts "String: #{obj}"
else
  puts "Unknown"
end

# Property pattern
if p1.is_a?(Person) && p1.name == "Alice" && p1.age == 25
  puts "Matched Alice, age 25"
end

# Tuple pattern
x, y = 10, 20
case {x, y}
when {0, 0}
  puts "Origin"
when {10, 20}
  puts "Equal"
else
  puts "Other"
end

# Advanced Crystal - Performance and Memory
# Slice (similar to Span)
numbers = [1, 2, 3, 4, 5]
slice = numbers[1, 3]
puts "Slice: #{slice.join(", ")}"

# Modify slice affects original
slice[0] = 99
puts "After slice modification: #{numbers.join(", ")}"

# Memory (similar to Memory)
memory = [10, 20, 30, 40, 50]
memory_slice = memory[1, 3]
puts "Memory slice: #{memory_slice.join(", ")}"

# Pool (similar to ArrayPool)
pooled = [] of Int32
10.times { pooled << 0 }
(0...10).each { |i| pooled[i] = i * 2 }
puts "Pooled: #{pooled.join(", ")}"

# Unsafe and pointer
bytes = [1, 2, 3, 4]
int_value = bytes.to_unsafe.as(Int32).value
puts "Bytes as int: #{int_value}"

# String creation
text = String.build(10) do |str|
  str << '*' * 10
  str[0] = 'X'
end
puts "Created: #{text}"

# ReadOnlySlice
readonly = "Hello, World!".to_slice
puts "ReadOnlySlice: #{readonly[0, 5].to_s}"

# Reflection and Dynamic Invocation
class Calculator
  def add(a : Int32, b : Int32)
    a + b
  end

  def multiply(a : Int32, b : Int32)
    a * b
  end

  private getter secret : String = "Hidden"

  private def get_secret
    @secret
  end

  def print(message : String)
    puts message
  end
end

calc = Calculator.new

# Get and invoke method
add_method = ->(calc : Calculator, a : Int32, b : Int32) { calc.add(a, b) }
result = add_method.call(calc, 5, 3)
puts "Add(5,3) = #{result}"

# Get all methods
puts "
All methods:"
Calculator.methods.each do |m|
  visibility = m.owner == Calculator ? "public" : "private"
  puts "  #{m.name} (#{visibility})"
end

# Access private field (via macro)
puts "Private field: #{calc.secret}"

# Invoke private method
secret_value = calc.private_methods.find { |m| m.name == "get_secret" }
puts "Private method: #{secret_value.try &.call(calc)}"

# Dynamic invocation with delegate
add_delegate = ->(calc : Calculator, a : Int32, b : Int32) { calc.add(a, b) }
puts "Delegate: #{add_delegate.call(calc, 10, 20)}"

# Advanced LINQ - Dynamic Queries and Expression Trees
class Person
  property name : String
  property age : Int32
  property city : String

  def initialize(@name : String, @age : Int32, @city : String)
  end
end

data = [
  Person.new("Alice", 25, "NYC"),
  Person.new("Bob", 30, "LA"),
  Person.new("Carol", 22, "NYC"),
  Person.new("Dave", 35, "Chicago")
]

# Dynamic query building
filter = ->(p : Person) { p.age > 25 && p.city == "NYC" }
result = data.select { |p| filter.call(p) }
puts "Filter result: #{result.map(&.name).join(", ")}"

# Dynamic ordering
sort_field = "age"
sorted = data.sort_by { |p| p.age }
puts "Sorted by Age: #{sorted.map { |p| "#{p.name}(#{p.age})" }.join(", ")}"

# Dynamic select
fields = ["name", "city"]
puts "Projections:"
data.each do |p|
  values = fields.map { |f| p.to_h[f] }
  puts "  #{values.join(", ")}"
end

# Group by dynamic
grouped = data.group_by { |p| p.city }
grouped.each do |city, people|
  puts "City: #{city} (#{people.size})"
end

# Complete Bank Account System in Crystal
class BankAccount
  @@next_id = 1000

  property account_id : String
  property owner : String
  property balance : Float64
  property transactions : Array(Transaction)

  class Transaction
    property type : String
    property amount : Float64
    property description : String
    property balance_after : Float64
    property timestamp : Time

    def initialize(@type : String, @amount : Float64, @description : String, @balance_after : Float64)
      @timestamp = Time.local
    end

    def print
      puts "#{@timestamp.to_s("%H:%M:%S")} | #{@type.ljust(10)} | $#{@amount.to_s.rjust(9)} | $#{@balance_after.to_s.rjust(9)} | #{@description}"
    end
  end

  def initialize(@owner : String, initial_deposit : Float64 = 0.0)
    @@next_id += 1
    @account_id = "ACC#{@@next_id}"
    @balance = 0.0
    @transactions = [] of Transaction
    deposit(initial_deposit, "Initial deposit") if initial_deposit > 0
  end

  def deposit(amount : Float64, description : String = "Deposit")
    raise "Deposit amount must be positive" if amount <= 0
    @balance += amount
    @transactions << Transaction.new("DEPOSIT", amount, description, @balance)
  end

  def withdraw(amount : Float64, description : String = "Withdrawal")
    raise "Withdrawal amount must be positive" if amount <= 0
    raise "Insufficient funds" if amount > @balance
    @balance -= amount
    @transactions << Transaction.new("WITHDRAWAL", amount, description, @balance)
  end

  def transfer(target : BankAccount, amount : Float64)
    withdraw(amount, "Transfer to #{target.account_id}")
    target.deposit(amount, "Transfer from #{@account_id}")
  end

  def print_statement
    puts "=" * 60
    puts "Account: #{@account_id} | Owner: #{@owner} | Balance: $#{@balance}"
    puts "-" * 60
    @transactions.each { |t| t.print }
    puts "=" * 60
  end
end

class Bank
  property name : String
  property accounts : Array(BankAccount)

  def initialize(@name : String)
    @accounts = [] of BankAccount
  end

  def create_account(owner : String, initial : Float64 = 0.0)
    acc = BankAccount.new(owner, initial)
    @accounts << acc
    puts "Account created: #{acc.account_id} for #{owner}"
    acc
  end

  def list_accounts
    puts "
=== #{@name} - All Accounts ==="
    @accounts.each do |acc|
      puts "#{acc.account_id} | #{acc.owner.ljust(15)} | Balance: $#{acc.balance}"
    end
  end

  def total_assets
    @accounts.sum { |acc| acc.balance }
  end
end

bank = Bank.new("Crystal National Bank")

alice = bank.create_account("Alice Johnson", 5000.0)
bob = bank.create_account("Bob Smith", 3000.0)
carol = bank.create_account("Carol White", 1000.0)

alice.deposit(2000.0, "Salary")
alice.withdraw(500.0, "Rent")
alice.transfer(bob, 1000.0)

begin
  carol.withdraw(5000.0)
rescue ex : Exception
  puts "Error: #{ex.message}"
end

bob.deposit(200.0, "Freelance payment")
carol.deposit(3000.0, "Bonus")
carol.transfer(alice, 500.0)

alice.print_statement
bob.print_statement
carol.print_statement

bank.list_accounts
puts "Total Assets: $#{bank.total_assets}"

# Iterative Deepening DFS (IDDFS) in Crystal
def dls(adj, curr, target, depth, visited)
  return true if curr == target
  return false if depth == 0
  visited[curr] = true
  adj[curr].each do |next_node|
    if !visited[next_node]
      return true if dls(adj, next_node, target, depth - 1, visited)
    end
  end
  visited[curr] = false
  false
end

def iddfs(adj, src, target, max_depth)
  (0..max_depth).each do |depth|
    visited = Array.new(adj.size, false)
    puts "Searching at depth #{depth}..."
    return true if dls(adj, src, target, depth, visited)
  end
  false
end

v = 7
adj = Array.new(v) { [] of Int32 }
adj[0] = [1, 2]
adj[1] = [3, 4]
adj[2] = [5, 6]

puts "IDDFS: Search for node 6 from 0"
found = iddfs(adj, 0, 6, 5)
puts "Found: #{found ? "Yes" : "No"}"

puts "
IDDFS: Search for node 9 from 0 (not exists)"
found = iddfs(adj, 0, 9, 3)
puts "Found: #{found ? "Yes" : "No"}"

# Sparse Table for Range Minimum Query
class SparseTable
  @table : Array(Array(Int32))
  @log2 : Array(Int32)

  def initialize(arr : Array(Int32))
    n = arr.size
    log = Math.log2(n).to_i + 1
    @table = Array.new(log) { Array.new(n, 0) }
    @log2 = Array.new(n + 1, 0)

    # Precompute log2
    (2..n).each { |i| @log2[i] = @log2[i // 2] + 1 }

    # Build sparse table
    @table[0] = arr
    (1...log).each do |j|
      (0..n - (1 << j)).each do |i|
        @table[j][i] = Math.min(@table[j - 1][i],
                               @table[j - 1][i + (1 << (j - 1))])
      end
    end
  end

  def query(l : Int32, r : Int32) : Int32
    k = @log2[r - l + 1]
    Math.min(@table[k][l], @table[k][r - (1 << k) + 1])
  end
end

arr = [2, 4, 3, 1, 6, 7, 8, 9, 1, 7]
st = SparseTable.new(arr)

puts "RMQ(0,4): #{st.query(0, 4)}"
puts "RMQ(2,7): #{st.query(2, 7)}"
puts "RMQ(5,9): #{st.query(5, 9)}"
puts "RMQ(0,2): #{st.query(0, 2)}"

# Fenwick Tree (Binary Indexed Tree) in Crystal
class FenwickTree
  @tree : Array(Int32)
  @n : Int32

  def initialize(@n : Int32)
    @tree = Array.new(@n + 1, 0)
  end

  def update(i : Int32, delta : Int32)
    while i <= @n
      @tree[i] += delta
      i += i & -i
    end
  end

  def query(i : Int32) : Int32
    sum = 0
    while i > 0
      sum += @tree[i]
      i -= i & -i
    end
    sum
  end

  def range_query(l : Int32, r : Int32) : Int32
    query(r) - query(l - 1)
  end

  def build(arr : Array(Int32))
    arr.each_with_index { |val, i| update(i + 1, val) }
  end
end

arr = [1, 3, 5, 7, 9, 11]
ft = FenwickTree.new(arr.size)
ft.build(arr)

puts "Prefix sum [1,3]: #{ft.range_query(1, 3)}"
puts "Prefix sum [2,5]: #{ft.range_query(2, 5)}"
puts "Total sum: #{ft.range_query(1, 6)}"

ft.update(3, 6)
puts "After update(3,6):"
puts "Prefix sum [1,3]: #{ft.range_query(1, 3)}"
puts "Total sum: #{ft.range_query(1, 6)}"

# Shell Sort and Interpolation Search in Crystal
def shell_sort(arr)
  n = arr.size
  gap = n // 2
  while gap > 0
    (gap...n).each do |i|
      temp = arr[i]
      j = i
      while j >= gap && arr[j - gap] > temp
        arr[j] = arr[j - gap]
        j -= gap
      end
      arr[j] = temp
    end
    gap //= 2
  end
  arr
end

def interpolation_search(arr : Array(Int32), target : Int32)
  low = 0
  high = arr.size - 1
  while low <= high && target >= arr[low] && target <= arr[high]
    if low == high
      return low if arr[low] == target
      return -1
    end
    pos = low + ((high - low) * (target - arr[low]) // (arr[high] - arr[low]))
    return pos if arr[pos] == target
    if arr[pos] < target
      low = pos + 1
    else
      high = pos - 1
    end
  end
  -1
end

arr = [64, 34, 25, 12, 22, 11, 90, 1, 55, 47]
puts "Before: #{arr.join(" ")}"

shell_sort(arr)
puts "After Shell Sort: #{arr.join(" ")}"

sorted = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
puts "Search 70: index = #{interpolation_search(sorted, 70)}"
puts "Search 45: index = #{interpolation_search(sorted, 45)}"
puts "Search 100: index = #{interpolation_search(sorted, 100)}"

# Advanced Crystal - Nilable Types and Pattern Matching
class Person
  property name : String
  property age : Int32
  property email : String?

  def initialize(@name : String, @age : Int32, @email : String? = nil)
  end
end

# Nilable reference types
maybe_null = nil.as(String?)
not_null = "Hello"

# Null check
if !maybe_null.nil?
  puts maybe_null.size
end

# Null coalescing
value = maybe_null || "Default"

# Null conditional
length = maybe_null.try &.size

# Pattern matching with nil
result = case maybe_null
         when nil
           "Null value"
         when String
           if maybe_null.size > 10
             "Long string"
           else
             "Length: #{maybe_null.size}"
           end
         else
           "Unknown"
         end
puts result

# Property pattern matching
person = Person.new("Alice", 25, "alice@email.com")

match_result = case person
               when .name == "Alice" && .age == 25
                 "Alice, age 25"
               when .email
                 "Has email: #{person.email}"
               else
                 "Other"
               end
puts match_result

# Tuple pattern
tuple = {name: "Bob", age: 30}
tuple_result = case tuple
               when {name: "Bob", age: 30}
                 "Bob, 30"
               when {age: Int32}
                 "Adult: #{tuple[:name]}"
               else
                 "Minor"
               end
puts tuple_result

# Multithreading with Tasks and Parallel Processing
require "concurrent"

# Parallel sum using tasks
def parallel_sum(arr : Array(Int32), l : Int32, r : Int32)
  if r - l <= 100000
    return arr[l...r].sum.to_i64
  end
  mid = (l + r) // 2
  channel = Channel(Int64).new(2)

  spawn { channel.send(parallel_sum(arr, l, mid)) }
  spawn { channel.send(parallel_sum(arr, mid, r)) }

  left = channel.receive
  right = channel.receive
  left + right
end

# Async task with return value
def fetch_data(id : Int32)
  sleep 0.1
  "Data from source #{id}"
end

# Promise and Future (using Channel)
def compute(channel : Channel(Int32), a : Int32, b : Int32)
  if b == 0
    channel.close
  else
    channel.send(a // b)
  end
end

# Parallel sum
arr = Array.new(1000000, 1)
total = parallel_sum(arr, 0, arr.size)
puts "Parallel sum: #{total}"

# Multiple async tasks
tasks = (1..3).map { |i| spawn { fetch_data(i) } }
results = tasks.map { |f| f.get }
puts "Results: #{results.join(", ")}"

# Promise / Future (using Channel)
channel = Channel(Int32).new
spawn { compute(channel, 42, 7) }
begin
  puts "Result: #{channel.receive}"
rescue ex
  puts "Exception: #{ex.message}"
end

# Complete Library Management System in Crystal
class Book
  property isbn : String
  property title : String
  property author : String
  property genre : String
  property year : Int32
  property total_copies : Int32
  property available_copies : Int32

  def initialize(@isbn : String, @title : String, @author : String,
                 @genre : String, @year : Int32, copies : Int32 = 1)
    @total_copies = copies
    @available_copies = copies
  end

  def available?
    @available_copies > 0
  end

  def checkout
    @available_copies -= 1 if available?
  end

  def return_book
    @available_copies += 1 if @available_copies < @total_copies
  end

  def display
    puts "#{@isbn.ljust(15)} #{@title.ljust(30)} #{@author.ljust(20)} #{@genre.ljust(12)} #{@year.to_s.ljust(6)} [#{@available_copies}/#{@total_copies}]"
  end
end

class Member
  @@next_id = 1
  property id : String
  property name : String
  property email : String
  property borrowed_isbns : Array(String)

  MAX_BORROW = 5

  def initialize(@name : String, @email : String)
    @id = "M#{@@next_id.to_s.rjust(3, '0')}"
    @@next_id += 1
    @borrowed_isbns = [] of String
  end

  def can_borrow?
    @borrowed_isbns.size < MAX_BORROW
  end

  def borrow(isbn : String)
    @borrowed_isbns << isbn
  end

  def return_book(isbn : String)
    @borrowed_isbns.delete(isbn)
  end

  def has_borrowed?(isbn : String)
    @borrowed_isbns.includes?(isbn)
  end

  def display
    puts "Member [#{@id}] #{@name} | Email: #{@email} | Borrowed: #{@borrowed_isbns.size}/#{MAX_BORROW}"
    if !@borrowed_isbns.empty?
      puts "  Books: #{@borrowed_isbns.join(", ")}"
    end
  end
end

class Library
  property name : String
  property books : Hash(String, Book)
  property members : Hash(String, Member)

  def initialize(@name : String)
    @books = {} of String => Book
    @members = {} of String => Member
  end

  def add_book(book : Book)
    @books[book.isbn] = book
    puts "Book added: #{book.title}"
  end

  def register_member(member : Member)
    @members[member.id] = member
    puts "Member registered: #{member.name}"
  end

  def borrow_book(member_id : String, isbn : String)
    member = get_member(member_id)
    book = get_book(isbn)

    raise "#{member.name} has reached borrow limit" if !member.can_borrow?
    raise "Book not available: #{book.title}" if !book.available?

    book.checkout
    member.borrow(isbn)
    puts "#{member.name} borrowed: #{book.title}"
  end

  def return_book(member_id : String, isbn : String)
    member = get_member(member_id)
    book = get_book(isbn)

    raise "#{member.name} did not borrow this book" if !member.has_borrowed?(isbn)

    book.return_book
    member.return_book(isbn)
    puts "#{member.name} returned: #{book.title}"
  end

  def search_by_author(author : String)
    @books.values.select { |b| b.author.includes?(author) }
  end

  def search_by_genre(genre : String)
    @books.values.select { |b| b.genre == genre }
  end

  def display_all_books
    puts "
=== #{@name} - Catalog ==="
    puts "ISBN".ljust(15) + "Title".ljust(30) + "Author".ljust(20) + "Genre".ljust(12) + "Year".ljust(6) + "Copies"
    puts "-" * 90
    @books.values.sort_by { |b| b.title }.each { |b| b.display }
  end

  def display_all_members
    puts "
=== #{@name} - Members ==="
    @members.values.each { |m| m.display }
  end

  def display_stats
    total = @books.size
    available = @books.values.count { |b| b.available? }
    puts "
=== Stats ==="
    puts "Total books: #{total}"
    puts "Available: #{available}"
    puts "Checked out: #{total - available}"
    puts "Total members: #{@members.size}"
  end

  private def get_book(isbn : String)
    @books[isbn]? || raise("Book not found: #{isbn}")
  end

  private def get_member(id : String)
    @members[id]? || raise("Member not found: #{id}")
  end
end

lib = Library.new("Crystal City Library")

# Add books
lib.add_book(Book.new("978-0", "The Crystal Book", "Crystal Team", "Programming", 2020, 3))
lib.add_book(Book.new("978-1", "Design Patterns", "Gang of Four", "Programming", 2015, 2))
lib.add_book(Book.new("978-2", "Clean Code", "Robert Martin", "Programming", 2008, 4))
lib.add_book(Book.new("978-3", "Dune", "Frank Herbert", "Sci-Fi", 1965, 2))
lib.add_book(Book.new("978-4", "1984", "George Orwell", "Fiction", 1949, 3))

# Register members
lib.register_member(Member.new("Alice Johnson", "alice@email.com"))
lib.register_member(Member.new("Bob Smith", "bob@email.com"))
lib.register_member(Member.new("Carol White", "carol@email.com"))

lib.display_all_books

# Borrow books
lib.borrow_book("M001", "978-0")
lib.borrow_book("M001", "978-2")
lib.borrow_book("M002", "978-1")
lib.borrow_book("M003", "978-3")

begin
  lib.borrow_book("M001", "978-9")
rescue ex : Exception
  puts "Error: #{ex.message}"
end

lib.return_book("M001", "978-0")
lib.borrow_book("M002", "978-0")

puts "
Search by genre 'Programming':"
lib.search_by_genre("Programming").each { |b| b.display }

lib.display_all_members
lib.display_stats