Задача на покрытие множество точек отрезками (или задача о ранце)

#алгоритм #любой_язык #соревнование #code_golf

Недавно закончились соревнования Яндекс.Блиц для фронтенд разработчкиов и я бы хотел
разобрать одну задачку. (Ещё раз повторюсь, что соревнования уже закончились). Как
мне показалось, задача представляет собой что-то между задачей о ранце и покрытия множества
точек отрезками. Вот её полная формулировака:

Есть девопс Петя. На работе ему нужно дежурить в определенные дни в течение последующих
100 дней. На работу Петя добирается на метро. В метро ввели билеты-абонементы, действующие
определенное количество дней со дня первой поездки по ним. Чем больше длительность
срока действия билета, тем меньше стоимость в пересчете на день. Нужно помочь Пете
сэкономить деньги и рассчитать какие билеты нужно ему купить на три месяца вперёд,
учитывая график его дежурств, таким образом, чтобы их суммарная стоимость была минимально
возможной. А еще Петя не любит носить много билетов с собой, и, если есть несколько
вариантов билетов с одинаковой минимальной стоимостью, то Пете нужен такой, в котором
меньше билетов. Если и таких вариантов окажется несколько (с одинаковой минимальной
стоимостью и количеством билетов) — то Пете подойдет любой из них.
Вам необходимо написать функцию getCheapestTickets(days, tickets), принимающую на
вход график дежурств Пети (days) и возможные варианты билетов-абонементов (tickets),
а на выходе дающую список билетов (в виде индексов из входного массива вариантов билетов),
которые нужно купить Пете.
График дежурств Пети задан в виде отсортированного массива чисел (от 1 до 100 включительно),
каждое из которых обозначает порядковый номер дня дежурства:

// Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно
текущей даты  
[2, 5, 10, 45]


Каждый билет-абонемент описывается следующим интерфейсом:

interface Ticket {  
    // количество дней, в течение которых билет действует со дня первой поездки по
нему,  
    // включая этот день (от 1 до 100 включительно)  
    duration: number;  
    // стоимость билета (от 1 до 100 включительно)  
    cost: number;  
}


Количество вариантов билетов не более 10 и гарантируется, что все билеты имеют разную
стоимость, причем, чем большее число дней действует билет, тем ниже его стоимость в
пересчёте на один день.

Формат ввода

days:
[1, 2, 4, 6, 7, 8, 9, 10, 20]
tickets:

[  
    { cost: 3, duration: 1 },  
    { cost: 10, duration: 7 },  
    { cost: 20, duration: 30 }  
]


Формат вывода

[0, 0, 1, 0]


Моя проблема заключается в том, что мои решения не проходили по времени. Сначала
я попытался решить задачу рекурсивно обходя наивно всё дерево решений (JavaScript):

const getCheapestTickets = (days, tickets) => {
  // Вспомогательная функция для обхода всех вариантов билетов.
  // l указывает на текущий день из массива days.
  const wrapper = (l) => {
    let min = null;

    // Обходим все билеты.
    for (let i = 0; i < tickets.length; i += 1) {
      const ticket = tickets[i];
      let j = l;

      // Считаем количество дней, которые покрывает данный билет.
      const skip = days[l] + ticket.duration;
      while (skip > days[j]) {
        j += 1;
      }

      let curr;
      if (j < days.length) {
        // Рекурсивно ищем решение для оставшихся дней.
        curr = wrapper(j);
        curr.sum += ticket.cost;
      } else {
        curr = { sum: ticket.cost, includes: [] };
      }

      const currIncludes = [i, ...curr.includes];
      curr = { ...curr, includes: currIncludes };

      if (min === null) {
        min = curr;
      } else if (
        (curr.sum === min.sum && curr.includes.length < min.includes.length)
        || curr.sum < min.sum) {
        min = curr;
      }
    }

    return min;
  };

  return wrapper(0, 0).includes;
};


Здесь я не понимаю, как отбросить ветви решений. Не вижу пути, как её свести к классической
задаче о рюкзаке, где решение ищется через матрицу. Далее я попробовал написать то
же решение, но уже без рекурсий, так же обходя все возможные варинаты, но уже с помощью
дерева. Оно так же не проходило по времени. Помогите, пожалуйста, составить более оптимальный
алгоритм. Важно, чтобы решение было однопоточным.
    

