mpuppe.de-blog-posts/posts/2016-04-03-knobeln-mit-clojure.markdown

---
layout: post
title: "Knobeln mit Clojure"
date: 2016-04-03 20:46:00 +0200
comments: true
---

Das [ZEITmagazin](https://de.wikipedia.org/wiki/Die_Zeit#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](http://www.zeit.de/2016/14/spiele-logelei-14) 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](https://en.wikipedia.org/wiki/Clojure)-[REPL](https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop)
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](https://github.com/puppe/zahlenschloss).
Bitte schön!

``` clojure
(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))))
```