Sort by Multiplying

You should write a program or function that given a list of positive integers multiplies each element with the smallest positive integer possible to create a strictly increasing list.

For example if the input is

5 4 12 1 3

the multiplications will be

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

and the output will be the increasing list

5 8 12 13 15

Input

• A list of positive integers containing at least 1 element

Output

• A list of positive integers

Examples

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

This is code golf so the shortest program or function wins.

Fun fact: the last element of the output for the input N, N-1, ... ,1 seems to be the (N+1)th element of the sequence A007952. If you find a proof, you are welcomed to include it in your golf answer or post it as a comment.

• has anyone made ground on that proof yet? – Connor Clark Feb 10 '16 at 22:53

Jelly, 6 5 bytes

:‘×µ\

First Jelly answer before @Dennis wakes up and beats me. Try it online!

Explanation

:          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

Thanks to @Dennis for -1 byte.

• :‘×µ\ saves a byte. – Dennis Feb 9 '16 at 15:53
• @Dennis Oh shit he woke up – Dennis van Gils Feb 9 '16 at 18:29

JavaScript (ES6), 28

Edit As suggested by @Patrick Roberts, p can be a uninitialized parameter. Same byte count but avoid using a global variable

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

TEST

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

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

;[
[, [ 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,k=t,r=f(i),ok=(k+'')==(r+'')
console.log(i + ' => ' + r + (ok?' OK':'FAIL expecting '+x))
})
<pre id=O></pre>

• I think you can save a few bytes by using modulo, just like I did in my answer. – aross Feb 9 '16 at 16:31
• Can't you skip the p=0? You need it to run it multiple on multiple lists but the question is just for a single list – Charlie Wynn Feb 9 '16 at 16:34
• @CharlieWynn if you don't initialize a variable you get the error for undefined variable. If by chance the variable already exists (that could easily happen in the environment of a web page), it could have any wrong value. – edc65 Feb 9 '16 at 17:47
• @edc65 sure enough, p is already defined on this page! – Charlie Wynn Feb 9 '16 at 17:52
• @PatrickRoberts thinking again, I could still avoid globals: f=a=>a.map(n=>a+=n-a%n,a=0). But it's not my algorithm (silly me) so I'll keep mine as is and upvote aross – edc65 Feb 10 '16 at 20:19

Python 2, 67 64 bytes

First try at code-golfing, so tips are appreciated.

def m(l):
for x in range(1,len(l)):l[x]*=l[x-1]/l[x]+1
print l
• Hi, I think you're counting the line returns as 2 bytes each (using Windows?), but on this site you count each line return as a single byte. So your score is actually 65 bytes. (You can copy and paste your code into mothereff.in/byte-counter if you're not sure.) Also, you can do print l instead of return l to save another byte. Nice job! – mathmandan Feb 10 '16 at 15:52
• Thanks, I didn't know about the line returns. That explains why I've always got different byte counts. And I didn't even consider, that printing is sufficient and it doesn't have to return the list. – Taronyu Feb 10 '16 at 20:34
• No problem! BTW, since you mentioned that "tips are appreciated", you might be interested in browsing through codegolf.stackexchange.com/questions/54/… . Enjoy! – mathmandan Feb 12 '16 at 17:11

PHP, 554642 41 bytes

Uses ISO 8859-1 encoding.

for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß; Run like this (-d added for aesthetics only): php -d error_reporting=30709 -r 'for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;' 10 10 8
• Saved 1 byte thx to Ismael Miguel.
• Saved 8 bytes by using modulo instead of floor
• Saved 4 bytes thx to Ismael Miguel (for instead of foreach)
• Saved a byte by using to yield a space.
• I think that you can replace $a+0 with +$a. Also, you can assume that the input will never have a 0, so, you can replace your $a+0&&print with simply +$a&print. In fact, you could even do $a&print, since in PHP "0" == 0 == 0.0 == false. But it may not be needed if you just use an echo, I think. – Ismael Miguel Feb 9 '16 at 15:56 • Binary and won't work (as opposed to logical), nor will echo work in this way. Since I'm taking input from CLI, the first argument is -, which I wanna catch instead of printing a zero. Try php -r 'print_r($argv);' foo. Saved 1 byte with your first suggestion though, thx. – aross Feb 9 '16 at 16:09
• unnamed function are allowed by default an scanl1(...) is an unnamed function. Regarding $vs. (): you're right, my mistake. – nimi Feb 9 '16 at 17:11 C++, 6360 57 bytes void s(int*f,int*e){for(int c=*f;++f!=e;c=*f+=c/ *f**f);} Works inplace given a range [first, last). Originally written as template variant, but that was longer: template<class T>void s(T f,T e){for(auto c=*f;++f!=e;c=*f+=c/ *f**f);} Extended version 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; } } CJam, 13 bytes q~{\_p1$/)*}*

Input as a CJam-style list. Output is linefeed separated.

Test it here.

Explanation

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. }* The final value is left on the stack and printed automatically at the end. Mathematica, 36 32 bytes #2(Floor[#1/#2]+1)&~FoldList~#& Test #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}} *) Perl, 17 + 3 = 20 bytes$p=$_*=$==1+$p/$_

Requires -p and -l flags:

$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 Explanation: # '-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/$_

Python (3.5), 63 62 bytes

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

Test

>>> print('\n'.join([str(i)+' => '+str(f(i)) for i in [,[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]]]))
 => 
[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]

Previous solution

some recursive solutions but larger

(68 bytes) f=lambda a,i=0:[i,*f(a[1:],a*(i//a+1))][i==0:]if a!=[]else[i]
(64 bytes) f=lambda a,i=0:a>[]and[i,*f(a[1:],a*(i//a+1))][i<1:]or[i]
• Also instead of r+=[…], you can use r+=…, – Cyoce Feb 10 '16 at 22:05
• @Cyoce i make changes but when i defined r= in default parameter r become nonlocal – Erwan Feb 11 '16 at 7:05
• you're right, I forgot how Python handled default params. The other tip should work though – Cyoce Feb 11 '16 at 7:26
• @Cyoce yes it works thanks for tips – Erwan Feb 11 '16 at 7:38

Brachylog, 12 bytes

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

Weird enough trying to multiply each variable by a number will start at trying to multiply by 2 and not 0 or 1. This seems to work though and beats both other Brachylog implementations

Explanation

{       }ᵐ          --  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

Try it online!

Brachylog, 54 bytes

:_{h_.|[L:T],LhH,(T_,IH;0:$Ie*H=:T>I),Lb:I:1&:[I]rc.}. Explanation :_{...}. § 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]

Pyth, 11

t.u*Yh/NYQ0

Test Suite

Does a cumulative reduce, a reduce that returns all intermediate values, starting with 0. Since the input is guaranteed to contain only positive integers, this is ok. In each step, we take the old value, divide it by the new value and add 1, then we multiply by the new value.

C, 79 bytes

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);
}
• Wouldn't p=p/x*x+x work? – Neil Feb 9 '16 at 18:57
• @Neil Yeah, that would work. Definitely overthought this one :) – Cole Cameron Feb 9 '16 at 19:04

PowerShell, 26 bytes

$args|%{($l+=$_-$l%$_)} Takes input as an explicit array, e.g., > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1) via$args.

We then for-loop over that with |%{...} and each iteration perform magic. Nah, just kidding, we use the same modulo trick as other answers (props to @aross because I spotted it there first).

Try it here!

Explanation

nd                   Take number from input and duplicate it
?.               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
*        Multiply
d\$z     Duplicate and store in register
N    Output as number

Essentially, the register keeps the latest member of the ascending list and this is divided by the input and incremented to get the multiplier for the next member. The toroidal feature of Minkolang's code field means that it loops horizontally without the need for () or [] loops.

Brachylog, 21 bytes

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

Try it online!

Uses the sum of input values as the upper bound for coefficients C. Pretty slow, times out on TIO for input list lengths beyond 5 or 6 (also depending on the sum of the values). But not as slow as my original version, which requires tiny lists of upto 3 elements, with tiny values, to not time out:

21 bytes

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

Try it online!

C (gcc), 37 bytes

o(int*_){for(;*++_;)*_*=_[~0]/ *_+1;}

Try it online!

Python 2, 53 bytes

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

Try it online!

k*x>y implies k>y/x; so the smallest k can be is k=floor(y/x)+1. Since in Python 2.7, integer division is already taken as floor, we want k=y/x+1, and k*x = (y/x+1)*x = y/x*x+x.

Oracle SQL 11.2, 210 bytes

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;

Chez Scheme (140 Bytes)

Golfed Version:

(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))

Ungolfed Version:

(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)
)

Try it Online!

• * m(car l) can be *(car l)m. – Jonathan Frech Aug 6 '18 at 8:52

{y*1+_x%y}\

Try it online!