Theseus' New Ship

Question

The Ship of Theseus is an old question that goes something like:

If a ship has had all of its original parts replaced, is it still the same ship?

For this golf, we're going to slowly replace "parts" on a "ship", and see how long it takes to get a whole new ship.

Task

A ship is comprised of at least two parts. The parts are given as an array of positive (non-zero) integers, representing the part's condition.

On each cycle, randomly choose one part from the list in a uniform fashion. That part's condition will be reduced by one. When a part's condition reaches zero, it is replaced by a new part. The new part starts with the same condition value as the original did.

On the first cycle where all parts have been replaced (at least) once, stop and output the number of cycles it took.

For example (assume I'm choosing parts randomly here):

2 2 3  <- starting part conditions (input)
2 1 3  <- second part reduced
2 1 2  ...
2 1 1 
2 2 1  <- second part reduced to zero, replaced
1 2 1 
1 2 3  <- third part replaced
1 1 3 
2 1 3  <- first part replaced

Output for this example would be 8, since it took eight cycles for all parts to be replaced. Exact output should differ for each run.

I/O

The only input is the list/array of integers for part condition. The only output is a number of cycles. You can take/give these values in any of the usual ways: STDIO, function arguments/returns, etc.

Test Cases

Since output is not fixed, you could use whatever you want to test, but here's a couple for standardization purposes:

1 2 3 4

617 734 248 546 780 809 917 168 130 418

19384 74801 37917 81706 67361 50163 22708 78574 39406 4051 78099 7260 2241 45333 92463 45166 68932 54318 17365 36432 71329 4258 22026 23615 44939 74894 19257 49875 39764 62550 23750 4731 54121 8386 45639 54604 77456 58661 34476 49875 35689 5311 19954 80976 9299 59229 95748 42368 13721 49790

Answer 1

Pyth, 12 bytes

f!eSXOUQQtZ1

Demonstration.

How it works:

This is based around Pyth's infinite filter, which tests an expression with increasing inputs until it returns something truthy, then returns the input which caused this to happen. However, the expression that will be tested will not use the input value.

Instead, the expression will modify the input list by decrementing a random entry. This is accomplished via the expression XOUQQtZ. This means increase the index OUQ in the list Q by tZ. OUQ is a random index in the length of Q, and tZ is -1. Q is initialized to the input list.

After modifying Q in this fashion, we take its current value, which X returns, take its maximum entry with eS, and take the logical not of that value with !. This returns a truthy value for the first time when every element of Q has been reduced to 0 or below for the first time.

To ensure that the number returned will be exactly the number of times that Q was modified, we will start the count at 1, indicating the the first time this is called, there has been 1 modification. To see what Q looks like after each iteration of the code, check out the version here.

Answer 2

GolfScript (26 24 bytes) / CJam (20 18 bytes)

GolfScript:

~{$)*}{.,rand{(+}*((+}/,

Online demo

CJam (same idea but slightly different implementation):

q~{_mr((+_$)*}g;],

Online demo

Input is on stdin in the form [2 2 3].

This is one of those rare occasions where GolfScript's unfold operator is useful. It allows us to accumulate the states which the ship passes through, and then count them at the end. Note that the array which is counted includes the initial (input) state but not the final state in which the last element has been reduced to 0.

However, although CJam doesn't have unfold its ability to shuffle an array uniformly for only 2 chars counts for a lot and allows it to come out on top.

Answer 3

Python 3, 91 71 bytes

20(!) bytes saved thanks to @xnor.

from random import*
def f(p):shuffle(p);p[0]-=1;return max(p)<1or-~f(p)

Recursive function calling itself with smaller piece-values until all piece-values are 0 or negative and every function returns the return value of its child + 1 and the lastly called one returns 1.

Answer 4

Python 3, 175 bytes

import random
p,t=input().split(),0;f,r=[int(i)for i in p],[0]*len(p)
while 0 in r:
 f[random.randint(0,len(f)-1)]-=1;t+=1
 for x in range(len(f)):
  r[x]=int(f[x]<1)
print(t)

Not especially well golfed.

Try it online here