Ruby (S-99: 1~60 http://aperiodic.net/phil/scala/s-99/)

s-99.rb

# -*- coding: utf-8 -*-

##############################
##### Working with lists #####
##############################

def last(ls)
  ls[-1]
end

def penultimate(ls)
  ls[-2]
end

def nth(index, ls)
  ls.at(index)
end

def length(ls)
  ls.size
end

def reverse(ls)
  ls.reverse
end

def palindrome?(ls)
  ls.reverse == ls
end

def flatten(ls)
  result = []
  case ls
  when Array then
    ls.each{|xs| result.concat(flatten(xs))}
  else
    result << ls
  end
  result
end

def compress(ls)
  result = [head = ls.first]
  ls[1..-1].each { |x|
    if head != x
      result << head = x
    end
  }
  result
end

def pack(ls)
  ls.group_by{|x| x}.values
end

def encode(ls)
  ls.group_by{|x| x}.map{|k, v| [v.length, k]}
end

def encode_modified(ls)
  ls.group_by{|x| x}.map{|k, v| v.length == 1 ? k : [v.length, k]}
end

def decode(ls)
  ls.map {|xs|
    [xs[1]] * xs[0]
  }.flatten
end

def encode_direct(ls)
  head, result, count = ls.first, [], 1
  ls[1..-1].each {|x|
    if head != x
      result << [count, head]
      head = x
      count = 1
    else
      count += 1
    end
  }
  result << [count, head]
end

def duplicate(ls)
  ls.map {|x| [x, x]}.flatten
end

def duplicate_n(n, ls)
  ls.map {|x| [x] * n}.flatten
end

def drop(n, ls)
  ls[0...n-1].concat(ls[n..-1])
end

def split(n, ls)
  [ls[0..n-1], ls[n-1..-1]]
end

def slice(from, to, ls)
  ls[from...to]
end

def rotate(n, ls)
  ls[n..-1].concat(ls[0...n])
end

def remove_at(n, ls)
  deleted = ls.delete_at(n)
  [ls, deleted]
end

def insert_at(obj, index, ls)
  ls.insert(index, obj)
end

def range(from, to)
  (from..to).to_a
end

def random_select(count, ls)
  ls.shuffle.take(count)
end

def lotto(count, max_value)
  (1..max_value).to_a.shuffle.take(count)
end

def random_permute(ls)
  pre_index, post_index = (1...ls.length).to_a.shuffle.take(2)
  ls[pre_index], ls[post_index]= ls[post_index], ls[pre_index]
  ls
end

def combinations(count, ls)
  def combinations_r(candidates, remain_count, remains)
    if remain_count == 0
      candidates
    elsif remains.empty?
      []
    else
      head, tail = remains[0], remains[1..-1]
      combinations_r(
        candidates.map {|xs| [*xs, head] },
        remain_count - 1,
        tail
      ) + combinations_r(candidates, remain_count, tail)
    end
  end
  combinations_r([[]], count, ls)
end

def group3(ls)
  two_groups = combinations(2, ls)
  two_groups.flat_map { |xs|
    remains = ls - xs
    combinations(3, remains).map { |ys|
      [xs, ys, remains - ys]
    }
  }
end

def group(spec, ls)
  raise "spec is invalid" if ls.size != spec.inject(:+)
  def group_r(candidates, spec, ls)
    if spec.size == 1
      [[*candidates, ls]]
    else
      combinations(spec.first, ls).flat_map {|xs|
        group_r([*candidates, xs], spec[1..-1], ls - xs)
      }
    end
  end
  group_r([], spec, ls)
end

def lsort(ls)
  ls.sort_by{|xs| xs.size}
end

def lsort_freq(ls)
  ls.group_by{|xs| xs.size}.sort_by{|k, v| -v.size}.flat_map{|arr| arr[1]}
end

#######################
##### Arithmetic ######
#######################

def gcd(a, b)
  b == 0 ? a : gcd(b, a%b)
end

class Fixnum
  @@prime_cache = {1 => false, 2 => true}
  def prime?
    return false if self < 1
    if @@prime_cache.has_key?(self)
      @@prime_cache[self]
    else
      is_prime = (2..Math.sqrt(self)).all?{|v| self % v != 0}
      @@prime_cache[self] = is_prime
      is_prime
    end
  end

  def coprime_to?(n)
    gcd(n) == 1
  end

  def totient
    (1...self).select{|n| coprime_to?(n)}.size
  end

  def prime_factors
    def prime_factors_r(factors, value, primes)
      if value == 1
        factors
      else
        prime = primes.first
        if value % prime == 0
          prime_factors_r([*factors, prime], value / prime, primes)
        else
          prime_factors_r(factors, value, primes[1..-1])
        end
      end
    end
    prime_factors_r([], self, primes_until(self))
  end

  def prime_factor_multiplicity
    prime_factors.group_by{|x| x}.map{|k, v| [k, v.size]}
  end

  def prime_factor_multiplicity_hash
    prime_factor_multiplicity.to_h
  end

  def totient_improve
    prime_factor_multiplicity_hash.inject(1){|value, arr|
      p, m = arr
      value * (p-1) * p**(m-1)
    }
  end

  # listPrimesinRange(7 to 31) <=> 7.list_primes_to(31)
  def list_primes_to(to)
    list_primes_in_range(self, to)
  end

  def goldbach
    primes = list_primes_in_range(2, self)
    for prime in primes
      if primes.include?(self-prime)
        return [prime, self-prime]
      end
    end
    []
  end

  # printGoldbachList(9 to 20) <=>
  # 9.goldbach_list_to(20).each{|p1, p2| puts "#{p1 + p2} = #{p1} + #{p2}"}
  def goldbach_list_to(to)
    (self..to).map{|n| n.goldbach}.select{|xs| !xs.empty?}
  end

  private
  def primes_until(n)
    (2..n).select {|i|
      (2..Math.sqrt(i)).all?{|j| i%j != 0}
    }
  end

  def list_primes_in_range(from, to)
    primes_until(to) - primes_until(from)
  end
end

############################
###### Logic and Codes #####
############################

def myand(b1, b2)
  b1 and b2
end

def myor(b1, b2)
  b1 or b2
end

def mynand(b1, b2)
  not myand(b1, b2)
end

def mynor(b1, b2)
  not myor(b1, b2)
end

def myxor(b1, b2)
  not myequ(b1, b2)
end

def myequ(b1, b2)
  (b1 and b2) or (!b1 and !b2)
end

# table2(lambda{|a, b| myand(a, myor(a, b))})
def table2(func)
  puts printf("%-5s %-5s %s","A", "B", "result")
  [true, false].each {|b1|
    [true, false].each {|b2|
      result = func.call(b1, b2)
      puts sprintf("%-5s %-5s %s", b1, b2, result)
    }
  }
end

# table2_yield {|a, b| myand(a, myor(a, b))}
def table2_yield
  puts printf("%-5s %-5s %s","A", "B", "result")
  [true, false].each {|b1|
    [true, false].each {|b2|
      result = yield(b1, b2)
      puts sprintf("%-5s %-5s %s", b1, b2, result)
    }
  }
end

def gray(n)
  @bits = ["0", "1"]
  def gray_r(candidates, count)
    if count == 0
      candidates
    else
      gray_r(candidates.flat_map{|xs| @bits.map{|bit| xs+bit}}, count-1)
    end
  end
  gray_r([""], n)
end

def huffman(ls)
  return [] if ls.size == 0;
  return [ls[0][0], "0"] if ls.size == 1;

  weights = ls.map{|ch, weight| [weight, [[ch, ""]]]}.sort_by{|arr| arr[0]}
  def huffman_r(weights)
    if weights.size == 1
      weights[0][1]
    else
      first, second = weights[0], weights[1]
      sum_weight = first[0] + second[0]
      mix_bits = add_bit(first[1], "0") + add_bit(second[1], "1")
      next_weights = ([[sum_weight, mix_bits]] + weights[2..-1]).sort_by{|arr| arr[0]}
      huffman_r(next_weights)
    end
  end

  def add_bit(ls, bit)
    ls.map{|ch, bits| [ch, bit + bits]}
  end

  huffman_r(weights)
end

########################
##### Binary Trees #####
########################

module TreeFactory
  def Leaf(value)
    Node.new(value, End.new, End.new)
  end
  def Node(value, left, right)
    Node.new(value, left, right)
  end

  def c_balanced(count, value)
    return [End.new] if count == 0
    children_count = count - 1
    if children_count % 2 == 0
      left = right = c_balanced(count/2, value)
      left.flat_map{|ltr| right.map{|rtr| Tree.Node(value, ltr, rtr)}}
    else
      less_tree = c_balanced(count/2-1, value)
      more_tree = c_balanced(count/2, value)
      less_tree.flat_map{|ltr| more_tree.flat_map{|mtr| [Tree.Node(value, ltr, mtr), Tree.Node(value, mtr, ltr)]}}
    end
  end

  def add_value(value)
    Leaf(value)
  end

  def from_list(ls)
    return End.new if ls.empty?
    root = Leaf(ls.first)
    ls[1..-1].inject(root) {|tree, nex| tree.add_value(nex)}
  end

  def symmetric_balanced_trees(count, value)
    c_balanced(5, value).select{|tree| tree.symmetric?}
  end

  def hbal_trees(height, value)
    return [End.new] if height <= 0
    return [Leaf(value)] if height == 1
    lack_trees = hbal_trees(height - 2, value)
    contented_trees = hbal_trees(height - 1, value)
    cc_trees = contented_trees.flat_map{|lt| contented_trees.map{|rt| Node(value, lt, rt)}}
    lc_trees = contented_trees.flat_map{|ct| lack_trees.flat_map{|lt| [Node(value, ct, lt), Node(value, lt, ct)]}}
    cc_trees + lc_trees
  end

  def min_hbal_nodes(height)
    return 0 if height == 0
    return 1 if height == 1
    min_hbal_nodes(height-1) + min_hbal_nodes(height-2) + 1
  end

  def max_hbal_height(count)
    (1..Float::INFINITY).take_while{|i| min_hbal_nodes(i) <= count}.last
  end

  def min_hbal_height(count)
    count = 1
    count += 1 while (count /= 2) > 0
    count
  end

  def hbal_trees_with_nodes(count, value)
    (min_hbal_height(count)..max_hbal_height(count)).flat_map{|height|
      hbal_trees(height, value)
    }.select{|tree| tree.node_count == count}
  end
end

class Tree
  extend TreeFactory
end

class Node
  extend TreeFactory
  def initialize(value, left, right)
    @value, @left, @right = value, left, right
  end

  def symmetric?
    @left.mirror_of?(@right)
  end

  def mirror_of?(tree)
    case tree
    when Node then
      @left.mirror_of?(tree.right) && @right.mirror_of?(tree.left)
    else
      false
    end
  end

  def add_value(value)
    if @value > value
      @left = @left.add_value(value)
    else
      @right = @right.add_value(value)
    end
    self
  end

  def node_count
    1 + @left.node_count + @right.node_count
  end

  def value
    @value
  end

  def left
    @left
  end

  def right
    @right
  end

  def to_s
    "T(#{@value.to_s} #{@left.to_s} #{@right.to_s})"
  end
end

class End
  extend TreeFactory
  def symmetric?
    true
  end

  def mirror_of?(tree)
    tree.class == End
  end

  def add_value(value)
    End.Leaf(value)
  end

  def node_count
    0
  end

  def to_s
    "."
  end
end