Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
has anyone made ground on that proof yet? – Hoten Feb 10 at 22:53

18 Answers 18

up vote 19 down vote accepted

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.

share|improve this answer
4  
:‘×µ\ saves a byte. – Dennis Feb 9 at 15:53
16  
@Dennis Oh shit he woke up – Dennis van Gils Feb 9 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], [ 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>

share|improve this answer
    
I think you can save a few bytes by using modulo, just like I did in my answer. – aross Feb 9 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 at 16:34
1  
@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 at 17:47
    
@edc65 sure enough, p is already defined on this page! – Charlie Wynn Feb 9 at 17:52
1  
@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 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
share|improve this answer
    
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 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 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 at 17:11

PHP, 55 46 42 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.
share|improve this answer
    
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 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 at 16:09
1  
How about for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,' ';? It is 42 bytes long and skips the first element. – Ismael Miguel Feb 9 at 16:36
    
Nice one, thx @IsmaelMiguel – aross Feb 9 at 16:44
    
You're welcome. If you want to be really kinky, you can replace the space with a^A, but that would spill too many warnings (warnings are ignorable). It won't change the bytecount in any way, but surelly looks different. – Ismael Miguel Feb 9 at 16:47

Haskell (30 28 25 bytes)

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

Expanded version

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)

Explanation

scanl1 enables you to fold a list and accumulate all intermediate values into another list. It's a specialization of scanl, which has the following type:

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

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

Therefore, all we need is a suitable function that takes two the last element of our list (acc in the expanded version) and the one we wish to process (next in the expanded version) and return a suitable number.

We can easily derive this number by dividing the accumulator through the next one and flooring the result. div takes care of that. Afterwards, we simply have to add 1 to ensure that the list is actually increasing (and that we don't end up with 0).

share|improve this answer
    
No need to give your function a name. You can also replace the ( ... ) with $ ... and I think you've counted a final newline which can be omitted: scanl1$\x y->y*div x y+y, 24 bytes. – nimi Feb 9 at 16:30
    
@nimi: Really? Expressions count? That being said, I don't save any bytes with (...) vs $, since $\ gets parsed as operator and I would need a single space after $. – Zeta Feb 9 at 17:10
    
unnamed function are allowed by default an scanl1(...) is an unnamed function. Regarding $vs. (): you're right, my mistake. – nimi Feb 9 at 17:11

C++, 63 60 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;
    }
}
share|improve this answer

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.

share|improve this answer

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}} *)
share|improve this answer

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/$_
share|improve this answer

Python (3.5), 63 62 bytes

def f(a):
 r=[0]
 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 [[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]

Previous solution

some recursive solutions but larger

(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]
share|improve this answer
    
Also instead of r+=[…], you can use r+=…, – Cyoce Feb 10 at 22:05
    
@Cyoce i make changes but when i defined r=[0] in default parameter r become nonlocal – Erwan Feb 11 at 7:05
    
you're right, I forgot how Python handled default params. The other tip should work though – Cyoce Feb 11 at 7:26
    
@Cyoce yes it works thanks for tips – Erwan Feb 11 at 7:38

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.

share|improve this answer

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

PowerShell, 26 bytes

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

Takes input as an explicit array, e.g., > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1) via $args[0].

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

The encapsulating parens (...) ensure that the result of the math operation is placed on the pipeline, and thus output. If we left those off, nothing would be output since the $l variable is garbage-collected after execution finishes.

Example

PS C:\Tools\Scripts\golfing> .\sort-by-multiplying.ps1 @(8,9,1,5,4)
8
9
10
15
16
share|improve this answer

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]
share|improve this answer

Japt, 11 bytes

Uå@Y*-~(X/Y

Test it online!

How it works

          // 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
share|improve this answer

05AB1E, 11 bytes

Code:

R`[=sŽDŠ/ò*

Try it online!

Explanation:

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

Uses CP-1252 encoding.

share|improve this answer

Minkolang 0.15, 17 bytes

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

Try it here!

Explanation

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

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.

share|improve this answer

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;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.