Dwarves and Coins

Question

The Situation:

Several (M) dwarves have found a goblin's chest with N gold coins and have to divide them. Due to ancient rules governing the allocation of loot to pirates in order of seniority, the oldest dwarf should get one coin more than the next oldest dwarf, and so on, so that the youngest dwarf gets M-1 fewer coins than the oldest dwarf. Additionally, no dwarf has to pitch in any coins (ie no negative coins to any dwarfs)

Help the dwarves to divide the coins in this way, or tell them that this is impossible.

Winner's code must always answer correctly (this challenge is deterministic) and follow the general code-golf rules.

Input

You are given an integer N (3 ≤ N ≤ 1000) for number of coins and an integer M (3 ≤ M ≤ N) for number of dwarves, space-separated.

Output

If it is impossible to divide the coins in the way that dwarves want, print -1 (minus one). Otherwise, print the numbers of coins that each dwarf will receive, from oldest to youngest. Separate the numbers with spaces.

Samples:

input

3 3

output

2 1 0

input

9 3

output

4 3 2

input

7 3

output

-1

input

6 4

output

3 2 1 0

• Rawling: You missed a "pirate".
• Raystafarian: relevant
• ProgrammerDan: Good find, @Raystafarian. Perhaps when the teacher gets a general solver for M dwarves instead of just 3, s/he will recognize that the user crowdsourced the answer :) -- especially if that solver is in J.
• Level River St: Homework or not, its a Smurfing good question!

Answer 1

J - (削除) 32 (削除ここまで) (削除) 29 (削除ここまで) (削除) 28 (削除ここまで) 25

(削除) Not (削除ここまで) shorter than other J solution, (削除) but (削除ここまで) and uses a different idea

(]{.[:i:-:@-.@]-%)/ ::_1:

The answer for the number of coins the highest rank gnome is getting is simply N/M+(M-1)/2 (if it's an integer), we construct the negative of this -:@-.@]-%. Then i: makes an array like that 2 1 0 _1 _2 for argument _2 and we take M elements from it.

• algorithmshark: +1 for a brilliant usage of i:. You can save another three char by writing % instead of [%], and by using -.@] instead of (1-]).
• TheConstructor: Can't +1 as @swish seems to be with the gnomes we just robbed. ;)

Answer 2

J - 30 char

Very fun to golf. A lot of things worked out neatly.

