Feeds:
Beiträge
Kommentare

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

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

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:

 

Als Programmierer beim Webmoritz war es meine ehrenvolle Aufgabe einen Adventskalender zu erstellen.

Anforderungen

Webmoritz Adventskalender

Webmoritz Adventskalender

Dabei war wichtig, dass der Kalender Wartungsfrei ist. Ich will da während des Betriebs nichts mehr von Hand machen. Für den Inhalt sollten die einzelnen Redakteure ihre eigenen Artikel schreiben und diese sollten dann ganz automatisch Tag für Tag im Kalender erscheinen.

Lösung

Zunächst dachte ich daran, die Türen in einer Lightbox zu öffnen. Weil aber der Inhalt entsprechend lang war habe ich das schnell verworfen.

Der Kalender besteht jetzt aus einem speziellen Template, nebst zugehöriger Seite. Die Türchen werden über eine eigens dafür eingerichtete Artikelkategorie geladen.

Code

<?php
/*
Template Name: Weihnachtskalender
*/
?>
<?php
get_header(); ?>
<!-- Ausgabe des Titels -->
<h2>Adventskalender</h2>

<!-- Hintergrundbild -->
<div style="background: url(*** Bildpfad *** ); width: *** Bildbreite *** px; height: *** Bildhöhe ***px; position: relative;">
<?php
/* Erzeigt einen Weihnachtskalender. Die URL des Bildes ist statisch.
 * Die Artikel werden automatisch aus einer entsprechenden Kategorie geholt
 * und müssen in dieser jewweils um 0 Uhr des Tages automatisch
 * veröffentlicht werden.
 *
 */
$monat = date("m");
$tag = date("d");
if ($monat == 12) : // nur im Dezember
// Artikel holen, älteste zuerst!

$category= ***; // entsprechende Kategorienummer
$weihnachtskalender = null;
$weihnachtskalender = new WP_Query();
$weihnachtskalender->query('&showposts='.$tag.'&cat='.$category.'&orderby=date&order=ASC');
 /* m zeilen, n spalten
 * Erzeugt 4 Spalten und 6 Reihen
 * Also 24 "Türchen"
 * Das Bild sollte 600*900 sein
 * die Türchen sind dann 100*100 und haben 40 Abstand in alle Richtungen
 */
for ($m = 0; $m < 6; $m++) {
 for ($n = 0; $n < 4; $n++ ) {
 $nummer = (4 * $m) + $n + 1;
 ?>
 <div style="width:100px; height: 100px; position: absolute; left:<?php echo ($n+1)*40+$n*100;?>px; top: <?php echo ($m+1)*40+$m*100;?>px; font-size: 32 !important; color: white; padding: auto; ">
 <?php if ($nummer <= $tag AND $weihnachtskalender->have_posts() ) : $weihnachtskalender->the_post(); ?>
 <a title="<?php the_title(); ?>" href="<?php the_permalink(); ?>"
 style="display:block; width:100px; height:100px; color: white;"><?php echo $nummer;?></a> <?php
 else : echo $nummer;
 endif; ?>
 </div>
 <?php
 }
}

endif;
 $weihnachtskalender = null;
 ?>

</div>
<!-- Aufruf der Sidebar -->
<?php include(TEMPLATEPATH . '/sidebar.php'); ?>

<?php get_footer(); ?>

Verbesserungen

Es wäre vielleicht schön gewesen, wenn die Türchen nicht in aufsteigender Reihenfolge angezeigt werden würden. Also wenn man diese verteilt wie bei einem richtigen Adventskalender. Das gibt es dann im nächsten Jahr. Weitere Vorschläge nehme ich gern entgegen.

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.

Im Moment erstelle ich für einen bekannten Fotografen eine Webseite. Das Ganze soll recht simpel und dunkel gehalten sein. Beim rumsurfen habe ich entdeckt, dass die meisten Webseiten von Fotografen, vor allem auf hohem Level, einfach irgendwelche Flash-Monstrositäten sind. Das ganze lädt ewig, ist nicht skalierbar und ist auf kleinen und lahmen Rechnern wie zum Beispiel Netbooks ungeniessbar.

Also frisch ans Werk, ein bisschen PHP für dynamische Seitenerstellung, jede Menge CSS3 und eine Prise Javascript. Andys Webseite ist das vorläufige Resultat. Da fehlt gefühlt noch irgendwie Alles. Der Stil braucht noch ein, zwei verspielte Elemente. Dazu eine Box für Text, eine hübsche Überschrift, vielleicht ein Logo …

Auf der technischen Seite müssen die URLs noch Suchmaschienenfreundlich geparst werden. Leider leider will Apache mod_rewrite irgendwie nicht so wie ich will. UPDATE Jetzt geht es! Der GET Parameter wird elegant versteckt übergeben. Google wird sich in Zukunft freuen.

Momentan gibt es zwei verschiedene Bildergalerien. Die Erste auf der Hauptseite ist nur als Slideshow gedacht und wird sicher noch stark geändert. Insbesondere wird es wohl noch größer werden. Die Zweite im Portfolio ist eigentlich ganz nett. Vielleicht ersetze ich die noch durch MiniGal Nano. Da muss man aber bischen umändern damit das ganze gut rein passt. Die Verzeichnisse passen mir mal so gar nicht in den Kram und trotz GDlib funktioniert die resize Funktion nicht. Naja muss ja noch was zu tun bleiben.

Sollte jemand Ideen haben was Verbesserungen angeht immer her damit.

Wenn man derzeit versucht sich durch Greifswald zu bewegen wird man früher oder später vor einer der Unterführungen stehen und sich fragen wo man sein Kanu gelassen hat. Bei meinem Versuch die andere Seite des Bahndammes zu erreichen sind folgende Bilder entstanden.

Viel Spaß

Diese Diashow benötigt JavaScript.

%d Bloggern gefällt das: