Feeds:
Beiträge
Kommentare

Archive for the ‘PHP’ Category

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;
}
?>

Read Full Post »

Wie angekündigt gibt es hier jetzt meine Lösung zum ersten Problem aus dem 2012er Hacker Cup.

Problem

Gegeben ist ein Rechteckiges Plakat mit gegebener Breite und Höhe sowie ein Schriftzug. Dieser Schriftzug soll auf das Plakat gedruckt werden. Welche Schriftgröße darf der Schriftzug maximal haben?

Dazu gab es noch die Vereinfachung, dass alle Zeichen genau quadratisch sind.

Lösungsidee

Mein Algorithmus geht alle Schriftgrößen von 0 an solange nach oben durch bis der Schriftzug nicht mehr passt. In jede Zeile werden solange Wörter geschrieben bis ein Wort zu groß für die Zeile ist. Dieses Wort wird dann einfach in die nächste Zeile geschrieben. Sind keine Zeilen mehr übrig, terminiert der Algorithmus und gibt die letzte noch passende Größe aus.

Code

Der Code ist so wie ich ihn eingereicht habe, also mit heißer Nadel gestrickt. Dementsprechend wenig elegant sieht das aus, aber das ist eben der Geist dieses Wettbewerbs.

<?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) {
  $case = explode(' ', $strLine, 3);
  $width = $case[0];
  $height = $case[1];
  $text = explode(' ', $case[2]);
  $case=null;
  //var_dump($text);
  fputs($fwrite, "Case #$i: ".solution($width, $height, $text)."\n");
  $i++;
}
//Close the input stream
fclose($fstream);
fclose($fwrite);
function solution($width, $height, $text) {
  $max=0;
  $fits=true;
  while ($fits) {
    //soviele Zeilen wie reinpassen
    $k=0;
    for ($i = 1; $i <= $height/($max+1); $i++) {
      $linelength = 0;
      $linefits=true;
      while ($linefits) {
        if($k>=count($text)) {
          break;
        }
        $linelength+=strlen($text[$k])+1;
        if (($linelength-1)*($max+1) > $width) {
          $linefits=false;
        } else {
          $k++;
        }
      }
    }
    if ($k < count($text)) {
      $fits = false;
    }
    if ($fits == true) {
      $max++;
    }
  }
  return $max;
}
?>

Read Full Post »

%d Bloggern gefällt das: