Feeds:
Beiträge
Kommentare

Posts Tagged ‘Billboards’

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

Read Full Post »

%d Bloggern gefällt das: