20

Внимание! Соревнование окончено! Огромное спасибо всем тем, кто принял в нем участие)

Вы можете ознакомиться с результатами и различными алгоритмами решения поставленной задачи ниже, а если вдруг у Вас возникнет хорошая идея реализации всего этого дела - не стесняйтесь и публикуйте, ведь пусть конкурс уже и закрыт, идеи, предложенные здесь, возможно, впоследствии порадуют одинокого странника ruSO, изучающего вопросы по меткам и )


Товарищи!
Давненько не проходило у нас никаких соревнований, так что стоит исправить сие досадное упущение)


Думаю, каждый из нас хоть немного знаком с эзотерическим языком Brainfuck и его в буквальном смысле мозговыносящим синтаксисом. Обычное Hello world выглядит страшнее и сложнее ПО для Аполлона 11...
А почему бы не автоматизировать процесс создания кода на Brainfuck для вывода нужных нам строк? Таки вопрос риторический, ибо этим мы и займемся)


Задача:

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


Подробнее:

Как Вы понимаете, функцию необходимо максимально ужать. Однако это еще не все: роль также будет играть длина выходного кода, так что решение "в лоб" не подойдет)
Вам необходимо будет протестировать свой код на следующих двух строках:

s1 = "Hello world"
s2 = "Goodbye Brainfuck"

Правила:

  1. При решении задачи можно использовать любой язык программирования
  2. Можно оставлять несколько вариантов ответа (в разных постах)
  3. Запрещено использовать какие-либо сторонние библиотеки для решения поставленной задачи, если они не являются частью используемого языка/платформы
  4. Запрещено внутри реализуемой функции использовать строки s1 и s2 в явном или зашифрованном виде
  5. Желательно оставлять ссылку на онлайн-компилятор Вашего кода
  6. В ответе приводите как минифицированную версию Вашей функции, так и "развернутую" (пояснения приветствуются), чтобы каждый мог разобраться в магии Вашего кода и, возможно, почерпнуть что-то для себя
  7. Сгенерированный код на Brainfuck должен быть рабочим и выводить строки s1 и s2 (проверить код можно, скажем, тут или тут)
  8. Обязательным условием является наличие у Вашего ответа заголовка в формате <h2>Язык, Кол-воСимволов</h2> (требуется для парсера таблицы лидеров)
  9. Рассчет символов определяется следующей формулой:

    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)
  10. Продолжительность соревнования: 7 дней

Определение победителей:

Победители определяются по следующей градации:

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

P.S. - работа автора поста не принимает участия в подведении итогов


Если возникнут вопросы по правилам проведения конкурса - задавайте их в комментариях)


Удачи в реализации, товарищи!


Итоги:

1 место: @Groxan - , ответ занял 745(!) символов
2 место: @b1nary - , ответ занял 827 символов
3 место: @rjhdby - , ответ занял 834 символа

Собственно, хотелось бы сказать пару слов о прошедшем соревновании)
Еще раз огромное спасибо каждому, кто принял участие в сием мероприятии, ведь, думаю, каждый из нас смог почерпнуть из идей других участников что-то новое и интересное!
Было очень интересно разбирать код, его ужатый вид, а также и логику во всех ответах, каждый из которых по-своему элегантен и интересен)

И отдельно, конечно, хочется сказать про работу @Groxan, которая заняла всего 745 символов! Честно, когда я предложил данный эвент, я даже не предполагал, что хоть одна реализация преодолеет барьер в 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:23px 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fold 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)}}.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:23px 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fold 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;}
<script src="https://mayorovp.github.io/codegolf/97314479fcd24a2386e1.js"></script><div class=cssload-container><div class=cssload-cube><div class=cssload-half1><div class="cssload-side cssload-s1"></div><div class="cssload-side cssload-s2"></div><div class="cssload-side cssload-s5"></div></div><div class=cssload-half2><div class="cssload-side cssload-s3"></div><div class="cssload-side cssload-s4"></div><div class="cssload-side cssload-s6"></div></div></div></div>

