Feeds:
Beiträge
Kommentare

Posts Tagged ‘Alphabet Soup’

Auch das dritte Problem aus dem diesjährigen Hacker Cup habe ich mit php gelöst. Ursprünglich hatte ich eine Lösung in Java aber nachdem der Debugger mich 20 Minuten mit merkwürdigen Fehlermeldungen bombardiert hat bin ich dann zu php übergelaufen.

Problem

Gegeben ist eine Menge an Wörtern. Es gilt herauszufinden wie oft man das Wort „HACKERCUP“ mit den Buchstaben aus den Wörtern schreiben kann

Lösungsidee

Mein Algorithmus nimmt einfach jeden Buchstaben aus „HACKERCUP“ und schaut nach wie oft dieser in der gegebenen Wortmenge vorhanden ist. Da das C zwei mal gebraucht wird muss die Anzahl hier noch halbiert werden. Anschließend wird geprüft welcher Buchstabe am seltensten ist. Die Anzahl dieses Buchstabens ist dann die Lösung.

Code

Auch hier ist der Code identisch mit meinem Wettbewerbsbeitrag. Jetzt wo ich den noch einmal anschaue gruselt es mich richtig was ich da getan habe. Aber der Algorithmus läuft!


<?php

$fstream = fopen("in.txt", 'r');
$fwrite = fopen("out.txt", "w");

// throw away first line

fgets($fstream);
$strLine = null;
$i=1;
while (($strLine = fgets($fstream)) != null) {
  fputs($fwrite, "Case #$i: ".solution($strLine)."\n");
  $i++;
}

//Close the input stream
fclose($fstream);
fclose($fwrite);

function solution($input) {
  $target = Array( 'C', 'A', 'H', 'K', 'E', 'R', 'U', 'P');
  $counts = Array(0,0,0,0,0,0,0,0);
  for ($i=0; $i<count($target);$i++) {
    $counts[$i]=substr_count($input, $target[$i]);
  }
  // c ist 2 mal drinn
  $counts[0]=floor($counts[0]/2);
  // maximum holen
  $max = $counts[0];
  foreach ($counts as $a){
    if ($a<$max) {
      $max=$a;
    }
  }
  return $max;
}
?>
Advertisements

Read Full Post »

%d Bloggern gefällt das: