HyperSnakes
HackConf 2017: HyperScience Problem
Time Limit: 0.2s, Memory Limit: 64MiB
Независимо дали на компютър, Gameboy, или на старата си Nokia, най-вероятно всеки от вас все някога е попадал на играта Snake.

Замисляли ли сте се някога да напишете изкуствен интелект, който я играе? Тук ще имате тази възможност, като при това ще разгледаме малко по-разчупен вариант на играта, в който двама играчи играят на една и съща дъска с 20 реда и 20 колони, борейки се да изядат общо 25 ябълки.

Стандартните правила важат:
  • В началото на играта змиите са с дължина 1.
  • Изяждането на ябълка прави змията ви с един сегмент по-дълга.
  • Когато змия изяде ябълка, тя расте откъм главата си. По-конкретно, главата на змията застава върху ябълката, а досегашното ѝ тяло не помръдва.
  • Опит да се премине през поле, в което има част от змия (независимо дали вашата собствена или тази на противника) е невалиден ход и води до моментална загуба.
  • Стъпването върху полето, където вашата змия свършва, не е позволено (тоест първо се движи главата, а после остатъка от тялото).
  • Опит да се излезе извън дъската е невалиден ход и води до моментална загуба.

Добавени са и още няколко правила, за да се отчете втория играч:
  • Всички ябълки са разположени на дъската (и достъпни за изяждане) още в началото на играта.
  • Играта е походова: в първия ход се движи змията на единия играч, във втория - тази на другия, в третия - отново тази на първия и т.н.
  • След изяждането на последната ябълка играта свършва, като печели играчът, чиято змия е по-дълга.
  • Ако 40 хода никоя от змиите не изяде ябълка, играта свършва и печели по-дългата от тях. Ако са с равна дължина, печели тази, която последна е изяла ябълка. Ако никоя от змиите не е изяла ябълка, печели първият играч.

Всеки двама противници играят един срещу друг при пет различни начални разположения на ябълките. За да е честно, всяко разположение на ябълките се играе по два пъти - веднъж вие като първи играч и веднъж противникът ви като първи играч, разменяйки си и стартовата позиция.

Пресрочването на допустимото време (0.2 секунди на ход), crash на програмата ви, опит за fork, ползване на мрежата, или печатането на каквото и да е друго, освен описаното в секцията "Изход", се счита за невалиден ход и води до моментална загуба.
Вход
За всеки ход вашата програма ще бъде извикана по веднъж. На стандартния вход (stdin) ще бъдат зададени 20 реда, всеки съдържащ по 20 символа. Символ '.' обозначава празно поле. Символ '@' обозначава ябълка. Главна буква от английската азбука ('A'-'Z') обозначава част от вашата змия, като буквата 'A' е главата ѝ, 'B' е частта от тялото точно след главата ѝ, и така нататък. Малка буква от английската азбука ('a'-'z') обозначава част от змията на противника ви, описана по сходен начин. На първия ход на дъската ще има 25 ябълки. Забележете, че с напредването на играта ще има все по-малко и по-малко ябълки на дадената дъска.
Изход
На стандартния изход (stdout) изведете посоката, в която искате главата на змията ви да се премести на текущия ход: "Up" за нагоре, "Down" за надолу, "Left" за наляво, или "Right" за надясно.
Примерен Вход Примерен Изход
...................@ .................... ..........@......... .................... ......CBA........... ......D............. ..IHGFE............. .................... .................... ...........@........ ..................@. .................... @................... ......bc............ ......ad............ .......efghijkl..... .................... ....@............... .................... .................... Up
Вашата змия в момента има дължина 9 (изяла е 8 ябълки), докато тази на противника ви има дължина 12 (изяла е 11 ябълки). Главата на змията ви се намира на ред 5 и колона 9 (индексирано от едно). Един възможен вариант е да тръгнете към най-близката ябълка на ред 3, колона 11 отивайки нагоре. Така главата на змията ви ще се премести от ред 5 на ред 4 (в колона 9), а краят на опашката ви в ред 7, колона 3 ще изчезне.
Мрън!