# Converts the given string into a "HH:MM:SS" timestamp.
def solution(string)
  digits = digits36(string)
  num_seconds = compress(*digits)
  Time.at(num_seconds).utc.strftime('%H:%M:%S')
end

# Converts each character in the given string into a base 36 digit.
def digits36(string)
  string.each_char.map { |char| digit36(char) }
end

# Converts the given character into a base 36 digit:
# decimal digits (0..9) + uppercase letters (10..35)
def digit36(char)
  case char
  when '0'..'9' then char.ord - '0'.ord
  when 'A'..'Z' then char.ord - 'A'.ord + 10
  else raise ArgumentError, "not a base36 digit: #{char.inspect}"
  end
end

# Combines the given base 36 digits together into a 16-bit integer.
SECONDS_PER_DAY = 24 * 60 * 60 # hours * minutes/hour * seconds/minute
SECONDS_PER_DAY_BITS = Math.log2(SECONDS_PER_DAY).ceil # 2 ** exponent
def compress(*chars)
  return 0 if chars.empty?
  bits = SECONDS_PER_DAY_BITS / chars.length
  mask = (1 << bits) - 1
  chars.inject(0) do |acc, char|
    # grab lower bits from each character and place them side by side
    (acc << bits) | (char & mask)
  end % SECONDS_PER_DAY
end

$ irb --simple-prompt -r ./solution.rb
## ruby 2.1.2p95 (2014-05-08) [x86_64-linux-gnu]

>> solution "ABCD"
"12:13:01"

>> digits36 "ABCD"
[10, 11, 12, 13]

>> compress 10, 11, 12, 13
43981

>> Time.at(43981).utc
1970-01-01 12:13:01 UTC

$ irb --simple-prompt -r ./solution.rb
## ruby 2.1.2p95 (2014-05-08) [x86_64-linux-gnu]

>> solution "ABCDEFG"
"03:09:32"

>> digits36 "ABCDEFG"
[10, 11, 12, 13, 14, 15, 16]

>> compress 10, 11, 12, 13, 14, 15, 16
11372

>> Time.at(11372).utc
1970-01-01 03:09:32 UTC

$ ruby -r ./comparison.rb -r pp -e 'pp Comparator.compare Input.combinations' > comparison.txt

$ vim comparison.txt # do some post-processing to format the results into a nice data table

# BEST CASE

$ ruby -r ./comparison.rb -r pp -e 'pp Comparator.compare Input.best_case, /^preserve_lower_bits$/'
[{"Compression algorithm"=>:preserve_lower_bits,
  "Number of strings (domain)"=>65536,
  "Number of timestamps (codomain)"=>65536,
  "Number of unique timestamps"=>65536,
  "Number of timestamps reused"=>0,
  "Probability of timestamp reuse"=>0.0,
  "Number of strings mapped to reused timestamps"=>0,
  "Probability of string mapped to reused timestamp"=>0.0}]

# WORST CASE

$ ruby -r ./comparison.rb -r pp -e 'pp Comparator.compare Input.worst_case, /^preserve_lower_bits$/'
[{"Compression algorithm"=>:preserve_lower_bits,
  "Number of strings (domain)"=>160000,
  "Number of timestamps (codomain)"=>65536,
  "Number of unique timestamps"=>20736,
  "Number of timestamps reused"=>44800,
  "Probability of timestamp reuse"=>0.68359375,
  "Number of strings mapped to reused timestamps"=>139264,
  "Probability of string mapped to reused timestamp"=>0.8704}]

# NO CASE

$ ruby -r ./comparison.rb -r pp -e 'pp Comparator.compare Input.no_case, /^preserve_lower_bits$/'
[{"Compression algorithm"=>:preserve_lower_bits,
  "Number of strings (domain)"=>1679616,
  "Number of timestamps (codomain)"=>65536,
  "Number of unique timestamps"=>0,
  "Number of timestamps reused"=>65536,
  "Probability of timestamp reuse"=>1.0,
  "Number of strings mapped to reused timestamps"=>1679616,
  "Probability of string mapped to reused timestamp"=>1.0}]

$ irb --simple-prompt -r ./comparison.rb
## ruby 2.1.2p95 (2014-05-08) [x86_64-linux-gnu]

>> Input.singleton_methods
[:combinations, :permutations, :best_case, :worst_case, :no_case]

>> Input.combinations
#<Enumerator: ...>

>> Input.combinations.take(3)
[["0", "1", "2", "3"], ["0", "1", "2", "4"], ["0", "1", "2", "5"]]

>> Input.permutations.take(3)
[["0", "0", "0", "0"], ["0", "0", "0", "1"], ["0", "0", "0", "2"]]

