Eruption explosive doomsday calculation

doomsday.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 19 05:54:37 2012

Eruption explosive doomsday calculation.
Copyright (C) 2012 Danilo de Jesus da Silva Bellini

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.

Problem description:

Given a generic 2D map with volcanos and cities, such as:

     ......*
     ..X....
     .......
     ....*..

Where X are the volcanos and * are the cities (or any representation without
data loss). After one day, each volcano cloud destroy a neighbor space (but
diagonals), so the map above after one day become like:

     ..X...*
     .XXX...
     ..X....
     ....*..

And so on, where the volcano cloud is interpreted as new volcanos.
Find the number of days until all cities gets destroyed by a volcano.
"""

import unittest
import sys
import copy


# =========================
# Solution one: assignments
# =========================
def doomsday(scenario):
  # Find the number of columns, assuming the scenario is a rectangle
  cols = len(scenario.split("\n", 1)[0])
  # Alternative:
  #cols = scenario.find("\n") if "\n" in scenario else len(scenario)

  # Find the scenario index for all volcanos and cities (generators)
  volcanos = (pos for pos, data in enumerate(scenario) if data == "X")
  cities = (pos for pos, data in enumerate(scenario) if data == "*")

  # Gets the coords (row, col) from the indexes
  coords_volcano = [divmod(volcano, cols + 1) for volcano in volcanos]
  coords_city = [divmod(city, cols + 1) for city in cities]

  # Manhattan distance from each vc (volcano coords) and cc (city coords)
  man_distance = lambda vc, cc: abs(vc[0] - cc[0]) + abs(vc[1] - cc[1])

  # Find last city to be destroyed (max days), where nearest volcano destroy
  # each city (min days, for each city)
  return max(min(man_distance(vc, cc)
                 for vc in coords_volcano)
             for cc in coords_city)


# =======================
# Solution two: one-liner
# =======================
def doomsday_oneliner(scenario):
  # Function from "doomsday" assignments version, but as one statement
  return (lambda cols:
            max(min(abs(vc[0] - cc[0]) + abs(vc[1] - cc[1])
                    for vc in (divmod(volcano, cols + 1)
                               for volcano in (pos
                                               for pos, data
                                                 in enumerate(scenario)
                                                   if data == "X")))
                for cc in (divmod(city, cols + 1)
                           for city in (pos
                                        for pos, data
                                          in enumerate(scenario)
                                        if data == "*")))
         )(len(scenario.split("\n", 1)[0]))


# ===============================
# Solution three: object-oriented
# ===============================
class Cell(object):
  """ Main class for all cell objects """

  def __init__(self, parent, row, col):
    self.parent = parent
    self.row = row
    self.col = col


class VolcanoCell(Cell):
  """ This class represents a volcano """

  def neighbor_coords(self):
    """ Generator for neighbor coords that should be destroyed! """
    if self.row > 0:
      yield (self.row - 1, self.col)
    if self.row < self.parent.rows - 1:
      yield (self.row + 1, self.col)
    if self.col > 0:
      yield (self.row, self.col - 1)
    if self.col < self.parent.cols - 1:
      yield (self.row, self.col + 1)


class CityCell(Cell):
  """ This class represents a city """


class Scenario(object):
  """ A rectangle scenario as an iterable cell container """

  def __init__(self, scenario_str):
    """ Constructor from a string """
    lines = scenario_str.strip("\n").splitlines() # Remove ending "\n" first
    self.rows = len(lines)
    self.cols = len(lines[0])

    # Initialize with empty cells
    self._cell_container = [[None for unused1 in xrange(self.cols)]
                                  for unused2 in xrange(self.rows)]


    # Creates all cells
    for row, line_data in enumerate(lines):
      for col, data in enumerate(line_data):
        self[row, col] = {".": Cell,
                          "X": VolcanoCell,
                          "*": CityCell
                         }[data](self, row, col)

  def __iter__(self):
    """ Scenario iterator (generator) """
    for row in xrange(self.rows):
      for col in xrange(self.cols):
        yield self[row, col]

  def has_cities(self):
    """ Is there at least one city in this scenario? """
    for cell in self:
      if isinstance(cell, CityCell):
        return True
    return False

  def doomsday(self):
    """ Calculate the doomsday creating new scenarios recursively """
    if self.has_cities():
      return 1 + self.one_day_after().doomsday()
    return 0

  def one_day_after(self):
    """ Create a new scenario where all volcanos got 1 step further """
    new_scenario = copy.deepcopy(self)

    new_volcano_coords = set()
    for cell in new_scenario:
      # Ensure the cell is really a copy (this fails with copy.copy)
      assert cell is not self._cell_container[cell.row][cell.col]

      # Updates the copy to know his real parent
      cell.parent = new_scenario

      # We need to know all volcano cells
      if isinstance(cell, VolcanoCell):
        for coords in cell.neighbor_coords():
          new_volcano_coords.add(coords)

    # Now we have a volcano in all volcano's neighbor cells
    for row, col in new_volcano_coords:
      new_scenario[row, col] = VolcanoCell(new_scenario, row, col)

    return new_scenario

  def __getitem__(self, item):
    """ Allows access to scn[row, col] """
    row, col = item
    return self._cell_container[row][col]

  def __setitem__(self, item, value):
    """ Allows scn[row, col] = value assignment, where item = (row, col) """
    row, col = item
    self._cell_container[row][col] = value


def doomsday_object_oriented(scenario):
  return Scenario(scenario).doomsday()


# =========================
# Solution four: functional
# =========================
def doomsday_functional(scenario):

  # Manhattan distance between 2 coord pairs
  man_distance = lambda vc, cc: abs(vc[0] - cc[0]) + abs(vc[1] - cc[1])

  # Find (row, col) tuple for each string index in the scenario input
  coords = lambda pos, total_cols: divmod(pos, total_cols + 1)

  # Finds the number of columns of a given string
  cols = lambda string_data: len(string_data.split("\n", 1)[0])

  # Given all coords, find the doomsday recursively
  days_from_coords = (lambda coords_city, coords_volcano:
                        reduce(max,
                               map(lambda cc:
                                     reduce(min,
                                            map(lambda vc:
                                                  man_distance(vc, cc),
                                                coords_volcano)
                                           ),
                                   coords_city
                               )
                        )
                     )

  # Returns all coords from the given string which have the given item
  # Item is "X" (volcano) or "*" (city)
  get_all_coords = (lambda string_data: lambda item:
                      map(
                        lambda (pos, data): coords(pos, cols(string_data)),
                        filter(lambda (pos, data): data == item,
                               enumerate(string_data)
                        )
                      )
                   )

  # Connect the parts and finish
  return days_from_coords(*map(get_all_coords(scenario),
                               ["*", "X"]
                              )
                         )



# ==================================
# Solution five: functional oneliner
# ==================================
doomsday_functional_oneliner = (lambda scenario:
  (lambda coords_city, coords_volcano:
     reduce(max,
            map(lambda cc:
                  reduce(min,
                         map(lambda vc:
                               abs(vc[0] - cc[0]) + abs(vc[1] - cc[1]),
                             coords_volcano)
                  ),
                  coords_city
            )
     )
  )(*map(lambda item: # Item is "X" (volcano) or "*" (city)
           map(
             lambda (pos, data): divmod(pos,
                                        len(scenario.split("\n", 1)[0]) + 1
                                       ),
             filter(lambda (pos, data): data == item,
                    enumerate(scenario)
             )
           ),
         ["*", "X"]
        )
   )
)


# ========
# Testers!
# ========
def snake2camel(name):
  return name.title().replace("_", "")

def create_tester(doomfunc):
  """ Function to create & register TestCase subclasses to test doomfunc """

  class DoomsdayTesterTemplate(unittest.TestCase):

    def test_linear_1_day(self):
      self.assertEqual(doomfunc("X*"), 1)

    def test_linear_2_days(self):
      self.assertEqual(doomfunc("X.*"), 2)

    def test_linear_2_days_rightpad(self):
      self.assertEqual(doomfunc("X.*."), 2)

    def test_linear_2_cities_2_days_rightpad(self):
      self.assertEqual(doomfunc("*X.*."), 2)

    def test_linear_2_cities_3_days(self):
      self.assertEqual(doomfunc("*X..*"), 3)

    def test_linear_2_cities_3_days_2_volcanos(self):
      self.assertEqual(doomfunc("*X.X..*"), 3)

    def test_vertical_1_day(self):
      self.assertEqual(doomfunc("*" "\n"
                                "X"
                               ), 1)

    def test_vertical_2_days(self):
      self.assertEqual(doomfunc("*" "\n"
                                "*" "\n"
                                "X"
                               ), 2)

    def test_vertical_1_day_upperpad(self):
      self.assertEqual(doomfunc("." "\n"
                                "*" "\n"
                                "X"
                               ), 1)

    def test_2x2_1_day(self):
      self.assertEqual(doomfunc(".." "\n"
                                "*X"
                               ), 1)

    def test_5x7_4_days(self):
      self.assertEqual(doomfunc("..*...." "\n"
                                "..*..*." "\n"
                                "...X*.." "\n"
                                "......." "\n"
                                "...*.*."
                               ), 4)

    def test_6x9_7_days_2_volcanos(self):
      self.assertEqual(doomfunc("..*....*." "\n"
                                "..*..*..." "\n"
                                "...X*...." "\n"
                                "*........" "\n"
                                ".*......." "\n"
                                ".X.*.*..*"
                               ), 7)

    def test_3x11_2_days_3_volcanos_residual_newline(self):
      self.assertEqual(doomfunc("*X......." "\n"
                                "........." "\n"
                                ".X.*....X" "\n"
                               ), 2)

    def test_3x11_2_days_3_volcanos(self):
      self.assertEqual(doomfunc("*X......." "\n"
                                "........." "\n"
                                ".X.*...*X"
                               ), 2)

  # Creates a PEP8-compliant class name
  DoomsdayTesterTemplate.__name__ = snake2camel(doomfunc.__name__) + "Tester"

  # Register the class in the namespace we're in
  setattr(sys.modules[__name__],
          DoomsdayTesterTemplate.__name__,
          DoomsdayTesterTemplate)


# Creates all testers we want (local names that starts with "doomsday")
names = filter(lambda key: key.startswith("doomsday"), locals().keys())
for name in names: # The locals() dict should be kept away from "for" loops
  create_tester(locals()[name]) # This changes locals()!!!


if __name__ == "__main__":
  unittest.main()