((+/@s~i.[){ ::_1:s=.+/&i.&-)/

Explanation:

• / - Take the space-separated integers as argument, and slip the function between them. That is to say, consider N the left argument to the function in the brackets (...) and M the right argument.

• i.&- - Negate (-) and then take integers (i.). Normally, when you do something like i.5 you get 0 1 2 3 4. Whenever i. receives a negative number, however, it reverses that output list. So e.g. i._5 will give 4 3 2 1 0.

• s=.+/& - Perform the above action on each argument (&) and then make an addition table (+/) out of these arrays. We now have a table where each row is a possible coin distribution to M dwarves, though maybe not when there's N coins. Finally, this table-making verb is so useful we're going to call it s and use it again later.

• +/@s~ - Now, we use s again, but we swap (~) the order of the arguments, so that we transpose the table. This is a golfy way of taking the sum of each row after creating the table (+/@), having to do with the way J sums multidimensional lists.

• i.[ - In this list of sums, we search for the left argument to the verb, i.e. N. If N is an item, we get that index: else we get the length of the list, which notably is an invalid index.

• { ::_1: - Now we try to use the index to pull out a row from table in s. { will throw a domain error if the index was invalid, so in that case we catch the error (::) and return -1 (_1:). This handles everything. Since we use i.&- previously, the coin distribution will be in descending order, as was required.

Usage:

 ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 9 3
4 3 2
 ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 7 3
_1
 ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 6 4
3 2 1 0
 ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 204 17
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4

• ProgrammerDan: Input 9 3 should return 4 3 2, not -1. Seems there is a transposition in your example usage?
• algorithmshark: @ProgrammerDan Thanks, didn't catch that. I typed up the examples wrong. 9 3 gives 4 3 2 and 7 3 gives _1, as expected.
• ProgrammerDan: Saw the fix and +1'd appropriately :D. I should look into J, looks nifty.

Answer 3

R - (削除) 71 (削除ここまで) (削除) 70 (削除ここまで) (削除) 67 (削除ここまで) (削除) 66 (削除ここまで) 65 chars

s=scan();m=s[2];x=s[1]-sum(1:m);cat(if(x%%m|-m>x)-1 else x/m+m:1)

Ungolfed:

s = scan() # Reads N and M by stdin.
m = s[2]
x = s[1] - m*(m-1)/2
cat(if (x %% m | x < -m) -1 else x/m + m:1)

Solution:

If M the number of dwarfs, then the sequence of paid gold can be decomposed to two singular series. First a series ending in zero: M-1, ..., 2, 1, 0 and a constant series of c, c, ..., c. The sum of the first series is always M*(M-1)/2. So if the remainder (x = N - M*(M-1)/2) could be divided without remainder (modulo equal 0), each dwarf gets x/M plus the part of the decreasing series.

Usage:

> s=scan()
1: 10 4
3: 
Read 2 items
> m=s[2]
> x = s[1] - m*(m-1)/2
> cat(if (x %% m || x<0) -1 else x/m + (m-1):0)
4 3 2 1

• user80551: -1, the question requires to write a complete program and not a function. See meta.codegolf.stackexchange.com/a/1146/8766
• lambruscoAcido: @user80551 You are right. Now I corrected the snippet: now it takes the space-separated input; the output also does not show anymore the '[1]'.
• Brian Diggs: You can save another character replacing m*(m+1)/2 with sum(1:m)
• lambruscoAcido: @Brian Thx, I will modify my code!

Answer 4

PHP (187)

It's my first attempt at golfing, and I know it could be better, but still :)

Golfed:

<?php
$b=fgets(STDIN);list($c,$d)=explode(' ',$b);if((($d&1)AND($c%$d==0))OR($c%$d==$d/2)){for($e=floor($c/$d)+floor($d/2);$e>floor($c/$d)-round($d/2);$e--){echo"$e ";}}else{die('-1');}?>

Ungolfed:

<?php
$a = fgets(STDIN);
list($coins, $dwarves) = explode(' ', $a);
if ((($dwarves & 1) AND ($coins % $dwarves == 0)) OR ($coins % $dwarves == $dwarves / 2)) {
 for (
 $i = floor($coins / $dwarves) + floor($dwarves / 2);
 $i > floor($coins / $dwarves) - round($dwarves / 2);
 $i--
 ) {
 echo "$i ";
 }
}
else { 
 die('-1');
}
?>

Execute in a shell

Basic idea:

Coins can be separated by these rules, if one of these is true:

1. The dwarves are odd number, and the coins are divisible by the dwarves with no remains
2. The dwarves are even number, and the coins remaining after dividing coins / dwarves is equal to half of the dwarves number

If so, we take for base the average coins per dwarf (ACPD). But we have to start from the highest and output until we reach the lowest. So we make a loop with counter starting from ACPD + the count of the rest of the dwarves towards the higher end, and go on until we reach the ACPD - the count of the rest of the dwarves towards the lower end.

It's basically the same if the dwarves are odd (i.e. 5 dwarves - the middle one is 3, and in both ends there remain 2), but not if they are even - which is why we rely on floor AND round.

Problems so far: Works with too low coins number, which means some dwarves will be smacked down and robbed of their precious earnings. And this is sad. Or at least if you like dwarves.

Solution:

1. Think of a way to calculate the lowest amount of coins so the calculation doesn't end up with dwarves in the dust.
2. Design not-so-greedy dwarves.

Smarter solution:

Coins are metal. Make the dwarves melt them all, and then cast them in smaller/larger amount of coins, so they are divisible in any case.

Smartest solution:

Steal their mountain, rename yourself to Smaug and keep it all for yourself. After all, why do you have to bother with grumpy dwarves?

Answer 5

Python 3 (100)

Using the same idea as @Geobits but conforming to the input and output requirements.

n,m=map(int,input().split())
κ,ρ=divmod(n-m*(m-1)//2,m)
x=[-1]if ρ else range(κ,κ+m)[::-1]
print(*x)

• Geobits: Thanks for the heads-up. Didn't notice the space-separation added to the input reqs.
• Jonathan Frech: Those may be 100 characters, but because of the greek variable names, it requires 105 bytes.

Answer 6

Python 3 - (削除) 109 (削除ここまで) (削除) 107 (削除ここまで) (削除) 103 (削除ここまで) (削除) 102 (削除ここまで) (削除) 90 (削除ここまで) 93

Using the same idea as Evpok, but with a number of improvements.

n,m=map(int,input().split())
k=n/m+m/2
a=int(k)
print(*(range(a,a-m,-1),[-1])[k-a-.5or~a>-m])

The improvements are:

1. Eliminating the space after else and before ' '. 1 character
2. Eliminating the ' ' inside split(), because splitting on spaces is a default. 3 characters
3. Lowering x by 1 changing the -1 to +1 inside divmod, and then changing the range function to use the range's reversed order option. 3 characters.
4. EDIT: ... if ... else ... changed to ... and ... or ... 2 characters.
5. EDIT: Divmod made explicit, r removed. 4 characters.
6. EDIT: x removed, m//n used explicitly. 1 character
7. EDIT: used starred expressions instead of ' '.join(map(str,...)), added x to avoid repeating print(). 12 characters.
8. EDIT: I realized that I was allowing negative numbers of coins to be given to the Dwarves. I changed the code to avoid this.

• Evpok: Well done, it was instructive :) I changed my answer to strip the unnecessary space, but your trick to save the [::-1] is better than my solution. +1
• Jonathan Frech: I may be missing something, but I counted 93 bytes instead of 94.

Answer 7

Python 3 - 114

n,m=map(int,input().split(' '))
r=range(m);n-=sum(r)
if n%m<1:
 for x in r:print(m-x+n//m-1,end=' ')
else:print -1

Works by checking if N-(M*(M-1)/2) is evenly divisible by M. New to python, so any tips appreciated.

Ideone.com example

Input:
735 30
Output:
39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10

• Jonathan Frech: Was there ever a Python 3 version that supported Python 2's print statement style? Or how does the last line (else:print -1) not result in an error?

Answer 8

C# - 322

using System;using System.Linq;namespace D{class P{static void Main(string[]args){int n=Convert.ToInt16(args[0]);int m=Convert.ToInt16(args[1]);bool b=false;int q=n/2+1;g:b=!b;int[]z=new int[m];for(int i=0;i<m;i++){z[i]=q-i;}if(z.Sum()==n)foreach(int p in z)Console.Write(p+" ");else{q--;if(b)goto g;Console.Write(-1);}}}}

Horrible score but I took a different approach and got to use goto :)

I will shorten it later.

• Aaronaught: You can definitely shorten all of those Convert.ToInt16 calls to just int.Parse. You can declare any pre-assigned variable with var (instead of e.g. int[]). Your command-line params don't need to be called args. And you can alias frequently-used types like using C = Console. I also think that for a solution this long, it's better to present with line spacing intact rather than saving just a couple of characters. Oh, and I'm not really sure why goto is better than alternatives here, either...

Answer 9

Java 210

class A { public static void main(String[] a){int d=Integer.parseInt(a[0]),c=Integer.parseInt(a[1]);if (2*c%d==0) for (int i=0;i<d;i++) System.out.print((((1+(2*c/d)-d)/2)+i)+" "); else System.out.print(-1);}}

• user12205: Welcome to PPCG, I see you have a lot of whitespace which can be removed.
• ProgrammerDan: You can strip out a lot more spaces to golf your answer a bit further -- for instance, class A{public static void main(String[]a) is valid, and saves you 3 characters. After each if, and around each for, remove the whitespace ... etc.
• Rob Grant: It's crazy that the "public static void main(S" part is as long as that entire J solution :)

Answer 10

R: (削除) 77 (削除ここまで) (削除) 73 (削除ここまで) 70 chars

a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))

Create a vector going from (M-1) to 0 and adds 1 to each number until the sum is no longer inferior to N. If it is superior, output -1 else output the vector.

Indented and slightly ungolfed:

a=scan() #Reads in stdin (by default numeric, space-separated)
r=a[2]:1-1 #Creates vector (M-1) to 0
while(sum(r)<a[1])r=r+1 #Increments all member of vector by 1 until sum is not inferior to N
cat( #Outputs to stdout
 `if`(sum(r)>a[1], -1, r) #If superior to N: impossible, returns -1
 )

Example usage:

> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 9 3
3: 
Read 2 items
4 3 2
> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 7 3
3: 
Read 2 items
-1
> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 204 17
3: 
Read 2 items
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4

Answer 11

Julia, 45

f(n,m)=(x=n/m-m/2+1/2;x%1==0?[x+m-1:-1:x]:-1)
julia> f(6,4)'
1x4 Array{Float64,2}:
 3.0 2.0 1.0 0.0

Just a bit of algebra, took me way longer than it should have.

Answer 12

JavaScript - 76

Observe that k + (k - 1) + ... + (k - (M - 1)) = M(k - (M - 1)/2) Setting this equal to N gives k = N/M + (M-1)/2 for the highest amount. If this is integer, then k % 1 == 0 and the amounts we are looking for are k, k - 1, ..., k - (M - 1).

I could probably have written this shorter in another language, but there was no JS solution yet so here it is:

N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Run in the console.

Example input:

N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output:

3
2
1 

Input:

N=6;M=4;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output:

3
2
1
0

Input:

N=7;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output: -1

Too bad console.log is so long to spell :) Unfortunately declaring l=console.log.bind(console) does not make it any shorter, and just l=console.log does not work.

Input:

"N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)".length

Output:

76

• user2428118: You can use c=console and c.log() to shorten it.

Answer 13

Golfscript, 35

~:M.(*2/-.M%{;-1}{M/M+,-1%M<' '*}if

How it works

In the following example, the input is 9 3.

 # STACK: "9 3"
~ # Interpret the input string.
 # STACK: 9 3
:M # Store the top of the stack (number of dwarves) in variable `M'.
. # Duplicate the top of the stack.
 # STACK: 9 3 3
( # Decrement the top of the stack.
 # STACK: 9 3 2
* # Multiply the topmost elements of the stack.
 # STACK: 9 6
2/ # Divide the top of the stack by `2'.
 # STACK: 9 3
 # So far, we've transformed `M' into `M*(M-1)/2', which is the minimum amount of
 # coins all dwarves together will get. This number comes from the fact that the
 # youngest dwarf will get at least 0 coins, the next at least 1 coin, etc., and
 # 0 + 1 + ... + (M - 1) = M*(M-1)/2.
- # Subtract the topmost elements of the stack.
 # STACK: 6
 # The remaining coins have to get reparted evenly to all dwarves.
. # Duplicate the top of the stack.
 # STACK: 6 6
M% # Calculate the top of the stack modulus `M'.
 # STACK: 6 0
{ # If the modulus is positive, the remaining coins cannot get reparted evenly.
 ;-1 # Replace the top of the stack by `-1'.
}
{ # If the modulus is zero, the remaining coins can get reparted evenly.
 M/ # Divide the top of the stack by `M'.
 # STACK: 2
 # This is the number of coins all dwarves will get after giving 1 to the second
 # youngest, etc.
 M+ # Add `M' to the top of the stack.
 # STACK: 5
 , # Replace the top of the stack by an array of that many elements.
 # STACK: [ 0 1 2 3 4 ]
 # The rightmost element is the number of coins the oldest dwarf will get.
 -1% # Reverse the array.
 # STACK: [ 4 3 2 1 0 ]
 M< # Keep the leftmost `M' elements.
 # STACK: [ 4 3 2 ]
 # There are only `M' dwarves.
 ' '* # Join the array, separating by spaces.
 # STACK: "4 3 2"
}if

Answer 14

Delphi XE3 (176)

uses SysUtils;var d,c,i:integer;begin read(c,d);for I:=1to d-1do c:=c-i;if c mod d>0then writeln(-1)else begin c:=c div d;for I:=d-1downto 0do write(IntToStr(i+c)+' ');end;end.

How it works.

Reads 2 integers, coins and dwarves.
Substracts the difference per dwarf.
If the remainder mod dwarves>0 its impossible.
Else get equal share per dwarf in a loop of dwarves-1 to 0 and prints dwarfIndex+equal share

Ungolfed

uses SysUtils;
var
 d,c,i:integer;
begin
 read(c,d);
 for I:=1to d-1do
 c:=c-i;
 if c mod d>0then
 writeln(-1)
 else
 begin
 c:=c div d;
 for I:=d-1downto 0do
 write(IntToStr(i+c)+' ');
 end;
end.

Answer 15

Mathematica 65

The function, g, generates all the increasing-by-one sequences, of length m, from 0 to n and checks whether any of them sum to m. If successful, the sequence is returned; otherwise, -1 is returned.

The sequences are made by Partitioning the list {0,1,2,3... m} into all possible sublists of n contiguous integers.

There are, of course, more efficient ways to achieve the same effect, but those that I have found require more code.

n_~g~m_:=If[(s=Select[Partition[0~Range~n,m,1],Tr@#==n&])=={},-1,s]

Examples

g[9, 3]

{{2, 3, 4}}

---

g[3, 3]

{{0, 1, 2}}

---

g[7, 3]

-1

---

g[705, 3]

{{234, 235, 236}}

---

g[840, 16]

{{45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60}}

---

g[839, 16]

-1

Answer 16

C 131

#include <edk.h>
main(int a,char **v){int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;k<0||k%j?j=1,k=-1:k/=j;while(j--)printf("%d ",k+j);}

Ungolfed

#include <edk.h> //Shortest standard header including stdio.h and stdlib.h
main(int a,char **v)
{
 int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;
 k<0||k%j?j=1,k=-1:k/=j; // If youngest dwarf gets < 0 or amount not equally divisible then set values such that ...
 while(j--)printf("%d ",k+j); // ... loop prints out correct values
}

This compiles with a warning because main has no type. If this is not valid in the rules of golf, I would have to add five characters.

Answer 17

Cobra - 198

Cobra Website

class P
 def main
 x,y=Console.readLine.split
 a,b=x to int,y to int
 l=[]
 t=n=0
 for i in b,t+=i
 while (t+=b)<=a,n+=1
 for i in b,l.insert(0,i+n)
 print if(t-b<>a,-1,l.join(" "))

Explained:

class P
 def main

Required for the code to run

 x,y=Console.readLine.split
 a,b=x to int,y to int

Takes input and stores it as a and b

 l=[]
 t=n=0

Initializes the output list l, and initializes the total required money t and number of coins to add to each dwarves pile n

 for i in b,t+=i

Finds the lowest possible money value that will result in all dwarves having an allowable number of coins in their pile

 while (t+=b)<=a,n+=1

Determines how many coins to add to each pile so that the total required money is>= to the total available money

 for i in b,l.insert(0,i+n)

Fills the list with the different sized piles of money

 print if(t-b<>a,-1,l.join(" "))

Outputs either -1 or l depending whether the total required money is equal to the total available money

Answer 18

Perl 5, 78 + 1 (-n) = 79 bytes

($d)=/ (.*)/;,ドル=$";say(($b=$_-($d**2-$d)/2)%$d?-1:map$_+$b/$d,reverse 0..$d-1)

Try it online!

Answer 19

Python ((削除) 100 (削除ここまで) (削除) 96 (削除ここまで) 94):

(削除) A nice, round-scoring answer. (削除ここまで) Not any more, but it IS shorter now.

def f(n,m):a=range(m)[::-1];b=n-sum(a);c=b/m;d=[i+c for i in a];return(d,-1)[-1in d or c*m!=b]

Ungolfed:

def f(n,m):
 a = range(m)[::-1]
 b = sum(a)
 c = (n-b)/m
 if c * m != n-b: return -1
 d = [i+c for i in a]
 return (d,-1)[-1 in d or c!=n-b]
 if -d in d or c*m!=n-b:
 return -1
 return d

Output:

def f(n,m):a=range(m)[::-1];b=sum(a);c=(n-b)/m;d=[i+c for i in a];return (d,-1)[-1 in d or c*m!=n-b]
f(3,3)
Out[2]: [2, 1, 0]
f(9,3)
Out[3]: [4, 3, 2]
f(7,3)
Out[4]: -1
f(6,4)
Out[5]: [3, 2, 1, 0]

• Austin Henley: This doesn't follow the input requirement.
• user80551: -1, the question requires to write a complete program and not a function. See meta.codegolf.stackexchange.com/a/1146/8766