# Assignment 2

## Hierarchical Data Structures -- Abstract Data Types

#### Notes

In scm, type the expression '() instead of nil which is predefined to be equal to #f in certain implementations.

There are 6 questions plus one bonus optional question.

### Question 1: Reverse

Write a function reverse that takes a list as argument and returns a list with the same elements in reverse order:
```(reverse (list 1 2 3 4)) --> (4 3 2 1)
(reverse (list (list 1 2) (list 3 4))) --> ((3 4) (1 2))
```
Write both a recursive (reverse1) and an iterative version (reverse2).

### Question 2: Iterative map

Write an iterative version of map. Map takes two arguments: a procedure proc and a list l and returns the list of the results of applying proc to each element of l. Name your function mapi.

### Question 3: substitute

Write a function that takes as argument a tree and two numbers and returns a tree with every occurrence of the first number replaced by the second.
```(substitute tree old new)

(substitute (list (list 1 2) (list (list 3 1))) 1 5) --> ((5 2) ((3 5)))
(substitute 1 1 5) --> 5
```

### Question 4: remove

Write a function that takes as argument a tree and a number and returns a tree similar to the input one but with all occurrences of the number removed.
```(remove (list 1 (list 2 1)) 1) --> ((2))
(remove 1 1) --> ()
(remove (list 1) 1) --> ()
(remove (list 1 (list 2 (list 1))) 1) --> ((2))
```

### 21 Simulator

For questions 5, 6 and 7 (optional bonus question), the following explanations apply. The game of 21 is a card game. The (simplified) rules are as follows:
1. There are 2 players.
2. Each card has a numeric value between 1 and 10.
3. The goal is to accumulate a set of cards that totals as close to 21 as possible without going over 21.
4. Each player receives one card that is visible to both players. The next cards are not visible to the other player.
5. The first player asks for a card or decides to stop. If he gets a card and the total goes over 21 he loses. The first player keeps playing until either he loses or he decides to stop. If the first player does not lose, the second player takes his turn and plays similarly.
6. When the second player decides not to take more card, both players show their cards and the player with the larger total wins.
The goal of the problem is to build a simulator of the game of 21 to evaluate the value of different strategies. The following data types need to be defined for implementing the simulation:
• A hand is the set of cards currently in the hand of each player. It will be represented as a pair of numbers: the visible card and the total of all the cards in the hand.
• A strategy determines when a player asks for another card and when he wants to stop and stay with what he has. Strategies will be implemented as procedures with the following arguments:
```     (define (a-strategy my-hand opponent-visible-card)
;; Return #t if want another card, #f otherwise
)
```
• A deck of cards contains the original set of cards. We simply give out cards at random from an infinite deck in which each card value from 1 to 10 is equally probable (this is a simplified model). To implement the deck, the following function is used:
```     (require 'random)     ;; this loads the function random
;; (random n) return a random number between 0
;; and n-1.
(define (get-a-card)
(+ 1 (random 10)))
```
The hand Abstract Data Type is implemented as follows:
```
;; Constructor
(define (make-hand visible-card total)
(cons visible-card total))

;; Selectors
(define (hand-visible-card hand)
(car hand))

(define (hand-total hand)
(cdr hand))

;; Operations
(define (make-new-hand first-card)
;; Create an initial hand with a single visible card
(make-hand first-card first-card))

;; Hand-add-card takes a hand and a new card and returns a hand with
;; the same visible-card as the original, but with the total augmented by the
;; value of the new card:
(make-hand (hand-visible-card hand)
(+ new-card (hand-total hand))))

```

### Question 5: twenty-one and test-strategy

Write a function `twenty-one` to run a simulation of a game between two strategies:
```(define (twenty-one player1-strategy player2-strategy)
;; Return 1 if player1 wins
;; Return 2 if player2 wins
)
```
To test your function, use the following strategy:
```
(define (interactive-strategy your-hand opponent-visible-card)
(newline)
(princ "Opponent visible card: ")
(princ opponent-visible-card)
(newline)
(princ (hand-total your-hand))
(newline)
(princ "Get another card (Y/N)? ")
(user-says-y?))

(define (user-says-y?)

;; Test the simulator as follows:
(twenty-one interactive-strategy interactive-strategy)

```
Define a procedure `test-strategy` that tests two strategies by playing a specified number of simulated Twenty-One games using the two strategies. `test-strategy` should return the number of games that were won by player1. For example,
```(test-strategy interactive-strategy interactive-strategy 10)
```
should play ten games of Twenty-One. It should return a non-negative integer indicating how many games were won by player1.

### Question 6: Strategies stop-at, watch-strategy

Define a procedure `stop-at` that takes a number as argument and returns a strategy procedure. The strategy `stop-at` should ask for a new card if and only if the total of a hand less than the argument to `stop-at`. For example `(stop-at 16)` should return a strategy that asks for another card if the hand total is less than 16, but stops as soon as the total reaches 16. To test your implementation of `stop-at`, play a few games by evaluating:
```(twenty-one interactive-strategy (stop-at 16))
```
Thus, you will be playing against a house whose strategy is to stop at 16. When the simulated games runs, it is impossible for us to tell what is going on. We want to watch a strategy play by observing its inputs and the decisions it makes. Define a procedure called `watch-player` that takes a strategy and the name of a player as arguments and returns a strategy as its result. The strategy returned by `watch-player` should implement the same result as the strategy that was passed to it as an argument, but, in addition, it should print the information supplied to the strategy and the decision that the strategy returns. For example:
```(test-strategy (watch-player (stop-at 16) 'yael)
(watch-player (stop-at 15) 'ido)
2)

Game 1:
Yael visible 6 -- hand 6 -- opponent visible 8
get card 4 -- ask   -- total 10
Yael visible 6 -- hand 10 -- opponent visible 8
get card 7 -- stop -- total 17
Ido visible 8 -- hand 8 -- opponent visible 6
get card 10 -- stop -- total 18
Win: Player 2.

Game 2:
Yael visible 3 -- hand 3 -- opponent visible 9
get card 10 -- ask   -- total 13
Yael visible 3 -- hand 13 -- opponent visible 9
get card 7 -- stop -- total 20
Ido visible 9 -- hand 9 -- opponent visible 3
get card 9 -- stop -- total 18
Win: Player 1.

--> 1 ;; Number of games won by player 1.
```

### Question 7 (OPTIONAL): both

Implement a procedure `both` that takes two strategies as arguments and returns a new strategy. This new strategy will ask for a new card if and only if both strategies would ask for a new card. For example, using the strategy:
```(both (stop-at 19) hit?)
```
will ask for a new card only if the hand total is less than 19 and the user requests a new card.
The end.