На codingame.com с 20:00 27.06.15 на 24 часа запустился контест "Code of the Rings" на оптимизацию. Кому не жалко выходных и делать нечего, можете попробовать силы.

Суть примерно такова
Выйти из леса произнеся магическую фразу. В лесу есть 30 рун, изначальна на рунах пробелы. Руны можно вращать, на них появляются буквы в алфавитном порядке. Надо составить набор инструкций для Бильбо, произнести магическую фразу и выйти из леса

Формально примерно так
Написать программу генерирующий набор инструкций для Бильбо (этакая машина Тьюринга) для заданной фразы. Чем меньше инструкций, тем выше место, на данный момент рекорд 4817 инструкций

(0) а зачем это нам?

(1) Если не интересно, то можешь пройти мимо

+ Написать программу проходящий все тесты не так уж сложно. Вся фишка в оптимизации.

Кто то хочет оптимизировать подбор осмысленных паролей?

Написал первую версию почти без оптимизации, прошел все 24 претеста. Сейчас нахожусь на 621 месте из 1003 участников.

Пока первые 3 места занимают российские программисты. Рекорд 4029 команд, у меня же 13477 команд

Запилил видео, пятого претеста
http://screencast.com/t/dY8xHTntLyOx

(5) метаграммы юзаем?

http://manas71.ru/statya/metagrammy-ili-prevrashchenie-slov

(6) Они тут причем? Тут они совсем не нужны

(7) "произнеся магическую фразу" - фраза предполагает какую то "осмысленность" или хотя бы "произносимость"

а не бессмысленный набор символов

(8) Магическая фраза здесь изначальные данные. Что за фраза и какой не имеет никакого значения.
Вот например фраза
OROZOLOKOTONOFOGOMOJOHOFOTOLOPO ODOYOWOAOZO OPOJOTO OROXOVOXO OC

Тут главное написать так чтоб было минимальное количество переходов инструкций

+ Вернее, смысл фразы не имеет значения

(9)(10) тогда нифига не понял задачу

т.е. есть готовая фраза, есть набор действий для ее "написания" и нужно просто оптимально написать?

"хрень какая то"©

ЗЫ думал надо подбором узнать фразу

(11) Есть Бильбо - человечек на видео, он понимает инструкции
< идти налево
> идти направо
+ вращать руну в одну сторону
- вращать руну в другую сторону
. добавляет текущую букву на руне к фразе

на руне буквы в алфавитном порядке и пробел

(12) гы забыл главное добавить... тупой человечек не должен долго стоять под камнем и тыкать + камень опустится и прихлопнет

т.е. еще более тупой алгоритм в несколько проходов

(12)(13)+ так совсем ничего уже не понимаю... а ТЗ где нибудь есть с правилами?

(14) Поскольку требуется регистрация заскринил ТЗ

http://screencast.com/t/mPkzbl2kSsd
http://screencast.com/t/UBkApsn2Ay
http://screencast.com/t/68aMyQ0B
http://screencast.com/t/FrM1H4Hm

(15) угу терь вроде понял

вообщем либо крутим рулетку (путой камень) от начала(" ") в + или в - до нужного символа, либо идем к камешку где рулетка стоит поближе к нужному и меньше там крутим смотря скоко действий нуна

т.е. или крутим текущий или топаем до другого

+ Например магическая фраза "AZ"
Инструкция будет
"+.>-."
Изначально на всех рунах пробелы
1 "+" вращаем руну и получаем букву "А" на руне
2 "." добавляем букву "А" к фразе
3 ">" Идем на направо, там руне пробел
4 "-" Вращаем руну в обратную сторону получаем "Z"
5 "." добавляем букву "Z" к фразе

Получаем искомую фразу.

Как вариант можно набор "+.--."

(17) лучши скажи скоко там символов в алфавите?

(16) Да, плюс есть инструкции триггера "[" "]"
для фраз типа
MELLON MORIAMELLON MORIAMORIAMORIAMELLON MELLON MELLON MORIAMORIAMELLON MELLON MORIA