Ответы

Ответ 1

Эта задача не имеет ничего общего с задачей о рюкзаке. Фундаментальное отличие в
том, что в задаче о рюкзаке (или про покрытие отрезками) количество элементов ограничено,
а в нашей задаче мы можем купить неограниченное количество каждого вида билета.

Легко увидеть, что если в нас есть оптимальное решение для множества дней, и оптимальное
покрытие, которое можно разбить на 2 части, то мы снова получим оптимальные решения
для 2 подмножеств. Если они будут не оптимальными, то и наше изначальное решение не
оптимальное:

дни дежурства [a1, a2, ..., an, b1, b2, ..., bn]
билета        [.t.]....[..t..]  [t]....[...t...] // оптимальное покрытие билетами
отсюда следует, 2 других оптимальных покрытий:
для [a1, a2, ..., an] -> [.t.] .. [..t..]
для [b1, b2, ..., bn] -> [t]....[...t...]


Поэтому задачу можно решать динамически используя жадную стратегию. Сложность при
этом , где n - количество дней дежурства.



function getCheapestTickets(days, tickets) {

    // функция пытается найти билет, который покроет интервал дней дежурства
    // начиная с days[from] заканчивая days[to]
    // при этом билет не должен покрывать days[from - 1] и days[to + 1]
    let getTicket = function (from, to) {
        let length = days[to] - days[from] + 1;
        let maxLength = 100;
        if (from > 0 && to < days.length - 1)
            maxLength = days[to + 1] - days[from - 1] + 1;
        for (let i = 0; i < tickets.length; i++)
            if (tickets[i].duration >= length && tickets[i].duration < maxLength)
                return i;
        return null;
    };

    let solutions = {};
    // каноническое решение для покрытия нуля дней
    solutions[-1] = { cost: 0, tickets: [] };
    const maxCost = 1000000000;
    for (let i = 0; i < days.length; i++) {
        // лучшее решение для покрытия дней с days[0] до days[i]
        let bestDaySolution = { cost: maxCost };
        // проходимся по всем лучшим решениям для меньших промежутков
        // и пытаемся добавить 1 билет
        for (let j = -1; j < i; j++) {
            if (solutions[j]) {
                let ticket = getTicket(j + 1, i);
                if (ticket == null)
                    continue;
                let cost = solutions[j].cost + tickets[ticket].cost;
                let better =
                    // если цена меньше
                    cost < bestDaySolution.cost ||
                    // или если цена такая же, но количество билетов меньше
                    (cost == bestDaySolution.cost && bestDaySolution.tickets.length
> solutions[j].tickets.length + 1)
                if (better) {
                    bestDaySolution.cost = cost;
                    bestDaySolution.tickets = solutions[j].tickets.slice();
                    bestDaySolution.tickets.push(ticket);
                }
            }
        }
        if (bestDaySolution.cost != maxCost)
            solutions[i] = bestDaySolution;
    }

    return solutions[days.length - 1].tickets;
}

console.log(getCheapestTickets([1, 2, 4, 6, 7, 8, 9, 10, 20], [  
    { cost: 3, duration: 1 },
    { cost: 10, duration: 7 },  
    { cost: 20, duration: 30 }  
]));


Ответ 2

Я расскажу про задачу, которая очень похожа на эту, но, всё-таки, отличается от неё.
Возможно, это будет полезно.

Факторизация числа по заданному множеству

Данный репозиторий представляет собой реализацию алгоритма, позволяющий разложить
число по заданному множеству чисел. Например, мы 
имеем набор чисел 1, 2, 2, 3, 4, 6. Сколькими способами мы можем получить число 5?
Очевидно:

1, 4
1, 2, 2
2, 3
2, 3


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

Бейзлайн

Давайте сопоставим набору чисел битовую маску:

[0, 0, 1, 0] 


Тогда, чтобы получить решение, достаточно перебрать все битовые маски. Сложность
такого алгоритма будет: $O(2^N)$, где
$N$ - размер маски. Очевидно, что уже при 22 элементах, придётся ждать очень долго
для получения всех решений.



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

Рассмотрим прикладную задачу, которую я решал в своей практике.

Задача