>> Input.best_case.take(3)
[["0", "0", "0", "0"], ["0", "0", "0", "1"], ["0", "0", "0", "2"]]

>> Input.worst_case.take(3)
[["G", "G", "G", "G"], ["G", "G", "G", "H"], ["G", "G", "G", "I"]]

>> Input.no_case.take(3)
[["0", "0", "0", "0"], ["0", "0", "0", "1"], ["0", "0", "0", "2"]]

>> def Compressor.my_new_solution(a, b, c, d)
>>   a + b - c * d
>> end
:my_new_solution

>> Comparator.measure Input.combinations, :my_new_solution
{"Compression algorithm"=>:my_new_solution,
 "Number of strings (domain)"=>58905,
 "Number of timestamps (codomain)"=>1183,
 "Number of unique timestamps"=>7,
 "Number of timestamps reused"=>1176,
 "Probability of timestamp reuse"=>0.9940828402366864,
 "Number of strings mapped to reused timestamps"=>58898,
 "Probability of string mapped to reused timestamp"=>0.9998811645870469}

>> Comparator.compare Input.combinations
# ... too much output, so it's omitted ...

>> Comparator.compare Input.combinations, /my_new|char/
[{"Compression algorithm"=>:merge_fourth_char_into_others,
  "Number of strings (domain)"=>58905,
  "Number of timestamps (codomain)"=>9936,
  "Number of unique timestamps"=>1841,
  "Number of timestamps reused"=>8095,
  "Probability of timestamp reuse"=>0.8147141706924316,
  "Number of strings mapped to reused timestamps"=>57064,
  "Probability of string mapped to reused timestamp"=>0.9687462863933453},
 {"Compression algorithm"=>:discard_fourth_char,
  "Number of strings (domain)"=>58905,
  "Number of timestamps (codomain)"=>6545,
  "Number of unique timestamps"=>561,
  "Number of timestamps reused"=>5984,
  "Probability of timestamp reuse"=>0.9142857142857143,
  "Number of strings mapped to reused timestamps"=>58344,
  "Probability of string mapped to reused timestamp"=>0.9904761904761905},
 {"Compression algorithm"=>:my_new_solution,
  "Number of strings (domain)"=>58905,
  "Number of timestamps (codomain)"=>1183,
  "Number of unique timestamps"=>7,
  "Number of timestamps reused"=>1176,
  "Probability of timestamp reuse"=>0.9940828402366864,
  "Number of strings mapped to reused timestamps"=>58898,
  "Probability of string mapped to reused timestamp"=>0.9998811645870469}]

# Combines the given base 36 digits together into a 16-bit integer.
module Compressor
  extend self

  #              _ _             _       _   _
  #  _ __  _   _| | |  ___  ___ | |_   _| |_(_) ___  _ __
  # | '_ \| | | | | | / __|/ _ \| | | | | __| |/ _ \| '_ \
  # | | | | |_| | | | \__ \ (_) | | |_| | |_| | (_) | | | |
  # |_| |_|\__,_|_|_| |___/\___/|_|\__,_|\__|_|\___/|_| |_|
  #

  # Why bother with all of this? Just discard the fourth character.
  def discard_fourth_char(a, b, c, d)
    (a * (36 ** 2)) + (b * 36) + c
  end

  #                              _       _   _
  #  _ __ ___  _   _   ___  ___ | |_   _| |_(_) ___  _ __  ___
  # | '_ ` _ \| | | | / __|/ _ \| | | | | __| |/ _ \| '_ \/ __|
  # | | | | | | |_| | \__ \ (_) | | |_| | |_| | (_) | | | \__ \
  # |_| |_| |_|\__, | |___/\___/|_|\__,_|\__|_|\___/|_| |_|___/
  #            |___/

  def merge_fourth_char_into_others(a, b, c, d)
    c += (d & 0b11)
    b += (d & 0b1100) >> 2
    a += (d & 0b110000) >> 4
    (a * (36 ** 2)) + (b * 36) + c
  end

  # This is the solution described in this article.  (((THE WINNER!)))
  def preserve_lower_bits(a, b, c, d)
    upper_byte = ((a & 0xF) << 4) | (b & 0xF)
    lower_byte = ((c & 0xF) << 4) | (d & 0xF)
    (upper_byte << 8) | lower_byte
  end

  # Generate preserve_bits_WXYZ() functions that try all combinations.
  preserve_bits_helper = lambda do |a, b, c, d, bits|
    fetch_bits = lambda do |char|
      bits.each_with_index.map do |bit, index|
        char[bit] << index
      end.reduce(:|).to_i
    end
    upper_byte = (fetch_bits.(a) << 4) | fetch_bits.(b)
    lower_byte = (fetch_bits.(c) << 4) | fetch_bits.(d)
    ((upper_byte << 8) | lower_byte)
  end
  (0..5).to_a.combination(4).each do |bits|
    define_method "preserve_bits_#{bits.sort.reverse.map(&:next).join}" do
      |a, b, c, d| preserve_bits_helper.(a, b, c, d, bits)
    end
  end

  def preserve_lower_bits_then_add_upper_bits(a, b, c, d)
    lower_bits = lambda {|char| (char & 0b001111) }
    upper_bits = lambda {|char| (char & 0b110000) >> 4 }
    upper_byte = (lower_bits.(a) << 4) | lower_bits.(c)
    lower_byte = (lower_bits.(b) << 4) | lower_bits.(d)
    extra_byte = (upper_bits.(a) << 6) | (upper_bits.(c) << 4) |
                 (upper_bits.(b) << 2) | (upper_bits.(d) << 0)
    ((upper_byte << 8) | lower_byte) + extra_byte
  end

  def preserve_lower_bits_then_xor_upper_bits(a, b, c, d)
    lower_bits = lambda {|char| (char & 0b001111) }
    upper_bits = lambda {|char| (char & 0b110000) >> 4 }
    xor_helper = lambda do |char|
      ((upper_bits.(char) ^ (lower_bits.(char) >> 2)) << 2) |
       (lower_bits.(char) & 0b11)
    end
    upper_byte = (xor_helper.(a) << 4) | xor_helper.(c)
    lower_byte = (xor_helper.(b) << 4) | xor_helper.(d)
    ((upper_byte << 8) | lower_byte)
  end

  #                 _             _       _   _
  #  _ __ ___  __ _| |  ___  ___ | |_   _| |_(_) ___  _ __  ___
  # | '__/ _ \/ _` | | / __|/ _ \| | | | | __| |/ _ \| '_ \/ __|
  # | | |  __/ (_| | | \__ \ (_) | | |_| | |_| | (_) | | | \__ \
  # |_|  \___|\__,_|_| |___/\___/|_|\__,_|\__|_|\___/|_| |_|___/
  #

  # https://en.wikipedia.org/wiki/Pearson_hashing
  PEARSON_TABLE = ( 0 ... 2**16 ).to_a.shuffle
  def pearson_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      index = hash ^ char
      hash = PEARSON_TABLE[index]
    end
    hash
  end

  # http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  def rotating_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash = (hash << 4) ^ (hash >> 28) ^ char
    end
    hash
  end

  # http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  def bernstein_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash = 33 * hash + char
    end
    hash
  end

  # http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  def bernstein_xor_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash = 33 * hash ^ char
    end
    hash
  end

  # http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  def shift_add_xor_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash ^= (hash << 5) + (hash >> 2) + char
    end
    hash
  end

  # http://www.isthe.com/chongo/tech/comp/fnv/#FNV-1
  def fnv1_hash(a, b, c, d)
    hash = 2166136261
    [a, b, c, d].each do |char|
      hash = (hash * 16777619) ^ char
    end
    hash
  end

  # http://www.isthe.com/chongo/tech/comp/fnv/#FNV-1a
  def fnv1a_hash(a, b, c, d)
    hash = 2166136261
    [a, b, c, d].each do |char|
      hash = (hash ^ char) * 16777619
    end
    hash
  end

  # https://en.wikipedia.org/wiki/Jenkins_hash_function
  def jenkins_one_at_a_time_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash += char
      hash += (hash << 10)
      hash ^= (hash >> 6)
    end
    hash += (hash << 3)
    hash ^= (hash >> 11)
    hash += (hash << 15)
    hash
  end

  # Algorithm::Nhash - Exim nhash algorithm
  # http://cpansearch.perl.org/src/MOOLI/Algorithm-Nhash-0.002/lib/Algorithm/Nhash.pm
  NHASH_PRIMES = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
                  61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
  def exim_nhash(a, b, c, d)
    sum = 0
    i = 0
    [a, b, c, d].each do |char|
      i += 28
      i %= 29
      sum += NHASH_PRIMES[i] * char
    end
    sum
  end

  # https://en.wikipedia.org/wiki/Fletcher%27s_checksum
  def fletcher16_checksum(a, b, c, d)
    sum1 = 0
    sum2 = 0

    [a, b, c, d].each do |char|
      sum1 = (sum1 + char) % 255
      sum2 = (sum2 + sum1) % 255
    end

    (sum2 << 8) | sum1
  end

  # https://en.wikipedia.org/wiki/BSD_checksum
  def bsd_checksum(a, b, c, d)
    checksum = 0                 # The checksum mod 2^16.
    [a, b, c, d].each do |char|
      checksum = (checksum >> 1) + ((checksum & 1) << 15)
      checksum += char
      checksum &= 0xffff         # Keep it within bounds.
    end
    checksum
  end

  # https://en.wikipedia.org/wiki/Longitudinal_redundancy_check
  def lrc_checksum(a, b, c, d)
    lrc = 0
    [a, b, c, d].each do |char|
      lrc = (lrc + char) & 0xFF
    end
    lrc = (((lrc ^ 0xFF) + 1) & 0xFF)
  end

  # http://www.cse.yorku.ca/~oz/hash.html
  def djb2_hash(a, b, c, d)
    hash = 5381
    [a, b, c, d].each do |char|
      hash = ((hash << 5) + hash) + char # hash * 33 + c
    end
    hash
  end

  # http://www.cse.yorku.ca/~oz/hash.html
  def sdbm_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash = char + (hash << 6) + (hash << 16) - hash
    end
    hash
  end

  # http://www.cse.yorku.ca/~oz/hash.html
  def lose_lose_hash(a, b, c, d)
    hash = 0
    [a, b, c, d].each do |char|
      hash += char
    end
    hash
  end

end

module Solver
  extend self

  # Converts the given 4-character string into a "HH:MM:SS" timestamp.
  def solution(string, compressor)
    a, b, c, d  = digits36(string)
    num_seconds = Compressor.send(compressor, a, b, c, d)
    Time.at(num_seconds).strftime('%H:%M:%S')
  end

  # Converts each character in the given string into a base 36 digits.
  def digits36(string)
    string.each_char.map { |char| digit36(char) }
  end

  # Converts the given character into a base 36 digit:
  # decimal digits (0..9) + uppercase letters (10..35)
  def digit36(char)
    case char
    when '0'..'9' then char.ord - '0'.ord
    when 'A'..'Z' then char.ord - 'A'.ord + 10
    else -1
    end
  end

  # Converts the given base 36 digit into a character.
  def undigit36(code)
    case code
    when  0..9  then ('0'.ord + code).chr
    when 10..35 then ('A'.ord + (code - 10)).chr
    else '?'
    end
  end

end

module Input
  extend self

  DOMAIN = ('0'..'9').to_a + ('A'..'Z').to_a

  def combinations
    DOMAIN.combination(4)
  end

  def permutations(domain=DOMAIN)
    if block_given?
      domain.each do |a|
        domain.each do |b|
          domain.each do |c|
            domain.each do |d|
              yield [a, b, c, d]
            end
          end
        end
      end
    else
      enum_for __method__, domain
    end
  end

  def best_case
    permutations DOMAIN[0..15]
  end

  def worst_case
    permutations DOMAIN[16..35]
  end

  alias no_case permutations

end

module Comparator
  extend self

  # Compares the fitness of all compressors that match the given regexp.
  def compare(inputs, compressor_regexp=//)
    Compressor.singleton_methods.grep(compressor_regexp).
      map { |compressor| measure(inputs, compressor) }.
      sort_by { |measurement| measurement['Probability of timestamp reuse'] }
  end

  # Measures the fitness of the given compressor.
  def measure(inputs, compressor)
    reuse_by_timestamp = measure_reuse(inputs, compressor)

    num_keys = reuse_by_timestamp.count
    num_values = reuse_by_timestamp.values.reduce(:+).to_i

    actual_reuse = reuse_by_timestamp.select {|k,v| v > 1 }
    num_keys_reused = actual_reuse.count
    num_values_reused = actual_reuse.values.reduce(:+).to_i

    {
      'Compression algorithm'                            => compressor,
      'Number of strings (domain)'                       => num_values,
      'Number of timestamps (codomain)'                  => num_keys,
      'Number of unique timestamps'                      => num_keys - num_keys_reused,
      'Number of timestamps reused'                      => num_keys_reused,
      'Probability of timestamp reuse'                   => num_keys_reused / num_keys.to_f,
      'Number of strings mapped to reused timestamps'    => num_values_reused,
      'Probability of string mapped to reused timestamp' => num_values_reused / num_values.to_f,
    }
  end

  def measure_reuse(inputs, compressor)
    reuse_by_timestamp = Hash.new(0)
    inputs.each do |characters|
      string = characters.join
      timestamp = Solver.solution(string, compressor)
      reuse_by_timestamp[timestamp] += 1
    end
    reuse_by_timestamp
  end

end