Есть такой редкий малоизвестный язык программирования tcl. В википедии он расписан хорошо, но при написании программы возникнут вопросы.
Цзяньшицзы — это такая китайская(судя по названию) игра, переводится как «выбирание камней», интересна сама по себе: есть две кучки камней с любым количеством камней, играют двое. Каждый игрок может взять любое число камней из любой кучи, а также равное количество сразу из обоих. Побеждает тот, кто возьмет последний камень. Более подробное описание тут. Игра на сохранение баланса: с одной стороны, нужно чтобы числа в кучах различались, с другой, чтобы различие было не слишком большим. Начнем с того, что игра имеет выигрышную стратегию, происхождение которой мы рассматривать не будем. Возьмем лишь краткое описание. Существуют сочетания размеров куч, при которых игрок, который будет делать следующий ход, проигрывает.
Квадратные скобки обозначают взятие целой части. Нет, первая формула — это не числа Фибоначчи, хотя коэффициент тот же, но тут арифметическая прогрессия, а не геометрическая. Сразу заметим, что разница между числами пары составляет n.
Ранее на хабре были Реверси на TCL в 64 строки и Пятнашки на TCL в 10 строк, в которых был компактный и красивый код, здесь вы такого не увидите. Также он, возможно, далек от правил хорошего тона. Вобщем, если вам что-то покажется говнокодом, скорее всего так оно и есть. С другой стороны, это даже хорошо, потому что будет что улучшать в дальнейшем. Отчасти из-за того, что язык для меня новый, отчасти чтобы было удобнее делать пояснения. Также отсутствуют необязательные проверки.
Далее будут идти куски программы. Она далеко не оптимальна, но показывает особенности языка и работает.
Начало программы такое:
#---укажем, чем запускать программу
#!/usr/bin/tclsh
#---сделаем доступной префиксную(+ a b) запись математических формул
#---это не более, чем прихоть автора, инфиксная(a + b) запись ничем не хуже
namespace path {::tcl::mathop ::tcl::mathfunc}
#---некоторые полезные команды
proc lsum L {expr [join $L +]+0}
proc random range {expr int(rand()*$range)}
Код для получения проигрышных пар:
set n_max 20 ;#количество пар
for {set i 1} {[<= $i $n_max]} {incr i} {
set q [/ [+ [sqrt 5] 1 ] 2] ;#коэффициент "золотого сечения"
set a [int [* $q $i]] ;#i-е число a
set b [+ $a $i] ;#i-e число b
lappend lPair1 "$a $b" ;#добавим в список lPair1 пару a и b
}
Просмотреть список можно так:
puts lPair1;
#если вы привыкли ставить ; в конце, не страшно, точка с запятой аналогична переводу строки
Вот что получим на выходе:
{0 0} {1 2} {3 5} {4 7} {6 10} {8 13} {9 15} {11 18} {12 20} {14 23} {16 26} {17 28} {19 31} {21 34} {22 36} {24 39} {25 41} {27 44} {29 47} {30 49} {32 52}
Итак, у нас есть список пар, которыми следует отвечать на ход человека, необходимо научиться выбирать конкретную пару. Есть 3 варианта перехода в новое состояние:
- изменение одной кучи: 9 5 -> 4 5;
- изменение другой кучи: 9 5 -> 9 2;
- изменение сразу обоих: 9 5 -> 6 2.
Так как камни мы должны только брать, то сумма камней уменьшается с каждым ходом.
Перейдем к рассмотрению команды хода компьютера:
#---входящие параметры:
#----st - текущая пара,
#----lAns - список для выбора второго числа по числу камней в одной из куч
#----lPair - список для выбора пары по разности,
#--------------которая по счастливому совпадению равна номеру в этом списке
proc turn {st lAns lPair} {
set st_cur_sum [lsum $st] ;#текущая сумма пары
#---так как числа неотрицательные, когда сумма равна 0 оба слагаемых равны 0,
#---а это означает, что был взят последний камень
if {[== 0 st_cur_sum]} {return {you win}}
set a [lindex $st 0] ;# число камней в первой куче
set b [lindex $st 1] ;# число камней во второй куче
#---lindex - одна из важных команд работы со списком,
#---берет элемент с номером во втором параметре из списка в первом
set c [abs [- $a $b]]
#---согласно правилам, число камней не увеличивается
#---если новое значение больше текущего, то оно ограничивается текущим
set a1 [min $a [lindex $lAns $b]]
set b1 [min $b [lindex $lAns $a]]
set cPair1 [lindex $lPair $c]
#---заранее заготовим числа для случайного хода
set a2 [random $a]
set b2 [random $b]
set c2 [random [+ 1 [min $a $b]]]
set cPair2 [list [- $a $c2] [- $b $c2]]
set st_next1 [list "$a $b1" [+ $a $b1]]
set st_next2 [list "$a1 $b" [+ $a1 $b]]
set st_next3 [list "$cPair1" [lsum $cPair1]]
#---создаем список из вариантов
set lst_next [list $st_next1 $st_next2 $st_next3]
#---выбираем вариант с минимальной суммой
set st_next [lindex [lsort -integer -index 1 $lst_next] 0]
set st_next_sum [lindex $st_next 1]
if {[== 0 $st_next_sum]} {return {i won}} ;#после хода компьютера - нулевое состояние, мы победили
#---согласно правилам, число камней должно уменьшаться
#---а согласно алгоритму, разнонаправленное изменение чисел - невозможно,
#---что значит: если сумма уменьшилась, то уменьшилось либо одно из чисел, либо оба
#---если человек походил правильно, то состояние уже проигрышное
if {[> $st_cur_sum $st_next_sum]} {
return [lindex $st_next 0]
} else {
#---и чтобы не сдаваться сразу - делаем случайный ход
switch [random 3] {
0 {return "$a $b2"}
1 {return "$a2 $b"}
2 {return "$cPair2"}
}
}
}
Небольшое пояснение по поводу того, что из себя представляют lAns и lPair. Выигрышный ответный ход должен соответствовать одному из трех приведенных выше вариантов. Причем первые два отличаются только тем, из какой кучи брать. Рассмотрим первый вариант, берем из первой кучи, что означает, что вторая куча не меняется, и по количеству камней в ней можно определить желаемый размер первой, т.е. не сколько мы возьмем, а сколько оставим. Содержание lAns имеет вид:
0 2 1 5 7 3 10 4 13 15 6 18 20 8 23 9 26 28 11 31 12 34 36 14 39 41…
Индекс в списке — число камней в куче, которая не меняется, значение по этому индексу — новое число камней в куче, из которой будем брать камни.
Содержимое lPair не отличается от содержимого lPair1, приведенного выше. Значение по индексу представляет в данном случае новую пару количеств камней с разностью, равной индексу.
А вот как мы организуем диалог с пользователем:
puts {Enter heap sizes:}
#---читаем ввод, если есть что читать
if {[< 0 [gets stdin state]]} {
#---выбираем максимальный размер кучи
set n_max [lindex [lsort -integer $state] end]
#---генерируем списки для ответов
genAnsList $n_max lPair lAns
#---обновляем состояние системы
set state [turn $state $lAns $lPair]
#показываем новое состояние
puts $state
#---читаем ввод пока есть что читать
while {[< 0 [gets stdin state]]} {
set state [turn $state $lAns $lPair]
puts $state
}
}
Код целиком можно увидеть на pastebin.
Синтаксис языка есть по ссылке.
Работа со списками важна, соответствующие команды есть в документации.
P.S. В следующей части, если она будет, будут учтены конструктивные замечания в комментариях.
Автор: dtestyk
