**Deklarative Programmierung**

**Übungszettel 08** - *Jonathan Wendt*

---

[originaler Übungszettel](Z8.pdf)

[Racket-File](Aufgabe_6.rkt)

# Aufgabe 06

**Aufgabenbeschreibung:**

> Das Nim-2-3-Spiel1 ist ein Spiel für 2 Personen. Zu Beginn werden
> **Streichhölzer in 2 Reihen** ausgelegt, wobei die **Anzahl** der Streichhölzer in den einzelnen
> Reihen **beliebig** gewählt werden kann. Die **Spieler ziehen** nun **abwechselnd**. Wer am Zug ist,
> **entnimmt aus** der **Reihe**, die **mehr Streichhölzer** enthält, **2 oder 3** Streichhölzer. Wenn beide
> **Reihen gleich viele** Streichhölzer enthalten, kann eine **beliebige** Reihe wählen. Wer **zuerst
> nicht mehr ziehen** kann, hat das Spiel **verloren**.

## Aufgabe 06 (a)

### Aufgabenbeschreibung

> Schreiben Sie eine Funktion:
> ```lisp
> ; Number Number -> Bool
> ; Checks if one can win the game if the two rows contain
> ; n and m matches.
> 
> (check-expect (win? 2 2) false)
> (check-expect (win? 3 2) false)
> (check-expect (win? 2 4) true)
> (check-expect (win? 2 5) true)
> (check-expect (win? 9 6) true)
> 
> (define (win? n m) ...
> ```

### Lösung

```lisp
; Number Number -> Bool
; Checks if one can win the game if the two rows contain
; n and m matches.
(check-expect (win? 2 2) false)
(check-expect (win? 3 2) false)
(check-expect (win? 2 4) true)
(check-expect (win? 2 5) true)
(check-expect (win? 9 6) true)

(define (win? n m)
  (if (and (< n 2) (< m 2)) false
    (not (and
      (if (>= n 3) (win? (- n 3) m) true)
      (if (>= n 2) (win? (- n 2) m) true)
      (if (>= m 3) (win? n (- m 3)) true)
      (if (>= m 2) (win? n (- m 2)) true)
     ))))
```

## Aufgabe 06 (b)

### Aufgabenbeschreibung

> Zeigen Sie, dass Ihre `(win? n m)`-Implementierung terminiert.

### Lösung

Der erste Aufruf von `win?` erfolgt mit beliebigen $n$ und $m$.
Sofern die **Abbruchbedingung $(n<2) \land (m<2)$ erfüllt** ist, erfolgt **kein weiterer rekursiver Aufruf** und die **Funktion terminiert**.
Ist die Bedingung **nicht erfüllt**, so erfolgt...

- falls $n \geq 3$ mit $n=n-3$
- falls $n \geq 2$ mit $n=n-2$
- falls $m \geq 3$ mit $m=m-3$
- falls $m \geq 2$ mit $m=m-3$

... ein **erneuter Aufruf** von `win?`, während der jeweils **andere Wert unverändert** bleibt.

In jedem **erneuten Aufruf** gilt also in jedem Fall **entweder $n_1 < n_0$ oder $m_1 < m_0$**, womit beide **Parameter** mit jeder Rekursionsstufe **gegen ihre Abbruchbedingung streben**.

## Aufgabe 06 (c)

### Aufgabenbeschreibung

> Schreiben Sie eine Funktion:
> ```lisp
> ; Number Number -> String
> ; Suggests a move for the pick-a-match game
> (check-expect (suggest 3 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
> (check-expect (suggest 2 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
> (check-expect (suggest 6 2) "Ziehe 3 aus der ersten Reihe")
> (check-expect (suggest 4 2) "Ziehe 2 aus der ersten Reihe")
> (check-expect (suggest 2 4) "Ziehe 2 aus der zweiten Reihe")
> (check-expect (suggest 2 5) "Ziehe 3 aus der zweiten Reihe")
> 
> (define (suggest n m) ...
> ```
> `(suggest m n)` soll dabei dem Spieler den **nächsten Zug empfehlen**, sodass dieser gewinnt. Greifen Sie dabei auf ihre `(win? n m)`-Funktion zurück. Ist es **nicht möglich** für den Spieler **zu gewinnen**, soll ein **Text mit dieser Information** zurückgegeben werden.

### Lösung

```lisp
; Number Number -> String
; Suggests a move for the pick-a-match game
(check-expect (suggest 3 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 2 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 6 2) "Ziehe 3 aus der ersten Reihe")
(check-expect (suggest 4 2) "Ziehe 2 aus der ersten Reihe")
(check-expect (suggest 2 4) "Ziehe 2 aus der zweiten Reihe")
(check-expect (suggest 2 5) "Ziehe 3 aus der zweiten Reihe")

(define (suggest n m)
  (if (not (win? n m)) "Du kannst das Spiel mit keinem Zug mehr gewinnen"
    (cond
      [(and (>= n 3) (not (win? (- n 3) m))) "Ziehe 3 aus der ersten Reihe"]
      [(and (>= m 3) (not (win? n (- m 3)))) "Ziehe 3 aus der zweiten Reihe"]
      [(and (>= n 2) (not (win? (- n 2) m))) "Ziehe 2 aus der ersten Reihe"]
      [(and (>= m 2) (not (win? n (- m 2)))) "Ziehe 2 aus der zweiten Reihe"])))
```