Trivia-based mystery-cache solver. Output in KML format.

geocache-solver.rb

#!/usr/bin/ruby

=begin
Easy quiz/trivia mystery-cache solver. Takes possible
answers to questions and instructions how to transform
the indices into coordinates. Brute-force is used to
check all possible combinations that produce meaningful
coordinates. Returns a set of waypoins in KML format.

The values here are real for a specific Geocache.
I won’t provide the GC code though. If somebody comes
here and knows what to do with this script, he deserves
the set of possibile coordinates as a reward.
=end

require 'set'
require 'pp'

# Possilble answers to questions. If we’re sure that
# some answers are bullshit or, on the other hand,
# we know some answers for sure, it is possible to
# fill in just those answers that are worth trying.
INPUT = {
    indices: {
      A: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
      B: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
      C: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
      D: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
      E: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
      F: Set.new([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    },
    transformations: {
      _1: -> ind { ind[:B] / ind[:A] },
      _2: -> ind { ind[:F] / ind[:D] },
      _3: -> ind { ind[:E] / 7 + ind[:A] ** 3 },
      _4: -> ind { Math.sqrt(ind[:F]) / 3 + 2 },
      _5: -> ind { (ind[:C] / ind[:E] + ind[:A]) * ind[:F] / (ind[:D] ** 2) },
      _6: -> ind { (10 * ind[:E] + ind[:C]) / (ind[:F] + ind[:A]) - ind[:A] }
    }
}

class Kml
  def initialize points = {}
    @points = points
  end

  def[]= name, coordinates
    @points[name] = coordinates
  end

  def to_s
    out = ""
    out << "<?xml version=\"1.0\" encoding=\"UTF-8\" ?>\n"
    out << "<kml xmlns=\"http://www.opengis.net/kml/2.2\">\n"
    out << "\t<Document>\n"

    @points.each_pair do |name, point|
      out << "\t\t<Placemark>\n"
      out << "\t\t\t<name>#{name}</name>\n"
      out << "\t\t\t<description>#{point.to_s :DM}</description>\n"
      out << "\t\t\t<Point>\n"
      out << "\t\t\t\t<coordinates>#{point.to_s :KML}</coordinates>\n"
      out << "\t\t\t</Point>\n"
      out << "\t\t</Placemark>\n"
    end

    out << "\t</Document>\n"
    out << "</kml>\n"
  end
end

class Point
  def initialize latitude, longitude = nil
    if latitude.is_a? String
      match = input ~ /^(?<LAT_CARDINAL>[NS]) (?<LAT_DEGREES>\d+)° (?<LAT_MINUTES>\d+\.\d+) (?<LON_CARDINAL>[EW]) (?<LON_DEGREES>\d+)° (?<LON_MINUTES>\d+\.\d+)$/
      raise ArgumentError if match.nil?

      @latitude = PointPart.new match[:LAT_CARDINAL],
                                match[:LAT_DEGREES],
                                match[:LAT_MINUTES]
      @longitude = PointPart.new match[:LON_CARDINAL],
                                 match[:LON_DEGREES],
                                 match[:LON_MINUTES]
    elsif latitude.is_a? LatitudePointPart and longitude.is_a? LongitudePointPart
      @latitude = latitude
      @longitude = longitude
    else
      raise ArgumentError
    end
  end

  def to_s format = :DM
    case format
      when :DM
        "#{@latitude.to_s :DM} #{@longitude.to_s :DM}"
      when :D
        "#{@latitude.to_s :D},#{@longitude.to_s :D}"
      when :KML
        "#{@longitude.to_s :D},#{@latitude.to_s :D},0"
      else
        raise ArgumentError
    end
  end
end

class PointPart
  def initialize cardinal, degrees = nil, minutes = nil
    raise NameError, "Do not initialize PointPart directy. Pick LatitudePointPart or LongitudePointPart instead." if self.class == PointPart

    if cardinal.is_a? String
      input = cardinal

      regexp = Regexp.new "^(?<CARDINAL>[#{allowed_cardinals.to_a.join}]) (?<DEGREES>\d+)° (?<MINUTES>\d+\.\d+)$"
      match = regexp.match input
      raise ArgumentError if match.nil?

      @cardinal = match[:CARDINAL].to_s
      @degrees = match[:DEGREES].to_i
      @minutes = match[:MINUTES].to_f
    elsif cardinal.is_a? Symbol and degrees.is_a? Fixnum and minutes.is_a? Float and allowed_cardinals.include? cardinal
      @cardinal = cardinal
      @degrees = degrees
      @minutes = minutes
    else
      raise ArgumentError
    end
  end

  def to_s format = :DM
    case format
      when :DM
        format_dm
      when :D
        format_d
      else
        raise ArgumentError
    end
  end

  def format_dm
    minutes = @minutes.round 3
    sprintf "%s %d° %.3f", @cardinal, @degrees, minutes
  end

  def format_d
    d = @degrees + (@minutes / 60)
    d = d * -1 if [:S, :W].include? @cardinal

    d
  end

end

class LatitudePointPart < PointPart
  def allowed_cardinals
    Set.new [:N, :S]
  end
end

class LongitudePointPart < PointPart
  def allowed_cardinals
    Set.new [:E, :W]
  end
end

# Transform the computed indiced to coordinates.
def indices2point ind
  # All indices need to be Floats. During the computation
  # process, Integers might not be sufficent, even though
  # the result must be an Integer.
  ind.each_key { |k| ind[k] = ind[k].to_f }

  begin
    computed = {};
    INPUT[:transformations].each_pair do |key, func|
      computed[key] = func.call ind
    end
  rescue ZeroDivisionError
    return nil
  end

  # Negative numbers, multi-figure numbers and decimal
  # numbers are not acceptable.
  computed.each_value do |kousek|
    return nil unless (0..9).include? kousek and kousek == kousek.round
  end

  citelne = []
  ind.each_key do |c| citelne << "#{c} = #{ind[c].to_i}" end

  computed.each_key { |k| computed[k] = computed[k].to_i }

  latitude = LatitudePointPart.new :N, 50, "10.#{computed[:_1]}#{computed[:_2]}#{computed[:_3]}".to_f
  longitude = LongitudePointPart.new :E, 14, "29.#{computed[:_4]}#{computed[:_5]}#{computed[:_6]}".to_f

  Point.new latitude, longitude
end

# The core of the solver: This method finds all
# permutations of the possible answers. It is
# called recursively: It adds all possible
# answers to the first already unanswered
# question. At the beginning, an empty object
# is passed. That means that the first
# unanswered question is the first one. When
# there is no answer to add up, result is
# returned.
def get_permutations already_known = {}
  $i = 0 if already_known.empty?
  $i = $i.succ
  $stderr.print "." if $i % 1000 == 0
  possible_results = Set.new

  INPUT[:indices].each_key do |key|
    # This indice is already known, next please.
    next if already_known.has_key? key

    INPUT[:indices][key].each do |prvek|
      possible_result = already_known.clone
      possible_result[key] = prvek

      extended = get_permutations possible_result
      if extended.empty?
        # Nothing to add. We’ve reached the end. This is the real
        # raw possible result we wanted to find.
        possible_results << possible_result
      else
        # The recursive call returned even more extended possible
        # results. That means the current indice is not the last
        # one. All these possible results for each possibility
        # already known are merged together.
        # E.g. if possibilities of an indice F has been added in
        # this level, the recursion call returns all possibilities,
        # how to add an indice G. The recursion is called for
        # every F and then merged together.
        possible_results = possible_results.merge extended
      end
    end

    # Only one indice is added in the call. The next ones are
    # added by a recursion call. Nothing to do on this level.
    break
  end

  return possible_results
end

# KML output.

kml = Kml.new

possible_results = get_permutations
i = 1
possible_results.each do |result|
  coordinates = indices2point result

  unless coordinates.nil?
    kml["Result no. #{i}"] = coordinates
    i = i.succ
  end
end

print kml