Hello world с пустой функцией main

#cpp #соревнование

                    
Столкнулся с такой задачей на собеседовании: 


  Написать программу, которая печатает в консоли фразу Hello world 


И всё бы ничего, если бы после этого стояла точка. Но фраза продолжается: 


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


int main() 
{
    return 0;
}

    

Ответы

Ответ 1

Ответ очень прост. Их даже несколько. Самый простой, основанный на свойстве глобальных
статических объектов.
int printHelloWorld() { printf("Hello World"); return 0; }
static int testVar = printHelloWorld();
int main ()
{
    return 0;
}

Это, если С стиль. С++ стиль: создаем класс, в конструкторе добавляем вывод, будет
вывод до main, в деструкторе - после.


Ответ 2

Используем препроцессор.
#define return puts("Hello World"); return

int main ()
{
  return 0;
}

Не такой красивый вариант как со статикой, но тоже работает.


Ответ 3

True programmer напишет это в hex редакторе в машинных кодах. Даже функция main не нужна.

BB 11 01 B9 0D 00 
B4 0E 8A 07 43 CD 
10 E2 F9 CD 20 48 
65 6C 6C 6F 2C 20 
57 6F 72 6C 64 21


Немного исправим, воспользовавшись примером выше для соответствию заданию.

using namespace std;
#include

class hello{
public:
hello()
{
    ofstream hello;
    hello.open ("hello.com");
    hello << "»..№..ґ.Љ.CН.вщН Hello, World!";
    hello.close();
    system("hello.com");
}put;

int main(){
    return 0;
}


Вуаля мы получили программу на языке С++ которая возвращает .com файл, затем запускает
его, после чего этот файл через BIOS прерывание выводит на экран Hello, world! При
этом наша программа имеет пустую функцию main и не обращается напрямую к стандартном
выводу в командную строку. Работает только в DOS command promt.


Ответ 4

Статические переменные и дефайны не обязательны:

#include 
int s = printf("Hello world\n");

int main()
{
    return 0;
}


Ответ 5

Вот ещё способ:
#include 

void hello()
{
    puts("Hello, World!");
}
#pragma data_seg(".CRT$XIY")
void(*pinit)()=&hello;

int main()
{
    return 0;
};

Только оказалось, что он только в дебаге работает.
ПРАВКА:
А ещё можно подменить точку входа:
#pragma comment(linker, "/ENTRY:Main") //Вместо прагмы можно использовать параметр
командной строки
#include  //CRT с его printf и puts (не говоря уже о cout) мы, к сожалению,
потеряли, поэтому придётся использовать средства ОС

int main(void) 
{
    return 0;
}

void Main()
{
    WriteConsoleA(GetStdHandle(STD_OUTPUT_HANDLE), "Hello, World!\n", 14, nullptr,
nullptr);
}

Кстати, у меня эта программка занимает 656 байт после того, как я немного похимичил
с ключами компиляции.


Ответ 6

#include

class hello {
    public:
        hello(){ std::cout << "Hello, world!\n"; }
} put;

int main(){
    return 0;
}


Ответ 7

#include 

const std::ostream& out = std::cout << "Hello World" << std::endl;


Ответ 8

Помимо многих предложенных ранее вариантов с выводом текста до выполнения main, предложу
вариант с выводом после выполнения main:

#include 
#include 

void hw() {
    puts("Hello world");
}

int v = atexit(hw);

int main() {
    return 0;
}


Ответ 9

gcc поддерживает атрибут "constructor", который помещает функцию в init-секцию ELF-файла.
Что, в свою очередь, означает, что эта функция вызовется перед функцией main. То есть,
то, что нам нужно.

void __attribute__((constructor)) init {
  printf("Hello world!");
}


Ответ 10

$ cat hellower.cpp 
#include "helper.cpp"
int main(void) {
        return 0;
}


второй файл:

$ cat helper.cpp 
#include 

int hello_helper() {
        printf("Hello World\n");
        return 0;
}

static int a = hello_helper();


Лаунч:

$ g++ hellower.cpp
$ ./a.out 
Hello World


Ответ 11

Первый файл (строго соответствует условию задачи):

$ cat main.cpp
int main(void)
{
    return 0;
}


Второй файл:

$ cat hello.cpp
#include 

int hello_helper() {
    printf("Hello World\n");
    return 0;
}

static int a = hello_helper();


Makefile для компилятора g++:

$ cat makefile
TARGET = hello
PREFIX = /usr/local/bin
.PHONY: all clean install uninstall
all: $(TARGET)
clean:
    rm -f $(TARGET) *.o
main.o: main.cpp
    g++ -c -o main.o main.cpp
hello.o: hello.cpp
    g++ -c -o hello.o hello.cpp
$(TARGET): main.o hello.o
    g++ -o $(TARGET) main.o hello.o
install:
    cp $(TARGET) $(PREFIX)/$(TARGET)
uninstall:
    rm -f $(PREFIX)/$(TARGET)


Ответ 12

Вот в стиле C++

#include 

class StaticOutput
{
    static int print();
    static int out;
};

int StaticOutput::out = StaticOutput::print();

int StaticOutput::print()
{
    std::cout << "Hello World!" << std::endl;
    return 0;
}


int main()
{
    return 0;
}

Hello world с пустой функцией main

#cpp #соревнование

Столкнулся с такой задачей на собеседовании: 


  Написать программу, которая печатает в консоли фразу Hello world 


И всё бы ничего, если бы после этого стояла точка. Но фраза продолжается: 


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


int main() 
{
    return 0;
}

    

Ответы

Ответ 1

Ответ очень прост. Их даже несколько. Самый простой, основанный на свойстве глобальных
статических объектов.
int printHelloWorld() { printf("Hello World"); return 0; }
static int testVar = printHelloWorld();
int main ()
{
    return 0;
}

Это, если С стиль. С++ стиль: создаем класс, в конструкторе добавляем вывод, будет
вывод до main, в деструкторе - после.


Ответ 2

Используем препроцессор.
#define return puts("Hello World"); return

int main ()
{
  return 0;
}

Не такой красивый вариант как со статикой, но тоже работает.


Ответ 3

True programmer напишет это в hex редакторе в машинных кодах. Даже функция main не нужна.

BB 11 01 B9 0D 00 
B4 0E 8A 07 43 CD 
10 E2 F9 CD 20 48 
65 6C 6C 6F 2C 20 
57 6F 72 6C 64 21


Немного исправим, воспользовавшись примером выше для соответствию заданию.

using namespace std;
#include

class hello{
public:
hello()
{
    ofstream hello;
    hello.open ("hello.com");
    hello << "»..№..ґ.Љ.CН.вщН Hello, World!";
    hello.close();
    system("hello.com");
}put;

int main(){
    return 0;
}


Вуаля мы получили программу на языке С++ которая возвращает .com файл, затем запускает
его, после чего этот файл через BIOS прерывание выводит на экран Hello, world! При
этом наша программа имеет пустую функцию main и не обращается напрямую к стандартном
выводу в командную строку. Работает только в DOS command promt.


Ответ 4

Статические переменные и дефайны не обязательны:

#include 
int s = printf("Hello world\n");

int main()
{
    return 0;
}


Ответ 5

Вот ещё способ:
#include 

void hello()
{
    puts("Hello, World!");
}
#pragma data_seg(".CRT$XIY")
void(*pinit)()=&hello;

int main()
{
    return 0;
};

Только оказалось, что он только в дебаге работает.
ПРАВКА:
А ещё можно подменить точку входа:
#pragma comment(linker, "/ENTRY:Main") //Вместо прагмы можно использовать параметр
командной строки
#include  //CRT с его printf и puts (не говоря уже о cout) мы, к сожалению,
потеряли, поэтому придётся использовать средства ОС

int main(void) 
{
    return 0;
}

void Main()
{
    WriteConsoleA(GetStdHandle(STD_OUTPUT_HANDLE), "Hello, World!\n", 14, nullptr,
nullptr);
}

Кстати, у меня эта программка занимает 656 байт после того, как я немного похимичил
с ключами компиляции.


Ответ 6

#include

class hello {
    public:
        hello(){ std::cout << "Hello, world!\n"; }
} put;

int main(){
    return 0;
}


Ответ 7

#include 

const std::ostream& out = std::cout << "Hello World" << std::endl;


Ответ 8

Помимо многих предложенных ранее вариантов с выводом текста до выполнения main, предложу
вариант с выводом после выполнения main:

#include 
#include 

void hw() {
    puts("Hello world");
}

int v = atexit(hw);

int main() {
    return 0;
}


Ответ 9

gcc поддерживает атрибут "constructor", который помещает функцию в init-секцию ELF-файла.
Что, в свою очередь, означает, что эта функция вызовется перед функцией main. То есть,
то, что нам нужно.

void __attribute__((constructor)) init {
  printf("Hello world!");
}


Ответ 10

$ cat hellower.cpp 
#include "helper.cpp"
int main(void) {
        return 0;
}


второй файл:

$ cat helper.cpp 
#include 

int hello_helper() {
        printf("Hello World\n");
        return 0;
}

static int a = hello_helper();


Лаунч:

$ g++ hellower.cpp
$ ./a.out 
Hello World


Ответ 11

Первый файл (строго соответствует условию задачи):

$ cat main.cpp
int main(void)
{
    return 0;
}


Второй файл:

$ cat hello.cpp
#include 

int hello_helper() {
    printf("Hello World\n");
    return 0;
}

static int a = hello_helper();


Makefile для компилятора g++:

$ cat makefile
TARGET = hello
PREFIX = /usr/local/bin
.PHONY: all clean install uninstall
all: $(TARGET)
clean:
    rm -f $(TARGET) *.o
main.o: main.cpp
    g++ -c -o main.o main.cpp
hello.o: hello.cpp
    g++ -c -o hello.o hello.cpp
$(TARGET): main.o hello.o
    g++ -o $(TARGET) main.o hello.o
install:
    cp $(TARGET) $(PREFIX)/$(TARGET)
uninstall:
    rm -f $(PREFIX)/$(TARGET)


Ответ 12

Вот в стиле C++

#include 

class StaticOutput
{
    static int print();
    static int out;
};

int StaticOutput::out = StaticOutput::print();

int StaticOutput::print()
{
    std::cout << "Hello World!" << std::endl;
    return 0;
}


int main()
{
    return 0;
}

самый короткий перебор паролей

#соревнование

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

Ответы

Ответ 1

Haskell, 25 символов

g s l=forM [1..l]$const s
g s l=forM [1..l] (\x->s) -- альтернативный вариант


Здесь параметр s - строка-алфавит, l - требуемая длина.

Для работы нужен модуль Control.Monad

Функция forM рекурсивно проходит по Traversable структуре и применяет функцию, возвращающую
монаду, к каждому элементу, после чего "собирает" внутри монады структуру, состоящую
из результатов функции.

Структура тут - список. Монада - тоже список (монада-список отвечает за перебор всех
вариантов).

Таким образом, происходит следующее:


Берется список индексов от 1 до l (l - требуемая длина пароля)
Каждому индексу сопоставляется набор вариантов (он задан как const s - то есть номер
индекса игнорируется и набор вариантов будет s независимо от индекса)
Варианты каждого индекса комбинируются в порядке исходного списка - и получается
список всех возможный строк длины l


Ответ 2

119 символов

IEnumerableF(char[]s,int l){return--l<0?new string[]{""}:from r in F(s,l)join
c in s on 0 equals 0 select r+c;}




IEnumerable F(char[] s, int l)
{
  return --l < 0
    ? new string[] { "" }
    : from r in F(s, l) join c in s on 0 equals 0 select r + c;
}


Чтобы можно было задавать задержку:

IEnumerable F(char[] s, int l, int t)
{
  foreach (var r in F(s, l))
  {
    Thread.Sleep(t);
    yield return r;
  }
}


Проверка:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ruSO_519441___Перебор
{
  class Program
  {
    IEnumerable F(char[] s, int l)
    {
      return --l < 0
        ? new string[] { "" }
        : from r in F(s, l) join c in s on 0 equals 0 select r + c;
    }

    static void Main(string[] args)
    {
      int i = 0;

      foreach (var s in (new Program()).F("01234567".ToCharArray(), 4))
        if (Convert.ToInt32(s, 8) != i++)
          throw new Exception();

      Console.WriteLine(i);
      Console.ReadKey();
    }
  }
}


Ответ 3

Javascript ES6, 113 символов

(s,l)=>eval(`${t="for(q of s)".repeat(l,l=[]).replace(/q/g,(q,i)=>q+i)}l.push(${t.match(/q\d+/g).join('+')})`)&&l


PS: Раз уж появился F#, пусть и JS будет :)


Ответ 4

Haskell, 42 символа

g s 0=[""];g s l=do{x<-g s$l-1;y<-s;[y:x]}


Развернутый вариант, для понимания:

gen :: [Char] -> Int -> [String]
gen chars 0 = return ""
gen chars len = do
  x <- gen chars (len-1)
  y <- chars
  return $ y:x

main = print $ gen ['a', 'b', 'c'] 3


Ответ 5

71 82 92 символа

Версия на F#:

let rec p (l:char seq)=function
|0->seq{yield[]}
|k->seq{for s in p l (k-1) do for c in l->c::s}


Это, конечно, не C#, но тоже .NET, так что можно использовать с программами на C#.

Тестовый код:

[]
let main argv = 
    p ['a'; 'b'; 'c'] 4
       |> Seq.map (fun arr -> new string(arr |> List.toArray))
       |> Seq.iter (printfn "%A")
    0


Развёрнутое состояние:

let rec combinations allowed = function
    | 0 -> seq { yield [] }
    | k -> seq { for s in combinations allowed (k-1) do for c in allowed -> c::s }




Типовыводитель рулит, укоротил:

let rec p l=function
|0->seq{yield[]}
|k->seq{for s in p l (k-1)do for c in l->c::s}




По совету @PetSerAl, можно уложить в одну строку:

let rec p l=function 0->seq{yield[]}|k->seq{for s in p l (k-1)do for c in l->c::s}




Можно сэкономить ещё пару символов, если перейти к спискам:

let rec p l=function 0->[[]]|k->[for s in p l (k-1)do for c in l->c::s]


Ответ 6

Ruby, 45 символов



->a, n{a.repeated_permutation(n).map(&:join)}


Функция (лямбда/проц), принимает массив  символов и число, возвращает последовательность
(перечислитель, генератор, Enumerator) перестановок его элементов с повторениями.

Но есть беда: он не ленивый (из-за .map(&:join)) и на сколько-нибудь больших входных
данных он сожрёт всю память и упадёт. Но требований к этому не ставилось :)

Починить этот досадный недостаток можно всего за $9.99 +5 символов:

->a, n{a.repeated_permutation(n).lazy.map(&:join)}




                        вот так ^^^^^


Ответ 7

r 38 символов

do.call(paste0,expand.grid(rep(s,l)))


где s-массив символов которые можно использовать,
l-длина

Пример :

s=list(letters[1:3])
l=2
do.call(paste0,expand.grid(rep(s,l)))
[1] "aa" "ba" "ca" "ab" "bb" "cb" "ac" "bc" "cc"

Обратить последовательность массива без reverse в 30 символов

#javascript #массивы #алгоритм #соревнование

Друзья, привет! Нужен коллективный разум. 

Второй день бьюсь с задачей. Необходимо написать функцию reverse без использования
Array.prototype.reverse() в 30 символов. Дошел до такого варианта, и похоже это мой
предел в знаниях JS. (Такой вариант не подходит так как solution.length > 30) 

let reverse=a=>[...a].map(a.pop,a)


Если кратко, [...a] - создает копию массива, мы проходимся по каждому элементу с
помощью map и при помощи cb функции a.pop, с контекстом a, возвращаем обратную последовательность
массива а. 

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

Ответы

Ответ 1

Можно использовать sort. Суть в том, что функция сравнивает два значения за счет
compareFunction, которую можно указать. И если в compareFunction возвращается 1, то
элементы меняются местами. Вот отсюда можно и плясать. То есть в итоге не сравнивать
элементы, а просто тупо всегда возвращать 1. Ну и так как нам не нужно сравнивать элементы,
то и во входных данных их (аргументы) опускаем



let reverse=a=>a.sort(a=>1); // 29
// let reverse=a=>a.sort(a=>1); // 28 - даже так работает

let myArray = [1, 5, 88, 3, 0, -666];
console.log(reverse(myArray));

Наиболее эффективный код парсинга строки в целое число

#java #соревнование

Часто приходится пАрсить строку в целое число, типа:

public static int string2Int(String s, int defaultValue) {
    int i=defaultValue;
    try {
        i=Integer.parseInt(s);
    }
    catch(Exception ex) {
    }
    return i;
}


Код хорош всем, за исключением, того, что Exception, как известно, дорогой процесс.

Так вот вопрос: кто предложит наиболее эффективный (в смысле ресурсов и скорости)
способ парсинга строки в int? Строка содержит число в десятичном исчислении (никаких
hex/bin/octal) - возможно и отрицательное. Если строка содержит дробное число, то дробная
часть откидывается. 

Условия: метод принимает 2 параметра: строка и значение по умолчанию - никаких Exception
не выкидывается. При ошибке парсинга возвращается значение по умолчанию.

Update

В итоге есть 3 способа, условно классический (в самом вопросе), метод прямого парсинга
в инкарнации @АртемКоновалов и удаленный способ через Apache Commons предложенный @LiashenkoV.

Я составил небольшой тест, который генерирует 50 тыс. случайных строк, 1/3 строка
типа int, 1/3 строка double, 1/3 строка портится внесением случайных символов. Получились
следующие цифры:

ClassicParser - 300 мс.
ArtemParser - 100 мс.
ApacheParser - 200 мс.

    

Ответы

Ответ 1

Получилось такое решение:   

public static long getNumber(String value, long defaultValue) {
    if (value == null)
        return defaultValue;

    value = value.trim();
    if (value.length() == 0)
        return defaultValue;

    final char[] chars = value.toCharArray();
    final char delimiter = DecimalFormatSymbols.getInstance().getDecimalSeparator();

    final boolean isNegative;
    if (chars[0] == '-' || chars[0] == '+') {
        if (chars.length == 1 || chars[1] == delimiter)
            return defaultValue;
        else
            isNegative = chars[0] == '-';
    } else if (isDigit(chars[0]))
        isNegative = false;
    else
        return defaultValue;


    final int radix = 10;
    boolean isFloat = false;
    long result = 0;

    for (int i = isDigit(chars[0]) ? 0 : 1; i < chars.length; i++) {
        char currentSymbol = chars[i];
        if (currentSymbol == delimiter)
            if (isFloat)
                return defaultValue;
            else
                isFloat = true;

        if (currentSymbol != delimiter && !isDigit(currentSymbol))
            return defaultValue;

        if (!isFloat) {
            long intermediateResult = result * radix + parse(currentSymbol);
            if (isOverflow(result, intermediateResult))
                return defaultValue;
            else
                result = intermediateResult;
        }
    }

    return isNegative ? -result : result;
}

private static boolean isOverflow(long prev, long current) {
    return prev != 0 && Math.signum(prev) != Math.signum(current);
}

private static boolean isDigit(char symbol) {
    return '0' <= symbol && symbol <= '9';
}

private static int parse(char symbol) {
    return symbol - '0';
}


Тест:

@Test
public void test() {
    final int defaultValue = 10;
    assertEquals(0, getNumber("0", 10));
    assertEquals(1, getNumber("1", 10));
    assertEquals(-1, getNumber("-1", 10));
    assertEquals(420, getNumber("0420", defaultValue));
    assertEquals(142, getNumber("142", defaultValue));
    assertEquals(-72, getNumber("-72", defaultValue));
    assertEquals(19, getNumber("+19", defaultValue));
    assertEquals(-19, getNumber("-19.11", defaultValue));
    assertEquals(19, getNumber("+19.16", defaultValue));
    assertEquals(defaultValue, getNumber("+19+.16", defaultValue));
    assertEquals(defaultValue, getNumber("+1.9+16", defaultValue));
    assertEquals(defaultValue, getNumber("1.1.16", defaultValue));
    assertEquals(defaultValue, getNumber("+.", defaultValue));
    assertEquals(defaultValue, getNumber(".", defaultValue));
    assertEquals(defaultValue, getNumber("+.0", defaultValue));
    assertEquals(defaultValue, getNumber(Long.MAX_VALUE + "0", 10));
    assertEquals(defaultValue, getNumber(Long.MIN_VALUE + "0", 10));
}

Напечатать символ N раз подряд

#bash #соревнование

Нужно напечатать в bash символ N раз подряд - максимально короткой командой.
    

Ответы

Ответ 1

Думаю, что короче не получится:

printf '=%.s' {1..100}


P.S. Украдено отсюда.


Ответ 2

myprint.sh:

for i in seq (1 $1)
do
   printf "$2"
done
printf "\n"


Использовать bash myprint.sh 10 x //напечатать x 10 раз
Можно, как у @kff: 

printf "$MYCHAR%.s" $(seq $COUNT)

В {1..N} у меня переменную вставить не получилось.

printf "=%.s" $(sec 100)


Да, у меня на 2 символа длиннее, чем у @Nick. Но для N=99, будет уже на 1)


Ответ 3

Ровно на символ короче, чем в ответе kff, 21 символ =)

printf '=%.s' {0..99}


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

printf "=%.s"$z{0..99}


Два варианта с заменой символов, первый придумал сам, второй позаимствовал.

printf %100s | sed 's/ /=/g' #28
printf %100s | tr " " "="    #25


Ещё один интересный вариант, работает не во всех шеллах, зато 21 символ.

repeat 100 printf "="


На большинстве ОС, где есть bash, есть и python:

python -c "print '='*100" #25

Напечатать символ N раз подряд

#bash #соревнование

Нужно напечатать в bash символ N раз подряд - максимально короткой командой.
    

Ответы

Ответ 1

Думаю, что короче не получится:

printf '=%.s' {1..100}


P.S. Украдено отсюда.


Ответ 2

myprint.sh:

for i in seq (1 $1)
do
   printf "$2"
done
printf "\n"


Использовать bash myprint.sh 10 x //напечатать x 10 раз
Можно, как у @kff: 

printf "$MYCHAR%.s" $(seq $COUNT)

В {1..N} у меня переменную вставить не получилось.

printf "=%.s" $(sec 100)


Да, у меня на 2 символа длиннее, чем у @Nick. Но для N=99, будет уже на 1)


Ответ 3

Ровно на символ короче, чем в ответе kff, 21 символ =)

printf '=%.s' {0..99}


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

printf "=%.s"$z{0..99}


Два варианта с заменой символов, первый придумал сам, второй позаимствовал.

printf %100s | sed 's/ /=/g' #28
printf %100s | tr " " "="    #25


Ещё один интересный вариант, работает не во всех шеллах, зато 21 символ.

repeat 100 printf "="


На большинстве ОС, где есть bash, есть и python:

python -c "print '='*100" #25

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

#алгоритм #любой_язык #соревнование #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 раза дольше, чем решение задачи
о рюкзаке. При этом, мы можем отдавать ответы итеративно.

Код из звёздочек

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

Как использовать это в качестве кода?

**       *****  **
 **     **  ** **
  **   **   ****
   ** **    ** **
    ***     **  **
                 **
********************
*********************


Приветствуются оригинальные решения. Вариант с наибольшим числом голосов побеждает.



function getAnswers(questionId, answer_filter, page) {
  return jQuery.ajax({
    url: '//api.stackexchange.com/2.2/questions/' + questionId + '/answers?page='
+ page + '&pagesize=100&order=desc&sort=activity&site=ru.stackoverflow&filter=' + answer_filter,
    method: "get",
    dataType: "jsonp",
    crossDomain: true
  }).then(function(data) {
    if (data.has_more) {

      return getAnswers(questionId, answer_filter, page + 1).then(function(d) {
        return data.items.concat(d.items);
      })
    }
    return data.items;
  });
}

function getAuthorName(e) {
  return e.owner.display_name
}

function process(items) {

  return items.map(function(item) {
    var matched = item.body.match(/\s*(.+?)\s*<\/h/);
    if (matched) {
      return {
        lang: matched[1],
        count: item.score,
        link: item.share_link,
        author: getAuthorName(item)

      };
    } else {
      return {
        lang: "N/A",
        count: "N/A",
        link: item.share_link,
        author: getAuthorName(item)
      }
    }
  });
}

function sort(items) {
  return items.sort(function(a, b) {
    return b.count - a.count;
  })
}

function fillTemplate(sortedItems) {
  $('#leadership').append(sortedItems.map(function(item, index) {
    return $('').append($('').html(index + 1))
      .append($('').html(item.author))
      .append($('').html(item.lang))
      .append($('').html(item.count))
      .append($('').append($('').attr('href', item.link).text('Link')));
  }));
  return sortedItems;
}

var QUESTION_ID = 520257,
  ANSWER_FILTER = "!4*SyY(4Kifo3Mz*lT",
  startPage = 1;
getAnswers(QUESTION_ID, ANSWER_FILTER, startPage)
  .then(process)
  .then(sort)
  .then(fillTemplate);
#leadership {
  border-collapse: collapse;
}
#leadership td,
#leadership th {
  padding: 5px;
}
#leadership th {
  text-align: center;
}

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

  

    

    
Автор
    
Язык
    
Счет
    

  




    

Ответы

Ответ 1

C++

http://ideone.com/JRY307

struct outputter { outputter operator*(); };

int main(int argc, char* argv[])
{
    outputter o;

    **       *****  **
     **     **  ** **
      **   **   ****
       ** **    ** **
        ***     **  **
                     **
    ********************
    *********************

    o;

    return 0;
}

#include 
#include 
#include 
#include 

using namespace std;

string text =
    "IF you happen to have read another book about Christopher Robin, "
    "you may remember that he once had a swan (or the swan had Christopher "
    "Robin, I don't know which) and that he used to call this swan Pooh. "
    "That was a long time ago, and when we said good-bye, we took the name "
    "with us, as we didn't think the swan would want it any more. "
    "Well, when Edward Bear said that he would like an exciting name all to himself, "
    "Christopher Robin said at once, without stopping to think, that he was "
    "Winnie-the-Pooh.";

istringstream iss{ text };
auto it = istream_iterator{ iss };

outputter outputter::operator*()
{
    cout << *it++ << " ";
    return *this;
}




Идея: объявим класс с оператором *, который будет возвращать сам объект. Таки образом,
можно вызывать оператор * сколько угодно раз подряд.

Чтобы объект делал что-нибудь полезное, возьмём текст из Винни-Пуха (string text
= ...), положим его в поток iss, и будем читать из потока итератором (istream_iterator)
(потоковое чтение строки читает одно слово за раз, так же, как и с cin, поэтому мы
фактически разбили текст на слова по пробелам). Каждый раз во время работы оператора
* выведем следующее слово и продвинем итератор.


Ответ 2

Clojure



'(**       *****  **
   **     **  ** **
    **   **   ****
     ** **    ** **
      ***     **  **
                   **
  ********************
  *********************)


А равно это... не поверите:

(** ***** ** ** ** ** ** ** ** **** ** ** ** ** *** ** ** ** ********************
*********************)


...это список из символов, которые используются для представления идентификаторов
в коде в виде данных (Clojure же лисп, помните?). И идентификаторы в Clojure имеют
довольно безумную свободу в именовании. Да, они вполне могут состоять из звёздочек!

Если бы в начале не было кавычки, оно бы попыталось разрешить в значения идентификаторы
*****, **, ********************, *********************, *** и ****, не смогло бы (ведь
их нет), и упало бы. Но можно их определить:

(let [** (fn [& args]) ; функция, принимает любое число аргументов и не делает ничего
                       ; но это моя реализация, в ней можно что-нибудь и сделать
                       ; ** надо быть чем-то функциеподобным, ведь он будет вызван
      ...] ; ...и остальные тоже нужно определить, хоть nil'ами
  (**       *****  **
    **     **  ** **
     **   **   ****
      ** **    ** **
       ***     **  **
                    **
   ********************
   *********************))




Ну и совсем неинтересный случай:

(comment
   **       *****  **
     **     **  ** **
      **   **   ****
       ** **    ** **
        ***     **  **
                     **
    ********************
    *********************)


Это nil. Ну, comment это макрос, схлопывающийся в nil. Вот его реализация:

(defmacro comment
  "Ignores body, yields nil"
  {:added "1.0"}
  [& body]) ; после объявления списка аргументов *ничего нет*


Это не совсем комментарий, в привычном смысле, в форме comment должен быть синтаксически
правильный код, иначе форма окажется некорректной и выполнение упадёт. Но этот символ
вполне себе корректный Clojure-код!.. ну, без определений.

Макросами, возможно, из него можно сделать что-то интересное.


Ответ 3

Perl

Данным логотипом можно немножечко напугать, если наложить его поверх perl-скрипта:

main.pl:

use strict;
use warnings;
use utf8;

use Ohlabishch;
use re 'eval';

**************************************
*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*
*****''=~('(*****?{**'.**('[^@._['.***
***'**|~{+]**].-%@]**@**?+__'^********
***'+**,)@**+{^?[_$****}]@@,>('.******
***'^@**~**}').'})'** **);;;;;;;;;****
***;;;;***;;;;;;;;;**;;**;;;;;;;;;****
***;;;;;;;;;;;;;;;;;;;; **;;;;;;;;****
***;;;;********************;;;;;;;****
***;;;;*********************;;;;;;****
***;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;****
*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;**
**************************************


Ohlabishch.pm:

package Ohlabishch;

use strict;
use warnings;

use Filter::Simple sub { s/\*//g };

1;




Как работает эта мешанина из символов?

Шаг 1. Подключаем модуль Ohlabishch, в задачи которого входит удалить все символы
из исходного таким.

Без них этот код примет вид:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
''=~('(?{'.('[^@._['.
'|~{+]].-%@]@?+__'^
'+,)@+{^?[_$}]@@,>('.
'^@~}').'})' );;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;; ;;;;;;;;
;;;;;;;;;;;
;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


Шаг 2. Добавим пустую операцию ;, которая опять же ничего не делаем. Без неё, код
имеет вид (последнюю ; оставим всё-таки):

''=~('(?{'.('[^@._['.
'|~{+]].-%@]@?+__'^
'+,)@+{^?[_$}]@@,>('.
'^@~}').'})' );


Шаг 3. Выполним соединения строк, там где это возможно и запишем всё в одну строку:

'' =~ ( '(?{' . ( '[^@._[|~{+]].-%@]@?+__' ^ '+,)@+{^?[_$}]@@,>(^@~}' ) . '})' );


Шаг 4. Рассмотрим внимательно строку:

'[^@._[|~{+]].-%@]@?+__' ^ '+,)@+{^?[_$}]@@,>(^@~}'


Несмотря на её устрашающий вид, задача у неё весьма простая, посимвольно применить
операцию xor для данных двух строк. Т.е:

perl -E 'say "["^"+"'
p

perl -E 'say "^"^","'
r


и т.д. В итоге мы получим строку вида: print "A ty smelchak!"

Шаг 5. На данный момент код преобразуется в:

'' =~ ( '(?{' . ( 'print "A ty smelchak!"' ) . '})' );


Шаг 6. Убираем лишние скобки и символы соединения строк, таким образом получая задуманный код:

'' =~ ( '(?{ print "A ty smelchak!" })' );


Что это такое? Это просто "регулярное выражение", которое применяется к пустой строке.
Само же регулярное выражение это форма "(?{ code })", которая позволяет выполнять код
в данном регулярном выражении. По умолчанию оно отключено, и чтобы его подключить нужно
добавить в программу строку: use re 'eval'. Вот и всё!


Ответ 4

C++

http://ideone.com/VpcGQz

int main() {

**       *****  **
 **     **  ** **
  **   **   ****
   ** **    ** **
    ***     **  **
                 **
********************
*********************

main;}


Ответ 5

C++

int main(int argc, const char * argv[])
{
    cout << R"(
**       *****  **
 **     **  ** **
  **   **   ****
   ** **    ** **
    ***     **  **
                 **
********************
*********************
)";
}

Код-гольф - Создание генератора кода для печати строк в 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)

Как сделать, чтобы (x==1 && x==2 && x==3 && x==4) возвращало true?

Сегодня задали весёлый вопрос по C++ - как добиться, чтобы 

(x==1 && x==2 && x==3 && x==4) 


имело значение true?
    

Ответы

Ответ 1

Навскидку - сразу два варианта: переопределить оператор == или оператор приведения. Оператор && сам по себе - вряд ли, только вкупе с каким-то из перечисленных...

Вот, примерно так - https://ideone.com/XM7O1s:

struct Cast
{
    int i;
    operator int() { return i++; }
    Cast(int i):i(i){}
};

struct Equl
{
    bool operator==(int) const { return true; }
};


Можно, конечно, извратиться - типа сравнение с конкретно 1,2,3 и 4 дает true, н
это уже сути дела не меняет...


Ответ 2

Примерно так

class X {
    public:
    bool operator==(int other) {
        return true;
   }
}

x = X();


Ответ 3

В рамках возможностей, предоставляемых С++, вопрос в таких условиях тривиален и неинтересен.

Что уж там мелочиться

template 
bool operator ==(const L &, const R &)
{
  return true;
}


Всем, всегда и везде сплошное true... (Не всем, не всегда и не везде, конечно, но идея понятна.)

А далее хоть

struct {} x;


хоть 

enum { x };




Вариант даже для С может выглядеть как

static int i;
#define x (++i)


Ответ 4

Еще вариант с перегрузкой operator== для типа, который не может сравниваться с int:

#include 
#include 

template
bool operator==(T&&, int)
{
    return true;
}

int main()
{
    std::string x;
    std::cout << (x==1 && x==2 && x==3 && x==4) ;
}


Ответ 5

Вот такой вариант работает:

int x = 0;
#include 
#define x (++x)
using namespace std;
int main()
{
    cout<<(x==1&&x==2&&x==3&&x==4)<
Ответ 6

Препроцессор:

#define x true || 0


Пример


Ответ 7

Сегодня задал эту задачу своему другу, он, методом научного тыка, нашёл ещё одн
странное решение:

#include  
#define x 1,2,3,4

int main()
{
    if (x == 1 && x == 2 && x == 3 && x == 4)
        puts("cheater!");
}

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

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

Имеется двумерный массив 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

Как так сокращают код?

Решал задачи на acmp.ru, и в самой простой задаче, где надо просто считать и вывест
число, в рейтинге есть решение вполовину короче моего(всего лишь 35 сим.)! Это читерство или волшебство?
Ну как можно придумать решение короче этого?

#include 
int main()
{
    int a;
    std::cin >> a;
    std::cout << a;
} // 59 символов


На этом сайте самые лучшие решения те, которые самые короткие.
    

Ответы

Ответ 1

Так как педантичной "стандартности" и "определенности поведения" С кода не требуется
завязываясь на особенности компилятора GCC в его конфигурации по умолчанию можно сократить код до

main(){char*gets(),b[9];puts(gets(b));}


http://coliru.stacked-crooked.com/a/bf02104f47ad8b3c

(по мотивам ответа @vegorov). Памятуя, однако, что функции gets в стандартной библиотеке формально больше нет.

Можно даже совсем грубо, ибо длина входной строки по условию не превосходит 3 (
предположении о том, что ведущие нули в записи чисел не допускаются), а тип int в GCC имеет размер 4

main(){int*gets(),b;puts(gets(&b));}


http://coliru.stacked-crooked.com/a/c64f32776b7fa150

а также

b;*gets();main(){puts(gets(&b));}


http://coliru.stacked-crooked.com/a/e92785b2be0324a6

Это уже 33 символа.



А на 32-битной платформе (т.е. на платформе, где размер указателя совпадает с размеро
типа int) можно даже обойтись и без объявления gets, хотя это будет уже совсем грубым, наглым и грязным хаком

b;main(){puts(gets(&b));}


К сожалению, онлайновых компиляторов GCC c библиотеками для -m32 я не нашел. Только https://godbolt.org/z/j3Ye9u . 

Однако если переменная b окажется расположенной в той области 64-битного адресног
пространства, где старшие 32 бита адреса являются нулевыми, то такой код с высокой долей вероятности будет работать и на 64-битной X86 платформе: http://coliru.stacked-crooked.com/a/b70346370d1f08f6


Ответ 2

#include 
main()
{
    char b[9];
    puts(gets(b));
}


48 символов. Следовал советам из статьи Сокращение кода на C++ для acmp.ru


Ответ 3

Вот немного короче. 

#include 
int main()
{
    std::cout << std::cin.rdbuf();
}


Радикальный вариант на С89:

main(){system("cp INPUT.TXT OUTPUT.TXT");}


online compiler


Ответ 4

С и POSIX read/write 

    avp@avp-ubu1:hashcode$ cat golf.c
    main(){char s[4]; write(1, s, read(0, s, 4));}
    avp@avp-ubu1:hashcode$ wc golf.c
     1  7 47 golf.c
    avp@avp-ubu1:hashcode$ gcc golf.c -Wno-implicit-function-declaration -Wno-implicit-int
    avp@avp-ubu1:hashcode$ echo 123 | ./a.out
    123
    avp@avp-ubu1:hashcode$ 


С потерей остатков читабельности легко сокращается до 40 символов:

main(){int s;write(1,&s,read(0,&s,4));}

Update

По подсказке @pavel в комментарии получилось 35!!! (и что характерно, без warnings -), и оказалось достаточно флажка -w)

avp@avp-ubu1:hashcode$ gcc golf.c  -w
avp@avp-ubu1:hashcode$ cat golf.c
s; main(){write(1,&s,read(0,&s,4));}
avp@avp-ubu1:hashcode$ 


Спасибо, @pavel



b;main(){puts((read(0,&b,4),&b));}

пользуясь подсказками из всех ответов и комментариях
 -- 34 (!) символа

Как ни странно gcc -w компилирует вообще без ругани, а ./a.out работает -)

Code golf: Flatten с вставкой дополнительного элемента

Обновление: обсуждение завершено, результаты в конце текста вопроса.



Обсуждение вопроса ведётся в чате «Code golf на русском».



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

Пример: пусть исходные данные таковы:

