Страницы

Поиск по вопросам

понедельник, 25 ноября 2019 г.

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

Комментариев нет:

Отправить комментарий