[haskell]Mastermind

[Boudewijn]

Hoi

Momenteel ben ik bezig voor een practicum om mastermind te schrijven in haskell.
Dit lukt heel aardig, en eigenlijk is alle functionaliteit al geimplementeerd.... op 1 ding na.

Wiki quote over het doel:

De codemaker kiest in het geheim vier code-pionnen en plaatst deze in een gekozen volgorde achter het zichtschermpje. Het is toegelaten om twee of meer pionnen in dezelfde kleur te kiezen. De codemaker heeft de keuze uit zes verschillende kleuren. Dit is de verborgen code die de codebreker moet gaan ontrafelen.

In zijn beurt plaatst de codebreker vier code-pionnen naar keuze in de eerste lege rij. Nu geeft de codemaker met de sleutel-pinnen het resultaat:

* met zwarte pinnen: hoeveel kleuren staan op de juiste positie?
* met witte pinnen: hoeveel kleuren komen wel in de code voor, maar staan niet op de juiste positie?

ik wil de witte pinnetjes goed berekenen, en vraag me af wat daar nou een goede strategie voor is in haskell. Ik wil het eerst in woorden uitdrukken en daarna omzetten naar een stukje code; ik vraag daarom ook geen oplossingen in code , alleen wat hints of ideeen. (ik moet er zelf nml ook wat van leren ).

Mijn huidige idee is als volgt (waarbij solution en guess allebei een Int lijst zijn):
neem de lengte van de intersectie van solution en guess en trek daar black vanaf.
In haskell:

code:

white [] [] = 0
white solution guess =  length (intersect guess solution) - black solution guess

black is de functie om het aantal goed geplaatste pionnetjes te berekenen. Hier trek ik dat ervanaf om te zorgen dat de pionnen die wel goed geplaatst zijn niet mee worden gerekend.

Dit werkt prima, maar heeft een groot manco.
Stel he, ik heb als guess: [1,1,2,3] en als solution [8,5,1,7]. Nu levert de intersection [1,1] op en dus een lengte van 2 . Dat is incorrect.
Als ik de intersectie van solution op guess doe krijg je hetzelfde probleem maar dan in omgedraaide zin.

Ik weet niet hoe ik dit 'probleem' nou moet uitdrukken; kan iemand me daar bij helpen?


Een mogelijkheid is om als een getal gevonden is in beide lijsten is het uit de solution lijst te verwijderen. Probleem is dat ik dan niet meer met intersect kan werken, maar een voor een de guess lijst door moet itereren.

[ Voor 5% gewijzigd door Boudewijn op 20-09-2007 16:14 ]

[Grijze Vos]

Eerst kijk je voor elke pion of ie op de goede plaats staat. Zo ja, haal dan die pionnen uit je guess set en je solution set.

Neem dan de intersection voor het aantal witte.

Haal dan een voor een je koppels witte pionnen uit je set totdat je niet meer kan.

[ Voor 20% gewijzigd door Grijze Vos op 20-09-2007 16:21 ]

[Salandur]

tellen?

[1,1,2,3] = 2 x 1, 1 x 2, 1 x 3
[8,5,1,7] = 1 x 1, 1 x 5, 1 x 7, 1 x 8
minumum van alles: 1 x 1, 0 x 2, 0 x 3 etc
dus 1 pinnetje -> 0 zwart, 1 wit

ander voorbeeldje:
[1,1,3,8] = 2 x 1, 1 x 3, 1 x 8
[1,8,4,5] = 1 x 1, 1 x 4, 1 x 5, 1 x 8
minimum van alles 1 x 1, 1 x 8 (rest even weggelaten)
dus 2 pinnetjes -> 1 zwart, 1 wit

[ Voor 46% gewijzigd door Salandur op 20-09-2007 16:34 ]

[Boudewijn]

hmmm dat is op zich wel een goed idee , dank je wel .
zowel grijze vos als salandur, straks eens implementeren

[Glimi]

Lijsten in Haskell zijn Linked Lists (als je pech hebt, soms ook nog boxed ) en haskell is ook pure (geen side-effects). Dus het verwijderen van elementen uit lijsten is vaak een eng idee, omdat je dan veel gaat concateneren ( n ++ m -> O(n) ). Daarom lijkt me de volgende oplossing een beter idee:
• Sorteer de lijsten
• Loop ze gelijk af en dwing een ordering af tussen de twee; zijn ze gelijk, dan hogen we de returnwaarde met een op. Is x kleiner dan y, dan mag x weg. Is x groter dan y, dan halen we y weg.

