прикреплённый файл:stones.py к странице LecturesVMSH/2011-04-20

   1 #!/usr/bin/python
   2 # coding: utf8
   3 '''
   4 Имеется задача на исследование стратегии (из пробного варианта ЕГЭ по информатике и ИКТ):
   5 
   6     Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает.
   7         Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. 
   8     Написать программу, на вход которой подаётся 5 параметров: начальное количество камней в кучках, множитель, приращение и рубежное количество камней (для приведённой выше задачи: 3, 4, 2, 4, 25), после чего программа либо успешно играет в игру (на каждом ходе вводится номер кучки и номер действия, выводится состояние кучек)
   9     Вариант: кучек произвольное количество, типов ходов также произвольное количество, условие конца игры и определения победителя задаются отдельно.
  10 
  11 формализация ввода для задачи 2.2
  12 
  13  - Количество камней в кучках хранится в списке H (индекс — номер кучки, начиная с 1)
  14    - Начальное значение задаётся списком через запятую в первой строке ввода 
  15  - Каждый тип хода описывается отдельной строкой как модификация H правилами вида индекс:преобразование
  16    - Если правила параметрические, в формулах можно использовать переменные I,J,K,L,M,N 
  17    - Если за один ход изменяются несколько кучек, правила записываются в виде I,J,...:формула1,формула2,...
  18  - Условие конца игры и определение победителя задаются в виде двух формул, разделённых символом ';', игроки имеют номера 1 и 2; номер игрока, сделавшего завершающий ход, хранится в переменной P, его соперника -- в Q. В конце этой строки стоит точка.
  19  - Далее пользователь вводит номер правила и параметры (целые числа в виде списка через запятую), а программа выводит результат хода, свой ход и результат своего хода, либо объявляет победителя 
  20 
  21 Пример: задача 2.1:
  22  Условия:
  23     3, 4
  24     I:H[I]*2
  25     I:H[I]+4
  26     H[0]+H[1]>25; Q.
  27 
  28 Пример: дополнительное правило: игрок может переложить из любой кучки в любую произвольное число камней
  29     3, 4
  30     I:H[I]*2
  31     I:H[I]+4
  32     I,J:H[I]-K,H[J]+K
  33     H[0]+H[1]>25; Q.
  34 '''
  35 import pickle, os
  36 
  37 def genall(Len, Range):
  38     if Len<1: yield ()
  39     else:
  40         for i in xrange(Range):
  41             for o in genall(Len-1, Range):
  42                 yield (i,)+o
  43 
  44 def calc(Hb, rule):
  45     H=Hb[:]
  46     l,r=rule
  47     for n,v in zip(eval(l+','),eval(r+',')):
  48         H[n]=v
  49         if H[n]<0: return 0,Hb
  50     if eval(Fin):
  51         return 1,H
  52     else:
  53         return -1,H
  54 
  55 H=list(input('Initial heaps (H0, H1, ... ): '))
  56 Rules=[]
  57 while True:
  58     rule=raw_input('Rule (Use I,J,K,L,M,N or A[] as index of H[]): ')
  59     if rule.endswith('.'):
  60         Fin,Win=rule[:-1].split(';')
  61         break
  62     l,r=rule.split(':')
  63     Rules.append((l.strip(),r.strip()))
  64 
  65 Data=hex(hash(str((Rules,Fin,Win,H))))
  66 if os.path.isfile(Data):
  67     FData=file(Data,"r")
  68     (Cache,Start)=pickle.load(FData)
  69 else:
  70     # NB: рассматриваются только случаи, в которых IJKLMN -- это номера кучек
  71     P,Q=1,2
  72     Start=[H[:],[],0,0]   # Позиция, следующие ходы, победитель, конец игры
  73     ToLook=[Start]        # Список непроверенных ходов
  74     Cache={(P,)+tuple(Start[0]):Start}
  75     while ToLook:
  76         NewLook=[]
  77         for Pos in ToLook:
  78             for n in xrange(len(Rules)):    # Применяем каждое правило
  79                 l,r=Rules[n]
  80                 for ind in genall(len(l),len(H)):   # Все наборы параметров
  81                     I,J,K,L,M,N=(ind+(0,)*5)[:6]
  82                     res, Hn = calc(Pos[0], Rules[n])
  83                     if res==0: continue     # Недопустимый ход
  84                     else:
  85                         key=(Q,)+tuple(Hn)
  86                         if Cache.has_key(key):  # Известный ход
  87                             Pos[1].append(Cache[key])
  88                         else:
  89                             PosN=Cache.setdefault(key,[Hn[:],[],0,0])
  90                             Pos[1].append(PosN)
  91                             if res==1:          # Конец игры
  92                                 PosN[2]=PosN[3]=eval(Win)
  93                             else:               # Проверить этот ход
  94                                 NewLook.append(PosN)
  95         ToLook=NewLook
  96         P,Q=Q,P
  97 
  98     # Обратное распространение выигрыша
  99     def prognose(P,Pos):
 100         if Pos[2]: return Pos[2]
 101         Ret=P
 102         for PosNext in Pos[1]:
 103             if prognose(3-P,PosNext) == 3-P:
 104                 Ret=3-P
 105         Pos[2]=Ret
 106         return Ret
 107 
 108     prognose(P,Start)
 109     FData=file(Data,"w")
 110     pickle.dump((Cache,Start),FData)
 111 FData.close()
 112 
 113 Me,P,Q=1,1,2
 114 Pos=Start
 115 print ""
 116 while True:
 117     if P==Me:
 118         print Cache[(P,)+tuple(H)][2],H
 119         for Ps in Pos[1]:
 120             if Ps[2] == Me:
 121                 Pos=Ps
 122                 break
 123         else:
 124             Pos=Pos[1][0]
 125         H=Pos[0]
 126         if Pos[3]:
 127             W=eval(Win)
 128             break
 129     else:
 130         for i in xrange(len(Rules)):
 131             print "{0}: {1}".format(i,Rules[i])
 132         print Cache[(P,)+tuple(H)][2],H
 133         i,I,J,K,L,M,N=(input("{0}: Rule number [, par1 [,par2 ...]]: ".format(P))+(0,)*6)[:7]
 134         res, Hn = calc(H, Rules[i])
 135         if not res:
 136             print "Illegal move"
 137             continue
 138         else:
 139             H=Hn
 140             if res>0:
 141                 W=eval(Win)
 142                 break
 143         Pos=Cache[(Q,)+tuple(Hn)]
 144     P,Q=Q,P
 145 print Cache[(P,)+tuple(H)][2],H
 146 print W