Пусть у нас есть покупки. Мы знаем суммарную цену, т.е. общую сумму всех товаров
и цену каждого товара. При этом, клиент
вернул некоторые из товаров. Требуется понять, какие из товаров клиент купил.

Продолжение

В ряде случаев, нам хочется понимать, сколько решений есть у этой задачи?

Решение

Есть товары:



Каждый из них сколько-то стоит:



Также есть отправление и возврат:



Существует решение:



Включая и исключая по очереди все в решение, мы можем найти все возможные решения.

Оптимизация - 1. (Задача о рюкзаке)

Прочитать подробнее можно тут
В данном случае, используется идея о том, что не обязательно заполнять всю матрицу,
а достаточно пойти от финального решения,
т.е. и рекурсивно перебрать все решения. Таким образом, мы ответим на все вопросы
задачи. Проблема данного подхода в том,
что мы не можем делать это итеративно, а значит нам придётся все решения хранить
в памяти, а их может быть довольно много.

Важно отметить, что данная задача является частным случаем задачи о рюкзаке. Задача
о рюкзаке выглядит так:



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

В нашем случае всё проще. Во-первых, вес рюкзака и ограничение в данном случае совпадают.



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

Оптимизация - 2

Для того, чтобы генерировать решения итеративно, предлагается отранжировать элементы.
В данном случае это возможно, покуда
ограничение и вес совпадают. Затем, на каждом шаге, мы будем набивать рюкзак, итерируясь
от максимального элемента к 
минимальному и будем пересчитывать остаток. Как только остаток станет меньше 0, возвращемся
к предыдущему шагу и продолжаем поиск.
Если остаток равен в точности 0, то возвращаем решение, а затем, с того же места
продолжаем поиск.

Заметим, что данное решение работает примерно в 2 раза дольше, чем решение задачи
о рюкзаке. При этом, мы можем отдавать ответы итеративно.

Код-гольф - Создание генератора кода для печати строк в Brainfuck

Внимание! Соревнование окончено! Огромное спасибо всем тем, кто принял в нем участие)
Вы можете ознакомиться с результатами и различными алгоритмами решения поставленно
задачи ниже, а если вдруг у Вас возникнет хорошая идея реализации всего этого дела 
не стесняйтесь и публикуйте, ведь пусть конкурс уже и закрыт, идеи, предложенные здесь, возможно, впоследствии порадуют одинокого странника 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)

Код-гольф: Обход двумерного массива змейкой

Задача соревнования:

Имеется двумерный массив N x N. Нужно написать функцию обхода двумерного массив
змейкой от правого ребра. Пример на картинке.





Пример двумерного массива:

На входе имеется следующий массив:

input = [[4, 3, 2, 1], [5, 6, 7, 8], [12, 11, 10, 9], [13, 14, 15, 16]]


На выходе одномерный массив после обхода:

output = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


Может использоваться любой язык. 

Основное условие: функция должна работать корректно для любого равностороннего двумерного массива. 

Указывать название языка в заголовке ответа и количество символов минифицированной версии функции через запятую.

Победителем станет тот, кто напишет ее за меньшее количество символов. За это о
получает 300 репутации. Победитель определится через 2 недели (12 января). 

Ответ автора не учитывается при выборе победителя. Желаю удачи :)

Таблица лидеров:



execute("ru.stackoverflow.com", 926927);







Победители:

1 место: Haskell - 39 (@АндрейNOP)

2 место: JavaScript - 40 (@Groxan)

3 место: Groovy - 42 (@Nick)

Всем огромное спасибо за участие и интересные решения ;)
    

Ответы

Ответ 1

Haskell, 39 40 42

r=reverse;s[]=[];s(h:t)=r h++s(map r t)


https://ideone.com/JYttmr


Ответ 2

Octave, 47



@(l,b=l(1:2:end,:)=fliplr(l(1:2:end,:)))l'(:)';


Try it online!

Если разрешить возвращать не вектор-строку, а вектор-столбец, сокращается на 1 символ:

Octave, 46



@(l,b=l(1:2:end,:)=fliplr(l(1:2:end,:)))l'(:);


Try it online!

Прошлый вариант без анонимной функции:

Octave, 40



l(1:2:end,:)=fliplr(l(1:2:end,:));l'(:)'


Try it online!


Ответ 3

Python, 56

