Code golf: Flatten с вставкой дополнительного элемента
1,00
р.
Обновление: обсуждение завершено, результаты в конце текста вопроса.
Обсуждение вопроса ведётся в чате «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, которая, к сожалению, удалена автором решения.
Огромное спасибо всем, кто принимал участие в обсуждении и предлагал собственные решения! Надеюсь, участникам сайта будет настолько же приятно и поучительно читать ваши решения и комментарии, насколько и мне.
Ответ
Вспомним истоки *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
", (int)pid, WEXITSTATUS(s))
return puts("End") == EOF }
Обсуждение вопроса ведётся в чате «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, которая, к сожалению, удалена автором решения.
Огромное спасибо всем, кто принимал участие в обсуждении и предлагал собственные решения! Надеюсь, участникам сайта будет настолько же приятно и поучительно читать ваши решения и комментарии, насколько и мне.
Ответ
Вспомним истоки *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
", (int)pid, WEXITSTATUS(s))
return puts("End") == EOF }