17
  • правило №2 какое то сомнительное. почему бы два разных подхода не реализовать на одном и том же языке?
    – teran
    4 июл 2018 в 9:12
  • @teran хм. Пожалуй, соглашусь с Вами) Просто в предыдущих гольфах порой наблюдал такое правило ¯\_(ツ)_/¯ 4 июл 2018 в 9:22
  • 1
    Пожалуйста, не апайте Ваш вопрос! Если вопрос может быть интересен, его поднимет Дух. Возможно.
    – user207618
    4 июл 2018 в 17:18
  • 1
    @Aid, если имеются ответы с положительным рейтингом, то не поднимет. 5 июл 2018 в 5:51
  • 1
    Слишком быстро завершили конкурс, я вот хотел что-нибудь из этого попробовать, но не успел (о награде можно было объявить заранее, но назначить ее позже, например, через неделю после старта)... 13 июл 2018 в 8:06

10 ответов 10

14

Brainfuck, 4277

Конечно же в подобных заданиях веселья ради должен найтись идиот сумасшедший, который напишет код на самом Brainfuck

Итак, сама функция (74 символа):

++++++[>+++++++<-]>+>++++++++[>++++++++<-]>-->,[[<<<.>>>-]<<<+++.--->>.>,]

Код для s1 (1106 символов):

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>

Код для s2 (1696 символов):

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>


Функция в более читаемом виде:

++++++[>+++++++<-]>+        // Записываем код для знака плюс
>
++++++++[>++++++++<-]>--    // Записываем код для знака перехода в следующую ячейку
>
,                           // Считываем символ
[                           // Запускаем цикл зпт который будет идти до символа '\0'
    [<<<.>>>-]              // Печатаем число плюсов зпт необходимое для печати символа
    <<<
    +++.---                 // Увеличиваем код ячейки плюса до точки зпт печатаем и возвращаем
    >>.>                    // Печатаем символ перехода в следующую ячейку
    ,                       // Читаем следующий символ
]

Логика алгоритма:
Собственно, думаю, логика ясна из пояснений к коду: мы читаем нуль-терминированную строку, для каждого символа выводим кол-во знаков +, равное его ASCII-коду, а также символы . (для печати) и > (для перехода в следующую ячейку)


Алгоритм совершенно не оптимален (видно из числа символов хД), зато функция короткая да и написана на языке-герое сего мероприятия)

12
+150

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<o.Length?t:o;}return o+".";}
return string.Concat($"\0{v}".Zip(v,m));

Hello world (97 символов):

-[------->+<]>-.-[->+++++<]>++.+++++++..+++.+[->--<]>.--[->++++<]>-.--------.+++.------.--------.

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);
}
8
  • @rjhdby Здравый совет! Конечно же я им воспользовался, хотя это и не совсем честно =)
    – Groxan
    6 июл 2018 в 13:47
  • 1
    Правильнее сказать, здесь используется заход через переполнение byte =)
    – Groxan
    7 июл 2018 в 11:38
  • 1
    Спасибо! Результат невероятный просто! :) 9 июл 2018 в 10:23
  • 1
    k>0?k:-k короче чем Math.Abs(k). int s,d,n можно внести внутрь первого for. 9 июл 2018 в 14:23
  • 1
    Вместо || достаточно |. n++ можно из заголовка цикла выбросить и перенести в тело: w(x+p-c(p+s,d)*n++%256). w(s)+$"[{w(d)}>{w(n)}<]>"+w(x+p-c(p+s,d)*n++%256) - еще 2 символа 10 июл 2018 в 6:46
8

С#, 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#)

8

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 символа):

>+++++++++[<++++++++>-]<-.>+++++++[<++++++>-]<--..-----------.--.>+++++[<++++>-]<+++.>+++++[<---->-]<.>+++++++++[<-------->-]<+++.>++++++[<+++++>-]<++++.>+++++++[<++++++>-]<++++++.>+++++[<---->-]<+++.++++++++.+++++.--------.+++++++++++++++.>+++++[<---->-]<++.++++++++.

4
  • 2
    А где разбор логики алгоритма? Или мы сами должны разбираться? :)
    – user207618
    6 июл 2018 в 11:22
  • Luke, use the online Interpreters!
    – user207618
    6 июл 2018 в 11:51
  • @Aid Заааануда!
    – rjhdby
    6 июл 2018 в 11:54
  • Yep :).........
    – user207618
    6 июл 2018 в 11:55