f=lambda l:sum([x[::i%2*2-1]for i,x in enumerate(l)],[])


Спасибо @АндрейNOP за подсказку!

Python, 60

f=lambda l:sum([[x[::-1],x][i&1]for i,x in enumerate(l)],[])


https://ideone.com/JPyzUQ (эта версия с лямбда функцией была любезно предоставлена @Let's say Pie)



Попытка 2: инвалидирована по причине неправильного оформления - решение должно быть реализовано как функция

Python, 49

sum([[x[::-1],x][i&1]for i,x in enumerate(l)],[])


https://ideone.com/WdHq4n

PS @КириллМалышев подсказал как можно сократить код еще на 6 символов - спасибо!!



Попытка 1:

Python, 55

sum([x if i&1 else x[::-1] for i,x in enumerate(l)],[])


https://ideone.com/2hoF3P


Ответ 4

JavaScript, 38

Данный код работает в Firefox, но не работает на V8 (из-за специфичного алгоритма сортировки). Если это неприемлемо, скажите =)



f=a=>a.flatMap((x,i)=>x.sort(_=>~i&1))

console.log(f([[4,3,2,1],[5,6,7,8],[12,11,10,9],[13,14,15,16]]));






JavaScript, 40



f=a=>a.flatMap((x,i)=>i%2?x:x.reverse())

console.log(f([[4,3,2,1],[5,6,7,8],[12,11,10,9],[13,14,15,16]]));


Ответ 5

JavaScript, 54



f=a=>a.reduce((c,n,i)=>c.concat(i%2?n:n.reverse()),[])

console.log(f([[4, 3, 2, 1], [5, 6, 7, 8], [12, 11, 10, 9], [13, 14, 15, 16]]));


Ответ 6

Python, 62 61

Пока ничего лучше варианта с рекурсией не придумал :)

f=lambda m,x:m and(x&1and m.pop(0)or m.pop(0)[::-1])+f(m,x+1)


https://ideone.com/i2d0f6


Ответ 7

Python, 43

f=lambda m,a=-1:m and m.pop(0)[::a]+f(m,-a)


https://ideone.com/fQVgtD


Ответ 8

F#, 68

let rec f=function|[]->[]|h::t->List.rev h@(t|>List.map List.rev|>f)


https://ideone.com/S6PhEZ


Ответ 9

PowerShell, 51

$f={$args[0]|%{if(++$i%2){[Array]::Reverse($_)}$_}}


Try it online!


Ответ 10

C#, 62

dynamic s(int[][]a)=>a.SelectMany((x,i)=>i%2>0?x:x.Reverse());


https://repl.it/repls/EmbarrassedHalfCommand


Ответ 11

PHP, 93 91

function f($a){foreach($a as$v)$r[]=$_++&1?$v:array_reverse($v);return array_merge(...$r);}


https://ideone.com/XsiPap


Ответ 12

PHP,  138 105

function f($a){foreach($a as$i=>$y){foreach($y as$x=>$w){$r[]=$i&1?$w:array_reverse($y)[$x];}}return $r;}


https://3v4l.org/DgDi8


Ответ 13

C#, 188 184