1; 2; 3; 4; 5 // 1 кусок
6; 5; 4; 3    // 2 кусок
              // 3 кусок пустой
-3; -3; -3    // 4 кусок


Тогда результирующая последовательность должна быть

1; 2; 3; 4; 5;   5.5;    6;  5;  4;  3;      0;      -3; -3; -3
// 1-ая часть  (5 + 6)/2  2-ая часть     (3 + -3)/2    4-я часть


Ограничения:


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


Код на C#, реализующий подобное, может быть таким:

IEnumerable FlattenWithInsertedValues(IEnumerable> seqs)
{
    double? firstAddend = null;
    foreach (var seq in seqs)
    {
        double? lastInThisSeq = null;
        foreach (var v in seq)
        {
            if (firstAddend != null)
            {
                yield return (firstAddend.Value + v) / 2;
                firstAddend = null;
            }
            yield return v;
            lastInThisSeq = v;
        }
        if (lastInThisSeq != null)
            firstAddend = lastInThisSeq;
    }
}


Этот код откровенно прямолинеен, некрасив и императивен. Существует ли более изящно
решение? Любители функциональных языков, разумеется, получают в данном вопросе фору на старте, т. к. в остальных ленивые последовательности не встроены в язык.

Приветствуются красивые решения, не обязательно короткие. Дополнительный плюс з
правильную обработку пустых кусков.

Поскольку гольф, пожалуйста, одно решение на ответ. Если есть разные решения, постите отдельным ответом.



Для того, чтобы было легче тестировать код, вот тесты на C#:

void Test1()
{
    var result = FlattenWithInsertedValues(TestGenerator1());
    foreach (var v in result)
        Console.Write(v + " ");
}

void Test2()
{
    var result = FlattenWithInsertedValues(TestGenerator2());
    Console.Write(result.Count());
}

IEnumerable> TestGenerator1()
{
    Console.Write("Generating outer seq 1 ");
    yield return Generator(1, 5, 1);
    yield return Generator(1, 0, 2);
    yield return Generator(1, 3, 3);
}

IEnumerable> TestGenerator2()
{
    Console.Write("Generating outer seq 2 ");
    yield return Generator(1, 5, 1);
    yield return Generator(1, 10000000000000, 2);
}

IEnumerable Generator(double from, double to, int seqNum)
{
    Console.Write($"Generating seq #{seqNum} ");
    for (double curr = from; curr < to; curr += 1)
        yield return curr;
}


Они выдают:

Test1:


  Generating outer seq 1 Generating seq #1 1 2 3 4 Generating seq #2 Generating seq #3 2,5 1 2


Test2:


  Generating outer seq 2 Generating seq #1 Generating seq #2


Второй тест может очень долго (я не дождался результата своего), но не должен падать по переполнению памяти.



Результаты:


Приз зрительских симпатий однозначно достаётся @avp, который показал, что генераторы
ленивость и функциональные фишки вполне реализуемы на таком близком к металлу языке как C, и не ограничены функциональными языками.
Решения @Qwertiy (ES6), @D-side (Ruby), @tonal (Python), @pavel (C++) по сути повторяю
идею из исходного вопроса, хотя и в более изящной форме. Эти решения также заслуженно получили высокие оценки.
Прекрасная алгоритмическая идея с энумерацией придумана @kmv (F#) и повторно реализован
@tonal (Python) и ещё раз @tonal (теперь Haskell). Мне кажется, решения, основанные на этой идее, остались недооценёнными.
Отдельной строкой идут решения с паттерн-мэтчингом на Хаскеле (@tonal, @Pavel Mayorov
снова @tonal) и Clojure (@D-side), которые выглядят неожиданно просто и легко (за счё
сложности реализации самого паттерн-мэтчинга для ленивых последовательностей). Это, пожалуй, самые правильные решения в смысле простоты и понятности кода. Поэтому самое популярное решение из них принято в качестве ответа.

(Как оказалось, паттерн-мэтчинг ленивых последовательностей есть и в F#, но решения с ним никто не предложил.)
Ещё красивая идея — явный конечный автомат на Clojure (@D-side). LISP показал, что он ещё может.
Ещё была реализация на языке Julia, которая, к сожалению, удалена автором решения.


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

Ответы

Ответ 1

На Haskell, втупую:

flatten :: [[Float]] -> [Float]
flatten [] = []
flatten [y] = y
flatten ([]:xs) = flatten xs
flatten (y:[]:xs) = flatten $ y:xs
flatten ([y]:(yy:ys):xs) = y : (y + yy)/2 : flatten ((yy:ys):xs)
flatten ((y:ys):zs:xs) = y : flatten (ys:zs:xs)

main = do
  let ls = [[1, 2, 3, 4, 5], [6, 5, 4, 3], [-3,  -3, -3]]
  print ls
  let fs = flatten ls
  print fs


Здесь используется сопоставление с образцами. Варианты следующие:


flatten [] = [] - На пустой список возвращаем пустой же.
flatten [y] = y - Во входном списке ровно 1 элемент - его и возвращаем.
flatten ([]:xs) = flatten xs - Входящий список начинается с пустого. Пропускаем его, а к хвосту xs применяем flatten.
flatten (y:[]:xs) = flatten $ y:xs - Во входном списке второй элемент пустой. Пропускаем его, а к списку из головы и хвоста y:xs применяем flatten.
flatten ([y]:(yy:ys):xs) = y : (y + yy)/2 : flatten ((yy:ys):xs) - В головном списк
остался 1 элемент y. Отдаём список из него, его среднего арифметического с первым элементом второй последовательности и хвостом полученным применением flatten к списку из второй последовательности и хвоста (yy:ys):xs.
flatten ((y:ys):zs:xs) = y : flatten (ys:zs:xs) - В головном списке несколько элементов. Выдаём список из первого y и применения flatten к остатку ys:zs:xs.


Ответ 2

Вспомним истоки *nix -- "все есть файл" и напишем на Си

#include 
#include 
#include 

#define DBLRead(fd, d)  (read(fd, d, sizeof(double)) == sizeof(double))
#define DBLWrite(fd, d) (write(fd, d, sizeof(double)) == sizeof(double))

int
flatten (int n, int in[], int out)
{
  int i, j, rc = 0;
  double d0 = NAN, d;

  for (i = 0; !rc && i < n; close(in[i++])) 
    for (j = 0; !rc && DBLRead(in[i], &d); j++) {
      if (!isnan(d0) && j == 0) {
        double m = (d0 + d) / 2;
        if (!DBLWrite(out, &m)) {
          rc = EX_IOERR;
          break;
        }
      }
      if (!DBLWrite(out, &d))
        rc = EX_IOERR;
      d0 = d;
    }


  close(out);
  return rc;
}


Проверка тоже не слишком длинная 

#include 
#include 
#include 

#include 
#include 
#include 
#include 

int
generate (int p[2], double from, int step, int n)
{
  if (fork()) {
    close(p[1]);
    return p[0];
  }

  int i, rc = 0;

  for (i = 0; i < n; i++, from += step)
    if (!DBLWrite(p[1], &from)) {
      rc = EX_IOERR;
      break;
    }

  exit(rc);
}

#define A_SIZE(a) (sizeof(a) / sizeof(a[0]))

int
main (int ac, char *av[])
{
  int p1[2], p2[2], p3[2], p4[2], res[2];
  if (pipe(p1) || pipe(p2) || pipe(p3) || pipe(p4) || pipe(res))
    err(EX_OSERR, "pipes");
  int gen_input[4] = {
    generate(p1, 1.0, 1, 5),
    generate(p2, 6.0, -1, 4),
    generate(p3, 1.0, 1, 0),
    generate(p4, -3.0, 0, 3)
  };

  if (!fork()) 
    exit(flatten(A_SIZE(gen_input), gen_input, res[1]));
  close(res[1]);

  double r = 0;
  while(DBLRead(res[0], &r) || (puts(""), 0))
    printf("%g ", r);

  pid_t pid;
  int s;
  while ((pid = wait(&s)) > 0)
    if (!WIFEXITED(s) || WEXITSTATUS(s))
      printf("pid: %d rc = %d\n", (int)pid, WEXITSTATUS(s));

  return puts("End") == EOF;
}


Ответ 3

Javascript ES6

function *f(g) {
  for (var x of g) {
    for (var y of x) {
      if (l === +l) { 
        yield (l+y)/2;
        l = '';
      }
      yield y;
    }
    var l = y;
  }
}


Тест:

for (var x of f([[1,2,3,4,5], [6,5,4,3], [], [-3,-3,-3]])) {
  console.log(x);
}


Что необычного тут используется?


ES6 вводит функции-генераторы: function *f(g) { с их yield.
Переменные, объявленные при помощи var видны во всей функции, что позволяет использовать y вне цикла и l раньше var l
l === +l - значение строго равно себе же, приведённому к числу. Это означает, чт
оно число. Тут отсеиваются начальное undefined и последующие пустые строки (некая дань гольфу - '' символа короче чем что-то ещё).


Ответ 4

Идея решение на С++, написал аналог итератора.

FLOAT next(){
static FLOAT prev = NAN;
static bool isFirst = false;
static Seq local = GLOBAL.next();
if (!local)      
    return null; //end result seq
if (isFirst)     //it's first elem in seq so we read it before
    isFirst = false; 
    return prev;    
} 
FLOAT temp = local.next();
if (!temp){ //if we read current seq
    local = GLOBAL.next();
    if (!local)      //we read all seq
        return null; //end result seq
    FLOAT tmp = prev;
    prev = local.next();
    if (!prev){      //if empty seq 
        prev = NAN;
        local = GLOBAL.next(); //go next seq
        return NAN;
    }
    isFirst = true; // we read first elem need save it
    return (prev + tmp)/2;
}
return prev = temp;
}


Ответ 5

ruby Обычный генератор на Enumerator::Lazy и несколько тестиков. Принимает что угодно, что внутри имеет Enumerable, с элементами, имеющими Enumerable.

def inter_means(sequences)
  Enumerator.new do |y|
    last_inserted = nil
    sequences.lazy.each do |seq|
      first = true
      seq.lazy.each do |element|
        if first && last_inserted
          y << (element + last_inserted) / 2.0
          last_inserted = nil
        end
        first = false
        y << element
        last_inserted = element
      end
    end
  end
end
# ---------------- ----------------
# Далее код для тестов

# Поток чисел из stdin (изначально не ленивый!)
stdin_number_stream = Enumerator.new do |y|
  number = ""
  STDIN.each_char.lazy.each do |c|
    if c =~ /\d/
      number += c
    else
      y << number.to_i if number != ""
      number = ""
    end
  end
  # Когда поток закрыли, могло накопиться число
  y << number.to_i if number != ""
end

inputs = [ #       v-вот теперь ленивый
  [[], stdin_stream.lazy, [1]],
  [[*1..5], [*3..6].reverse, [], [-3, -3, -3]],
  [],
  [[], [], []],
  [[], [1, 2, 3], [], [-3, -2, -1], [], []]
]

inputs.each do |input|
  puts "  #{input.inspect}\n=> #{inter_means(input).to_a.inspect}"
end


Пример на ideone.com с печатью stdin в stdout наглядности ради.



  [[1, 2, 3, 4, 5], [6, 5, 4, 3], [], [-3, -3, -3]]
=> [1, 2, 3, 4, 5, 5.5, 6, 5, 4, 3, 0.0, -3, -3, -3]
  []
=> []
  [[], [], []]
=> []
  [[], [1, 2, 3], [], [-3, -2, -1], [], []]
=> [1, 2, 3, 0.0, -3, -2, -1]


Ответ 6

Ещё один вариант на Python-е:

from itertools import chain

def flatten(*lists):
  prev_i = -1
  prev_elt = None
  for i, elt in chain(*map(enumerate, lists)):
    if prev_i != i - 1:
      yield (prev_elt + elt) / 2
    yield elt
    prev_i = i
    prev_elt = elt

lst = [[1, 2, 3, 4, 5], [6, 5, 4, 3], [-3,  -3, -3]]
print(list(flatten(*lst)))
[1, 2, 3, 4, 5, 5.5, 6, 5, 4, 3, 0.0, -3, -3, -3]


Идея та же, что и в F#, но получилось несколько компактнее. :)

Здесь:


enumerate делает из последовательности пронумерованную
последовательность,
map - применяет enumerate ко всем переданным
последовательностям,
chain - сцепляет последовательности.
В цикле остаётся только проверить, что предыдущий и пекущий индексы не последовательны.


Да, здесь всё "лениво", т. е. элементами lists могут быть любые итераторы.


Ответ 7

На Python тоже вполне компактненько:

def flatten(*lists):
  prev = elt = None
  for lst in lists:
    for elt in lst:
      if prev is not None:
         yield (prev + elt) / 2
         prev = None
      yield elt
    prev = elt

lst = [[1, 2, 3, 4, 5], [6, 5, 4, 3], [-3,  -3, -3]]
print(list(flatten(*lst)))


Ровно то же, что и на C# в вопросе.
Как мне кажется, на любом императивном языке решение будет тоже, с точностью до синтаксиса. :)


Ответ 8

Решение не претендует на красоту кода, это скорее демонстрация идеи

clojure Автомат, также известный как машина состояний на функциях и трамплинах.

Состояния:


(initial S), когда элементы ещё не выдавались и оставшиеся последовательности лежат в S, это начальное состояние
(processed X C S), когда последним выдан X, от последовательности остался хвост C (может быть пустой), оставшиеся последовательности S
(junction X S), когда последовательность обработали и последним выданным был X, оставшиеся последовательности в S




(ns inter-means.core
  "Полный исполняемый пример описываемого решения"
  (require [clojure.test :refer [deftest testing is run-tests]]))

(defmacro =>
  "Макрос, разворачивающий переход автомата в указанное состояние:
 без аргументов завершает автомат, с одним аргументом вызывает
 немедленный переход, с двумя и более возвращает список указанных
 элементов с продолжением из указанного состояния"
  ([]
   ())
  ([state]
   `(fn [] ~state))
  ([element state]
   `(cons ~element (lazy-seq (trampoline ~@state))))
  ([element other & others]
   `(cons ~element (=> ~other ~@others))))

(defn inter-means
  "Функция, принимающая последовательность последовательностей и
 возвращающая ленивую последовательность их конкатенации через
 средние арифметические граничных элементов"
  [input-seqs]
  (letfn [(initial [[[head & tail :as current] & remainder :as inputs]]
            (cond head    (=> head
                              (processed head tail remainder))
                  current (=> (initial remainder))
                  :else   (=>)))
          (processed [last-inserted [head & tail :as current] remainder]
            (cond head  (=> head
                            (processed head tail remainder))
                  :else (=> (junction last-inserted remainder))))
          (junction [last-inserted [[head & tail :as current] & remainder :as inputs]]
            (cond head    (=> (/ (+ last-inserted head) 2)
                              head
                              (processed head tail remainder))
                  current (=> (junction last-inserted remainder))
                  :else   (=>)))]
    (trampoline initial input-seqs)))

(deftest spec
  (is (= (inter-means [[1 2 3 4 5] [6 5 4 3] [] [-3 -3 -3]])
         [1 2 3 4 5 11/2 6 5 4 3 0 -3 -3 -3]))
  (is (= (inter-means [])
         []))
  (is (= (inter-means [[] []])
         [])))

(run-tests)


Ответ 9

Решение на F#, в функциональном стиле, без использования его императивных возможностей (for, yield и т.д.):

UPD. Убраны лишние обращения к генератору.

UPD. Полностью ленивая реализация.

let flatten seqs =
    // нумеруем каждый элемент внутренней пос-ти его индексом
    let numbering = Seq.zip (Seq.initInfinite id) in
    // сливаем внутренние посл-ти
    let pairs = (Seq.map numbering >> Seq.concat) seqs in

    let folder (prev_i, prev_elem, _) (cur_i, cur_elem) =
        // если индексы текущего и предыдущего элементов не последовательны
        // значит, это граница, добавляем средний
        let is_bound = cur_i - prev_i <> 1 in
        let with_mean =
            if is_bound then [| (cur_elem + prev_elem) / 2.; cur_elem |]
            else [| cur_elem |] in
        (cur_i, cur_elem, Seq.ofArray with_mean) in

    let take_3rd = function | _, _, x -> x in
        (Seq.scan folder (-1, 0., Seq.empty)
            >> Seq.skip 1
            >> Seq.map take_3rd
            >> Seq.concat) pairs


Тесты:

[[1; 2; 3; 4; 5]; [6; 5; 4; 3]; []; [-3; -3; -3]]
    |> List.map (List.map float) |> List.map Seq.ofList |> Seq.ofList
    |> flatten
    |> List.ofSeq
    |> printfn "%A"

seq {
    printfn "Generating outer seq";
    yield seq { printfn "Generating inner seq 1"; yield 1.0; };
    yield seq { printfn "Generating inner seq 2"; yield 2.0; };
    yield seq { printfn "Generating inner seq 3"; yield 3.0; }
}
|> flatten
|> List.ofSeq
|> printfn "%A"


Результат:

[1.0; 2.0; 3.0; 4.0; 5.0; 5.5; 6.0; 5.0; 4.0; 3.0; 0.0; -3.0; -3.0; -3.0]
Generating outer seq
Generating inner seq 1
Generating inner seq 2
Generating inner seq 3
[1.0; 1.5; 2.0; 2.5; 3.0]


Ответ 10

А вот еще на Haskell, не настолько втупую как прошлое - но компактнее и (надеюсь) понятнее. На одну строку меньше, ну и сами строки короче.

flatten :: (Fractional a, Foldable l) => l [a] -> [a]
flatten = foldr concat' []
    where concat' [] y = y
          concat' (x:[]) (y:ys) = x : (x+y)/2 : ys
          concat' (x:xs) y = x : concat' xs y
          concat' x [] = x

main = print ls >> print (flatten ls)
    where ls = [[1, 2, 3, 4, 5], [6, 5, 4, 3], [], [-3,  -3, -3]]


Тут еще можно было бы concat' упростить при помощи функций init и last - но их совместное применение материализует список, что по условию недопустимо.

Кстати, тот факт что строчка concat' x [] = x стоит последней очень важен - без этог
входная последовательность окажется полностью материализована при попытке проверить все ее элементы на пустоту :)

Если кто-то решит начать подсчитывать символы - то вот минифицированная версия:

f = foldr c []
    where c [] y = y
          c (x:[]) (y:b) = x : (x+y)/2 : b
          c (x:a) y = x : c a y
          c x [] = x


Ответ 11

На Haskell-е реализация идеи с нумерацией:

flatten [] = []
flatten [y] = y
flatten lists = concat . append_end . map adder . zip xxs $ xs
  where
    xxs@(_:xs) = concat . map (zip [1..]) $ lists
    adder ((n, a), (m, b))
      | n + 1 == m = [(a, b)]
      | otherwise  = [(a, undefined), ((a + b) /2, b)]
    append_end [] = []
    append_end [x] = [map fst x, [snd $ last x]]
    append_end (x:xs) = map fst x : append_end xs



flatten [] = [] - Пустой вход - пустой выход.
flatten [y] = y - Единственный список - его и возвращаем.
Общий случай:
xxs@(_:xs) = concat . map (zip [1..]) $ lists - нумеруем подсписки map (zip [1..]) и собираем из них общий список xxs с хвостом xs.
zip xxs $ xs - Собираем список пар (текущий, следующий).
map adder - Преобразуем список с вычислением вставляемых элементов.
concat . append_end - собираем результат с добавлением последнего элемента из последней пары.


Ответ 12

clojure Pattern-matching не является частью языка, так что приходится брать core.match:

(ns inter-means.match
  (:require [clojure.core.match :refer [match]]))

(defn inter-means
  "Функция, возвращающая ленивую конкатенацию переданной последовательности
  последовательностей через средниые арифметические крайних элементов"
  ([input-seqs]
   (inter-means input-seqs nil false))
  ([input-seqs last-inserted junction?]
   (match input-seqs
      ([] :seq)
      ()

      ([([] :seq) & remainder] :seq)
      (recur remainder last-inserted (-> last-inserted nil? not))

      ([([head & tail] :seq) & remainder] :seq)
      (let [continuation
            (cons head (lazy-seq (inter-means
                                   (cons tail remainder)
                                   head
                                   false)))]
         (if junction?
           (cons (/ (+ head last-inserted) 2) continuation)
           continuation)))))


Ответ 13

Ну и свёртка, на Haskell:

flatten = fst . foldl adder ([], undefined)
  where
    adder x [] = x
    adder ([], _) xs = llist xs
    adder (ys, prev) [x] = (ys ++ [(prev + x)/2, x], x)
    adder (ys, prev) (x:xs) = let (lxs, lx) = llist xs
      in (ys ++ [(prev + x)/2, x] ++ lxs, lx)
    llist [x] = ([x], x)
    llist (x:xs) = let (ys, y) = llist xs in (x:ys, y)



flatten = fst . foldl adder ([], undefined) - результат функции есть первый элемент свёртки слева с применением функции adder и начальным значением ([], undefined)
adder x [] = x - если второй аргумент - пустой список, возвращаем первый.
adder ([], _) xs = llist xs - если первый элемент первого аргумента - пустой список, возвращаем кортеж из списка и его последнего элемента.
adder (ys, prev) [x] = (ys ++ [(prev + x)/2, x], x) - второй аргумент - список и
одного элемента x, возвращаем кортеж из дополненного списка из первого аргумента и элемента x.
adder (ys, prev) (x:xs) = let (lxs, lx) = llist xs
   in (ys ++ [(prev + x)/2, x] ++ lxs, lx) - общий случай. Возвращаем кортеж из дополненного списка из первого аргумента и последнего элемента xs.
llist - возвращает кортеж из списка и его последнего элемента. Нужна, чтобы не проходить список повторно last-ом.


Ответ 14

Может, кому понадобится на Java 8:

// Flattener.java:

import java.util.stream.Stream;

public class Flattener {
    private Double lastElement;
    private boolean isFirst;

    @SafeVarargs
    public final Stream flattenWithInsertedValues(final Stream... streams) {
        lastElement = null;
        return Stream.of(streams).flatMap(stream -> {
            isFirst = true;
            return stream.flatMap(x -> {
                Stream part;
                if (isFirst && lastElement != null)
                    part = Stream.of((lastElement + x) / 2.0, x);
                else part = Stream.of(x);
                isFirst = false;
                lastElement = x;
                return part;
            });
        });
    }
}


Проверка:

// Main.java:

import java.util.stream.Stream;

public class Main {

    public static void main(String[] args) {

        Stream s1 = Stream.of(1.0, 2.0, 3.0, 4.0, 5.0); // 1 кусок
        Stream s2 = Stream.of(6.0, 5.0, 4.0, 3.0);    // 2 кусок
        Stream s3 = Stream.empty(); // 3 кусок пустой
        Stream s4 = Stream.of(-3.0, -3.0, -3.0);    // 4 кусок

        Stream all = (new Flattener()).flattenWithInsertedValues(s1, s2, s3, s4);
        all.forEach(System.out::println);
    }
}