IB000 – L´am´an´ı ˇcokol´ady Martin Milata, <
[email protected]> 27.11.2007
1
ˇ Cokol´ ada s alespoˇ n jedn´ım sud´ ym rozmˇ erem
Pokud je alespoˇ n jeden rozmˇer ˇcokol´ ady sud´ y (s v´ yjimkou tabulky velikosti 1x2, kter´a uˇz je od zaˇc´ atku podle pravidel nedˇeliteln´ a a proto vyhr´av´a druh´ y hr´aˇc), m´a prvn´ı hr´aˇc trivi´aln´ı vyhr´avaj´ıc´ı strategii. Hr´ aˇce, kter´ y l´ ame jako prvn´ı, budu oznaˇcovat jako hr´aˇce A, druh´eho jako hr´aˇce B. Strategie hr´ aˇce A je n´ asleduj´ıc´ı: 1. Hr´ aˇc A rozlom´ı tabulku na dvˇe stejnˇe velk´e poloviny. Jednu si oznaˇc´ıme jako ˇcervenou, druhou jako modrou. 2. Pokud jsou vˇsechny kousky d´ ale nedˇeliteln´e hra konˇc´ı a vyhr´av´a hr´aˇc A, protoˇze l´amal jako posledn´ı. Pokud hra pokraˇcuje, zˇrejmˇe plat´ı, ˇze ˇcerven´a i modr´a ˇc´ast ˇcokol´ady jsou rozl´am´any identick´ ym zp˚ usobem. 3. Hr´ aˇc B rozlom´ı nˇejak´ y kousek ˇcokol´ady. Protoˇze existuje i identick´ y kousek opaˇcn´e barvy, rozlom´ı jej stejn´ ym zp˚ usobem hr´aˇc A. 4. Pokraˇcujeme bodem 2.
2
Tabulka s lich´ ymi rozmˇ ery
Pro jednotliv´e tabulky o lich´ ych rozmˇerech jsem probl´em ˇreˇsil prochazen´ım hern´ıho stromu1 . Uzly tohoto stromu jsou jednotliv´e moˇzn´e stavy hry, tj. jak je v dan´em okamˇziku nal´am´ana ˇcokol´ada, koˇren je poˇc´ ateˇcn´ı stav hry, tj. cel´ y kousek ˇcokol´ady o dan´ ych rozmˇerech a listy jsou koneˇcn´e stavy hry, kdy nelze zlomit dalˇs´ı kousek a jeden z hr´aˇc˚ u t´ım p´adem vyhr´al. Pokud je vzd´alenost od koˇrene k listu lich´ a, vyhr´ al hr´ aˇc A, pokud je sud´a, vyhr´al hr´aˇc B. Skuteˇcnost zjiˇstˇen´a ohlednˇe ˇcokol´ ady s jedn´ım sud´ ym rozmˇerem se d´a zobecnit na stav ˇcokol´ady, kdy jeden jej´ı d´ıl m´a aspoˇ n jeden sud´ y rozmˇer a neexistuj´ı jin´e d´ıly, kter´e by se podle pravidel hry daly zlomit. K proch´ azen´ı tohoto stromu jsem pouˇzil jednoduch´ y rekurzivn´ı algoritmus: • Pokud neexistuje kousek, kter´ y by se dal rozlomit, hr´aˇc, kter´ y je na tahu nem˚ uˇze nic dˇelat, proto v takov´e situaci vˇzdy prohr´av´a a v´ yhern´ı (pr´azdnou) strategii m´a v tomto pˇr´ıpadˇe hr´ aˇc, kter´ y zrovna nen´ı na tahu. • Pokud existuje pouze jedin´ y rozlomiteln´ y kousek a alespoˇ n jeden jeho rozmˇer je sud´ y, pak hr´ aˇc, kter´ y je moment´ alnˇe na tahu m˚ uˇze pouˇz´ıt strategii popsanou v prv´ı ˇc´asti tohoto dokumentu a tak si pokaˇzd´e zajistit v´ıtˇezstv´ı. Tuto ˇc´ast algoritmu lze vynechat, slouˇz´ı pouze pro jeho zrychlen´ı. 1 Sp´ ıˇse se jedn´ a o orientovan´ y acyklick´ y graf, protoˇ ze ke stejn´ emu vrcholu se d´ a doj´ıt v´ıce cestami a pokud jsou dva vrcholy stejn´ e, je stejn´ y i podstrom jejich potomk˚ u. Z d˚ uvodu jednoduchosti jsem ale pracoval se stromem, ˇ c´ımˇ z jsem pravdˇ epodobnˇ e algorimus mi tˇ eˇ zko odhadnutelnou mˇ erou zpomalil.
1
• Pokud nen´ı splnˇena ani jedna z ukonˇcovac´ıch podm´ınek, pak algoritmus rekurzivnˇe zjist´ı zda-li m´ a druh´ y hr´ aˇc vyhr´ avaj´ıc´ı strategii pro vˇsechny potomky aktu´aln´ıho vrcholu hern´ıho stromu. Pokud ano, aktu´ aln´ı hr´ aˇc nem˚ uˇze hru svou volbou ovlivnit a prohr´al. Pokud existuje potomek, pro kter´ y nem´ a druh´ y hr´aˇc vyhr´avaj´ıc´ı strategii, pak jej aktu´aln´ı hr´aˇc m˚ uˇze zvolit a t´ım si zajistit v´ yhru. D˚ ukaz spr´ avnosti algoritmu struktur´aln´ı indukc´ı na hern´ım stromˇe v podstatˇe kop´ıruje jeho definici: B´ aze – listy stromu. Pokud neexistuje rozlomiteln´ y kousek, pak algoritmus urˇc´ı prohru hr´aˇce, kter´ y je pr´ avˇe na tahu, coˇz je podle pravidel hry spr´avnˇe. Algoritmus tedy vrac´ı spr´avn´ y v´ ysledek pro listy stromu. Indukˇ cn´ı krok – pˇredpokl´ ad´ ame, ˇze algoritmus je spr´avn´ y pro vˇsechny potomky vrcholu V a chceme dok´ azat, ˇze je t´ım p´adem spr´avn´ y i pro nˇej. Pokud algoritmus ozn´am´ı existenci v´ yhern´ı strategie druh´eho hr´aˇce pro vˇsechny potomky vrcholu V, pak pro vrchol V urˇc´ı, ˇze aktu´ aln´ı hr´ aˇc nem´ a vyhr´avaj´ıc´ı strategii, coˇz je zˇrejmˇe spr´avn´e. Pˇr´ıpad neexistence v´ yhern´ı strategie druh´eho hr´ aˇce pro alespoˇ n jednoho potomka pak znamen´a, ˇze aktu´aln´ı hr´aˇc vyhr´ avaj´ıc´ı strategii m´ a. Algoritmus je tedy korektn´ı pro vˇsechny vrcholy hern´ıho stromu, vˇcetnˇe koˇrene.
3
Vypoˇ c´ıtan´ e hodnoty
Vzhledem k exponenci´ aln´ı sloˇzitosti algoritmu a jeho pravdˇepodobnˇe nepˇr´ıliˇs efektivn´ı implementaci se mi podaˇrilo urˇcit hr´ aˇce s v´ yhern´ı strategi´ı pouze u velmi mal´ ych hodnot m a n. A znamen´a, ˇze vˇzdy vyhr´ avaj´ıc´ı strategii m´ a hr´ aˇc, kter´ y zaˇc´ın´a l´amat, B znamen´a, ˇze ji m´a druh´ y hr´aˇc a ,,-“ znamen´ a, ˇze jsem z ˇcasov´ ych d˚ uvod˚ u nebyl schopen hr´aˇce urˇcit. m/n
1 3 5 7 9 11 13 15 17 19 21 23
1 B B A B A B A A B A A B
3
5
7
9
B B B B B B A B -
B B B -
B -
-
Pro m=1 m´ a hr´ aˇc A d´ ale vyhravaj´ıc´ı strategii pro tato n: 25, 29, 33, 35; hrac B pak pro 27, 31, 37.
4
Zdrojov´ y k´ od
Algoritmus je implementov´ an ve funkcion´aln´ım jazyce Haskell. N´asleduje kompletn´ı zdrojov´ y k´od.
2
module Main where import Data . List import System . Environment type P i e c e = ( Int , Int , Int ) −− mensi rozmer , v e t s i rozmer p o c e t , p o c e t type Cut = [ Piece ] −− n e k o l i k kousku c o k o l a d y − h e r n i s t a v −− −− h l a v n i f u n k c e − z k o n t r o l u j e argumenty predane na p r i k a z o v e m radku , −− p r e v e d e j e na c i s l a , preda j e f u n k c i whowins , k t e r a e v e n t u a l n e −− v r a t i h r a c e s v y h e r n i s t r a t e g i i , k t e r e h o f u n k c e main v y p i s e −− main : : IO ( ) main = do a r g s <− getArgs i f length a r g s /= 2 then error ” Spatny p o c e t argumentu ” e l s e do l e t m = head a r g s n = head $ t a i l a r g s putStr ( ”Rozmery ” ++ m ++ ”x” ++ n ++ ” : ” ) i f whowins ( read m) ( read n ) then putStrLn ” Prvni h r a c ma v i t e z n o u s t r a t e g i i ” e l s e putStrLn ”Druhy h r a c ma v i t e z n o u s t r a t e g i i ” −− −− wrapper o k o l o p l a y e r w i n s , argumenty j s o u rozmery c o k o l a d y , v r a c i −− t r u e pokud ma v i t e z n o u s t r a t e g i i p r v n i hrac , j i n a k f a l s e −− whowins : : Int −> Int −> Bool whowins m n = p l a y e r w i n s $ n o r m a l i z e [ (m, n , 1 ) ] −− −− v r a t i t r u e , pokud ma hrac , k t e r y j e v t e t o p o z i c i na t a h u pro danou −− h e r n i p o z i c i v y h e r n i s t r a t e g i i −− − pokud s e c o k o l a d a j i z neda r o z l o m i t , h ra c v z d y p r o h r a v a −− − pokud ma c o k o l a d a j e d i n y p o d l e p r a v i d e l r o z l o m i t e l n y d i l e k a t e n −− ma a l e s p o n j e d e n sudy rozmer , h rac muze v z d y v y h r a t −− − v o s t a t n i c h p r i p a d e c h j e r e k u r z i v n e z k o n t r o l o v a n o , j e s t l i −− a l e s p o n j e d n o z moznych r o z l o m e n i ma pro t o h o t o h r a c e v y h e r n i −− s t r a t e g i i ( t z n . zda− l i v s e c h n a r o z l o m e n i n e v y h r a v a druhy hra c ) −− p l a y e r w i n s : : Cut −> Bool playerwins [ ] = False p l a y e r w i n s c | s i n g l e E v e n S i d e c = True | otherwise = not ( a l l p l a y e r w i n s ( c u t s c ) )
3
−− −− v r a t i t r u e , pokud ma c o k o l a d a j e d i n y r o z l o m i t e l n y d i l e k a t e n ma −− a l e s p o n j e d e n rozmer sudy −− s i n g l e E v e n S i d e : : Cut −> Bool s i n g l e E v e n S i d e [ ( m, n , c ) ] = c == 1 && ( even m | | even n ) singleEvenSide c = False −− −− v r a t i seznam v s e c h moznych r o z l o m e n i c o k o l a d y , k t e r e j e mozne p o d l e −− p r a v i d e l u d e l a t jednim zlomenim j e d n o h o kousku c o k o l a d y predanych −− j a k o argument −− c u t s : : Cut −> [ Cut ] c u t s c = nub $ sortBy cmpCuts $ map n o r m a l i z e $ concat $ zipWith f [ 0 . . ( length c ) −1] ( repeat c ) where f n px = map ( \ x −> x ++ take n px ++ drop ( n+1) px ) ( b r e a k p i e c e ( px ! ! n ) ) −− −− p o r o v n a v a c i f u n k c e , k t e r a u r c u j e v jakem p o r a d i ma f u n k c e c u t s −− v r a c e t mozna r o z l o m e n i −− cmpCuts : : Cut −> Cut −> Ordering cmpCuts xs ys | s i n g l e E v e n S i d e xs = LT | s i n g l e E v e n S i d e ys = GT | otherwise = compare ( a r e a xs ) ( a r e a ys ) where a r e a = f o l d r ( \ (m, n , c ) a −> a+m∗n∗ c ) 0 −− −− f u n k c e v r a c e j i c i v s e c h n a mozna r o z l o m e n i j e d n o h o kousku c o k o l a d y − −− j s o u v y t v o r e n y v s e c h n y mozne v e r t i k a l n i i h o r i z o n t a l n i r o z l o m e n i , −− p r e v e d e n y do normalniho t v a r u , o d s t r a n e n y d u p l i c i t y a o d s t r a n e n y −− r o z l o m e n i s kouskem 1 x1 , p r o t o z e t a k o v e n e n i p o d l e p r a v i d e l l e g a l n i −− b r e a k p i e c e : : P i e c e −> [ Cut ] b r e a k p i e c e p = f i l t e r not1x1 $ nub $ map n o r m a l i z e $ ( breakpH p ) ++ ( breakpV p ) where not1x1 ( (m, n , c ) : xs ) = not (m == n && n == 1 ) not1x1 [ ] = True −− −− f u n k c e v r a c e j i c i v s e c h n a mozna r o z l o m e n i kousku ’ h o r i z o n t a l n e ’ −− breakpH : : P i e c e −> [ Cut ] breakpH (m, n , c ) = zipWith f [ 1 . . m‘ div ‘ 2 ] ( repeat (m, n , c ) ) where f x (m, n , c ) = [ ( x , n , 1 ) , (m−x , n , 1 ) ] ++ i f c > 1 then [ (m, n , c −1)] else [ ]
4
−− −− f u n k c e v r a c e j i c i v s e c h n a mozna r o z l o m e n i kousku ’ v e r t i k a l n e ’ −− breakpV : : P i e c e −> [ Cut ] breakpV (m, n , c ) = zipWith f [ 1 . . n ‘ div ‘ 2 ] ( repeat (m, n , c ) ) where f x (m, n , c ) = [ ( m, x , 1 ) , (m, n−x , 1 ) ] ++ i f c > 1 then [ (m, n , c −1)] else [ ] −− −− f u n k c e p r e v a d e j i c i rozlamanou c o k o l a d u do ” normalniho t v a r u ” , t z n . −− o t o c i v s e c h n y k o u s k y t ak , aby j e j i c h p r v n i rozmer b y l mensi nebo −− roven druhemu , s e r a d i j e p o d l e v e l i k o s t i , ’ s l o u c i ’ k o u s k y s t e j n e −− v e l i k o s t i a o d s t r a n i k o u s k y v e l i k o s t i 1 x2 a 1 x3 , p r o t o z e t y uz s e −− n e d a j i d a l e r o z l o m i t a tim padem j s o u pro nas n e z a j i m a v e −− n o r m a l i z e : : Cut −> Cut n o r m a l i z e = k i l l 1 2 1 3 . u n P i e c e s . s o r t P i e c e s . normPieces −− −− o t o c e n i −− normPieces normPieces normPieces
kousku : : Cut −> Cut [] = [] ( (m, n , c ) : ps ) = normal : ( normPieces ps ) where normal = i f m > n then ( n ,m, c ) e l s e (m, n , c )
−− −− s e r a z e n i kousku −− s o r t P i e c e s : : Cut −> Cut s o r t P i e c e s = sort −− −− s l o u c e n i kousku s t e j n e v e l i k o s t i −− u n P i e c e s : : Cut −> Cut unPieces [ ] = [] unPieces (p : [ ] ) = p:[] u n P i e c e s ( (m, n , c ) : ( m’ , n ’ , c ’ ) : ps ) = i f m == m’ && n == n ’ then u n P i e c e s ( (m, n , c+c ’ ) : ps ) e l s e (m, n , c ) : ( u n P i e c e s ( (m’ , n ’ , c ’ ) : ps ) ) −− −− o d s t r a n e n i kousku v e l i k o s t 1 x2 a 1 x3 −− k i l l 1 2 1 3 : : Cut −> Cut k i l l 1 2 1 3 ( (m, n , c ) : xs ) | m == 1 && n == 2 = k i l l 1 2 1 3 xs | m == 1 && n == 3 = xs k i l l 1 2 1 3 xs = xs
5
