Внимание! Соревнование окончено! Огромное спасибо всем тем, кто принял в нем участие)
Вы можете ознакомиться с результатами и различными алгоритмами решения поставленно
задачи ниже, а если вдруг у Вас возникнет хорошая идея реализации всего этого дела
не стесняйтесь и публикуйте, ведь пусть конкурс уже и закрыт, идеи, предложенные здесь, возможно, впоследствии порадуют одинокого странника ruSO, изучающего вопросы по меткам code-golf и соревнование)
Товарищи!
Давненько не проходило у нас никаких соревнований, так что стоит исправить сие досадное упущение)
Думаю, каждый из нас хоть немного знаком с эзотерическим языком Brainfuck и его
буквальном смысле мозговыносящим синтаксисом. Обычное Hello world выглядит страшнее и сложнее ПО для Аполлона 11...
А почему бы не автоматизировать процесс создания кода на Brainfuck для вывода нужных нам строк? Таки вопрос риторический, ибо этим мы и займемся)
Задача:
Требуется описать на любом языке программирования функцию, которая в качестве аргумент
принимает строку, а на выход дает код на языке Brainfuck (также в виде строки), позволяющий распечатать входную строку
Подробнее:
Как Вы понимаете, функцию необходимо максимально ужать. Однако это еще не все: роль также будет играть длина выходного кода, так что решение "в лоб" не подойдет)
Вам необходимо будет протестировать свой код на следующих двух строках:
s1 = "Hello world"
s2 = "Goodbye Brainfuck"
Правила:
При решении задачи можно использовать любой язык программирования
Можно оставлять несколько вариантов ответа (в разных постах)
Запрещено использовать какие-либо сторонние библиотеки для решения поставленной задачи, если они не являются частью
используемого языка/платформы
Запрещено внутри реализуемой функции использовать строки s1 и s2 в явном или зашифрованном виде
Желательно оставлять ссылку на онлайн-компилятор Вашего кода
В ответе приводите как минифицированную версию Вашей функции, так и
"развернутую" (пояснения приветствуются), чтобы каждый мог
разобраться в магии Вашего кода и, возможно, почерпнуть что-то для
себя
Сгенерированный код на Brainfuck должен быть рабочим и выводить
строки s1 и s2 (проверить код можно, скажем, тут или тут)
Обязательным условием является наличие у Вашего ответа заголовка в
формате Язык, Кол-воСимволов
(требуется для парсера
таблицы лидеров)
Рассчет символов определяется следующей формулой:N = func.Length + Ceil(1.5 * (B(s1).Length + B(s2).Length))
N - число символов, которое необходимо указать в ответе
func.Length - длина Вашей минифицированной функции (следует учитывать только длину тела функции)
B(s1).Length - длина выходного кода для строки s1
B(s2).Length - длина выходного кода для строки s2
Ceil - функция округления к ближайшему целому, которое больше заданного значени
(Ceil(2.5) == 3)
Продолжительность соревнования: 7 дней
Определение победителей:
Победители определяются по следующей градации:
Реализация с наименьшим числом символов
Реализация с наивысшим активным рейтингом (общее число плюсов -
общее число минусов)
Реализация с самой ранней первой редакцией
P.S. - работа автора поста не принимает участия в подведении итогов
Если возникнут вопросы по правилам проведения конкурса - задавайте их в комментариях)
Удачи в реализации, товарищи!
Итоги:
1 место: @Groxan - c#, ответ занял 745(!) символов
2 место: @b1nary - python, ответ занял 827 символов
3 место: @rjhdby - php, ответ занял 834 символа
Собственно, хотелось бы сказать пару слов о прошедшем соревновании)
Еще раз огромное спасибо каждому, кто принял участие в сием мероприятии, ведь, думаю, каждый из нас смог почерпнуть из идей других участников что-то новое и интересное!
Было очень интересно разбирать код, его ужатый вид, а также и логику во всех ответах, каждый из которых по-своему элегантен и интересен)
И отдельно, конечно, хочется сказать про работу @Groxan, которая заняла всего 74
символов! Честно, когда я предложил данный эвент, я даже не предполагал, что хоть одн
реализация преодолеет барьер в 800 символов. Но это таки случилось. Работа победителя нашего соревнования проделала уверенный путь от 912 символов к победным и действительно удивительным 745 символам!
Почему "удивительным"? Предложенный алгоритм смог посоревноваться не только с участниками данного код-гольфа, но и с решением, приведённым на Wikipedia (111 символов):
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
Сгенерировав код для строки Hello World! (отличается от конкурсной строки s1) алгоритмом из ответа-победителя, мы получим ровно те же 111 символов:
-[------->+<]>-.-[->+++++<]>++.+++++++..+++.+[->--<]>.---[->+++<]>.+[--->--<]>-.+++.------.--------.-[--->+<]>.
Удивительное совпадение)
Очень радует, что наше соревнование и совместные усилия участников смогли создать такой вот замечательный алгоритм!
Так что еще раз отдельное спасибо каждому участнику! До новых соревнований!
Таблица лидеров:
execute(849931);
.cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23p
84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:cente
49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fol
11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1an
11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50
0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3an
11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100
50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:
50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg
rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg
rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0
rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframe
s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframe
s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframe
s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframe
s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframe
s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframe
half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}.cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23p
84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:cente
49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fol
11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50% 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100% 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:0 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}body{font-size: 1rem;line-height: 1.5rem;font-family: 'Open Sans', sans-serif;background: #fff;padding: 0 2rem;}h1{font-weight: 600;margin-bottom: 3rem;text-align: center;color: #212121;}#leadership{width: 100%;margin: 1rem auto;border-collapse: collapse;box-shadow: 0 2px 7px rgba(0,0,0,0.2);background: #fafafa;}#leadership td{padding: 1rem .5rem !important;text-align: left;font-weight: 500;transition: all .3s ease-in-out;}#leadership tr:hover td{background: #03a9f4;color: #fefefe;}#leadership tr:hover td a{color: #fff;}#leadership th{padding: 1.5rem .5rem !important;color: #727272;text-align: left !important;font-weight: 500;border-bottom: 1px solid #dcdcdc;}#leadership a{text-decoration: none;color: #212121;}#leadership a:hover{color: #03a9f4;}#leadership td:nth-of-type(1){text-align: center;color: #727272;font-size: .75rem;}#leadership td:nth-of-type(2){}#leadership td:nth-of-type(2) img{width: 34px;border-radius: 50%;}#leadership th:nth-of-type(5),#leadership th:nth-of-type(6),#leadership th:nth-of-type(7),#leadership td:nth-of-type(5),#leadership td:nth-of-type(6),#leadership td:nth-of-type(7) {text-align: center !important;}
Ответы
Ответ 1
C#, 745
Функция (334 символа):
string w(int k)=>new string(k>0?'+':'-',k>0?k:-k);
int c(int a,int b,int f=0)=>f>255|a%256==0?f:c(a+b,b,++f);
string m(char p,char x){var o=w(x-p);for(int d,n,s=-9;++s<9;)for(d=-9;++d<9;)for(n=-9;++n<9;){var t=w(s)+$"[{w(d)}>{w(n)}<]>"+w(x-c(p+s,d)*n%256);o=t.Length+<]>-.-[->+++++<]>++.+++++++..+++.+[->--<]>.--[->++++<]>-.--------.+++.------.--------.
Goodbye Brainfuck (177 символов):
-[------->+<]>--.+[->--<]>-..-----------.--.[->----<]>+.--[->+++<]>.--[--->+<]>-.+[->++<]>.[----->---<]>.--[--->--<]>+.++++++++.+++++.--------.-[--->+<]>--.+[->+++<]>+.++++++++.
Чё происходит вообще?
string Brainfuck(string text)
{
//Трансформируем текст в массив разностей и подбираем кротчайший код для каждой
return string.Concat($"\0{text}".Zip(text, FindBestCode));
}
string FindBestCode(char state, char target)
{
//Сперва генерируем тупой код
var code = Fill(target - state);
//Потом пытаемся подобрать цикл вида 's[d>n<]>r.' так, чтобы он был как можно короче
//Достаточно перебирать только три параметра, а четвертый вычислять на ходу
//Вообще, чем шире диапазон перебора, тем лучше точность поиска
for (int d, n, s = -9; ++s < 9;)
for (d = -9; ++d < 9;)
for (n = -9; ++n < 9;)
{
//Формируем цикл, попутно вычисляя 'r'
var cycle = Fill(s)+$"[{Fill(d)}>{Fill(n)}<]>"+Fill(target - (IterationsCnt(state + s, d) * n + 256 * 10) % 256);
//Если он короче, то запоминаем
code = cycle.Length < code.Length ? cycle : code;
}
return code + ".";
}
int IterationsCnt(int state, int step, int cnt = 0)
{
//Определяем количество итераций в цикле с шагом 'step', который стартует из 'state'
//Т.к. цикл может быть бесконечным, добавляем ограничение в 256 итераций
return cnt > 255 | state % 256 == 0 ? cnt : IterationsCnt(state + step, step, ++cnt);
}
string Fill(int cnt)
{
//Спамим '+' или '-' в зависимости от знака
return new string(cnt > 0 ? '+' : '-', cnt > 0 ? cnt : -cnt);
}
Ответ 2
Brainfuck, 4277
Конечно же в подобных заданиях веселья ради должен найтись идиот сумасшедший, который напишет код на самом Brainfuck
Итак, сама функция (74 символа):
++++++[>+++++++<-]>+>++++++++[>++++++++<-]>-->,[[<<<.>>>-]<<<+++.--->>.>,]
Код для s1 (1106 символов):
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
Код для s2 (1696 символов):
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
Функция в более читаемом виде:
++++++[>+++++++<-]>+ // Записываем код для знака плюс
>
++++++++[>++++++++<-]>-- // Записываем код для знака перехода в следующую ячейку
>
, // Считываем символ
[ // Запускаем цикл зпт который будет идти до символа '\0'
[<<<.>>>-] // Печатаем число плюсов зпт необходимое для печати символа
<<<
+++.--- // Увеличиваем код ячейки плюса до точки зпт печатаем и возвращаем
>>.> // Печатаем символ перехода в следующую ячейку
, // Читаем следующий символ
]
Логика алгоритма:
Собственно, думаю, логика ясна из пояснений к коду: мы читаем нуль-терминированну
строку, для каждого символа выводим кол-во знаков +, равное его ASCII-коду, а также символы . (для печати) и > (для перехода в следующую ячейку)
Алгоритм совершенно не оптимален (видно из числа символов хД), зато функция короткая да и написана на языке-герое сего мероприятия)
Ответ 3
С#, 1436
Собственно, сама функция (146 символов):
string s(int i)=>new string('+',i);return string.Join("",t.Select(x=>{int a = (int)Math.Sqrt(x);return$"{s(a)}[>{s(x/a)}<-]>{s(x-a*(x/a))}.>";}));
Код для s1 (342 символа):
++++++++[>+++++++++<-]>.>++++++++++[>++++++++++<-]>+.>++++++++++[>++++++++++<-]>++++++++.>++++++++++[>++++++++++<-]>++++++++.>++++++++++[>+++++++++++<-]>+.>+++++[>++++++<-]>++.>++++++++++[>+++++++++++<-]>+++++++++.>++++++++++[>+++++++++++<-]>+.>++++++++++[>+++++++++++<-]>++++.>++++++++++[>++++++++++<-]>++++++++.>++++++++++[>++++++++++<-]>.>
Код для s2 (518 символов):
++++++++[>++++++++<-]>+++++++.>++++++++++[>+++++++++++<-]>+.>++++++++++[>+++++++++++<-]>+.>++++++++++[>++++++++++<-]>.>+++++++++[>++++++++++<-]>++++++++.>+++++++++++[>+++++++++++<-]>.>++++++++++[>++++++++++<-]>+.>+++++[>++++++<-]>++.>++++++++[>++++++++<-]>++.>++++++++++[>+++++++++++<-]>++++.>+++++++++[>++++++++++<-]>+++++++.>++++++++++[>++++++++++<-]>+++++.>++++++++++[>+++++++++++<-]>.>++++++++++[>++++++++++<-]>++.>++++++++++[>+++++++++++<-]>+++++++.>+++++++++[>+++++++++++<-]>.>++++++++++[>++++++++++<-]>+++++++.>
Функция в более читаемом виде:
string s(int i) => new string('+', i);
return string.Join("", t.Select(x => {
int a = (int)Math.Sqrt(x);
return $"{s(a)}[>{s(x/a)}<-]>{s(x-a*(x/a))}.>";
}));
Логика алгоритма:
Для каждого символа я генерирую цикл на Brainfuck, который идет sqrt(x) итераций
каждый раз инкрементируя текущую клетку на x/sqrt(x). Так как цикл идет целое число итераций, то после него я инкрементирую текущую ячейку еще на x-(x/sqrt(x))*sqrt(x), тем самым добирая остаток и получая ASCII-код нужного мне символа
Посмотреть работу функции можно тут (пришлось изменить код, так как online-компиляторы пока не поддерживают новейшие версии C#)
Ответ 4
PHP, 834
PHP код (тело 208 символа):
sandbox
for(;$c=ord($s[$i++]);$l=$c){$x=$l<=>$c;$o.=(($r=($t=abs($l-$c))>16?(int)sqrt($t):0)?'>'.str_pad('',$r+1,'+').'[<'.str_pad('',$r,'+ -'[$x+1]).'>-]<':'').str_pad('',abs($t-=$r*$r++),'+ -'[$x*($t<=>0)+1]).'.';}
Читабельно(ну...так.)
function f ($s, &$o) {
// Перебираем посимвольно. $l - предыдущий ascii код, $c - текущий
for (; $c = ord($s[$i++]); $l = $c) {
// Направление движения, + или -
$x = $l <=> $c;
// Адский ад
$o .= ((
// Вычисляем длину цикла и хвоста
$r = ($t = abs($l - $c)) > 16
? (int)sqrt($t)
: 0
)
// Если цикл не нулевой, то отрисовываем его в нужном направлении
? '>' . str_pad('', $r+1, '+') . '[<' . str_pad('', $r, '+ -'[$x + 1]) . '>-]<'
: ''
// Отрисовываем хвост в нужном направлении
) . str_pad('', abs($t -= $r * $r++), '+ -'[$x * ($t <=> 0) + 1]) . '.';
}
}
Hello world (149 символа):
>+++++++++[<++++++++>-]<.>++++++[<+++++>-]<-.+++++++..+++.>+++++++++[<-------->-]<-------.>++++++++++[<+++++++++>-]<---.--------.+++.------.--------.
Goodby Brainfuck (268 символа):
>+++++++++[<++++++++>-]<-.>+++++++[<++++++>-]<--..-----------.--.>+++++[<++++>-]<+++.>+++++[<---->-]<.>+++++++++[<-------->-]<+++.>++++++[<+++++>-]<++++.>+++++++[<++++++>-]<++++++.>+++++[<---->-]<+++.++++++++.+++++.--------.+++++++++++++++.>+++++[<---->-]<++.++++++++.
Ответ 5
Python, 827
Минифицированный исходник (189 символов)
l=0
g="+-"
def f(c):global l;c,l=c-l,c;d=abs(c);z=round(d**.5);D=d-z*z;a='>'+z*'+'+'[<'+z*g[c<0]+'>-]<'+abs(D)*g[D*c<0];d*=g[c<0];return(a,d)[len(a)>len(d)]+'.'
s=''.join(map(f,map(ord,s)))
Hello world (156 символов).
>++++++++[<++++++++>-]<++++++++.>+++++[<+++++>-]<++++.+++++++..+++.>+++++++++[<--------->-]<++.>+++++++++[<+++++++++>-]<++++++.--------.+++.------.--------.
Goodbye Brainfuck (269 символов).
>++++++++[<++++++++>-]<+++++++.>++++++[<++++++>-]<++++..-----------.--.>+++++[<+++++>-]<--.>++++[<---->-]<----.>++++++++[<-------->-]<-----.>++++++[<++++++>-]<--.>+++++++[<+++++++>-]<-.>++++[<---->-]<-.++++++++.+++++.--------.+++++++++++++++.>++++[<---->-]<--.++++++++.
Итого
189 + 1.5 * (156 + 269) ≈ 827
Что тут происходит?
Опредлим входную строку как переменную s.
s = "Hello world"
Заметим, что символ для знака числа N можно получить из g[N<0].
g = "+-"
Предусмотрим lookback на один символ в переменной l.
l = 0
Итак, определим ƒ от c (кода символа).
def f(c):
global l
Далее c — разность старого и нового значением, а d — расстояние.
c, l = c - l, c
d = abs(c)
Пусть z — квадратный корень из расстояния d, округленный до ближайшего целого значения.
z = round(d**.5)
Строим цикл вида >z_iterations[-]<, который прибавляет или вычитает (в зависимости от знака c) квадрат числа z в ячейке памяти.
a = '>' + z*'+' + '[<' + z*g[c < 0] + '>-]<'
Найдем длина хвоста цикла, т.е. разность D между расстоянием d и квадратом z — ровно столько нужно сделать операций "+" или "-" после исполнения цикла.
D = d - z*z
Доводим значение в ячейке до желаемого.
a += abs(D) * g[D*c < 0]
Однако, вариант без цикла может быть короче.
d *= g[c < 0]
return (a, d)[len(a) > len(d)] + '.'
Применим ƒ для последовательности кодов символов строки s и склеим возвращенные значения в одну строку.
s = ''.join(map(f, map(ord, s)))
Осталось сделать только...
print(s, end='')
Ответ 6
С#, 1194
В качестве первого приближения.
Функция (103 символа):
string GetBfSrc(string s)
{
return string.Concat(s.Select((c,i)=>new string("-+"[c>('\0'+s)[i]?1:0],Math.Abs(c-('\0'+s)[i]))+"."));
}
Hello world (313 символов):
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.--------.+++.------.--------.
Goodbye Brainfuck (414 символов):
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++..-----------.--.+++++++++++++++++++++++.--------------------.---------------------------------------------------------------------.++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++.-----------------.++++++++.+++++.--------.+++++++++++++++.------------------.++++++++.
Ответ 7
C, 898
Минифицированный (238)
#define A*(K++)=
int O[999],*K=O,p=0;F(n,c){while(n--)A c;}M(a){if(a<0)F(-a,45);else F(a,43);}P(c){in
d=c-p;if(d*d<225)M(d);else{A'>';M(8);A'[';A'<';M(d/8);A'>';A'-';A']';A'<';M(d%8);}A'.';p=c;}*B(int*s){while(*s)P(*(s++));A 0;return O;}
Hello world (156)
>++++++++[<+++++++++>-]<.>++++++++[<+++>-]<+++++.+++++++..+++.>++++++++[<--------->-]<-------.>++++++++[<++++++++++>-]<+++++++.--------.+++.------.--------.
Goodbye Brainfuck (284)
>++++++++[<++++++++>-]<+++++++.>++++++++[<+++++>-]<..-----------.--.>++++++++[<++>-]<+++++++.>++++++++[<-->-]<----.>++++++++[<-------->-]<-----.>++++++++[<++++>-]<++.>++++++++[<++++++>-]<.>++++++++[<-->-]<-.++++++++.+++++.--------.>++++++++[<+>-]<+++++++.>++++++++[<-->-]<--.++++++++.
Код с пояснениями
int codeOutput[999], *codeEnd = codeOutput, p = 0;
int repeatChar(int n, int c) {
while(n--) *(codeEnd++) = c; // Пишет n раз символ c
}
int modifyValue(int a) { //Пишет код, изменяющий значение в текущей ячейке
if(a < 0) {
repeatChar(-a, '-');
} else {
repeatChar(a, '+');
}
}
int proceedChar(int c) { //Обработать символ исходной строки
int d = c;
d -= p; //Разность с предыдущим значением в ячейке
if(d*d < 225) { //Если abs(d) < 15
modifyValue(d); //Тогда предполагается, что выгоднее менять значение без цикла
} else {
*(codeEnd++) = '>'; //Запись в bf код сдвига ячейки
modifyValue(8); //Счётчик цикла. разность d преобразуется в 8 * a + b
*(codeEnd++) = '[';
*(codeEnd++) = '<';
modifyValue(d / 8); //В цикле прибавляем (вычитаем) целую часть от деления
*(codeEnd++) = '>';
*(codeEnd++) = '-';
*(codeEnd++) = ']';
*(codeEnd++) = '<';
modifyValue(d % 8); //Прибавляем остаток
}
*(codeEnd++) = '.';
p = c; //Запоминаем текущее значение в ячейке
return 0;
}
int *B(int *s) { //Главная функция
while(*s != '\0') {
proceedChar(*(s++));
}
*(codeEnd++) = '\0';
return codeOutput;
}
#include
int main(void) {
printf("%ls", B(L"Hello world"));
}
Ответ 8
JS, 1067
Тело функции (446 символов):
var u=n=>Math.round(n);var p=n=>n>0?n:-n;var g=c=>(c>0?"+":"-").repeat(p(c));va
d=c=>c.charCodeAt(0);var r=f=>(f?">":"<").repeat(l+2);var h=[0,0];var l=0;s=s.split("");s.forEach((e,i,a)=>{va
j="";var k=d(e);var m=p(k-h[1])l?">":"<";l=m;}var o=k-h[m];var y=u(Math.sqrt(p(o)));var z=u(o/y);var q=g(o);var t=r(1)+g(y)+"["+r()+g(z)+r(1)+"-]"+r()+g(o-y*z);a[i]=j+(t.length>-]<<.>>+++++[<<++++++>>-]<<-.+++++++..+++.>>>>++++++[<<<+++++>>>-]<<<++.<++++++++.--------.+++.------.--------.
Код для s2 (279 символов):
++++++++[<<+++++++++>>-]<<-.>>++++++[<<+++++++>>-]<<--..-----------.--.+++++++++++++++++++++++.--------------------.>>>>++++++[<<<+++++>>>-]<<<++.>>>++++++[<<<++++++>>>-]<<<--.<+++++++++++++.-----------------.++++++++.+++++.--------.+++++++++++++++.------------------.++++++++.
Функция в развернутом виде:
function Brainfuck(s) {
// Генерация последовательности из '+' или '-'
var gen = count => (count > 0 ? "+" : "-").repeat(Math.abs(count));
// Получение кода символа
var code = c => c.charCodeAt(0);
// Получение пути к ячейке, хранящей счетчик цикла
var getCell = forward => (forward ? ">" : "<").repeat(currentCell + state.length);
// Состояние двух используемых для печати ячеек
var state = [0, 0];
// Текущая ячейка
var currentCell = 0;
// Массив символов
var chars = s.split("");
// Обрабатываем все символы
chars.forEach((element, index, arr) => {
var answer = "";
var now = code(element);
// Выбираем наиболее выгодную ячейку и рассчитываем необходимые изменения ячейки
var cell = 0;
var need = Math.abs(now - state[0]);
for (var i = 1; i < state.length; i++) {
var newNeed = Math.abs(now - state[i]);
if (newNeed < need) {
need = newNeed;
cell = i;
}
}
need = now - state[cell];
// Сдвигаемся, если выгодная ячейка отличается от текущей
if (cell != currentCell) {
answer += (cell > currentCell ? ">" : "<").repeat(Math.abs(cell - currentCell));
currentCell = cell;
}
// Генерируем последовательность из '+' или '-' без всяких циклов
var genned = gen(need);
var a = Math.round(Math.sqrt(Math.abs(need)));
var b = Math.round(need / a);
// Генерируем равнозначную по выполнению genned команду, но с циклом
var test = getCell(true) + gen(a) + "[" + getCell(false) + gen(b) + getCell(true) + "-]" + getCell(false) + gen(need - a*b);
// Выбираем самое короткое решение
genned = test.length < genned.length ? test : genned;
answer += genned;
// Добавляем символ печати и обновляем текущий элемент массива
arr[index] = answer + ".";
// Изменяем состояние текущей ячейки
state[cell] = now;
});
// Возвращаем объединенный массив
return chars.join("");
}
console.log(Brainfuck("Hello world"));
console.log();
console.log(Brainfuck("Goodbye Brainfuck"));
Идея:
Мы используем 3 ячейки памяти, отводя первые 2 для хранения кода символов, а последню
- для счетчика цикла Brainfuck. Тем самым на каждом шаге мы выбираем ту ячейку, которая должна претерпеть минимальные изменения для получения кода текущего символа.
В теории, с ростом числа используемых ячеек (до некого абстрактного максимума, которы
необходимо подобрать эмпирически) на больших текстах можно получить хороший выигры
по длине генерируемого кода. Расширить число ячеек в принципе просто, так что если кто захочет с этим поиграться - прошу (достаточно просто увеличить число элементов в массиве state))
P.S. - минифицированная функция немного отличается от развернутой, так как в минифицированной я ориентируюсь на ровно 2 ячейки (что является оптимальным решением для указанных строк)
Ответ 9
JavaScript 6, 1216
Минифицированная: 613
(()=>{var c,v,f,e,h;B=(n)=>{var r,t,u,i,o,f="",e=0,a=[0];for(r in n=c(n))o=(t=n[r])-a[e],u=[v(o,e),v(o+256,e),v(o-256,e),">"+v(t,e+1),">"+v(t-256,e+1)],2<(i=h(u))&&e++,a[e]=t,f+=u[i]+".";retur
f},c=(n)=>{var r;for(r in n=n.split(""))n[r]=n[r].charCodeAt(0);return n},v=(n,r)=>{if(29999"+v(n/t|0,r+1)+"[<"+f(o,t)+">-]<"+f(o,n%t),e(u){var t=[];return t.length=r+1,t.join(n)},e=(n)=>{return n.length},h=(n)=>{var r,t=(n=n.map(e))[0],u=0;for(r in n)n[r]+++++++++[<++++++++>-]<.>+++++[<+++++>-]<++++.+++++++..+++.>>++++++[<+++++>-]<++.>+++++++++[<+++++++++>-]<++++++.--------.+++.------.--------.
Goodbye Brainfuck: 259
>++++++++[<++++++++>-]<+++++++.>++++++[<++++++>-]<++++..-----------.--.>+++++[<++++>-]<+++.>+++++[<---->-]<.>>++++++[<+++++>-]<++.>++++++[<+++++>-]<++++.>++++++++[<++++++>-]<.>++++[<---->-]<-.++++++++.+++++.--------.+++++++++++++++.>++++[<---->-]<--.++++++++.
Исходный код:
(function(){
var s2a, Ba, rep, L, shortest, G = '+-', M = 29999;
B = function(s) {
var C = '', i, c, v, vi, d, bi = 0, U = [0];
s = s2a(s); //s в массив чисел
for(i in s) {
c = s[i];
d = c - U[bi];
v = [Ba(d, bi), Ba(d + 256, bi), Ba(d - 256, bi), '>' + Ba(c, bi + 1), '>' + Ba(c - 256, bi + 1)]; //Несколько вариантов получения нужного числа
vi = shortest(v); //Индекс наиболее короткого
if(vi > 2) {
bi++; //Сдвигаем указатель текущего положения
}
U[bi] = c;
C += v[vi] + '.'; //Сохранение кода
}
return C;
}
s2a = function(s) {
var i;
s = s.split('');
for(i in s) s[i] = s[i].charCodeAt(0);
return s;
}
Ba = function(d, bi) { //Эффективный код прибавления разности d в ячейке bi
if(bi > M) return rep('#', 256); //Переполнение массива, выдаём очень длинный код
var s = +(d < 0), r, R, C, D;
if(s) d = -d; //d = abs(d)
s = G[s]; //Знак разности
D = rep(s, d); //Код без цикла
if(d > 15 && bi < M) { //Когда разность < 15, цикл не выгоден; проверка на переполнение
r = Math.sqrt(d) | 0; //r = int(sqrt(d))
R = (d / r) | 0;
C = '>' + Ba(R, bi + 1) + '[<' + rep(s, r) + '>-]<' + rep(s, d % r);
if(L(C) < L(D)) {
return C; //Если с циклом выгоднее, возвращаем его
}
}
return D;
}
rep = function(s, n) { //Повторенние строки s n раз
var a = [];
a.length = n + 1;
return a.join(s);
}
L = function(a) { //Длинна массива/строки
return a.length;
}
shortest = function(v) { //Индекс наиболее короткого
v = v.map(L);
var m = v[0], mi = 0, i;
for(i in v) {
if(v[i] < m) {
m = v[i];
mi = i;
}
}
return mi;
}
})();
Ответ 10
05AB1E, 709
Жаль, соревнование уже кончилось
Код 80 символов, 96 UTF-8 байт:
0IÇDdgi)}v'+sys-D0‹i(s\'-s}D15s‹i'>?DtóD'+s.×J?„[-]<"?s}.×J?'.?y
Интерпретатор
Hello world 153:
>++++++++[<+++++++++>-]<.>+++++[<+++++>-]<++++.+++++++..+++.>++++++++[<--------->-]<-------.>+++++++++[<+++++++++>-]<++++++.--------.+++.------.--------.
Goodbye Brainfuck 266:
>++++++++[<++++++++>-]<+++++++.>++++++[<++++++>-]<++++..-----------.--.>++++[<+++++>-]<+++.>++++[<----->-]<.>++++++++[<-------->-]<-----.>+++++[<++++++>-]<++++.>++++++[<++++++++>-]<.>++++[<---->-]<-.++++++++.+++++.--------.+++++++++++++++.>++++[<---->-]<--.++++++++.
Пояснение
Алгоритм является упрощённой версией моего алгоритма на JS6 (без переполнения char и без перехода в следующую ячейку, если выгоднее начать с нуля)
Условные обозначения:
y - код текущего символа
p - код предыдущего символа
d' = y - p (на сколько изменить код символа)
d = abs(d')
s = char(sign(d'))
a, b -> b, a - поменять местами верхние два элемента на стеке
a, b, c -> c, a, b - циклический сдвиг верхних трёх элементов (вставить верхний под a)
write(s) = print(s, end = "")
Сам код:
0 push(p = 0)
I push(input())
Ç push(pop().map(charToInt))
Ddgi)} Если введён ровно 1 символ, вместо массива будет число => оборачиваем в массив
v for y in pop():
'+s push(s = "+"); p, s -> s, p
ys- push(y); p, y -> y, p; push(d' = (-pop(p) + pop(y)))
D0‹ push(peek(d')); push(0); push(pop(0) > pop(d'))
i(s\'-s} if(pop(d' < 0)) {push(d = -pop(d')); s, d -> d, s; pop(s = "+"); push(s = "-"); d, s -> s, d}
D15s‹i if(peek(d) > 15): (см. комментарий к JS коду)
'>? write(">")
Dtó push(fsd = floor(sqrt(peek(d))))
D'+s push("+", peek(fsd))
.×J? write(int(pop(fsd)) * str(pop("+")))
„[ (d % fsd), s, (d // fsd), s
s.×J? write(str(pop(s)) * int(pop(d // fsd)))
">-]<"? write(">-]<")
s (d % fsd), s -> s, (d % fsd)
} end if
.×J? write(int(pop((d % fsd) if d > 15 else d)) * str(pop(s)))
'.?y write("."); push(p = y)
