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

There is an existing "game" where pirates rationally divide gold coins according to certain rules. Quoting from Wikipedia:

There are 5 rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates, including the proposer, then vote on whether to accept this distribution. In case of a tie vote the proposer has the casting vote. If the distribution is accepted, the coins are disbursed and the game ends. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Second, given survival, each pirate wants to maximize the number of gold coins each receives. Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal. The pirates do not trust each other, and will neither make nor honor any promises between pirates apart from a proposed distribution plan that gives a whole number of gold coins to each pirate.

Challenge

Take as input an integer n, 1<=n<=99, where n is the number of pirates - and output the distribution of coins, starting with the first pirate.

Test cases (first line is input; the second output):

1
100

2
100 0

3
99 0 1

5
98 0 1 0 1

This is , so the shortest solution in bytes wins.

share|improve this question
1  
I think this was asked before, but I wouldn't know where to find it. – feersum Jan 13 at 21:40
2  
@feersum codegolf.stackexchange.com/questions/54235/… (deleted) – Dennis Jan 13 at 21:42
1  
Args[0]. Java now has a reason to use this. – VTCAKAVSMoACE Jan 13 at 21:48
3  
Why limit n < 100? Over-staffed, under-gilded pirate ships need distributional help as well. – Ryan Cavanaugh Jan 14 at 7:56
1  
@Neil that is a terrible idea. If that is what "rational" pirates do, then all pirate other than A will try to kill A so that they get $100/(n-1)$ instead. This will quickly kill off everyone except the last two pirates. – kaine Jan 14 at 15:48

11 Answers 11

up vote 11 down vote accepted

Jelly, 11 10 bytes

R%2ḊµSȷ2_;

Try it online! or verify all test cases at once.

How it works

For input n, the task boils down to creating the list x, 0, 1, 0, … of length n whose sum is 100.

R%2ḊµSȷ2_;  Main link. Input: n

R           Yield [1, 2, ..., n].
 %2         Replace each integer by its parity. Yields [1, 0, 1, 0, ...].
   Ḋ        Dequeue; remove the first 1. This yields the list a = [0, 1, ...].
    µ       Begin a new, monadic link. Argument: a
     S      Compute the sum of a.
      ȷ2_   Subtract the sum from 100. (ȷ2 is 1e2 in Python syntax)
         ;  Prepend the difference to a.
share|improve this answer

Python, 33 bytes

lambda n:([-n/2+101]+[0,1]*n)[:n]

Computes the first value, appends some 0, 1, 0, 1..., truncates to length n.

Note that -n/2+101 can't be shortened to 101-n/2 because unary and binary - have different precedence: the former is parsed as (-n)/2 and the latter as 101-(n/2).

Recursion was much longer (45):

f=lambda n,i=100:1/n*[i]or f(n-1,i-n%2)+[n%2]
share|improve this answer

MATL, 12 bytes

:2\ts_101+l(

This uses current version (9.2.2) of the language/compiler, which is earlier than this challenge.

Example

>> matl :2\ts_101+l(
> 5
98  0  1  0  1

Explanation

:         % implicitly input number "n". Generate vector [1, 2, ..., n]
2\        % modulo 2. Gives [1, 0, 1, ...]
ts        % duplicate and compute sum
_101+     % negate and add 101
l(        % assign that to first entry of [1, 0, 1, ...] vector. Implicitly display
share|improve this answer

Pyth, 13 bytes

+-100sJ%R2tQJ

Test suite.

share|improve this answer

Python, 62 58 bytes

EDIT: Glad I made it a one-liner. But I lose for Python. Therefore, this is just for reference. Thanks @Zgarb

def x(i):n=[~j%2for j in range(i)];n[0]=101-sum(n);print n

It takes the input, creates a list pf parity of all numbers from 1 to i. Then sets the first element in i to 101-sum(n) and prints.

Try it here

share|improve this answer

Javascript ES6, 45 bytes

a=>[...Array(a)].map((x,y)=>y?--y%2:202-a>>1)

Thanks to @Neil for 1 byte saved!

share|improve this answer
1  
202-a>>1 saves a byte. – Neil Jan 14 at 13:16

𝔼𝕊𝕄𝕚𝕟, 14 chars / 26 bytes

⩥ï⒨?‡$%2:ỉ-ï»1

Try it here (Firefox only).

Not bad, but not good either...

Explanation

⩥ï⒨?‡$%2:ỉ-ï»1 // implicit: ï=input, ṥ=101
⩥ï⒨            // map over a range [0,ï) and return:
    ?‡$%2       // (if mapitem>0) then ($-1) mod 2
         :ỉ-ï»1 // (else) 202-ï>>1
                // implicit output
share|improve this answer

Japt, 14 bytes

Yet another challenge where I find myself wishing for a built-in I had just considered adding...

1oU mv u#Ê-UÁ1

Try it online!

1oU mv u#Ê-UÁ1  // Implicit: U = input integer
1oU             // Create the range [1, U).
    mv          // Map each item to 1 if even, 0 otherwise.
       u        // Unshift (add to the beginning of the array)
        #Ê-UÁ1  //  the char code of Ê (202), minus U >>> 1 (floor of U / 2).
share|improve this answer

Actionscript 3, 87 bytes

function x(n){var l=[],i=1;for (l[0]=int(101-n/2);i<n;){l[i]=++i%2;}return l.join(" ")}

It's not the best golfing language, but I enjoy posting as3 answers.

share|improve this answer

Seriously, 23 17 bytes

EDIT: Thanks @quintopia

,R`2@%`M;Σ2╤u-0(T

Uses the same approach as my Python answer, but I do the modulo 2 using mapping, and several times, I rotate my stack.

Explanation

Push input (I will call it i), push range(1,i+1), make a function take pushes 2, rotates stack, and take modulo. Then map this function onto the range iterable. This gives the parity of each element in the list. Duplicate stack, sum the parity list, push 2, 10^2, and 100+1, and subtract the sum (let me call this value n) Push 0, rotate stack by 1, and set the list's index 0 element to n. Implict printing of the resulting list.

share|improve this answer
    
This should be no more than 17 bytes: ,R`2@%`M;Σ2╤u-0(T – quintopia Jan 14 at 15:02

Perl 51 49 44 bytes

$,=$";@"=map{$i++%2}2..<>;say 100-(@">>1),@"

Need the following perlrun options -E

$ perl -E'$,=$";@"=map{$i++%2}2..<>;say 100-(@">>1),@"'<<<5
98
0
1
0
1
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.