Nog steeds is de code vrij duur ( Log(n)*O(n) + Log(m)*O(n), plus dat je nog steeds tweemaal de lijsten afloopt (voor black en in f). Echter het is allicht goedkoper dan constant nieuwe heapcells alloceren, voor het constant verwijderen van elementen.

De code:

code:

module Main where

import Data.List

white :: (Ord a) => [a] -> [a] -> Int
white sol gue = f (sort sol) (sort gue) - black sol gue
  where f [] ys  = 0
        f xs []  = 0
        f (x:xs) (y:ys) =
          case (compare x y) of
            LT -> f xs (y:ys)
            EQ -> 1 + f xs ys
            GT -> f (x:xs) ys


black :: (Eq a) => [a] -> [a] -> Int
black sol gue = length [ () | (s,g) <- zip sol gue, s == g ]

Ik heb typeclasses gebruikt (zie signatures) maar wel de returnvalue een Int gedeclareerd (dat scheelt instanties van typeclasses en dus dictionaries op runtime). Verder spreekt het allemaal wel voor zich Mocht je problemen hebben, laat het even weten.

[ Voor 181% gewijzigd door Glimi op 20-09-2007 20:09 ]

[Infinitive]

Glimi, bitneukert
Of gewoon Data.Map gebruiken als multiset, dan krijg je wat je wilt doen vrijwel kado.

Haskell:

import Data.Map(Map)
import qualified Data.Map as Map

Om in onderstaande type signaturen duidelijker te maken wat pinnetjes/pionnetjes zijn en wat getallen zijn neem ik even aan dat de pionnetjes en pionnetjes van het type Pawn zijn, bijv:

Haskell:

type Pawn = Int

De representatie van zo'n multiset is een map van pionnetje naar het aantal voorkomens ervan. Eerst je rijtje met pinnetjes/pion naar een multiset converteren:

Haskell:

toMultiset :: [Pawn] -> Map Pawn Int
toMultiset pawns = Map.fromListWith (+) [(p,1) | p <- pawns]

Vervolgens kan je de intersectie nemen, waarbij je het minimum neemt van de voorkomens van een gemeenschappelijke pinnetje/pion in beide sets. Dan is het een kwestie om al die counts bij elkaar op te tellen:

Haskell:

white :: [Pawn] -> [Pawn] -> Int
white solution guess = sum counts
  where
    counts = Map.elems commons
    commons = Map.intersectionWith min solSet guessSet
    solSet = toMultiset solution
    guessSet = toMultiset guess

Werkt dit ook? Even wat rekenen:

code:

guess = [5,5,4,4]
solution = [4,4,4,5]

guessSet = { 5->2, 4->2 }
solSet = { 4->3, 5->1 }

commons = { 5->min 1 2, 4->min 2 3 }
commons = { 5->1, 4->2 }

counts = [ 1, 2 ]
sum [1,2] = 3

Erg handige library, die Data.Map

[ Voor 30% gewijzigd door Infinitive op 20-09-2007 23:10 ]

[Boudewijn]

Glimi en infinitve.
hardstikke mooi, maar vrij ingewikkeld.

kan dit ook met gewone aritmethic? dit omdat de huidige constructies erg leuk zijn ,maar ik het gewoon met losse lists wil

edit: die truc van salandur is wel netjes trouwens, denk dat ik die doe.

[ Voor 16% gewijzigd door Boudewijn op 21-09-2007 19:09 ]

[Verwijderd]

Glimi's oplossing ziet er m.i. wel goed uit.
Volstrekt onleesbaar voor normale stervelingen, en daar gaat 't bij Haskell toch om, toch?

[Grijze Vos]

Verwijderd schreef op vrijdag 21 september 2007 @ 19:58:
Glimi's oplossing ziet er m.i. wel goed uit.
Volstrekt onleesbaar voor normale stervelingen, en daar gaat 't bij Haskell toch om, toch?

Valt wel mee, beetje highlighting support en het is behoorlijk leesbaar.

offtopic:
Glimi: volgens mij is de officiele naam voor de lijst in Haskell trouwens Cons-list.

[ Voor 13% gewijzigd door Grijze Vos op 22-09-2007 12:39 ]

[Glimi]

Grijze Vos schreef op zaterdag 22 september 2007 @ 12:39:
[...]

Valt wel mee, beetje highlighting support en het is behoorlijk leesbaar.

offtopic:
Glimi: volgens mij is de officiele naam voor de lijst in Haskell trouwens Cons-list.

Ik kom zoiets eigenlijk niet tegen in de 98 report (http://www.haskell.org/onlinereport/basic.html). In mijn opinie is Cons slechts een van de twee lijst constructoren. De reden dat ik het feitelijk een linked list noem, is om de implementatie ervan die de compiler (GHC, EHC, ik ben er eigenlijk van overtuigd dat andere compilers het niet erg veel anders implementeren) er van maakt. Een Cons-closure bevat een pointer naar z'n tweede lijst parameter en een pointer (of unboxed een value) naar z'n waarde.

[Soultaker]

Boudewijn schreef op donderdag 20 september 2007 @ 16:12:
Dit werkt prima, maar heeft een groot manco.
Stel he, ik heb als guess: [1,1,2,3] en als solution [8,5,1,7]. Nu levert de intersection [1,1] op en dus een lengte van 2 . Dat is incorrect.
Als ik de intersectie van solution op guess doe krijg je hetzelfde probleem maar dan in omgedraaide zin.

Is dit niet het hele probleem met die ambiguë definitie van de witte pionnetjes? Tel je de pionnetjes van de codebreker, van de codemaker, of paren van pionnetjes? Volgens mij is duidelijk krijgen hoe dat kutspelletje nou eigenlijk werkt de helft van het werk.
* Soultaker begreep het in echt Mastermind ook nooit.

[Glimi]

Boudewijn schreef op vrijdag 21 september 2007 @ 18:15:
Glimi en infinitve.
hardstikke mooi, maar vrij ingewikkeld.

kan dit ook met gewone aritmethic? dit omdat de huidige constructies erg leuk zijn ,maar ik het gewoon met losse lists wil

edit: die truc van salandur is wel netjes trouwens, denk dat ik die doe.

Ik doe gewone arithmethic Het algoritme is als volgt (en kan ook heel goed imperatief geimplementeerd worden, bijvoorbeeld met een queue!) :

• Stel ik heb een solution [8,5,1,7] en een guess [1,1,2,3]
• Ik sorteer beide lijsten en krijg solution [1,5,7,8] en guess [1,1,2,3]
• Ik peek bij beide lijsten naar het eerste element in dit geval 1 en 1
• De elementen zijn gelijk, dus we hebben een overeenkomst. Dus we kunnen een bij het uiteindelijke resultaat optellen, en we gaan verder met de overgebleven lijsten zonder de elementen, [5,7,8] en [1,2,3]
• Weer peeken we de eerste elementen van beide lijsten, 5 en 1
• Omdat 1 kleiner is dan 5 en dus er nog een 5 achter de 1 kan zitten, gaan we verder in recursie met [5,7,8] en [2,3]
• Hetzelfde als hierboven maar dan met 5 en 2
• Hetzelfde als hierboven maar dan met 5 en 3
• We peeken weer de eerste elementen van beide lijsten, maar de guess lijst is leeg: in dat geval kan er geen element meer gelijk zijn, dus returnen we nul.

Uiteindelijk komt er uit f (sort sol) (sort gue) dus 1 (1+0).

Ik zal zo deze post ff uitbreiden waarom het verwijderen van elementen een slecht idee is en wat de [ | ] syntax is, eerst ff eten

-----
Zo done Eerst over de list list comprehensions:

Een veelvoorkomend patroon in haskell is dat je een lijst hebt, daar enkele uit wilt selecteren en daar een actie op uitvoeren. Je kunt het een beetje vergelijken met SQL, uit een dataset maak je een selectie en die waardes kun je dan aanpassen.
Een straightforward way om dat te doen zou een combinatie van map en filter zijn, bijvoorbeeld, pak alle even getallen van de set 1 t/m 100 en ram ze door een functie f. Dan zou je iets krijgen als

code:

bla = map f (filter even [1..100])

Omdat dit zoveel voorkomt, is er speciale syntax voor in Haskell (en omdat we alles graag zo compact mogelijk opschrijven natuurlijk )

code:

bla = [ f x | x <- [1..100], even x]

is precies hetzelfde.

In de syntax [ a | b, c ] is a het bewerken van de waarde, b is de generator (voor elk element van een lijst) en c is een predicaat waarmee je waardes filtert.
Eventueel kun je ook meerdere generatoren hebben. Dan werkt het net als een crossjoin in SQL. Probeer dit maar eens in GHCI (of hugs)

code:

[ (x,y) | x <- [1..5], y <- "abcde" ]

Nu ik er over nadenk, het gebruiken ervan in black is totaal onnodig, gewoon zippen en filteren is genoeg , want we doen immers geen bewerkingen met de data. Oja voor als je weten wat zip ( zip :: [a] -> [b] -> [(a,b)] ), is gewoon het combineren van twee lijsten in een lijst van pairs.

[ Voor 31% gewijzigd door Glimi op 22-09-2007 20:01 ]

[Soultaker]

Glimi schreef op zaterdag 22 september 2007 @ 18:28:
Ik kom zoiets eigenlijk niet tegen in de 98 report (http://www.haskell.org/onlinereport/basic.html). In mijn opinie is Cons slechts een van de twee lijst constructoren.

Ik denk dat de term Cons gewoon overgenomen is uit LISP. Daar is een cons-cell (die je maakt met de (cons x y) call) simpelweg een paar van twee objecten (of een object met twee pointers naar andere objecten), en wordt het gebruikt voor verschillende dingen: paren, binary trees, linked lists. Om met een cons-cell een linked list te maken heb je alleen een list terminator object (nil) nodig.

In LISP heb je alleen een cons cell en geen enkel ander aggregate data type. In Haskell kun je vrij aggregate datatypes maken in de vorm van algebraïsche datatypen. Daar heb je geen cons-cell voor nodig dus lijkt het me niet logisch om dat nog een cons-list te noemen (behalve naar analogie met LISP) ook al werkt het intern natuurlijk ongeveer hetzelfde.

[Boudewijn]

Glimi schreef op zaterdag 22 september 2007 @ 18:41:
Ik zal zo deze post ff uitbreiden waarom het verwijderen van elementen een slecht idee is en wat de [ | ] syntax is, eerst ff eten

al klaar met eten?
dank je trouwens voor de uitleg, erg leerzaam

[Glimi]

Soultaker schreef op zaterdag 22 september 2007 @ 18:46:
[...]
Ik denk dat de term Cons gewoon overgenomen is uit LISP.

Dat verklaart het wel ja. Het is eigenlijk schandalig hoe weinig ik weet van talen die aan de basis hebben gestaan van de talen van vandaag (LISP, Ada, Smalltalk). Misschien leuk om eens op te pakken

Boudewijn schreef op zaterdag 22 september 2007 @ 19:35:
[...]
al klaar met eten?
dank je trouwens voor de uitleg, erg leerzaam

Snel eten is slecht voor je spijsvertering (A) Maar de post is uitgebreid met de list comprehensions, nu nog even over waarom het verwijderen van data uit lijsten een slecht idee is.

Het belangrijkste om te weten is dat haskell een pure language is. Er zijn dus geen side effects. Als f de waarde [1,2,3] heeft gekregen, zal hij dit in lengte van dage blijven hebben (nouja tot f uit de scope is en ge-GC'd is). Dat vervolgens in dezelfde scope als f, g de waarde delete 2 [1,2,3] (evaluated [1,3]) krijgt, doet er niets aan af dat f nog steeds [1,2,3] heeft.
Er zal dus voor g een nieuwe lijst gemaakt moeten worden, f wordt niet gewijzigd!

Dus stel, we maken white als volgt:

code:

white :: (Eq a) => [a] -> [a] -> Int
white sol gue = f sol gue - black sol gue
  where f ys []     = 0              -- asume length ys >= xs
        f ys (x:xs) = if x `elem` ys
                      then 1 + f (delete x ys) xs
                      else f ys xs

Dan bouwen we voor elke keer dat x een element is van ys, een nieuwe lijst op! Natuurlijk is de haskell compiler ook niet dom, en deelt common subsequences van de lijsten, maar toch levert dit een hoop allocaties op.

Nu zou ik er in jouw geval niet zo bang voor zijn. 't zijn immers maar weinig elementen in de guess/solution set, maar het is allicht handig om te weten, mocht je later met iets grotere collecties gaan werken

[edit]Hahaha, zit je in de course FPGO van Andres Niet bang zijn om gedag te zeggen op het ST colloqium dan maar he

[ Voor 4% gewijzigd door Glimi op 22-09-2007 20:42 ]

[Verwijderd]

Grijze Vos schreef op zaterdag 22 september 2007 @ 12:39:
Valt wel mee, beetje highlighting support en het is behoorlijk leesbaar.

code:

white sol gue = f (sort sol) (sort gue) - black sol gue...

Ik ken maar 1 taal die slechter leesbaar is, en dat is APL.

[Glimi]

Verwijderd schreef op zaterdag 22 september 2007 @ 21:12:
[...]

code:

white sol gue = f (sort sol) (sort gue) - black sol gue...

Ik ken maar 1 taal die slechter leesbaar is, en dat is APL.

Mwoah dit zit voornamelijk in dat ik het compact opgeschreven heb (vermoed ik)
Als het

code:

white sol gue = amountInGuessThatAreInSolution - amountCorrectlyPlaced
  where amountInGuessThatAreInSolution = f (sort sol) (sort gue)
        amountCorrectlyPlaced = black sol gue

was geweest, maakt dat dan verschil?

[Verwijderd]

Nauwelijks, maar toch bedankt.

[Boudewijn]

Glimi schreef op zaterdag 22 september 2007 @ 20:26:
[edit]Hahaha, zit je in de course FPGO van Andres Niet bang zijn om gedag te zeggen op het ST colloqium dan maar he

offtopic:
who the fsck ben jij dan wel niet?
en correct.
wss kun je via mijn username ook nog wel afleiden welke ik ben