Обновление: обсуждение завершено, результаты в конце текста вопроса.
Обсуждение вопроса ведётся в чате «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);
}
}
Комментариев нет:
Отправить комментарий