kva

// Scala Implementierung in Anlehnung an die Haskell Version von
// https://github.com/almost/regex-crossword-solver/blob/master/recross.hs

import scala.util.matching.Regex

object HexRegexCrossword {

  // Aufgabe 2
  // 2.1
  type Coords = (Int, Int)
  type Possibilities = List[Char]
  type Hex = List[(Coords, Possibilities)]
  type GameState = (Int, Hex)

  // 2.2
  def validCoords(x: Int, y: Int, size: Int): Boolean = {
    // Eine Koordinate ist gültig, wenn sie im Intervall [-size, size] liegt.
    def ok(i: Int): Boolean = i.abs <= size

    // In dem gegebenen achsenbasierten Koordinatensystem gilt die Bedingung, dass immer x + y + z = 0 gelten muss.
    // Dadurch kann aus x und y die Koordinate z berechnet werden.
    val z = -(x + y)

    // Alle Koordinaten müssen gültig sein.
    ok(x) && ok(y) && ok(z)
  }

  // 2.3
  def allPossibilites(): Possibilities =
    '!' :: '$' :: '?' :: '\\' :: ('A' to 'Z').toList ::: ('0' to '9').toList

  // 2.4
  def startGameState(size: Int): GameState = {
    def startHex(): Hex =
    // Alle Koordinaten-Kombinationen durchprobieren und für die gültigen Koordinaten ein Hex-Feld anlegen.
      (for {
        x <- -size to size
        y <- -size to size
        if validCoords(x, y, size)
      } yield ((x, y), allPossibilites())).toList

    // Rückgabewert muss ein GameState-Tuple sein.
    (size, startHex())
  }

  // Aufgabe 3
  // 3.1
  // Eine Variation der in der Aufgabenstellung geforderten simplePrinter-Funktion.
  def simplePrinter(x: Int, y: Int, z: Int, p: Possibilities): String = p.length match {
    case 1 => p.head.toString + " " // das letzte verbleibende Element ausgeben
    case l if l == allPossibilites().length => "* " // noch keine Einschränkung vorgenommen
    case l if l < allPossibilites().length => "+ " // Möglichkeiten konnten schon eingeschränkt werden
    case _ => "- " // falls keine Möglichkeiten mehr vorhanden
  }

  // 3.2
  def printGameState(gs: GameState, printer: ((Int, Int, Int, Possibilities) => String)): String = {
    // Hilfsfunktion, die die z-Koordinate berechnet, die verbleibenden Möglichkeiten abruft und die printer-Funktion aufruft.
    def printCell(x: Int, y: Int): String = {
      val z = -(y + x)
      getPossibilities(x, y, gs) match {
        case None => "" // Wenn das Ergebnis None ist, wurde ein ungültiges Hex-Feld angefragt. Wir ignorieren dies mit einem leeren String.
        case Some(p) => printer(x, y, z, p) // Bei einem gültigen Feld übernimmt die printer-Funktion die Bestimmung des Ergebnis-Strings.
      }
    }

    // Hilfsfunktion, die eine Zeile des Hex-Feldes erzeugt:
    // - List.fill(n)(c) erzeugt eine Liste der Länge n mit Elementen c. Da die "mittlerste" Zeile die längste ist und die Koordinaten 0 hat,
    //   können wir für jede Zeile darüber oder darunter den absoluten Wert der Zeilen-Koordinate nehmen um die Zeilen entsprechen einzurücken.
    // - Nach den Einrückungsleerzeichen verwenden wir flatMap um für alle möglichen x-Werte der Zeile, den Inhalt über die Hilfsfunktion ausgeben zu lassen.
    //   flatMap sorgt hier dafür, dass das Ergebnis schon ein einzelner String ist, den wir über toList zu einer List[Char] wandeln und mit der
    //   Einrückungsliste verbinden können.
    // - Zum Schluss wird die List[Char] durch mkString(s) zu einem String zusammengesetzt. Dabei wird zwischen jedem Listenelement der Seperator s
    //   (hier ein Leerzeichen) eingefügt.
    def printRow(y: Int): String = (List.fill(y.abs)(' ') ::: (-gs._1 to gs._1).flatMap(printCell(_, y)).toList).mkString(" ")

    // Für jede Zeile wird die Zeilen-Hilfsfunktion aufgerufen und die Ergebnis-Liste durch Zeilenumbrüche zu einem einzigen String zusammengebaut
    (-gs._1 to gs._1).map(printRow).mkString("\n")
  }

  // Rekursive Funktion, die alle Hex-Felder nach den gegebenen Koordinaten durchsucht, und bei Erfolg die mit dem Hex-Feld verbundenen Möglichkeiten zurückgibt
  // Wenn das gesuchte Feld nicht in dem GameState vorhanden ist, wird None zurückgegeben
  def getPossibilities(x: Int, y: Int, gs: GameState): Option[Possibilities] = gs._2 match {
    case ((a, b), p) :: gss if a == x && b == y => Some(p)
    case (_, _) :: gss => getPossibilities(x, y, (gs._1, gss))
    case _ => None
  }

  // Aufgabe 4
  // 4.1
  def generator[A](el: List[Possibilities]): List[String] = {
    // Hilfsfunktion zum zusammensetzen aller möglichen Strings
    // In jedem Schritt der Rekursion wird jedes Element aus der ersten Liste (dem letztendlichen Ergebnis)
    // mit jedem Zeichen des Kopfes der verbleibenden Möglichkeiten kombiniert.
    def h(ergebnis: List[String], rest: List[Possibilities]): List[String] = rest match {
      case x :: xs => h(for {str <- ergebnis; chr <- x} yield str + chr.toString, xs)
      case _ => ergebnis
    }

    // Initial wir die Funktion mit den Möglichkeiten für die erste Position (umgewandelt in Strings) und den folgenden Positionen aufgerufen
    h(el.head.map(_.toString), el.tail)
  }

  // 4.2
  // Hier muss nur das Listenfunktional filter mit der gegebenen Funktion matches angewendet werden
  def reducePossibilities(r: Regex, l: List[String]): List[String] = l.filter(matches(r, _))

  // Testet ob ein regulärer Ausdruck einen String vollständig erfasst
  def matches(r: Regex, s: String): Boolean = r.findAllMatchIn(s).exists(_.toString == s)

  // 4.3
  // Aus der Darstellung für Achsen- bzw. Würfelkoordinaten https://www.redblobgames.com/grids/hexagons/#coordinates-cube
  // kann die Reihenfolge des Durchlaufens der Koordinaten ermittelt werden.
  // Zum Zusammensetzten kann jeweils eine geschachtelte Listenkomprehension verwendet werden.
  def regexCoordinates(gs: GameState): List[List[Coords]] = {
    val xAxis = for {x <- -gs._1 to gs._1} yield (for {y <- (-gs._1 to gs._1).reverse if validCoords(x, y, gs._1)} yield (x, y)).toList
    val yAxis = for {z <- -gs._1 to gs._1} yield (for {x <- (-gs._1 to gs._1).reverse; y = -(x + z) if validCoords(x, y, gs._1)} yield (x, y)).toList
    val zAxis = for {y <- -gs._1 to gs._1} yield (for {x <- -gs._1 to gs._1; z = -(y + x) if validCoords(x, y, gs._1)} yield (x, y)).toList
    xAxis.toList ::: yAxis.toList ::: zAxis.toList
  }

  // 4.4
  def runIteration(rl: List[Regex], gs: GameState): GameState = {
    def update(x: (List[Coords], Regex), h: Hex): Hex = {
      // Erst werden alle möglichen Kombinationen der Zellen zu dem regulären Ausdruck erstellt
      val set: List[String] = generator(x._1.map((c: Coords) => getPossibilities(c._1, c._2, (gs._1, h)).getOrElse(List())))
      // Das Set aller Möglichkeiten wird dann durch matchen mit dem regulären Ausdruck reduziert
      val rSet: List[String] = reducePossibilities(x._2, set)

      // Rückwandeln der Strings in List[Char] für die Möglichkeiten der einzelnen Zellen.
      // Zunächst wird eine leere Liste, die für jede Position eine leere Liste an möglichen Chars enthält, angelegt.
      val t: List[List[Char]] = List.fill(x._1.length)(List())
      // Ausgehend von dieser Liste ohne Einträge für die jeweiligen Möglichkeiten, wird mit fold durch die reduzierte Ergebnisliste gegangen.
      val u = rSet.foldRight(t)((m: String, l: List[List[Char]]) =>
        // Dabei wird der aktuelle String, der für jedes beteiligte Hex-Feld ein mögliches Zeichen enthält, durch zip mit der Liste der Möglichkeiten nach Hex-Feldern verknüpft.
        // Das Resultat des zip-Aufrufs ist eine Liste von Tupeln (Char, Possibilites)
        m.zip(l).map(ct =>
          // Damit es keine Duplikate für die einzelnen Positionen gibt, wird beim Zusammenfassen der Tupeleinträge überprüft, ob der Char schon in der Liste der Möglichkeiten existiert.
          if (ct._2.contains(ct._1)) ct._2 else ct._1 :: ct._2).toList)

      // Zum Schluss muss das alte Hex ohne die Hex-Felder, die aktualisiert wurden, kopiert werden.
      // Die aktualisierten Felder werden dann angehängt um ein vollständiges aktualisiertes Hex zu bekommen.
      h.filter(_ match { case (c, _) => !x._1.contains(c); case _ => false }) ::: x._1.zip(u)
    }

    // Die zunächst werden die Koordinatenlisten mit den regulären Ausdrücken zu einer Liste von Tupeln (Koordinatenliste, regulärer Ausdruck) zusammen gezipped.
    // Das aktuelle Hex wird dann kontinuierlich durch den fold mit der update-Funktion und allen regulären Ausdrücken aktualisiert.
    // Damit das Ergebnis wieder ein GameState ist, muss das Ergebnis zu einem entsprechenden Tupel zusammengesetzt werden.
    (gs._1, regexCoordinates(gs).zip(rl).foldRight(gs._2)(update))
  }

  def main(args: Array[String]): Unit = {
    val g1RegX: List[Regex] = List(
      """[^XRAY]?[CROWN]*$""".r,
      """^[D-F\?][^CAMPED]+""".r,
      """[KIP?\!]*(BU|L|B){1,2}""".r
    )
    val g1RegY: List[Regex] = List(
      """[78NGUA\!E]{2}""".r,
      """(F|^L|Y)?[POWER!]*""".r,
      """[^ZENI$](TA|NG|LE|R)""".r
    )
    val g1RegZ: List[Regex] = List(
      """[FIND]?\$?[LAKME]""".r,
      """[^PESCE]?[POS3]*.""".r,
      """[^OPRES!]+[^STICKO]*""".r
    )
    val g1r = g1RegX ::: g1RegY ::: g1RegZ

    val g1s = startGameState(1)
    println(printGameState(g1s, simplePrinter))
    println(printGameState(runIteration(g1r, g1s), simplePrinter))
  }

}