(18) Рун всего 30, а букв как и в английском алфавите 26 плюс пробел

(19) поподробнее про триггер?

"[" если руна с пробелом, все что в скобках пропускается
"]" если руна с пробелом, то триггер закрывается, иначе все что в скобках начинается заново

For example, AAAAAAAAAAAAAAAAAAAAAAAAAA (A x26) can be achieved with a simple
+.......................... as well as with +>-[<.>-].

Вся фишка в этих квадратных скобках. Пока еще не придумал как можно сделать

(21) хотя понял... алгоритм лучшего сжатия данных за счет минимума инструкций, причем можно не только повторять в цикле цепочки байт но и использовать старые

(23) про RLE почитай

+ (22) Кажется строка  "+>-[<.>-]." делает много лишних движений, но она короче "+.........................."

(2)Тут сжатие конечно поможет, но не сильно

Подумываю делать через деревья, но боюсь не уложусь по времени. Ограничение по времени 2 сек

Кстати прогать можно в любом ИДЕ, надо поставить расширение и прожку. Отлаживаю в Visual Studio, проверяю на сайте автоматом

(28) просто храни у себя текущее состояние рун

затем смотреть что выгоднее крутить рулетку или если где то есть цепочка готовая то сбегать туда и сделать циклу

вообщем классический архиватор так то нужно написать

нуна анализировать фразу, на повторы символов и подстрок, и в процессе анализировать текущий словарь на уже готовые или "почти готовые" построки

т.е. нужно ввести AAABA а у нас уже есть где то AAAAA то бежим туды, меням одну B на A и юзаем "слово"

(30)+ но они конечно хитро...е

там на готовый алгоритм который кто то наваяет и отправит права у кого?

(31) т.е. алгоритмы победителей это готовые алгоритмы сжатия для архиваторов

(32) Ну что ты заладил про архиваторы. Они тут не сильно помогут. Ну как архиватор сделает из "+.........................."
"+>-[<.>-]."  Тут принцип совершенно другой.

(33) как бы сделать минимальную последовательность простых операций на ленточном поле для вывода требуемого файла ))

т.е. распаковать такой сжатый файл может вообще любой КА, причем очень быстро

причем скорость распаковки будет очень высокая, и требующая минимум памяти

Сделал небольшую оптимизацию, получилось 11893 команд, но все равно опустился до 730 места. Наши продолжают лидировать

(33) и как бы какие принципы архивации(сжатия) данных то вообще знаем?

(36)+
3 основных это:
1. RLE,
2. словарное кодирование и
3. частотное кодирование

да мое в 14 строк пока на 940 месте и оно не проходит последний тест 24 long spell

тупо ошибка что не влазит ))

(38)+

static void Main(string[] args)
    {
        string magicPhrase = Console.ReadLine();
        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");
        int currentCode = 32;
        int lenPhrase = magicPhrase.Length;
        foreach (char symbol in magicPhrase){
            char rune = (char)currentCode;
            while (rune!=symbol){
                Console.Write("+");
                currentCode++;
                if (currentCode==33) currentCode = 65; else
                if (currentCode==31) currentCode = 90; else
                if (currentCode==91) currentCode = 32; else
                if (currentCode==64) currentCode = 32;
                rune = (char)currentCode;
            }
            Console.Write(".");
        }
        Console.WriteLine("");
    }

(39) совсем тупой алгоритм "на месте стою рулетку кручу"

(39) Начало положено )

(40) надо хотя бы крутить в разные стороны будет получеше или смещаться если так будет ближе от " "

(37) развивая алгоритмы

1. пример в (22) и (26)
2. если следующие символы уже есть в виде рун (причем неважно слева-направо или справа-налево) то проще их протыкать чем крутить рулетку
3. некоторые наиболее часто встречающиеся символы в магической фразе лучше хранить в виде готовых рун и тыкать с минимальными переходами

(43)+ вообщем совмещение 1 и 3 дает место в 1-й сотне легко