BwInf Runde 2 Aufgabe 3

triangle.php

<?php
/**
 * Eine Farbe
 */
class Color
{
	/**
	 * Ein Wert fuer die Ausgabe, der die Farbe darstellt
	 *
	 * @var int
	 */
	private $color = 0;

	/**
	 *
	 * @param int $color Wert der Farbe
	 */
	public function __construct ($color)
	{
		$this->color = $color;
	}

	/**
	 * Gibt den Wert der Farbe zurueck
	 *
	 * @return int
	 */
	public function getColor ()
	{
		return $this->color;
	}
}

/**
 * Eine Sammlung von Farben
 */
class ColorCollection
implements Countable
{
	/**
	 * Die Farben in dieser Sammlung
	 *
	 * @var array
	 */
	private $colors = array();

	/**
	 *
	 * @param array $colors Farben
	 * @throws InvalidArgumentException wenn $colors nicht nur Color-Objekte enthaelt
	 */
	public function __construct (array $colors)
	{
		foreach ($colors as $color)
		{
			if (($color instanceof Color) === false)
			{
				throw new InvalidArgumentException(
					'$colors has to be an array of Color objects'
				);
			}
		}

		$this->colors = array_values($colors);
	}

	/**
	 * Gibt die Anzahl der Farben in dieser Sammlung zurueck
	 *
	 * @return int
	 */
	public function count ()
	{
		return count($this->colors);
	}

	/**
	 * Checkt, ob die Sammlung leer ist
	 *
	 * @return bool
	 */
	public function isEmpty ()
	{
		if ($this->count() === 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	/**
	 * Gibt das erste Element der Sammlung zurueck
	 *
	 * @return Color
	 * @throws UnderflowException wenn die Sammlung kein erstes Element hat
	 */
	public function first ()
	{
		if ($this->isEmpty())
		{
			throw new UnderflowException('Collection has no first element');
		}

		return $this->colors[0];
	}

	/**
	 * Gibt eine Array-Repraesentation der Sammlung zurueck
	 *
	 * @return array
	 */
	public function toArray ()
	{
		return $this->colors;
	}
}

/**
 * Ein Farbrepository zur Verwaltung
 */
class ColorRepository
{
	/**
	 * Die verwalteten Farben
	 *
	 * @var array
	 */
	private $colors = array();

	/**
	 * Die Farbe, die als naechste Farbe zurueckgegeben wird
	 *
	 * @var Color
	 */
	private $nextColor = null;

	public function __construct ()
	{
		$this->nextColor = new Color(1);
	}

	/**
	 * Gibt alle verwalteten Farben als Sammlung zurueck
	 *
	 * @return ColorCollection
	 */
	public function getColors ()
	{
		return new ColorCollection($this->colors);
	}

	/**
	 * Erzeugt eine neue Farbe und gibt sie zurueck
	 *
	 * @return Color
	 */
	public function getNextColor ()
	{
		$nextColor = $this->nextColor;
		$this->colors[] = $nextColor;

		$this->nextColor = new Color($nextColor->getColor() + 1);

		return $nextColor;
	}
}

/**
 * Ein Regenbogen
 */
class Rainbow
{
	/**
	 * Anzahl der Streifen
	 *
	 * @var int
	 */
	private $numberOfStripes = 0;

	/**
	 * Das Farbrepository
	 *
	 * @var ColorRepository
	 */
	private $colorRepository = null;

	/**
	 * Die Streifen
	 *
	 * @var array
	 */
	private $stripes = array();

	/**
	 * Die Streifen werden mit jeder Farbe aus dem Farbrepository initialisiert
	 *
	 * @param ColorRepository $colorRepository
	 * @param int $numberOfStripes Anzahl der Streifen
	 * @throws OutOfRangeException wenn der Regenbogen weniger als 0 Streifen haben soll
	 */
	public function __construct (ColorRepository $colorRepository, $numberOfStripes)
	{
		$numberOfStripes = (int)$numberOfStripes;

		if ($numberOfStripes < 0)
		{
			throw new OutOfRangeException('There cannot be less than 0 stripes');
		}

		$this->numberOfStripes = $numberOfStripes;
		$this->colorRepository = $colorRepository;
		$this->stripes = new SplFixedArray($this->numberOfStripes);

		$colors = $this->colorRepository->getColors();
		$colorCount = $colors->count();

		for ($i = 0; $i < $this->numberOfStripes; $i++)
		{
			$this->stripes[$i] = new SplObjectStorage();

			foreach ($colors->toArray() as $color)
			{
				$this->stripes[$i][$color] = false;
			}
		}
	}

	/**
	 * Gibt die Anzahl der Streifen zurueck
	 *
	 * @return int
	 */
	public function getNumberOfStripes ()
	{
		return $this->numberOfStripes;
	}

	/**
	 * Gibt die Anzahl der noch freien Farben in einem Streifen zurueck
	 *
	 * @param int $stripe
	 * @return ColorCollection
	 * @throws OutOfBoundsException wenn $stripe kein gueltiger Streifen ist
	 */
	public function getFreeColorsInStripe ($stripe)
	{
		if ($stripe < 0 || $stripe >= $this->numberOfStripes)
		{
			throw new OutOfBoundsException(
				'Stripe ' . $stripe . ' does not exist'
			);
		}

		$freeColors = array();
		$colors = $this->colorRepository->getColors()->toArray();

		foreach ($colors as $color)
		{
			if ($this->stripes[$stripe][$color] === false)
			{
				$freeColors[] = $color;
			}
		}

		return new ColorCollection($freeColors);
	}

	/**
	 * Setzt den Status einer Farbe in einem Streifen auf "geblockt"
	 *
	 * @param Color $color Zu blockende Farbe
	 * @param int $stripe Streifen
	 * @return void
	 * @throws OutOfBoundsException wenn $stripe kein gueltiger Streifen ist
	 */
	public function blockColorInStripe (Color $color, $stripe)
	{
		if ($stripe < 0 || $stripe >= $this->numberOfStripes)
		{
			throw new OutOfBoundsException(
				'Stripe ' . $stripe . ' does not exist'
			);
		}

		$this->stripes[$stripe][$color] = true;
	}

	/**
	 * Checkt, ob eine Farbe einen Streifen vollblocken wuerde
	 *
	 * @param Color $color
	 * @param int $stripeIndex
	 * @return bool
	 * @throws OutOfBoundsException wenn $stripe kein gueltiger Streifen ist
	 */
	public function wouldColorFullBlockStripe (Color $color, $stripeIndex)
	{
		if ($stripeIndex < 0 || $stripeIndex >= $this->numberOfStripes)
		{
			throw new OutOfBoundsException(
				'Stripe ' . $stripeIndex . ' does not exist'
			);
		}

		$stripe = $this->stripes[$stripeIndex];

		if ($stripe[$color] === true)
		{
			return false;
		}

		for ($stripe->rewind(); $stripe->valid(); $stripe->next())
		{
			$stripeColor = $stripe->current();
			$blocked = $stripe->getInfo();

			if ($color === $stripeColor)
			{
				continue;
			}

			if ($blocked === false)
			{
				return false;
			}
		}

		return true;
	}

	/**
	 * Checkt, ob eine Farbe einen Streifen blocken wuerde
	 *
	 * @param Color $color
	 * @param int $stripe
	 * @return bool
	 * @throws OutOfBoundsException wenn $stripe kein gueltiger Streifen ist
	 */
	public function wouldColorBlock (Color $color, $stripe)
	{
		if ($stripe < 0 || $stripe >= $this->numberOfStripes)
		{
			throw new OutOfBoundsException(
				'Stripe ' . $stripe . ' does not exist'
			);
		}

		if ($this->stripes[$stripe][$color] === false)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	/**
	 * Fuegt dem Regenbogen und dadurch auch dem Farbrepository eine neue Farbe
	 * hinzu und gibt sie zurueck
	 *
	 * @return Color
	 */
	public function addColor ()
	{
		$color = $this->colorRepository->getNextColor();

		foreach ($this->stripes as $stripe)
		{
			$stripe[$color] = false;
		}

		return $color;
	}
}

/**
 * Ein Farbfilter
 */
abstract class ColorFilter
{
	/**
	 * Das Dreieck fuer das dieser Filter ist
	 *
	 * @var Triangle
	 */
	private $triangle = null;

	/**
	 *
	 * @param Triangle $triangle Das Dreieck fuer das dieser Filter ist
	 */
	public function __construct (Triangle $triangle)
	{
		$this->setTriangle($triangle);
	}

	/**
	 * Setzt das Dreieck
	 *
	 * @param Triangle $triangle
	 * @return void
	 */
	public function setTriangle (Triangle $triangle)
	{
		$this->triangle = $triangle;
	}

	/**
	 * Gibt das Dreieck zurueck
	 *
	 * @return Triangle
	 */
	public function getTriangle ()
	{
		return $this->triangle;
	}

	/**
	 * Filtert aus einem SplObjectStorage die Objekte raus, die die niedrigsten
	 * assoziierten Werte haben
	 *
	 * @param SplObjectStorage $storage
	 * @return array
	 */
	protected function getKeysWithLeastValues (SplObjectStorage $storage)
	{
		$storage->rewind();
		$firstKey = $storage->current();

		$keys = array($firstKey);
		$leastValue = $storage->getInfo();

		$storage->next();

		for (; $storage->valid(); $storage->next())
		{
			$key = $storage->current();
			$value = $storage->getInfo();

			if ($value === $leastValue)
			{
				$keys[] = $key;
			}
			else if ($value < $leastValue)
			{
				$leastValue = $value;
				$keys = array($key);
			}
		}

		return $keys;
	}

	/**
	 * Filtert aus $colors die passenden Farben raus
	 *
	 * @param Rainbow $rainbow Der Regenbogen
	 * @param ColorCollection $colors Die zu filternden Farben
	 * @param int $row Reihe des Feldes fuer das die Farbe ist
	 * @param int $index Index in der Reihe des Feldes fuer das die Farbe ist
	 * @return ColorCollection
	 */
	abstract public function apply (Rainbow $rainbow, ColorCollection $colors, $row, $index);
}

/**
 * Filtert die Farben raus, die die wenigsten Fullblocks verursachen
 */
class LeastFullBlocksFilter
extends ColorFilter
{
	public function apply (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		return new ColorCollection(
			$this->getKeysWithLeastValues(
				$this->countFullBlocks($rainbow, $colors, $row, $index)
			)
		);
	}

	/**
	 * Zaehlt die Fullblocks, die eine Farbe verursachen wuerde
	 *
	 * @param Rainbow $rainbow
	 * @param ColorCollection $colors
	 * @param int $row
	 * @param int $index
	 * @return SplObjectStorage
	 */
	private function countFullBlocks (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		$fullBlocks = new SplObjectStorage();
		$triangle = $this->getTriangle();

		foreach ($colors->toArray() as $color)
		{
			$fullBlocks[$color] = 0;

			for ($i = $index; $i < $row; $i++)
			{
				if ($color !== $triangle->getField($i, $index))
				{
					continue;
				}

				$stripe = $i - $index;

				if ($rainbow->wouldColorFullBlockStripe($color, $stripe))
				{
					$fullBlocks[$color] = $fullBlocks[$color] + 1;
				}
			}
		}

		return $fullBlocks;
	}
}

/**
 * Filtert die Farben raus, die die wenigsten neuen Blocks verursachen
 */
class LeastBlocksFilter
extends ColorFilter
{
	public function apply (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		return new ColorCollection(
			$this->getKeysWithLeastValues(
				$this->countBlocks($rainbow, $colors, $row, $index)
			)
		);
	}

	/**
	 * Zaehlt die Blocks, die eine Farbe verursachen wuerde
	 *
	 * @param Rainbow $rainbow
	 * @param ColorCollection $colors
	 * @param int $row
	 * @param int $index
	 * @return SplObjectStorage
	 */
	private function countBlocks (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		$blocks = new SplObjectStorage();
		$triangle = $this->getTriangle();

		foreach ($colors->toArray() as $color)
		{
			$blocks[$color] = 0;

			for ($i = $index; $i < $row; $i++)
			{
				if ($color !== $triangle->getField($i, $index))
				{
					continue;
				}

				$stripe = $i - $index;

				if ($rainbow->wouldColorBlock($color, $stripe))
				{
					$blocks[$color] = $blocks[$color] + 1;
				}
			}
		}

		return $blocks;
	}
}

/**
 * Filtert die Farben raus, deren Blocks die kuerzeste Distanz zu dem zu
 * fuellenden Feld haben
 */
class LeastBlockDistancesFilter
extends ColorFilter
{
	public function apply (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		return new ColorCollection(
			$this->getKeysWithLeastValues(
				$this->countBlockDistances($rainbow, $colors, $row, $index)
			)
		);
	}

	/**
	 * Gibt die Summen aller Blockdistanzen der Farben zurueck
	 *
	 * @param Rainbow $rainbow
	 * @param ColorCollection $colors
	 * @param int $row
	 * @param int $index
	 * @return SplObjectStorage
	 */
	private function countBlockDistances (Rainbow $rainbow, ColorCollection $colors, $row, $index)
	{
		$distances = new SplObjectStorage();
		$triangle = $this->getTriangle();

		foreach ($colors->toArray() as $color)
		{
			$distances[$color] = 0;

			for ($i = $index; $i < $row; $i++)
			{
				if ($color !== $triangle->getField($i, $index))
				{
					continue;
				}

				$stripe = $i - $index;

				if ($rainbow->wouldColorBlock($color, $stripe) === false)
				{
					continue;
				}

				$distance = $row - $i;
				$distances[$color] = $distances[$color] + $distance;
			}
		}

		return $distances;
	}
}

/**
 * Das Dreieck
 */
class Triangle
{
	/**
	 * Anzahl der Ebenen
	 *
	 * @var int
	 */
	private $numberOfRows = 0;

	/**
	 * 2-dimensionales Array mit der "Form" des Dreiecks
	 *
	 * @var array
	 */
	private $triangle;

	/**
	 *
	 * @param int $numberOfRows Anzahl der Reihen
	 * @throws Exception wenn $numberOfRows kleiner als 0 ist
	 */
	public function __construct ($numberOfRows)
	{
		$numberOfRows = (int)$numberOfRows;

		if ($numberOfRows < 0)
		{
			throw new Exception();
		}

		$this->numberOfRows = $numberOfRows;
		$this->triangle = $this->createTriangle($numberOfRows);
	}

	/**
	 * Fuellt das Dreieck mit Farben
	 *
	 * @return void
	 */
	public function fill ()
	{
		$colors = new ColorRepository();

		for ($i = 0; $i < $this->numberOfRows; $i++)
		{
			$rainbow = new Rainbow($colors, $i + 1);

			for ($j = 0; $j <= $i; $j++)
			{
				$color = $this->getColor($i, $j, $rainbow);
				$this->triangle[$i][$j] = $color;

				for ($k = $j; $k < $i; $k++)
				{
					if ($this->triangle[$k][$j] === $color)
					{
						$stripe = $k - $j;
						$rainbow->blockColorInStripe($color, $stripe);
					}
				}
			}
		}

		echo 'Colors: ' . $colors->getColors()->count() . "\n\n";
	}

	/**
	 * Berechnet die passendeste Farbe fuer das Feld mit den Koordinaten ($row|$index)
	 *
	 * @param int $row
	 * @param int $index
	 * @param Rainbow $rainbow
	 * @return Color
	 * @throws OutOfBoundsException wenn die Koordinaten nicht in dem Dreieck liegen
	 */
	private function getColor ($row, $index, Rainbow $rainbow)
	{
		$row = (int)$row;
		$index = (int)$index;

		if ($row < 0 || $row >= $this->numberOfRows
			|| $index < 0 || $index >= $this->numberOfRows)
		{
			throw new OutOfBoundsException('Coordinates out of bounds');
		}

		$stripe = $row - $index;
		$potentialColors = $rainbow->getFreeColorsInStripe($stripe);

		if ($potentialColors->isEmpty())
		{
			return $rainbow->addColor();
		}

		if ($potentialColors->count() === 1)
		{
			return $potentialColors->first();
		}

		$filters = array(
			new LeastFullBlocksFilter($this),
			new LeastBlocksFilter($this),
			new LeastBlockDistancesFilter($this)
		);

		foreach ($filters as $filter)
		{
			$potentialColors = $filter->apply(
				$rainbow,
				$potentialColors,
				$row,
				$index
			);

			if ($potentialColors->count() === 1)
			{
				return $potentialColors->first();
			}
		}

		return $potentialColors->first();
	}

	/**
	 * Gibt die Farbe des Feldes an der Stelle ($row|$index) zurueck
	 *
	 * @param int $row
	 * @param int $index
	 * @return Color
	 * @throws OutOfBoundsException wenn die Koordinaten nicht in dem Dreieck liegen
	 */
	public function getField ($row, $index)
	{
		if ($row < 0 || $row >= $this->numberOfRows
			|| $index < 0 || $index >= $this->numberOfRows)
		{
			throw new OutOfBoundsException('Coordinates out of bounds');
		}

		if (is_object($this->triangle[$row][$index]) === false)
		{
			throw new Exception(
				'There is no color set in the position (' . $row . '|' . $index . ')'
			);
		}

		return $this->triangle[$row][$index];
	}

	/**
	 * Erzeugt ein 2-dimensionales Array mit der passenden Anzahl an Feldern
	 *
	 * @param int $numberOfRows Anzahl der Reihen
	 * @return array
	 */
	private function createTriangle ($numberOfRows)
	{
		$triangle = array();

		for ($i = 0; $i < $numberOfRows; $i++)
		{
			$triangle[] = array_fill(0, $i + 1, array());
		}

		return $triangle;
	}

	/**
	 * Gibt das Dreieck auf der Standardausgabe aus
	 *
	 * @return void
	 */
	public function dump ()
	{
		foreach ($this->triangle as $row)
		{
			foreach ($row as $entry)
			{
				printf('%01u ', $entry->getColor());
			}

			echo "\n";
		}
	}
}

try
{
	if (!isset($_SERVER['argv'][1]))
	{
		throw new Exception();
	}

	$triangle = new Triangle((int)$_SERVER['argv'][1]);
	$triangle->fill();
	$triangle->dump();
}
catch (Exception $e)
{
	?>
Das Programm erwartet als erstes Argument die Anzahl der Ebenen des Dreiecks.
<?php
}