7

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[<z_operations>-]<, который прибавляет или вычитает (в зависимости от знака 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='')
3
  • 2
    Я думаю, не стоит учитывать input и print. Переписал немного ваш код. 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)]+'.' l=0;g="+-";s=''.join(map(f,map(ord,s))) 190
    – user207200
    10 июл 2018 в 12:23
  • repl.it
    – user207200
    10 июл 2018 в 12:32
  • @mkkik, спасибо! Обновил ответ с вашими изменениями.
    – tie
    10 июл 2018 в 23:26
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
  • А где разбор логики алгоритма? Или мы сами должны разбираться? :)
    – user207618
    6 июл 2018 в 12:18
  • @Aid таки правила не оговаривают ¯\_(ツ)_/¯
    – rjhdby
    6 июл 2018 в 18:51
  • @rjhdby, А 6-ой пункт правил?
    – user207618
    6 июл 2018 в 18:54
  • 1
    @Aid вот что точно не обязательно, так это навязывание всем своих представлений о мироустройстве
    – rjhdby
    7 июл 2018 в 10:17
  • 1
    @rjhdby, Я их не навязываю, а обращаю внимание что разбор логики даже в правилах рекомендуют сделать.
    – user207618
    7 июл 2018 в 10:35
3

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]+".";return f},c=(n)=>{var r;for(r in n=n.split(""))n[r]=n[r].charCodeAt(0);return n},v=(n,r)=>{if(29999<r)return f("#",256);var t,u,i,o=+(n<0);return o&&(n=-n),i=f(o="+-"[o],n),15<n&&r<29999&&(t=0|Math.sqrt(n),u=">"+v(n/t|0,r+1)+"[<"+f(o,t)+">-]<"+f(o,n%t),e(u)<e(i))?u:i},f=(n,r)=>{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]<t&&(t=n[r],u=r);return u}})();

Hello world: 143

>+++++++++[<++++++++>-]<.>+++++[<+++++>-]<++++.+++++++..+++.>>++++++[<+++++>-]<++.>+++++++++[<+++++++++>-]<++++++.--------.+++.------.--------.

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;
    }
})();
3

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){int 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<stdio.h>
int main(void) {
    printf("%ls", B(L"Hello world"));
}
12
  • 1
    Можно убрать #define V void и использовать везде возвращаемое значение, например I
    – rjhdby
    11 июл 2018 в 11:34
  • Не забудьте привести и развёрнутую версию вашей функции, дабы другие могли понять алгоритм ее работы хоть не из Ваших пояснений, а из самого кода 11 июл 2018 в 12:18
  • Приведенный результат не соответствует результату приведенного кода
    – Groxan
    11 июл 2018 в 13:05
  • @Groxan да, я тоже только что заметил. Но это не проблема, я переписал код на repl.it/repls/OrchidShallowJavabeans — так хоть по размеру исходника соответсвует рез-ту по формуле.
    – tie
    11 июл 2018 в 13:11
  • 252 + 1.5*(204 + 322) ≈ 1041
    – tie
    11 июл 2018 в 13:16
3

JS, 1067

Тело функции (446 символов):

var u=n=>Math.round(n);var p=n=>n>0?n:-n;var g=c=>(c>0?"+":"-").repeat(p(c));var 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)=>{var j="";var k=d(e);var m=p(k-h[1])<p(k-h[0])?1:0;if (m!=l){j+=m>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<q.length?t:q)+".";h[m]=k;});return s.join("");

Код для s1 (135 символов):

++++++++[<<+++++++++>>-]<<.>>+++++[<<++++++>>-]<<-.+++++++..+++.>>>>++++++[<<<+++++>>>-]<<<++.<++++++++.--------.+++.------.--------.

Код для 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 ячейки (что является оптимальным решением для указанных строк)

2

05AB1E, 709

Жаль, соревнование уже кончилось

Код 80 символов, 96 UTF-8 байт:

0IÇDdgi)}v'+sys-D0‹i(s\'-s}D15s‹i'>?DtóD'+s.×J?„[<?‰`sŠŠ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("+")))
„[<?    write("[<")
‰`  push(*[d // fsd, d % fsd])
sŠŠDŠ   s, (d // fsd), (d % fsd) -> (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)
1
  • 1
    Очень интересное решение) Опишете сам алгоритм для будущих поколений?) 28 июл 2018 в 16:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.