# Q: Write a function that takes two sorted lists/arrays,
# and returns a third list/array, which is also sorted, and
# which contains all the elements from the two input arrays.
# NOTE: Depending on the language used, being destructive
# to your input may be a very important consideration.
# Assume inputs are *proper* lists/collection/whatever. Depending
# on the language, this may include nulls (e.g. bare-bones
# linked lists in Java/C/C++.
# PS: Does that remind you of some sorting algorithm?
def merge(a_list, b_list)

  if (a_list.empty?)
    return b_list
  elsif (b_list.empty?)
    return a_list
  end
  a_top = a_list.first
  b_top = b_list.first
  if (a_top < b_top)
    return [a_top] + merge(
        a_list[1..-1], b_list)
  else
    return [b_top] + merge(a_list, b_list[1..-1])
  end
end

# Q: given a list of stock prices (just a single stock),
# where indices can be treated as days. Write a function that
# will determine the best deal - made of a single buy order
# followed by a single sell order - which will maximize
# the profit. Return a tuple (struct, object) with the recommendation.
# NOTE: this version also includes some logging code, which is just
# me trying some more advanced Ruby concepts... because inner functions,
# apparently, don't have access to outer function scope.
# NOTE2: let's wrap Deal in a class, just for giggles (OpenStruct would be better, but less giggly).
class Deal
  attr_accessor :buy_date
  attr_accessor :sell_date
  attr_accessor :buy_price
  attr_accessor :sell_price

  def to_s
    "[Buy on day #{buy_date} for #{buy_price}" + (sell_date.nil? ? "]" : " and sell on day #{sell_date} for #{sell_price}]")
  end

  def == (another_deal)
    result = (buy_date.eql? another_deal.buy_date) && (sell_date.eql? another_deal.sell_date)
    return result
  end
end

def max_profit(stock_prices, debug = false)
  def gen_log(debug)
    return Proc.new { |msg| puts msg if debug }
  end

  if (stock_prices.empty?)
    raise ArgumentError, "Please provide a non-empty list of prices"
  end
  log = gen_log(debug)
  # initialize best deal by buying and selling (maybe prices will only go down) on the first day
  best_deal = Deal.new
  candidate_deal = Deal.new
  best_deal.buy_date = best_deal.sell_date = candidate_deal.buy_date = 0
  best_deal.buy_price = best_deal.sell_price = candidate_deal.buy_price = stock_prices.first

  stock_prices[1..-1].each_with_index do |stock_price, index|
    today = index + 1 # since we already considered the first (0'th) day
    log.call("day #{today}, price is #{stock_price}, best deal so far is #{best_deal}, current buy candidate price is #{candidate_deal.buy_price}")
    if (best_deal.sell_price - best_deal.buy_price < stock_price - candidate_deal.buy_price)
      # selling at this time would make for a better deal
      log.call("old sell price was #{best_deal.sell_price}, found better deal for #{stock_price} on day #{today}. Buy price was #{candidate_deal.buy_price}")
      best_deal.sell_date = today
      best_deal.buy_date = candidate_deal.buy_date
      best_deal.sell_price = stock_price
      best_deal.buy_price = candidate_deal.buy_price
    end
                      # consider buying today
    if (candidate_deal.buy_price > stock_price)
      # buying at this price *could* make for a better deal, depending on future prices
      log.call("buying for #{stock_price} on day #{today} is now a buy candidate")
      candidate_deal.buy_date = today
      candidate_deal.buy_price = stock_price
    end
  end

  return best_deal

end

# max_profit

# Q: oldest problem in the book. Used mostly to fill in the last 10 minutes, unless
# the conversation is interesting!
# Write a function that takes a string and determines whether it is a palindrome
def palindrome?(str)
  return true if str.length < 2
  middle_index = str.length/2
  forward_index = str.length.even? ? middle_index : middle_index + 1
  backward_index = middle_index - 1
  while (backward_index >= 0) do
    if str[forward_index] != str[backward_index]
      return false
    end
    forward_index += 1
    backward_index -= 1
  end
  return true
end

class TrieNode
  def initialize(value)
    @node_value = value
    @children = []
  end

  def add_child(node)
    @children.push(node)
  end
end

# produce all the permutations of a given string
def build_permutations(str)
  # a helper function which returns a new array which is equal to the one passed,
  # but without the element at the index i.
  def array_minus(arr, i)
    i == 0 ? arr[1..-1] : arr[0..i-1] + (arr[i+1..-1] || [])
  end

  # recursive helper implementation, working over an array
  # returns an array of all the permutations of a given array (each being iself an array)
  def permutations_rec(arr)
    # base case - if array is empty or one-element, return it
    return [arr] if arr.length <= 1

    result = []
    for i in 0..arr.length-1
      # get the element at the index i and the 'rest' of the array
      element = arr[i]
      rec_arr = array_minus(arr, i)
      # recursively find all the permutations of what's left
      rec_result = permutations_rec(rec_arr)
      # recursive result is a list of lists, each of those lists being one permutation
      rec_result.each do |rec_result_arr|
        # add the element popped earlier to the beginning of each permutation,
        # and store that in the result
        result.push([element] + rec_result_arr)
      end
    end
    return result
  end

  # convert the string into an array and call the recursive helper
  arr = str.split("")
  result = permutations_rec(arr)
  # return lists of strings, for better readability
  return result.collect do |one_permutation|
    one_permutation.join()
  end

end

# rotating cipher
def rotx(x, string, encrypt=true)

  def is_lower?(c)
    /[a-z]/ =~ c
  end

  def is_upper?(c)
    /[A-Z]/ =~ c
  end

  def rotate_char(c, distance)
    base = (is_lower?(c) ? 97 : 65)
    top = (is_lower?(c) ? 122 : 90)
    where_to = c.ord + distance

    if where_to > top
      where_to = base + (where_to - top) - 1
    elsif where_to < base
      where_to = top - (base - where_to) + 1
    end
    where_to.chr
  end

  def map_char(c, distance)
    # it is not a character, leave it alone
    (is_lower? c or is_upper?(c)) ? rotate_char(c, distance) : c
  end

  direction = encrypt ? 1 : -1
  distance = (x * direction) % (26 * direction)

  input_chars = string.chars

  input_chars.map { |c| map_char(c, distance ) }.join('')

end
