Wähle drei Töpfe

Jeder Topf hat vier Eigenschaften:

  • verschiedene Deckel: kein Deckel, flacher Griff, hoher Griff
  • verschiedene Farben: hell, gestreift, dunkel
  • verschiedene Zeichen: Ring, Kreuz, Doppelkreuz
  • verschiedene Zeichenanzahl: 1, 2 oder 3

Es sollen genau drei Töpfe so ausgewählt werden, dass für jede der vier Eigenschaften alle Töpfe entweder den gleichen Wert oder alle unterschiedliche Werte haben.

XML-Notation

Die Eigenschaften sind Attribute (zur Vereinfachung nenne ich diese a, b, c und d) und jedes Attribut muss einen von drei möglichen Werten annehmen (1, 2, 3).

<pots>
  <pot a="1" b="1" c="3" d="2" />
  <pot a="1" b="1" c="3" d="3" />
  <pot a="3" b="2" c="1" d="2" />
  <pot a="1" b="3" c="2" d="1" />
  <pot a="1" b="1" c="1" d="1" />
  <pot a="2" b="2" c="1" d="2" />
  <pot a="3" b="2" c="2" d="1" />
  <pot a="3" b="2" c="1" d="1" />
  <pot a="3" b="1" c="3" d="2" />
  <pot a="3" b="1" c="1" d="1" />
  <pot a="2" b="1" c="3" d="2" />
  <pot a="3" b="2" c="3" d="3" />
</pots>

Lässt sich die Lösung mit einem XPath-Ausdruck angeben? Nein, wohl nicht, und ich bin auch nur auf eine brute force-Lösung gekommen, die mir wenig elegant erscheint:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0" 
  xmlns:xs="http://www.w3.org/2001/XMLSchema" 
  xmlns:my="my" 
  exclude-result-prefixes="#all">
  <xsl:output indent="yes" />

  <xsl:template match="pots">
    <xsl:variable name="a" as="node()*" select="my:triples(*, 'a')" />
    <xsl:variable name="b" as="node()*" select="my:triples(*, 'b')" />
    <xsl:variable name="c" as="node()*" select="my:triples(*, 'c')" />
    <xsl:variable name="d" as="node()*" select="my:triples(*, 'd')" />
    <result>
      <!-- only triples which are present for all attributes are returned -->
      <xsl:for-each select="$a[. = $b][. = $c][. = $d]">
        <xsl:sequence select="." />
      </xsl:for-each>
    </result>
  </xsl:template>

  <!-- this function returns all valid triples for a single attribute -->
  <xsl:function name="my:triples" as="node()*">
    <xsl:param name="nodes" as="node()+" />
    <xsl:param name="attr" as="xs:string" />

    <!-- look for common values -->
    <xsl:for-each select="$nodes">
      <xsl:variable name="t1" select="." />
      <xsl:for-each select="$t1/following-sibling::*[@*[name() eq $attr] eq $t1/@*[name() eq $attr]]">
        <xsl:variable name="t2" select="." />
        <xsl:for-each select="$t2/following-sibling::*[@*[name() eq $attr] eq $t1/@*[name() eq $attr]]">
          <triple>
            <xsl:value-of select="(my:pos($nodes, $t1), my:pos($nodes, $t2), my:pos($nodes, .))" />
          </triple>
        </xsl:for-each>
      </xsl:for-each>
    </xsl:for-each>

    <!-- look for distinct values -->
    <xsl:for-each select="$nodes">
      <xsl:variable name="t1" select="." />
      <xsl:for-each select="$t1/following-sibling::*[@*[name() eq $attr] ne $t1/@*[name() eq $attr]]">
        <xsl:variable name="t2" select="." />
        <xsl:for-each select="
              $t2/following-sibling::*[@*[name() eq $attr] ne $t1/@*[name() eq $attr] 
              and 
              @*[name() eq $attr] ne $t2/@*[name() eq $attr]]">
          <triple>
            <xsl:value-of select="(my:pos($nodes, $t1), my:pos($nodes, $t2), my:pos($nodes, .))" />
          </triple>
        </xsl:for-each>
      </xsl:for-each>
    </xsl:for-each>
  </xsl:function>

  <xsl:function name="my:pos" as="xs:string">
    <xsl:param name="nodes" as="node()+" />
    <xsl:param name="node" as="node()" />
    <xsl:value-of select="count($nodes[$node >> .]) + 1" />
  </xsl:function>

</xsl:transform>

Wer kann eine elegantere Lösung anbieten?

Textänderungen anzeigen

Ich habe das Tool XTC = XML Tree Compare von Martin Achtziger http://www.xmldifftool.com/ schon auf der tekom-Tagung vorgestellt und in meinem Blog erwähnt. Im praktischen Einsatz in Projekten geht es mittlerweile nicht um so banale Dinge wie die Performance (die mit der aktuellen Version 3.x gefühlt doppelt so schnell ist) sondern um die Feinheiten, die letzten Details.

Ein automatisch erstellter Vergleich ist immer um ein Vielfaches wirtschaftlicher als jedes vorstellbare manuelle Verfahren. Mit der einmaligen Anker-Technik verfügt das Tool über eine Funktion, die es ermöglicht, dass Blöcke anhand eindeutiger Kennungen einander sauber zugeordnet werden, und nicht ein neu eingeschobener Abschnitt 1.3 verzweifelt mit dem alten 1.3 verglichen wird, der ja jetzt die 1.4 ist. Auf diese Weise können auch größere Umstellungen erkannt werden und die Änderungsanzeige hält sich nicht mit Irrelevantem auf.

Bleibt die Anzeige gelöschtem, geändertem und neuem Text. Hier ist der Automat im Nachteil, weil er nicht weiß, wie wir tatsächlich geändert haben, was die Absicht war. Er kann nur den alten und neuen Satz (eigentlich: Textknoten) betrachten und technisch analysieren. Zum Einsatz kommt hier zunächst ein bekannter Algorithmus: Longest common substring.

Beispiele

V1: Der Absatz enthält ganz und gar nichts.
V2: Der Absatz enthält gar nichts.

Diff: Der Absatz enthält ganz und gar nichts.

Der längste gemeinsame Text ist der Textanfang bis einschließlich »ga«. Ideal wäre natürlich dies gewesen: Der Absatz enthält ganz und gar nichts. Aber dies ist für den Computer wohl kaum zu erkennen.

V1: Datentyp des Feldes, sofern Ausprägungen vorgebbar.
V2: Datentyp des Feldes, genau dann wenn Ausprägungen vorgebbar.

Diff: Datentyp des Feldes, sofergenau dann wenn Ausprägungen vorgebbar.

Natürlich erschwert es auch hier die Lesbarkeit, dass vom Ende sowohl »sofern« als auch »wenn« mit einem »n« enden. Ideal wäre hier ein die Ausdehnung auf ganze Wörter: Datentyp des Feldes, soferngenau dann wenn Ausprägungen vorgebbar.

Aber die Ausdehnung auf ganze Wörter kann auch unerwünscht sein, wenn zum Beispiel nur Anfangs- oder Endbuchstaben ergänzt oder Tippfehler korrigiert wurden:

V1: Die Erklärung war nicht hinrecihend.
V2: Die Erklärungen waren nicht hinreichend.

Diff: Die Erklärungen waren nicht hinreciichend.

Hier wäre die Ganzwortmethode wohl eher hinderlich: Die ErklärungErklärungen warwaren nicht hinrecihendhinreichend.

Fragen

In meinen Augen stellen sich zwei Fragen:

  • Sollten Optimierungen beim Textvergleich vom Diff-Tool oder von einer nachgelagerten Aufbereitung durchgeführt werden?
  • Wie soll diese Optimierung aussehen?

Gerade-ungerade Sudoku

Auch als Sudokulino ist mir diese Form eines Sudoku begegnet. Naben den üblichen Bedingungen – jede Ziffer nur einmal pro Reihe und Spalte – gilt hier noch: Rechts, links, oben, unten benachbarte Zahlen dürfen keine Nachbarzahlen sein, sie müssen sich um mehr als 1 unterscheiden.

XML-Struktur

In Erinnerung an Michael Kays XSLT-Lösung des Rösselsprungs (»Knight’s Tour«) fassen wir das XML ganz einfach, indem wir alle Felder einfach der Reihe nach angeben.

<fields max="6">
 <field val="5"/><field /><field /><field /><field /><field val="2" />
 <field /><field /><field /><field /><field val="4" /><field val="6" />
 <field /><field val="5" /><field val="3" /><field /><field /><field />
 <field val="4"/><field /><field /><field /><field val="5" /><field />
 <field val="2"/><field val="6" /><field /><field /><field /><field />
 <field /><field /><field /><field /><field val="1" /><field val="3" />
</fields>

Jetzt benötigt es Methoden, um für ein beliebiges Feld festzustellen, welche Ziffern gültig sind. Damit lassen sich alle eindeutigen Zuordnungen durchführen und nach ein paar Runden ist das Quiz gelöst. Was aber, wenn es einmal keine eindeutige Lösung gibt?