Feeds:
Beiträge
Kommentare

Posts Tagged ‘php’

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 »

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 »

An diesem Wochenende lief die Qualifikationsrunde vom 2. Facebook Hacker Cup. Das heißt genaugenommen läuft sie noch ein paar Stunden. Für die Teilnehmer gab es, wie bereits im letzten Jahr drei Probleme zu bewältigen. Zwei davon waren sehr einfach und innerhalb weniger Minuten zu lösen. Problem Nummer 2 jedoch gab den meisten Leuten Rätsel auf.

Glücklicherweise jedoch reicht den Teilnehmern die korrekte Lösung eines der drei Probleme um sich für die Folgerunde zu qualifizieren.

Ich habe zwei der drei Probleme gelöst, beides in php und werde diese Morgen hier veröffentlichen.

Ihr habt noch bis 1 Uhr heute Nacht Zeit um Euch zu qualifizieren, also werft Eure Entwicklungsumgebung an und legt los!

Zu den Lösungen:

 

Read Full Post »

So heute wird es technisch. Das Umschreiben vor URLs mit mod_rewrite ist inzwischen Standard. Im konkreten Fall möchte ich über meine index.php die Unterseite „translate“ aufrufen und als zu übersetzendes Wort das Wort „kuchen“ übermitteln. Das bedeutet zum Beispiel, setzt man einen Link auf http://www.example.com/translate/kuchen.html  so erzeugt mod_rewrite daraus http://www.example.com/index.php?page=translate&query=kuchen. Das ist etwas das meine index.php verstehen und bearbeiten kann. Der .htaccess-File sieht wie folgt aus:

RewriteEngine On</pre>
RewriteRule ^([^/]*)/([^/]*)\.html$ index.php?page=$1&query=$2 [L]

Das bedeutet: auch wenn die Seite dynamisch generiert wird habe ich zu dem Suchwort „kuchen“ eine feste URL. Ich kann diese also nehmen und jemandem schicken und er bekommt das selbe Ergebnis. Die URL ist schön Suchmaschienenfreundlich, was will man mehr?

Das Problem

Das Problem entsteht woanders nämlich im Formular.

<form action="www.example.com/index.php" method="get">
		<input type="hidden" name="page" value="translate" />
		<input type="text" name="query" />
		<input type="submit" value="übersetzen" />
</form>

Der Browser erzeugt daraus nämlich wieder den Aufruf http://www.example.com/index.php?page=translate&query=kuchen und das steht dann in der Adressleiste. Niemand wird also die schöne rewrite rule je zu Gesicht bekommen.

Die Lösung

Die Lösung lautet: Weiterleitung. Da gibt es erst einmal grundsätzlich zwei Möglichkeiten. Die Erste besteht darin diese Weiterleitung auch mit mod_rewrite zu regeln. Ein Beispiel hierfür bietet talkincode.com. Eine weitere Möglichkeit bietet php selbst.

Der Code

Zunächst wird der action-Parameter des Formulars geändert. Dieses soll nun auf die neue Datei url.php verweisen. Sieht dann also so aus:

<form action="www.example.com/index.php" method="get">

Die Datei url.php enthält folgenden Code:

<?php
// renames URLs from get parameters to the rewrite rules from .htaccess
$q = '';
// creates the static path
if (isset( $_GET['page'] ) ) $q .= $_GET['page'];
if (isset( $_GET['query'] )  AND $_GET['page'] == 'translate' ) $q .= '/'.$_GET['query'];

if ($q != '') {
   header( 'Location: www.example.com/' . $q . '.html' );
}
?>

Zunächst wird hier der Pfad erzeugt. Anschliessend wird die „page“-Variable angehängt, dann ein Schrägstrich und dann die „query“ Variable. Sind beide Variablen übergeben worden und der Pfad ist nicht leer wird dem Browser der Location Header gesendet. Dieser weiss nun, dass er das gesuchte Dokument unter der neuen URL finden kann.

Das Ergebnis

Benutzt der Nutzer nun das Formular wird vom Browser url.php aufgerufen und die Formulardaten page und query als GET Parameter angehängt. Diese Datei erzeugt nun die Weiterleitung zu der umgeschriebenen URL. Und genau diese steht dann auch in der Adressleiste des Browsers.

Problem gelöst. Sollten Fragen oder Anmerkungen sein freue ich mich sehr über Feedback.

Read Full Post »

%d Bloggern gefällt das: