#!/usr/bin/env ruby

# Experimental compression for hypnotoad1k image data

HYPNOTOAD =
  "00000111110000000011111000000000000000000000000000" +
  "00001222221000000122222100000000000000000000000000" +
  "00001233321100001123332100000000000000000000000000" +
  "00001311131410014131113100000000000000000000000000" +
  "00001233321441144123332100000000000000000000000000" +
  "00001222211444444122222100000000000000000000000000" +
  "00000111144444444411111410000000000000000000000000" +
  "00000014444444444444444510000000000000000000000000" +
  "00000154444444455555555510000000000000000000000000" +
  "00000155444444555555555551000000000000000000000000" +
  "00001555544455555555555551000000000000000000000000" +
  "00015555555555555555555545100000000000000000000000" +
  "00001111111111111555515545100000000000000000000000" +
  "00001666666666666111551544510000000000000000000000" +
  "00001666666666666666151544551000000000000000000000" +
  "00000166666666666661555554555110000000000011100000" +
  "00000016666666666666155555551771100000000144411000" +
  "00000016666666666666666555551771411000001444444100" +
  "00000016666666666666666555517771445110014444444410" +
  "00000016666666666666666555177771445551014444444410" +
  "00000011666666666666666611777715444455114444444441" +
  "00000017116666666666661177777155544445114441444441" +
  "00000117771111111111117777771555554444514414444441" +
  "00001511777777777777777777115555555444514414444410" +
  "00001516117777171717177111555554455555544144444410" +
  "00001551661111111111111666555554155555544144444410" +
  "00001551666666661888816666555554144555541444444410" +
  "00001515166666661888816666555554414555441444444100" +
  "00000115166666666111166666155555415455411444444100" +
  "00000015516666666666666666615555515555414444441000" +
  "00111115516666666666666666661555551544414444441000" +
  "01555515551666666666666666666115551544414444410000" +
  "15155515555166666666666611111555551544414444100000" +
  "01515515555511166666666155555555515541144444411000" +
  "00155515555555166666666611155555511114444444444110" +
  "00011115555511111111111115555551100014441141114441" +
  "00000001155510000000000001151510000014110141001111" +
  "00000000151151000000000000015100000001000144100000" +
  "00000000151010000000000000001000000000000014100000" +
  "00000000010000000000000000000000000000000001000000"

def substitute_chars(input, unused_chars, subst_map)
  word_count = {}
  input.each_char.with_index(0) do |char, idx|
    next if idx == input.size - 1
    word = input[idx .. idx + 1]
    word_count[word] = 0 if word_count[word].nil?
    word_count[word] += 1
  end
  compressed_candidate = input
  compressed = input
  subst = nil
  word_count.each do |word, count|
    next if count < 4 || !compressed.include?(word) || unused_chars.empty?
    subst = unused_chars.shift if subst.nil?
    compressed_candidate = input.gsub(word, subst)
    if compressed_candidate.size < compressed.size
      compressed = compressed_candidate
      subst_map[subst] = word
    end
  end
  return compressed
end

def compress(input)
  unused_chars = []
  subst_characters = (' ' .. '~').to_a.reverse
  subst_characters.each do |char|
    # substitution characters must be safe from RegExp point of view
    next if ['|', '\\', '[', ']', '?', '+', '*', '(', ')',
             '.', '^', '\'', '$', '{', '}'].include?(char)
    unused_chars.push(char) if !input.include?(char)
  end
  subst_map = {}
  compressed = input
  prev_compressed = ''
  while (unused_chars.size > 0) do
    prev_compressed = compressed
    compressed = substitute_chars(compressed, unused_chars, subst_map)
    break if prev_compressed == compressed
  end

  subst = ''
  subst_map.keys.each do |char|
    subst = subst + "#{char}#{subst_map[char]}"
  end

  puts "Compressed : '#{compressed}'"
  puts "Subst. map : '#{subst}'"
  puts "Size       : #{compressed.size + subst.size} / #{input.size}"
end

compress(HYPNOTOAD)