List S(T[,]a){var l=new List();int m=a.GetLength(1);for(int i=0;i=0;j--)l.Add(a[i,j]);else for(int j=0;j
Ответ 14

C#,171 168 163 153

Так как решения через LINQ уже были, то предлагаю вашему вниманию традиционных подход.

Минифицированная версия:

T[]F(T[,]a){var d=a.GetUpperBound(1);var r=new List();for(int i=0;i<=d;i++){var b=i%2>0;int j=b?0:d;while(j<=d&j>=0){r.Add(a[i,j]);j=b?++j:--j;}}return r.ToArray();}


Удобночитаемая:

    static T[] F(T[,] a)
    {
        var d = a.GetUpperBound(1);
        var r = new List();
        for (int i = 0; i <= d; i++)
        {
            var b = i % 2 > 0;
            int j = b ? 0 : d;
            while (j <= d & j >= 0)
            {
                r.Add(a[i, j]);
                j = b ? ++j : --j;//Трюк, что бы сэкономить символы на if/else
            }
        }
        return r.ToArray();
    }




Чуть чуть подправил:

T[]F(T[,]a){var d=a.GetUpperBound(1);var r=new List();for(int i=0;i<=d;i++){var b=i%2>0;int j=b?0:d;while(j<=d&j>=0){r.Add(a[i,b?j++:j--]);}}return r.ToArray();}


Удобночитаемая:

 T[] F(T[,] a)
    {
        var d = a.GetUpperBound(1);
        var r = new List();
        for (int i = 0; i <= d; i++)
        {
            var b = i % 2 > 0;
            int j = b ? 0 : d;
            while (j <= d & j >= 0)
            {
                r.Add(a[i, b ? j++ : j--]);
            }
        }
        return r.ToArray();
    }




Опять чуть подправил:

T[]F(T[,]a){var d=a.GetLength(1)-1;var r=new List();for(int i=0;i<=d;i++){var b=i%2>0;int j=b?0:d;while(j<=d&j>=0)r.Add(a[i,b?j++:j--]);}return r.ToArray();}


Удобночитаемая:

T[] F(T[,] a)
{
    var d = a.GetLength(1) - 1;
    var r = new List();
    for (int i = 0; i <= d; i++)
    {
        var b = i % 2 > 0;
        int j = b ? 0 : d;
        while (j <= d & j >= 0)
            r.Add(a[i, b ? j++ : j--]);
    }
    return r.ToArray();
}




И еще чуть-чуть убрал все лишнее:

T[]F(T[,]a){int d=a.GetLength(1),g=0;var r=new T[d*d];for(int i=0;i0;int j=b?0:d-1;while(j=0)r[g++]=a[i,b?j++:j--];}return r;}


Удобночитаемый:

    T[] F(T[,] a)
    {
        int d = a.GetLength(1), g = 0;
        var r = new T[d * d];
        for (int i = 0; i < d; i++)
        {
            var b = i % 2 > 0;
            int j = b ? 0 : d - 1;
            while (j < d & j >= 0)
                r[g++] = a[i, b ? j++ : j--];
        }
        return r;
    }


Ответ 15

Perl 5, 81

sub f{foreach$row(@_){foreach$val(@$row){push@$s,$i++%2?@$val:reverse@$val;}}$s;}


Try it online!


Ответ 16

Groovy, 42

f={i=0;it.each{it.reverse i=!i}.flatten()}


https://ideone.com/XirvAC


Ответ 17

C, 97

int f(int n,int a[n][n],int*b){for(int i=0;i
Ответ 18

Ruby, 63

def f(a,x)a[0]?(x%2==0?a.shift.reverse: a.shift)+f(a,x+1):[]end


https://ideone.com/T0MECG

Код-гольф: Увеличиваем цифры

Задача: Написать код минимально возможной длины, выводящий полученную на вход, строк
из цифр большим, символьным шрифтом. Шрифт должен быть в точности такой, как указан тут, в вопросе.

Пример:

На вход получена строка "0123456789", на стандартный вывод программа должна вывести:

  ###      #     #####   #####  #       #######  #####  #######  #####   #####
 #   #    ##    #     # #     # #    #  #       #     # #    #  #     # #     #
#     #  # #          #       # #    #  #       #           #   #     # #     #
#     #    #     #####   #####  #    #  ######  ######     #     #####   ######
#     #    #    #             # #######       # #     #   #     #     #       #
 #   #     #    #       #     #      #  #     # #     #   #     #     # #     #
  ###    #####  #######  #####       #   #####   #####    #      #####   #####


Правила и ограничения:


Программа может, но не обязана быть оформленной в виде функции. Если    она функци
- синтаксис объявления этой функции (int main() {} для C)    не учитывается в размере, важен размер самого рабочего кода.
Входная строка может поступать в программу любым, удобным вам, способом: в виде переменной
указанной в тестовом примере непосредственно перед кодом, в виде параметра функции или со стандартного ввода.
Входная строка может содержать только цифры
Результат должен быть выведен на стандартный вывод в текстовом виде. Если стандартны
вывод направлен на терминал, экран считать достаточной ширины для вывода всего контрольног
примера c запасом. Переход на новую строку обозначайте (явно или не явно) любым символом/комбинацией символов, использующейся для перевода строки на вашей платформе (Например, \n или \r\n).
Шрифт результата должен в точности соответствовать указанному выше. Между цифрам
на выводе должен быть минимум один пробел (цифры не должны сливаться). Шрифт считается моноширинным, т.е. вокруг единицы может быть больше пустого пространства т.к. ее изображение ýже остальных цифр.
В программе запрещено использовать любые встроенные в язык и библиотеки к нему функции сжатия и кодирования данных (Такие как: zip/unzip, base64)
Программа должна содержать шрифт (или код его формирующий) непосредственно в свое
теле. Получать шрифт из внешних источников (ввод, диск, сеть, память видеоадаптера, bios) запрещено.
Размер программы учитывается в байтах. Побеждает программа имеющая минимальный размер




Конкурс окончен

Первое место занимает @RusArt с ответом на 05AB1E, длиной всего 91 "байт".

Втрое место занимает @Anton Petrusevich с ответом на perl, длиной 150 байт.

И третье место достается @retorta с ответом на python, длиной 161 байт.

В ответах рассмотрены самые разные способы сжатия шрифта. При подготовке к конкурс
я рассматривал большинство из них. Самым простым для реализации и в то же время достаточн
эффективным оказалось сжатие до 70 байт в 7 битной, горизонтальной, кодировке (оригинально
моя кодировка представлена в ответе на postgresql. Даже удалось попасть в диапазон допустимы
символов, поменяв 6-7 биты и вычтя 2. Правда не все участники заморачивались и тратил
драгоценные байты на кодирование в диапазон печатных символов с 0x20 до 0x7E. Применяли кодирование как есть, часто с 8 битом или залезая вообще в диапазон управляющих. В принципе такое кодирование имеет право на жизнь, программы на той платформе, где писались работают. Хотя мне и не очень нравится когда программу нельзя напечатать на принтере, ввести по новой с листа и что бы при этом она продолжила работать (Вы не сможете опубликовать свой код в книге ;) ).

Победителем была использована совершенно другая кодировка шрифта. Словарь из 16 возможны
7и символьных элементов шрифта (в битовом кодировании) и кодовая таблица с номерам
частей для каждого символа, которая благодаря нестандартной кодовой странице языка 05AB1
заняла 35 "байт" (технически в этом языке используются 256 графем, которые принято считат
"байтами" потому что их именно 256 и если бы реально существовала такая кодовая таблица, то их все действительно можно было бы закодировать одним байтом). К сожалению подобное кодирование в других языках невозможно в принципе, в связи с тем, что из 256 значений байта в кодировке ASCII 31 используется для управляющих кодов, а 128 старших значений плохо переносятся между платформами.

Подобный подход со словарем в принципе был использован еще в нескольких ответах
но там не применялось бинарное кодирование в результате чего шрифт занимает горазд
больше места. В процессе подготовки конкурса я рассматривал даже несколько варианто
кодирования со словарем. Например, две комбинации ##### и #     #, встречающиеся очен
часто, предполагалось кодировать двумя битами со значениями 10 и 11, а остальные варианты 5и битным значением, первый бит которого 0, что бы отличить от первых двух и остальные 4 бита номер варианта. На практике же это давало совсем небольшой выигрыш в кодировании шрифта и при этом код декодирования оказывался слишком сложным и в код-гольфе неприменимым и опять же в обычном ascii коде уложить это очень сложно.

В ответах можно найти и совершенно иные способы кодирования, например, кодирование повторов # и пробелов просто количествами подряд, представленном в ответе @Qwertiy

К сожалению никто из участников не пробовал использовать вертикальное кодирование
т.е. где элементом выступает 7 бит кодируемого символа берущихся из него по вертикали
А при таком способе кодирования получается очень много повторов. Присмотритесь к цифра
5689 у них отличаются только 1 и последняя вертикаль, остальные одинаковы. При кодировании повторов в такой строке удается достичь практически такого же сжатия как и в случае с словарем и битовым кодированием. Но на практике гольфа опять же слабо применимое из за роста объема декодирующего кода. 



Альтернативный рейтинг

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


Anton Petrusevich, ответ на perl, длиной 150 байт
Андрей, ответ на C#, длиной 176 байт
Visman, ответ на PHP, длиной 235 байт




Пожалуйста, указывайте в ответе количество байт, чтобы проще было выявить победителя.



execute("ru.stackoverflow.com", "674415");
.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)}}@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)}}