Сортировать по умножению

34

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

Например, если вход

5 4 12 1 3

умножения будут

5*1=5 4*2=8 12*1=12 1*13=13 3*5=15

и вывод будет увеличивающимся списком

5 8 12 13 15

вход

  • Список натуральных чисел, содержащий хотя бы 1 элемент

Выход

  • Список целых положительных чисел

Примеры

9 => 9
1 2 => 1 2
2 1 => 2 3
7 3 => 7 9
1 1 1 1 => 1 2 3 4
5 4 12 1 3 => 5 8 12 13 15
3 3 3 8 16 => 3 6 9 16 32
6 5 4 3 2 1 => 6 10 12 15 16 17
9 4 6 6 5 78 12 88 => 9 12 18 24 25 78 84 88
8 9 41 5 12 3 5 6 => 8 9 41 45 48 51 55 60
15 8 12 47 22 15 4 66 72 15 3 4 => 15 16 24 47 66 75 76 132 144 150 153 156

Это код гольф, поэтому выигрывает самая короткая программа или функция.

Забавный факт: последний элемент вывода для входа N, N-1, ... ,1представляется (N+1)thэлементом последовательности A007952 . Если вы найдете доказательство, вы можете включить его в свой гольф-ответ или опубликовать в качестве комментария.

randomra
источник
кто-нибудь еще обосновал это доказательство?
Коннор Кларк

Ответы:

20

Желе , 6 5 байт

:‘×µ\

Первый ответ Jelly прежде, чем @Dennis просыпается и бьет меня. Попробуйте онлайн!

объяснение

:          Integer division, m//n
 ‘         Increment, (m//n+1)
  ×        Multiply, (m//n+1)*n
   µ       Turn the previous links into a new monadic chain
    \      Accumulate on the array

Спасибо @Dennis за -1 байт.

Sp3000
источник
4
:‘×µ\сохраняет байт.
Деннис
20
@ Деннис О, дерьмо, он проснулся
Деннис ван Гилс
9

JavaScript (ES6), 28

Редактировать По предложению @Patrick Roberts, pможет быть неинициализированным параметром. Тот же счетчик байтов, но избегайте использования глобальной переменной

(a,p)=>a.map(n=>p=n*-~(p/n))

ТЕСТ

f=(a,p)=>a.map(n=>p=n*-~(p/n))

console.log=x=>O.textContent+=x+'\n'

;[
[[9], [ 9]],
[[1, 2], [ 1, 2]],
[[2, 1], [ 2, 3]],
[[7, 3], [ 7, 9]],
[[1, 1, 1, 1], [ 1, 2, 3, 4]],
[[5, 4, 12, 1, 3], [ 5, 8, 12, 13, 15]],
[[3, 3, 3, 8, 16], [ 3, 6, 9, 16, 32]],
[[6, 5, 4, 3, 2, 1], [ 6, 10, 12, 15, 16, 17]],
[[9, 4, 6, 6, 5, 78, 12, 88], [ 9, 12, 18, 24, 25, 78, 84, 88]],
[[8, 9, 41, 5, 12, 3, 5, 6], [ 8, 9, 41, 45, 48, 51, 55, 60]],
[[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4], [ 15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),ok=(k+'')==(r+'')
  console.log(i + ' => ' + r + (ok?' OK':'FAIL expecting '+x))
})
<pre id=O></pre>

edc65
источник
Я думаю, что вы можете сэкономить несколько байтов, используя модуль, как я сделал в своем ответе .
aross
Не можете ли вы пропустить р = 0? Вам нужно запустить его несколько раз в нескольких списках, но вопрос только в одном списке
Чарли Уинн
1
@CharlieWynn, если вы не инициализируете переменную, вы получите ошибку для неопределенной переменной. Если случайно переменная уже существует (что может легко произойти в среде веб-страницы), она может иметь любое неправильное значение.
edc65
@ edc65, конечно, p уже определено на этой странице!
Чарли Уинн
1
@PatrickRoberts подумав еще раз, я все еще мог бы избежать глобальных f=a=>a.map(n=>a+=n-a%n,a=0). Но это не мой алгоритм (глупый я), так что я оставлю свой как есть и воздержусь от голосования
edc65
6

Python 2, 67 64 байта

Сначала попробуйте сыграть в гольф, так что советы приветствуются.

def m(l):
 for x in range(1,len(l)):l[x]*=l[x-1]/l[x]+1
 print l
Taronyu
источник
Привет, я думаю, что вы считаете, что возврат строки составляет 2 байта каждая (с использованием Windows?), Но на этом сайте вы считаете каждый возврат строки как один байт. Таким образом, ваш счет на самом деле составляет 65 байтов. (Вы можете скопировать и вставить свой код в mothereff.in/byte-counter, если вы не уверены.) Кроме того, вы можете сделать это print lвместо того, return lчтобы сохранить другой байт. Хорошая работа!
Матмандан
Спасибо, я не знал о возврате строки. Это объясняет, почему я всегда получаю разные байты. И я даже не считал, что печати достаточно и ей не нужно возвращать список.
Таронью
Нет проблем! Кстати, так как вы упомянули, что «советы приветствуются», вы можете быть заинтересованы в просмотре codegolf.stackexchange.com/questions/54/… . Наслаждайтесь!
Матмандан
5

PHP, 55 46 42 41 байт

Использует кодировку ISO 8859-1.

for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;

Запустите так ( -dдобавлено только для эстетики):

php -d error_reporting=30709 -r 'for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;' 10 10 8
  • Сохранено 1 байт, спасибо Исмаилу Мигелю.
  • Сохранено 8 байт с использованием модуля вместо пола
  • Сохранено 4 байта thx в Исмаэль Мигель (вместо вместо foreach)
  • Сохраненный байт, используя для получения пробела.
aross
источник
Я думаю, что вы можете заменить $a+0на +$a. Кроме того, вы можете предположить, что вход никогда не будет иметь 0, так что вы можете $a+0&&printпросто заменить его на +$a&print. На самом деле, вы могли бы даже сделать $a&print, так как в PHP "0" == 0 == 0.0 == false. Но это может не понадобиться, если вы просто используете echo, я думаю.
Исмаэль Мигель
Двоичный код andне будет работать (в отличие от логического) и не будет работать таким же образом. Поскольку я беру информацию из CLI, первый аргумент - это то -, что я хочу поймать вместо вывода нуля. Попробуй php -r 'print_r($argv);' foo. Сохранено 1 байт с первым предложением, спасибо.
aross
1
Как насчет for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,' ';? Он имеет длину 42 байта и пропускает первый элемент.
Исмаэль Мигель
Ницца один, ТНХ @IsmaelMiguel
aross
Пожалуйста. Если вы хотите быть действительно странным, вы можете заменить пробел на a^A, но это вылилось бы слишком много предупреждений (предупреждения игнорируются). Это никак не изменит байтаунта, но, безусловно, выглядит иначе.
Исмаэль Мигель
4

Haskell (30 28 25 байт)

scanl1(\x y->y*div x y+y)

Расширенная версия

f :: Integral n => [n] -> [n]
f xs = scanl1 increaseOnDemand xs
 where
   increaseOnDemand :: Integral n => n -> n -> n
   increaseOnDemand acc next = next * (1 + acc `div` next)

объяснение

scanl1позволяет вам свернуть список и собрать все промежуточные значения в другой список. Это специализация scanl, которая имеет следующий тип:

scanl  :: (acc  -> elem -> acc)  -> acc -> [elem] -> [acc]
scanl1 :: (elem -> elem -> elem) ->        [elem] -> [elem]

scanl1 f (x:xs) = scanl f x xs

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

Мы можем легко получить это число, разделив аккумулятор на следующий и получив результат. divзаботится об этом. После этого нам просто нужно добавить, 1чтобы убедиться, что список действительно увеличивается (и что мы не заканчиваем 0).

Zeta
источник
Не нужно давать имя вашей функции. Кроме того, можно заменить ( ... )с , $ ...и я думаю , что вы насчитали окончательную строку , которая может быть опущена: scanl1$\x y->y*div x y+y24 байта.
Ними
@nimi: Правда? Выражения рассчитывать? При этом я не сохраняю байты с (...)vs $, так $\ как анализируется как оператор, и после этого мне понадобится один пробел $.
Зета
безымянные функции разрешены по умолчанию и scanl1(...)являются неназванными функциями. Относительно $против (): ты прав, моя ошибка.
Ними
4

C ++, 63 60 57 байт

void s(int*f,int*e){for(int c=*f;++f!=e;c=*f+=c/ *f**f);}

Работает на месте с учетом диапазона [first, last). Первоначально написано как вариант шаблона, но это было дольше:

template<class T>void s(T f,T e){for(auto c=*f;++f!=e;c=*f+=c/ *f**f);}

Расширенная версия

template <class ForwardIterator>
void sort(ForwardIterator first, ForwardIterator last){
    auto previous = *first;

    for(++first; first != last; ++first){
        auto & current = *first;
        current += current * (current / previous);
        previous = current;
    }
}
Zeta
источник
3

CJam, 13 байтов

q~{\_p1$/)*}*

Ввод в виде списка в стиле CJam. Выход отделен переводом строки.

Проверьте это здесь.

объяснение

q~    e# Read and evaluate input.
{     e# Fold this block over the list (i.e. "foreach except first")...
  \   e#   Swap with previous value.
  _p  e#   Duplicate and print previous value.
  1$  e#   Copy current value.
  /   e#   Integer division.
  )*  e#   Increment and multiply current value by the result.
}*

Окончательное значение остается в стеке и печатается автоматически в конце.

Мартин Эндер
источник
3

Mathematica, 36 32 байта

 #2(Floor[#1/#2]+1)&~FoldList~#&

Тест

#2(Floor[#1/#2]+1)&~FoldList~#& /@ {{5, 4, 12, 1, 3}, 
   {15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4}}
(* {{5, 8, 12, 13, 15}, {15, 16, 24, 47, 66, 75, 76, 132, 144, 
  150, 153, 156}} *)
Джейсон Б.
источник
3

Perl, 17 + 3 = 20 байт

$p=$_*=$==1+$p/$_

Требуются -pи -lфлаги:

$ perl -ple'$p=$_*=$==1+$p/$_' <<< $'15\n8\n12\n47\n22\n15\n4\n66\n72\n15\n3\n4'
15
16
24
47
66
75
76
132
144
150
153
156

Объяснение:

# '-p' reads each line into $_ and auto print
# '-l' chomp off newline on input and also inserts a new line when printing
# When assigning a number to `$=` it will automatic be truncated to an integer
# * Added newlines for each assignment 
$p=
  $_*=
    $==
      1+$p/$_
andlrc
источник
3

Python (3,5), 63 62 байта

def f(a):
 r=[0]
 for i in a:r+=i*(r[-1]//i+1),
 return r[1:]

Тест

>>> print('\n'.join([str(i)+' => '+str(f(i)) for i in [[9],[1,2],[2,1],[7,3],[1,1,1,1],[5,4,12,1,3],[3,3,3,8,16],[6,5,4,3,2,1],[9,4,6,6,5,78,12,88],[8,9,41,5,12,3,5,6],[15,8,12,47,22,15,4,66,72,15,3,4]]]))
[9] => [9]
[1, 2] => [1, 2]
[2, 1] => [2, 3]
[7, 3] => [7, 9]
[1, 1, 1, 1] => [1, 2, 3, 4]
[5, 4, 12, 1, 3] => [5, 8, 12, 13, 15]
[3, 3, 3, 8, 16] => [3, 6, 9, 16, 32]
[6, 5, 4, 3, 2, 1] => [6, 10, 12, 15, 16, 17]
[9, 4, 6, 6, 5, 78, 12, 88] => [9, 12, 18, 24, 25, 78, 84, 88]
[8, 9, 41, 5, 12, 3, 5, 6] => [8, 9, 41, 45, 48, 51, 55, 60]
[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4] => [15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]

Предыдущее решение

некоторые рекурсивные решения, но больше

(68 bytes) f=lambda a,i=0:[i,*f(a[1:],a[0]*(i//a[0]+1))][i==0:]if a!=[]else[i]
(64 bytes) f=lambda a,i=0:a>[]and[i,*f(a[1:],a[0]*(i//a[0]+1))][i<1:]or[i]
Эрвана
источник
Также вместо r+=[…], вы можете использоватьr+=…,
Cyoce
@Cyoce я делаю изменения, но когда я определен r=[0]в параметре по умолчанию, rстановится нелокальным
Erwan
Вы правы, я забыл, как Python обрабатывает параметры по умолчанию. Другой совет должен работать, хотя
Cyoce
@Cyoce да, это работает, спасибо за советы
Erwan
3

Brachylog , 12 байт

{≤.;?%0∧}ᵐ<₁

Как ни странно, попытка умножить каждую переменную на число начнется с попытки умножения на 2, а не на 0 или 1. Это, кажется, работает, хотя и превосходит обе другие реализации Brachylog

объяснение

{       }ᵐ          --  Map each number
 ≤.                 --      to a number greater or equal to the original
  .;?%0             --      and a multiple of the original
       ∧            --      no more constraints
          <₁        --  so that the list is strictly increasing

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

Kroppeb
источник
2

Брахилог , 54 байта

:_{h_.|[L:T],LhH,(T_,IH;0:$Ie*H=:T>I),Lb:I:1&:[I]rc.}.

объяснение

:_{...}.                § Call sub-predicate 1 with [Input, []] as input. Unify its output
                        § with the output of the main predicate


§ Sub-predicate 1

h_.                     § If the first element of the input is an empty list, unify the
                        § output with the empty list
|                       § Else
[L:T],LhH,              § Input = [L,T], first element of L is H
    (T_,IH              §     If T is the empty list, I = H
    ;                   §     Else
    0:$Ie*H=:T>I),      §     Enumerate integers between 0 and +inf, stop and unify the
                        §     enumerated integer with I only if I*H > T
Lb:I:1&                 § Call sub-predicate 1 with input [L minus its first element, I]
:[I]rc.                 § Unify the output of the sub-predicate with
                        § [I|Output of the recursive call]
Fatalize
источник
2

Пиф, 11

t.u*Yh/NYQ0

Тестирование

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

FryAmTheEggman
источник
2

C, 79 байтов

p;main(x,v)char**v;{for(;*++v;printf("%d ",p=((x+p-1)/x+!(p%x))*x))x=atoi(*v);}

Ungolfed

p; /* previous value */

main(x,v) char**v;
{
    /* While arguments, print out x such that x[i] > x[i-1] */
    for(;*++v; printf("%d ", p = ((x+p-1)/x + !(p%x)) * x))
        x = atoi(*v);
}
Коул Камерон
источник
Не p=p/x*x+xсработает?
Нил
@ Нил Да, это сработало бы. Определенно обдумал этот :)
Коул Камерон
2

PowerShell, 26 байт

$args[0]|%{($l+=$_-$l%$_)}

Принимает ввод как явный массив, например, > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1)через $args[0].

Затем мы зациклимся на этом |%{...}и каждая итерация выполняет магию . Нет, просто шучу, мы используем тот же трюк по модулю, что и другие ответы (реквизит @aross, потому что я сначала заметил его там ).

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

пример

PS C:\Tools\Scripts\golfing> .\sort-by-multiplying.ps1 @(8,9,1,5,4)
8
9
10
15
16
AdmBorkBork
источник
1

Japt, 11 байт

Uå@Y*-~(X/Y

Проверьте это онлайн!

Как это работает

          // Implicit: U = input array of integers
Uå@       // Cumulative reduce: map each previous value X and current value Y to:
-~(X/Y    //  floor(X/Y+1).
          // Implicit: output last expression
ETHproductions
источник
1

05AB1E , 11 байт

Код:

R`[=sŽDŠ/ò*

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

Объяснение:

R            # Reverse input
 `           # Flatten the list
  [          # While loop
   =         # Print the last item
    s        # Swap the last two items
     Ž       # If the stack is empty, break
      D      # Duplicate top of the stack
       Š     # Pop a,b,c and push c,a,b
        /    # Divide a / b
         ò   # Inclusive round up
          *  # Multiply the last two items

Использует кодировку CP-1252.

Аднан
источник
1

Минколанг 0,15 , 17 байт

nd1+?.z0c:1+*d$zN

Попробуй это здесь!

объяснение

nd                   Take number from input and duplicate it
  1+                 Add 1
    ?.               Stop if top of stack is 0 (i.e., when n => -1 because input is empty).
      z              Push value from register
       0c            Copy first item on stack
         :           Pop b,a and push a//b
          1+         Add 1
            *        Multiply
             d$z     Duplicate and store in register
                N    Output as number

По сути, регистр хранит последний элемент в восходящем списке, и он делится на входные данные и увеличивается, чтобы получить множитель для следующего члена. Тороидальная особенность кодового поля Минколанга означает, что оно зацикливается по горизонтали без необходимости ()или []петель.

Эльендия Старман
источник
1

Брахилог , 21 байт

l~lCℕ₁ᵐ≤ᵛ~+?&;Cz≜×ᵐ<₁

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

Использует сумму входных значений в качестве верхней границы для коэффициентов C. Довольно медленно, тайм-аут на TIO для длины входного списка больше 5 или 6 (также в зависимости от суммы значений). Но не так медленно, как моя оригинальная версия, для которой требуются крошечные списки до 3 элементов с крошечными значениями, чтобы не истекло время ожидания:

21 байт

l~l.&+^₂⟦₁⊇.;?z/ᵐℕ₁ᵐ∧

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

sundar - Восстановить Монику
источник
1

Python 2 , 53 байта

lambda a:reduce(lambda b,v:b+[b[-1]/v*v+v],a,[0])[1:]

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

k*x>y подразумевает k>y/x ; так что самое маленькое kможет быть k=floor(y/x)+1. Поскольку в Python 2.7 целочисленное деление уже принято как floor, мы хотим k=y/x+1, и k*x = (y/x+1)*x = y/x*x+x.

Час Браун
источник
0

Oracle SQL 11.2, 210 байт

WITH v AS(SELECT TO_NUMBER(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))),c(p,n)AS(SELECT a,2 FROM v WHERE i=1UNION ALL SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n)SELECT p FROM c;

Un-golfed

WITH v AS                                           
(
  SELECT TO_NUMBER(COLUMN_VALUE)a, rownum i            -- Convert the input string into rows 
  FROM   XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))   -- using space as the separator between elements
)
, c(p,n) AS                        
(
  SELECT a, 2 FROM v WHERE i=1                         -- Initialize the recursive view
  UNION ALL 
  SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n       -- Compute the value for the nth element
)
SELECT p FROM c;
школа для водителей
источник
0

Схема Chez (140 байт)

Версия для гольфа:

(define(f l)(define(g l p m)(cond((null? l)l)((<(*(car l)m)(+ p 1))(g l p(+ m 1)))(else(cons(*(car l)m)(g(cdr l)(* m(car l))1)))))(g l 0 1))

Безголовая версия:

(define(f l)
  (define(g l p m)
    (cond
      ((null? l) l)
      ((< (* (car l) m) (+ p 1)) (g l p (+ m 1)))
      (else (cons (* (car l) m) (g (cdr l) (* m (car l)) 1)))
    )
  )
  (g l 0 1)
)

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

Захари Хлопок
источник
* m(car l)может быть *(car l)m.
Джонатан Фрех