Martin Puppe

Knobeln mit Clojure

Das ZEITmagazin enthält regelmäßig unter der Überschrift “Logelei” ein Logikrätsel. Neulich hatte ich Ausgabe 14/2016 vor mir liegen. Der vollständige Text ist hier zu finden. Ich fasse die wesentlichen Punkte zusammen. Gesucht wird die Kombination für ein Zahlenschloss. Das Zahlenschoss hat sechs Ziffern. Die gesuchte Zahl muss die folgenden Bedingungen erfüllen:

  1. Die Zahl ist durch 4 teilbar.
  2. Die Zahl ist rückwärts ebenfalls durch 4 teilbar.
  3. Die Zahl ist durch 7 teilbar.
  4. Die Zahl ist nicht durch 11 teilbar.
  5. Die Quersumme der Zahl beträgt 32.
  6. Jede Ziffer kommt in der Zahl entweder doppelt oder gar nicht vor.

Nun habe ich erst versucht das Rätsel nur mit Papier und Stift zu lösen. Leider ist Zahlentheorie nicht meine Stärke und mein Wissen erschöpfte sich im konkreten Fall in dem Fakt, dass es reicht die letzten beiden Ziffern einer Zahl zu betrachten, um zu überprüfen, ob sie durch 4 teilbar ist. Also habe ich stattdessen meinen Laptop zur Hand genommen und eine Clojure-REPL geöffnet. Ich habe mir die nötigen Funktionen definiert und schließlich alles zusammengestöpselt. So war das Rätsel trotz Brute-Force-Ansatz relativ schnell gelöst.

Heute habe ich alles noch mal ordentlich aufgeschrieben.Zusätzlich habe ich noch ein paar Tests geschrieben. Den gesamten Quellcode habe ich auf Github veröffentlicht. Bitte schön!

(ns zahlenschloss.core
  (:gen-class))

(defn teilbar?
  "Gibt `true` zurück, genau dann wenn `n` durch `x` teilbar
  ist."
  [x n]
  (= 0 (mod n x)))

(doseq [x [4 7 11]]
  (intern *ns*
          (symbol (str "teilbar" x "?"))
          (partial teilbar? x)))


(defn ziffern
  "Nimmt eine Zahl `n` und gibt die Folge der Ziffern der Zahl
  zurück."
  [n]
  (loop [n n
         ziffern (list)]
    (if (= n 0)
      ziffern
      (recur (int (/ n 10)) (conj ziffern (mod n 10))))))

; http://stackoverflow.com/a/5058544
(defn- exp [x n]
  "Berechnet x hoch n."
  (reduce * (repeat n x)))

(defn wert
  "Nimmt eine Folge von Ziffern und berechnet ihren Zahlenwert."
  [ziffern]
  (loop [summe 0
         faktor (exp 10 (dec (count ziffern)))
         [ziffer & ziffern] ziffern]
    (if ziffer
      (recur
        (+ summe (* ziffer faktor))
        (/ faktor 10)
        ziffern)
      summe)))

(defn links-auffuellen
  "Nimmt eine Folge von Ziffern und füllt sie, falls nötig,
  links mit Nullen auf, sodass das Ergebnis aus mindestens sechs
  Ziffern besteht."
  [ziffern]
  (loop [laenge (count ziffern)
         ziffern ziffern]
    (if (>= laenge 6)
      ziffern
      (recur
        (inc laenge)
        (conj ziffern 0)))))

(defn rueckwaerts
  "Nimmt eine Zahl und dreht die Folge ihrer Ziffern um. Dabei
  wird angenommen, dass die Zahl mindestens sechsstellig ist.
  Das Ergebnis ist daher mindestens auch sechsstellig."
  [n]
  (wert (reverse (links-auffuellen (ziffern n)))))

(defn quersumme
  "Berechnet die Quersumme der Zahl `n`."
  [n]
  (apply + (ziffern n)))

(defn zaehle-ziffern
  "Zählt, wie oft die einzelnen Ziffern in der Zahl `n`
  vorkommen. Es wird angenommen, dass `n` mindestens
  sechsstellig ist."
  [n]
  (reduce
    (fn [m ziffer]
      (assoc m ziffer (inc (get m ziffer 0))))
    {}
    (links-auffuellen (ziffern n))))

(defn doppelt-oder-gar-nicht?
  "Gibt `true` zurück, genau dann wenn jede Ziffer in der Zahl
  doppelt oder gar nicht vorkommt. Es wird angenommen, dass `n`
  mindestens sechsstellig ist."
  [n]
  (if (some #(not= % 2) (vals (zaehle-ziffern n)))
    false
    true))

(defn -main
  [& args]
  (println "Mögliche Lösung(en):")
  (apply
    println
    (->> (range 0 1000000)
         ; Die Zahl ist durch 4 teilbar.
         (filter teilbar4?)
         ; Die Zahl ist rückwärts ebenfalls durch 4 teilbar.
         (filter #(teilbar4? (rueckwaerts %)))
         ; Die Zahl ist durch 7 teilbar.
         (filter teilbar7?)
         ; Die Zahl ist nicht durch 11 teilbar.
         (filter (complement teilbar11?))
         ; Die Quersumme der Zahl beträgt 32.
         (filter #(= 32 (quersumme %)))
	 ; Jede Ziffer kommt entweder doppelt oder gar nicht
	 ; vor.
         (filter doppelt-oder-gar-nicht?)
         ; Wir geben maximal 10 Zahlen aus.
         (take 10))))