Дополнение вверх ногами пирамиды ... ОБРАТНО!

22

Добавление пирамиды вверх ногами - это процесс составления списка чисел и последовательного их сложения, пока вы не достигнете одного числа.

При задании чисел 2, 1, 1происходит следующий процесс:

 2   1   1
   3   2 
     5

Это заканчивается в количестве 5.


ТВОЕ ЗАДАНИЕ

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

Новый дополнительный вызов : попробуйте сделать это меньше, чем O (n ^ 2)

ПРИМЕР

f([5, 2, 1]) => [2, 1, 1]
f([84,42,21,10,2]) => [4,7,3,8,2]

ПРИМЕЧАНИЕ. Пирамида вверх ногами никогда не будет пустой и всегда будет состоять только из положительных целых чисел.

хнычет
источник
6
Добро пожаловать в PP & CG! Эта задача достойна, хотя может быть улучшена. Я бы порекомендовал публиковать ваши задания в Песочнице, чтобы улучшить пост до того, как он будет размещен на главной странице
Тау
13
Свободное понимание того, что я не могу найти язык, на котором он короче:
f([a,b,c,d,e])=[1464101331001210001100001][abcde]
Линн
4
Просто к вашему сведению, это то же самое, что и ката CodeWars .
Ггорлен
6
@ggorlen я знаю. Я тот, кто сделал ката :)
хныкает
8
Try doing this in less than O(n)Разумеется, невозможно выделить массив размером n или изменить в нем O (n) элементов быстрее, чем сложность O (n)?
мое местоимение monicareinstate

Ответы:

17

JavaScript (ES6),  62 58 49  46 байт

Сохранено 3 байта благодаря @Oliver

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

f=a=>+a||f(a.map(n=>a-(a=n),a=a.shift()))+[,a]

Попробуйте онлайн!

комментарии

f = a =>              // f = recursive function taking the input list a[]
  +a                  // if a[] consists of a single positive integer:
                      //   stop recursion and return this integer
  ||                  // else:
    f(                //   do a recursive call to f:
      a.map(n =>      //     for each value n in a[]:
        a - (a = n),  //       yield the difference between the previous value and n
                      //       and update a to n
        a = a.shift() //       start by removing the first element and saving it in a
                      //       (because of the recursion, it's important here to reuse
                      //       a variable which is defined in the scope of f)
      )               //     end of map()
    )                 //   end of recursive call
    + [, a]           //   append the last entry from a[]
Arnauld
источник
@ Оливер, да
Лохматый
6

TI-BASIC, 54 байта

Ans→L₁:dim(L₁→dim(L₂:While 1-Ans:L₁(Ans→L₂(Ans:-ΔList(L₁→L₁:dim(Ans:End:L₁(Ans→L₂(Ans:L₂

Ввод - это список правой стороны треугольника Ans, как описано в задании.
Выход - верхний ряд указанного треугольника.

Примеры:

{5,2,1
         {5 2 1}
prgmCDGF19
         {2 1 1}
{84,42,21,10,2
 {84 42 21 10 2}
prgmCDGF19
     {4 7 3 8 2}

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

Другими словами,

2 1 1
 3 2
  5

будет выглядеть так:

5 2 1
 3 1
  2

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

Ans→L₁          ;store the input list in L₁
dim(L₁→dim(L₂   ;set the length of L₂ to the length of L₁
While 1-Ans     ;while the L₁'s length is not 1
L₁(Ans→L₂(Ans   ;set the last element of L₁ to the corresponding index in L₂
-ΔList(L₁→L₁    ;get the change in each element, then negate
                ; (elements are in descending order so the change in each
                ;  element will be negative)
                ; and store the resulting list in L₁
dim(Ans         ;leave the length of L₁ in "Ans"
End
L₁(Ans→L₂(Ans   ;set the element again
                ; (needed for final step)
L₂              ;leave L₂ in "Ans"
                ;implicit print of "Ans"

Примечание: TI-BASIC - это токенизированный язык. Количество символов не равно количеству байтов.

Тау
источник
4

Желе , 6 байт

ṚIƬZḢṚ

Монадическая ссылка, принимающая список целых чисел, которая выдает список целых чисел.

Попробуйте онлайн!

Как?

Создает весь треугольник, затем извлекает необходимые элементы.

ṚIƬZḢṚ - Link: list of integers          e.g.  [84,42,21,10,2]
Ṛ      - reverse                               [2,10,21,42,84]
  Ƭ    - collect & apply until a fixed point:
 I     -   incremental differences            [[2,10,21,42,84],[8,11,21,42],[3,10,21],[7,11],[4],[]]
   Z   - transpose                            [[2,8,3,7,4],[10,11,10,11],[21,21,21],[42,42],[84]]
    Ḣ  - head                                  [2,8,3,7,4]
     Ṛ - reverse                               [4,7,3,8,2]
Джонатан Аллан
источник
Было почти идентичное решение, но с Us вместо !
Ник Кеннеди
IƬUZḢAбудет работать с данным вопросом тоже; Интересно, есть ли где-нибудь сохранение байта ...
Джонатан Аллан
ạƝƬZṪ€тоже работает но опять шестерка
Ник Кеннеди
Да, я заметил этот вариант; Теперь у меня меньше надежды.
Джонатан Аллан
Я только что опубликовал 5-байтовый код, но он немного отличается от вашего подхода к части после постройки пирамиды.
Эрик Аутгольфер
4

MathGolf , 14 11 байт

xÆ‼├│?;∟;]x

Попробуйте онлайн!

объяснение

x             reverse int/array/string
 Æ     ∟      do while true without popping using 5 operators
  ‼           apply next 2 operators to TOS
   ├          pop from left of list
    │         get differences of list
     ?        rot3
      ;       discard TOS (removes rest from ├ command)
              loop ends here
        ;     discard TOS (removes empty array from stack)
         ]    wrap stack in array
          x   reverse array
maxb
источник
3

Python 2 , 56 байт

f=lambda a:a and f([l-r for l,r in zip(a,a[1:])])+a[-1:]

Рекурсивная функция, принимающая список целых положительных чисел, которая возвращает список неотрицательных целых чисел.

Попробуйте онлайн!

Джонатан Аллан
источник
3

Желе , 5 байт

_ƝƬa/

Попробуйте онлайн!

Мы можем предположить, что вся пирамида положительна, поэтому мы можем использовать операцию && вместо «правильной» операции.

Эрик Аутгольфер
источник
3

Пари / ГП , 36 байт

Основываясь на комментарии @Lynn :

Бесплатная информация о том, что я не могу найти язык, на котором он короче:

е([a,б,с,d,е])знак равно[1-46-4101-33-1001-210001-100001][aбсdе]

Pari / GP имеет встроенную матрицу Паскаля, а ее обратная - это именно та матрица, которая нам нужна:

[1000011000121001331014641]-1знак равно[10000-110001-2100-13-3101-46-41]

a->r=Vecrev;r(r(a)/matpascal(#a-1)~)

Попробуйте онлайн!

alephalpha
источник
3

R , 69 67 байт

function(n,x=sum(n|1):1-1,`[`=outer)(x[x,choose]*(-1)^x[x,"+"])%*%n

Попробуйте онлайн!

Возвращает вектор столбца.

-2 байта благодаря Кириллу Л.

Также на основе комментария Линн :

Бесплатная информация о том, что я не могу найти язык, на котором он короче:

е([a,б,с,d,е])знак равно[1-46-4101-33-1001-210001-100001][aбсdе]

Это длиннее, чем другой ответ R, но это был интересный подход, чтобы взять и попробовать в гольф.

Giuseppe
источник
2

Javascript (ES6), 127 байт

f=a=>{for(e=[a],a=[a[l=a.length-1]],i=0;i<l;i++){for(e.push(g=[]),j=-1;j<l;)g.push(e[i][j]-e[i][++j]);r.unshift(g[j])}return r}

Оригинальный код

function f(a){
  var e=[a];
  var r=[a[a.length-1]];
  for (var i=1;i<a.length;i++){
    var g=[];
    for (var j=0;j<a.length;j++){
      g.push(e[i-1][j-1]-e[i-1][j]);
    }
    e.push(g);
    r.unshift(g[j-1]);
  }
  return r;
}

О, я потерял, как ... много ... к предыдущему ответу ...

Naruyoko
источник
2

05AB1E , 12 11 байт

R.¥.Γ¥}¨ζнR

Порт @JonathanAllan 's Jelly ответ , хотя я желе о более удобных встроенных функциях Jelly в этом случае. ;)
-1 байт благодаря @Emigna .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

R            # Reverse the (implicit) input-list
             #  i.e. [16,7,4,3] → [3,4,7,16]
           # Undelta it (with leading 0)
             #  → [0,3,7,14,30]
    }      # Continue until the result no longer changes, and collect all steps:
     ¥       #  Get the deltas / forward differences of the current list
             #  → [[3,4,7,16],[1,3,9],[2,6],[4],[]]
       ¨     # Remove the trailing empty list
             #  → [[3,4,7,16],[1,3,9],[2,6],[4]]
        ζ    # Zip/transpose; swapping rows/column (with space as default filler)
             #  → [[3,1,2,4],[4,3,6," "],[7,9," "," "],[16," "," "," "]]
         н   # Only leave the first inner list
             #  → [3,1,2,4]
          R  # Revert it back
             #  → [4,2,1,3]
             # (after which it's output implicitly as result)
Кевин Круйссен
источник
2
Вы можете сохранить байт с R.¥.Γ¥}¨помощью, начиная со списка, дельта которого является входным.
Эминья
@Emigna Ах, разверните цикл с дельтами, чтобы сохранить байт на предисловии. :) Благодарность!
Кевин Круйссен
2

Perl 6 , 37 байт

{[R,]($_,{@(.[]Z-.skip)}...1)[*;*-1]}

Попробуйте онлайн!

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

Объяснение:

{                                  }  # Anonymous code block
      $_,               ...   # Create a sequence starting from the input
         {             }      # Where each element is
            .[]Z-.skip          # Each element minus the next element
          @(          )         # Arrayified
                           1  # Until the list has one element left
 [R,]                                # Reverse the sequence
     (                     )[*;   ]  # For every list
                               *-1   # Take the last element
Джо Кинг
источник
1

Древесный уголь , 19 байт

Fθ«PI§θ±¹↑UMθ⁻§θ⊖λκ

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Fθ«

Цикл один раз для каждого термина в исходном списке.

PI§θ±¹↑

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

UMθ⁻§θ⊖λκ

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

Нил
источник
1

APL + WIN, 34 или 28 байт

v←⊂⌽⎕⋄1↓⌽↑¨⍎∊'v',(∊⍴¨v)⍴⊂',-2-/¨v'

Попробуйте онлайн! Предоставлено Dyalog Classic

Запрашивает правый боковой вектор.

или реализуя подход @ Линн:

0⍕⌽(⌹⍉n∘.!n←0,⍳¯1+⍴n)+.×⌽n←⎕

Попробуйте онлайн! Предоставлено Dyalog Classic

Запрашивает правый боковой вектор.

Грэхем
источник
1

Атташе , 29 байт

{y.=Delta@-_If[_,$@y'_@-1,y]}

Попробуйте онлайн!

Просто повторяет Deltaфункцию до тех пор, пока она не станет пустой. Гораздо короче самого многословного PeriodicStepsрешения ...

Конор О'Брайен
источник
1

C 76 байт

i=0;int*f(int*a,int n){for(;i<n;a[i++]=a[i]-a[i+1]);if(!n)return a;f(a,n-1);}  

вход : (*a = pointer to array, n = last element's index of that array)
выход :return int* = output

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

негольфированный (из C ++)

#include <iostream>
#define SIZE_F 5

int*recFind(int*a, int n) {
    int i = 0;
    while (i < n)
        a[i++] = a[i] - a[i+1];
    if (!n) return a;
        recFind(a, n - 1);
}
int main()
{
    int first[SIZE_F],*n;
    for (int i = 0; i < SIZE_F; i++)
        std::cin >> first[i];

    n = recFind(first, SIZE_F - 1);//size - 1
    for (int i = 0; i < SIZE_F; i++)
        std::cout << n[i];
}
Мукул Кумар
источник
1

Japt , 11 9 байт

Nc¡=äa
yÌ

Попытайся

2 байта сохранены благодаря Оливеру.

12 11 байт

_äa}hUÊN yÌ

Попытайся

1 байт сохранен благодаря Оливеру.

мохнатый
источник
2
9 байтов и 10 байтов
Оливер
@ Оливер, не думать о том, чтобы использовать, y(f)достаточно плохо, но совершенно забыть о новой строке непростительно! Скоро обновлю. Спасибо :)
Лохматый