Google Code Jam 2009 - Qualifizierung

Aliens, die Nachrichten senden, Wasser, das über eine Karte fließt und die versteckte Willkommensnachricht in einem String finden... Ja, Google Code Jam ist für die Ausgabe 2009 zurückgekehrt! Ich habe an der Qualifikationsrunde teilgenommen und konnte bis auf 1 alle Eingaben lösen....

Klingt nach Spaß? Das war es auch! Da ich damit beschäftigt war, Scala zu lernen, dachte ich, ich probiere das mal aus und schaue, wie es während des Wettbewerbs funktioniert. Ich glaube, das hat mir zumindest ein paar Zeilen Code erspart. Beim ersten Problem hat Google einige außerirdische Kommunikationen abgefangen, aber das Signal ist so schwach geworden, dass einige der Worte unklar sind. Sie brauchen nun unsere Hilfe, um einen cleveren Algorithmus zu entwickeln, der ihnen sagen kann, wie viele verschiedene Wörter das Signal darstellen kann. Zu diesem Zweck haben sie das vollständige Wörterbuch der außerirdischen Sprache erstellt. Als Beispiel haben sie uns die folgende fremde Sprache zur Verfügung gestellt, die aus 5 Wörtern mit 3 Buchstaben und 4 empfangenen Signalen besteht. 3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc Für meine Lösung entschied ich mich, das Wörterbuch mit allen Wörtern zu lesen und anschließend jedes der Signale in einen regulären Ausdruck umzuwandeln, indem ich [scala] val pattern = "(ab)(bc)(ca)".replaceAll("(", "[").replaceAll(")", "]").r [/scala] Dies führt zu folgendem Code: [scala] object AlienLanguage { def main(args: Array[String]) = { if (args.length == 0) { throw new IllegalArgumentException("Konnte keine Eingabedatei in den Argumenten finden") } val input = args(0) val outputFile = new File((input substring(0, input lastIndexOf(".")))) + ".out") val reader = Quelle ausDatei(input) getLines val ar = Leser nextIntArray val (tokens, nrWords, nrProblems) = (ar(0), ar(1), ar(2)) val results = new Array [String] ( nrProbleme ) val words = (1 bis nrWords).map(x => reader.trimmedLine).toList für (val i <- 1 bis nrProbleme) { results(i - 1) = "Fall #" + i + ": " + solveProblem(reader, words) } outputFile Ergebnisse schreiben } def solveProblem(reader : Iterator[String], words : List[String]) : String = { val pattern = reader.trimmedLine val regex = pattern.replaceAll("(", "[").replaceAll(")", "]").r matchWords(regex, words.head, words.tail).toString } def matchWords(regex : scala.util.matching.Regex, word: String, words : List[String]) : Int = { words.isEmpty Übereinstimmung { Fall true => matchWord(regex, wort) Fall false => matchWord(regex, word) + matchWords(regex, words.head, words.tail) } } def matchWord(regex : scala.util.matching.Regex, word: String) : Int = { regex.findFirstIn(wort) match { case Some(x) => 1 Fall Keine => 0 } } } [/scala] Der Code verwendet zwei Hilfsklassen, die Implicits verwenden, um Methoden zu einer Datei und einem Iterator[String] hinzuzufügen. Diese finden Sie in meinem GitHub-Repository (siehe unten). Dieser Code war in der Lage, den großen Eingabesatz (max. 5000 Wörter mit 15 Buchstaben und 500 Signale) innerhalb von 2,5 Sekunden zu lösen. Für das zweite Problem bekamen wir eine Höhenkarte, für die wir auf der Grundlage einer Reihe von Regeln Einzugsgebiete berechnen mussten:

• Von jeder Zelle fließt Wasser zu höchstens einer Nachbarzelle
• Wasser fließt immer zum niedrigsten Nachbarn, bei Gleichstand bevorzugt das Wasser Norden, Westen, Osten, Süden in dieser Reihenfolge
• Wenn kein Nachbar eine niedrigere Höhe hat, bleibt das Wasser in dieser Zelle, wir nennen dies eine Senke
• Entwässerungssysteme werden durch einen einzigen eindeutigen Kleinbuchstaben identifiziert, so dass die Zeichenkette lexographisch am kleinsten ist, wenn alle Zeilen verkettet werden. Eine Beispieleingabe mit 1 5x5 Karte 1 5 5 1 2 3 4 5 2 9 3 9 6 3 3 0 8 7 4 9 8 9 8 5 6 7 8 9 Meine Lösung besteht darin, zunächst die Karte zu erstellen und sie dann in eine "Flusskarte" umzuwandeln, in der jede Zelle auf den Index der Zelle zeigt, in die sie entwässert. Diese Flusskarte kann dann ganz einfach in eine "Einzugsgebietskarte" umgewandelt werden, indem Sie in der linken oberen Ecke beginnen und die Karte von links nach rechts und von oben nach unten durchlaufen, wobei Sie dem Entwässerungssystem einen eindeutigen Buchstaben zuweisen. Der Code lautet: [scala] object Watersheds extends CodeJam { def solveProblem(reader : Iterator[String]) : String = { val ar = reader.nextIntArray val (h, w) = (ar(0), ar(1)) val theMap = (1 bis h).map(x => reader.nextIntArray).toArray val shed = new Shed(h, w, theMap) val basins : Array[String] = shed.solve printRecursive(becken, w) } def printRecursive(basins : Array[String], length : Int) : String = { basins.size entsprechen { Fall 0 => "" Fall => "n" + basins.take(length).reduceLeft(+" "+) + printRecursive(basins.drop(length), length) } } } class Shed(val h : Int, val w : Int, val theMap : Array[Array[Int]]) { val flowMap = (for (hPos <- 0 bis h; wPos <- 0 bis w) yield determineFlowTo(hPos, wPos)).toArray val basins : Array[Int] = Array.make(h * w, -1) def determineFlowTo(hPos : Int, wPos : Int) : Int = { val north = determineAltitude(hPos - 1, wPos) val west = determineAltitude(hPos, wPos - 1) val east = determineAltitude(hPos, wPos + 1) val south = determineAltitude(hPos + 1, wPos) val me = determineAltitude(hPos, wPos) val minAltitude = List(me, north, west, east, south).sort(<_).head wenn (ich > north && north == minAltitude) { convertToIndex(hPos - 1, wPos) } else if (me > west && west == minAltitude) { convertToIndex(hPos, wPos - 1) } else if (me > east && east == minAltitude) { convertToIndex(hPos, wPos + 1) } else if (me > south && south == minAltitude) { convertToIndex(hPos + 1, wPos) } sonst { convertToIndex(hPos, wPos) } } def determineAltitude(hPos : Int, wPos : Int) : Int = { if (hPos == h || hPos < 0) { 10001 // mehr als die maximale Höhe in der großen Karte, da außerhalb der Reichweite } else if (wPos == w || wPos < 0) { 10001 // mehr als die maximale Höhe in der großen Karte, da außerhalb der Reichweite } sonst { theMap(hPos)(wPos) } } def convertToIndex(hPos : Int, wPos : Int) = { hPos w + wPos } /
• Methoden auflösen / def solve() : Array[String] = { val basinString = "abcdefghijklmnopqrstuvwxyz".split("") var currentHighestBasin = -1 (0 bis h w).foreach(i => if (basins(i) == -1) currentHighestBasin = fillFlow(i, currentHighestBasin)) basins.map(i => basinString(i + 1)).toArray } def fillFlow(index : Int, currentHighestBasin : Int) : Int = { val flowTo = flowMap(index) if (basins(flowTo) != -1) { basins(index) = basins(flowTo) currentHighestBasin } sonst { val basinValue = findBasinValue(index) if (basinValue != -1) { fillTheFlow(index, basinValue) currentHighestBasin } sonst { fillTheFlow(index, currentHighestBasin + 1) aktuellHöchstesBassin + 1 } } } def findBasinValue(index : Int) : Int = { flowMap(index) match { Fall MARKDOWN_HASH6a992d5529f459a44fee58c733255e86MARKDOWNHASH => basins(index) Fall => findBasinValue(flowMap(index)) } } def fillTheFlow(index : Int, basin : Int) { basins(index) = basin val flowTo = flowMap(index) if (flowTo != index && basins(flowTo) == -1) fillTheFlow(flowTo, basin) } } [/scala] Beachten Sie, dass die erweiterte CodeJam-Eigenschaft eine Main-Methode bereitstellt, die der Methode aus dem ersten Problem sehr ähnlich ist. Die vom Code erzeugte Ausgabe sieht für die oben angegebene Beispieleingabe wie folgt aus Case #1: a a a a a a a b b a a b b b a a b b b a a a a a a Das Programm war in der Lage, sowohl den großen als auch den kleinen Datensatz in weniger als 1 Sekunde zu lösen. Das letzte Problem war (zumindest für mich) eine harte Nuss. Obwohl die kleine Eingabe leicht zu lösen war, konnte mein Programm die große Eingabe nicht innerhalb der vorgesehenen 8 Minuten lösen. Die Problemstellung lautete wie folgt: Ausgehend von einer Textzeichenkette sollen Sie ermitteln, wie oft die Zeichenkette "welcome to code jam" als Teilsequenz dieser Zeichenkette vorkommt. Mit anderen Worten: Finden Sie eine Folge s von aufsteigenden Indizes in der Eingabezeichenkette, so dass die Verkettung von input[s[0]], input[s[1]], ..., input[s[18]] die Zeichenkette "welcome to code jam" ist. Mein Ansatz bestand aus den folgenden Schritten:
  • • zunächst alle Zeichen aus der Zeichenfolge herausfiltern, die nicht zur Nachricht "Willkommen bei Code Jam" gehören
    • einen einfachen Trick der Lauflängencodierung anwenden, um die Länge der Zeichenkette noch weiter zu verringern (während die Informationen erhalten bleiben)
    • Schleife über die Zeichenkette und Berechnung der Anzahl der Vorkommen
      [scala]

   

  • • object WelcomeToCodeJam extends CodeJam {

   

  • • def solveProblem(reader : Iterator[String]) : String = {

   

  • • val expr = "willkommen bei code jam"

   

  • • val line = reader.trimmedLine

   

  • • // filtert zunächst alle Zeichen, die nicht im Muster vorkommen

   

  • • val filteredLine = makeHisto(line.toList.filter(x => expr.contains(x)))

   

  • • val exprList = expr.toList

   

  • • (solve(filteredLine, exprList) % 10000) formatiert ("%04d")

   

  • • }

   

  • • def makeHisto(line : List[Char]) : List[(Char, Long)] = {

   

  • • if (line.isEmpty) {

   

  • • Liste[(Char, Long)]()

   

  • • } sonst {

   

  • • val h = histoLetter(line.tail, line.head)

   

  • • val newLine = line.drop(h._2.toInt)

   

  • • newLine.isEmpty entspricht {

   

  • • case true => Liste(h)

   

  • • case false => Liste(h) ++ makeHisto(newLine)

   

  • • }

   

  • • }

   

  • • }

   

  • • def histoLetter(line : List[Char], c : Char) : (Char, Long) = {

   

  • • (c, (Zeile takeWhile (_ == c)).size + 1)

   

  • • }

   

  • • def solve(line : List[(Char, Long)], expr : List[Char]) : Long = {

   

  • • var count : Long = 0L

   

  • • if (!expr.isEmpty) {

   

  • • var restLine = findNext(Zeile, expr)

   

  • • while (!restLine.isEmpty) {

   

  • • count += (restLine.head._2 * solve(restLine.tail, expr.tail))

   

  • • restLine = findNext(restLine.tail, expr)

   

  • • }

   

  • • } sonst {

   

  • • Anzahl = 1

   

  • • }

   

  • • zählen

   

  • • }

   

  • • def findNext(line : List[(Char, Long)], expr : List[Char]) = {

   

  • • line.dropWhile(_._1 != expr.head)

   

  • • }

   

  • • }

   

  • • [/scala]

   

  • • In Anbetracht der Tatsache, dass einige Leute dies in sehr kurzer Zeit geschafft haben, vermute ich, dass ich etwas übersehen habe, weshalb der große Eingabesatz (Zeilen mit 500 Zeichen) nicht verarbeitet werden konnte. Die kleine Eingabemenge wurde jedoch korrekt generiert. Ich habe mich in den letzten Tagen damit beschäftigt, das dritte Programm zu überarbeiten, um seine Geschwindigkeit zu verbessern. Die neueste Version ist die oben gezeigte. Wer kann mir sagen, was ich übersehen habe oder wie man es schneller machen kann?

   

  • • Den Code der Ausgabe 2009 und einige der Probleme der Ausgabe 2008 finden Sie auch in meinem GitHub-Repository unter:

  github.com/hierynomus

  • . Wer hat sonst noch mitgemacht, oder wer hat eine bessere Lösung in Scala?