Let’s say there are two persons, **Composer** and **Performer**.

The **Composer** randomly selects three different **Pitch** which constructed by two part, **Note** and **Octave**. **Note** in the range of “A” to “G”, **Octave** in the range of “1” to “3”.

For example, here is a typical **Pitch** combined by ‘A’ and ‘1’, in which ‘A’ is the **Note**, and ‘1’ is the **Octave**.

Once **Composer** selected a Combination, **Performer** needs to guess it as quick as possible. After each guess, **Performer** get a feedback which indicates that:

- how many pitches in the guess are included in the target (
**correct pitches**) - how many pitches have the right note but the wrong octave (
**correct notes**) - how many pitches have the right octave but the wrong note (
**correct octaves**)

Now, the question is how to get the corrected answer as less times as possible.

```
-- Subject : UniMelb 2019 SM1 COMP90048 Declarative Programming
-- File : Proj1.hs
-- Author : Mingzhe Du
-- Origin : Mon Apr 8 2019
-- Purpose : This program for guessing a target chord. In each round of the game,
-- the program will generate a chord from a possible set, and then a feedback
-- against the guess will be given. Depanding on these feedbacks, the aim of this
-- program is get the correct chord with as less as possible guess times.
module Proj1 (Pitch, GameState, toPitch, feedback, initialGuess, nextGuess) where
-- Pitch structure
data Pitch = Pitch { note :: Char,
octave :: Char
} deriving (Eq)
instance Show Pitch where
show (Pitch note octave) = [note, octave]
-- Game State
data GameState = GameState { times :: Int, -- Guess times
cCombinations :: [[[Char]]] -- Possible set
} deriving (Eq, Show)
-- Converting String to Pitch
toPitch :: String -> Maybe Pitch
toPitch (a:b:t)
| not (null t) = Nothing
| (elem note' ['A'..'G']) && (elem octave' ['1'..'3']) = Just Pitch {note = note', octave = octave'}
| otherwise = Nothing
where note' = a
octave' = b
-- Comparing target chord and guessed chord
feedback :: [Pitch] -> [Pitch] -> (Int,Int,Int)
feedback pitch_a pitch_b
| (length pitch_a == 3) && (length pitch_b == 3) = (c_p, c_n - c_p, c_o - c_p)
| otherwise = (0,0,0)
where get_key key = foldr (\x acc -> key x:acc) []
c_p = getCounter pitch_a pitch_b 0 -- Correct pitches
c_n = getCounter (map note pitch_a) (map note pitch_b) 0 -- Correct notes
c_o = getCounter (map octave pitch_a) (map octave pitch_b) 0 -- Correct Octaves
-- Initial guess
initialGuess :: ([Pitch], GameState)
initialGuess = (currentGuess, gameState)
where currentGuess = combinationToPitch (cGuess)
gameState = GameState 0 all_combinations
all_items = getCombination "ABCDEFG" "123"
cGuess:all_combinations = subsequencesOfSize 3 all_items -- New guess and new possible set
getCombination p_note p_octave = foldr (\x acc -> (map (\y -> y:[x]) p_note) ++ acc) [] p_octave
combinationToPitch combinations = map (\(Just x) -> x) $ map toPitch combinations -- Converting String to Pitch
-- Get the next guess
nextGuess :: ([Pitch], GameState) -> (Int,Int,Int) -> ([Pitch],GameState)
nextGuess (pGuess, pGameState) pFeedback = (cGuess, cGameState)
where cGuess':cCombs = getNewCombination pGuess pCombinations pFeedback
pCombinations = cCombinations pGameState
cGuess = toChord cGuess'
cGameState = GameState ((times pGameState) + 1) cCombs
toChord = map (\x -> Pitch (x !! 0) (x !! 1))
-- Help Functions
-- remove an item from a list
removeItem :: (Eq a) => a -> [a] -> [a]
removeItem _ [] = []
removeItem x (y:ys)
| x == y = ys
| otherwise = y : removeItem x ys
-- get the number of same elements in two lists
getCounter :: (Eq a) => [a] -> [a] -> Int -> Int
getCounter [] y c = c
getCounter (x:xs) y c
| elem x y = getCounter xs (removeItem x y) (c+1)
| otherwise = getCounter xs y c
-- Generate combinations by a specifc size
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs in if n>l then [] else subsequencesBySize xs !! (l-n)
where subsequencesBySize [] = [[[]]]
subsequencesBySize (x:xs) = let next = subsequencesBySize xs in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
-- Converting a string list to pitch list
toChord :: [[Char]] -> [Pitch]
toChord a = map (\x -> Pitch (x !! 0) (x !! 1)) a
-- retrive a new guess
getNewCombination :: [Pitch] -> [[[Char]]] -> (Int, Int, Int) -> [[[Char]]]
getNewCombination guess allCombinations pFeedback = foldr (\x acc -> if checkFeedback (toChord x) then x:acc else acc) [] allCombinations
where checkFeedback nChord = if pFeedback == (feedback guess nChord) then True else False
```