Cosmetic Surgery and the Worm

[BMAD]

A long worm crawls into a cosmetic veterinary surgery, complaining of a problem with 1's. 

 

A worm can be thought of as a string of 0's and 1's and the most beautiful worm is 00000 ... 0. The worm is a sequence of segments and there is a 0 or a 1 on each segment. The procedure for removing 1's is complicated. If there is a 1 at the right hand end (where the tail is), then the surgeon can remove this 1 (and the segment it lies on) and place a new segment with 0 or a 1 at the left hand end (where the head is).

 

If however there is a 0 at the right hand end then the surgeon can remove it, but he has no control over what appears on the new segment at the left hand end. Indeed, the surgeon has to operate under the assumption that there is an adversary making a choice of what to replace a 0 by.

 

The adversary would like the operation to continue indefinitely. The surgeon claims a 100% success rate. Do you believe him?

[k-man]

 

Nice puzzle and title, BMAD.

 

There are successful strategies that will work for short worms, but if a worm is of a certain length the adversary can keep the process going forever. I haven't figure out exactly what the absolute minimum length is, but I can keep it going forever with 9.

 

For the surgeon, regardless of his strategy, the worst starting configuration (i.e. the ugliest worm) is 1 followed by all zeros (1000...000). This basically gives the adversary the ability to decide the initial configuration by making the fist n-1 moves.

 

For the adversary, the favorable pattern of the worm is isolated 1s surrounded by long strings of 0s (000010001). The ideal number of 1s in the worm is 2. This basically allows the surgeon to make 2 isolated moves, while the adversary makes the rest of the moves each cycle. The strategy for the adversary is

1) never allow two 1s next to each other

2) maintain more than one 1 in the worm at all times, but ensure that there is at least 1 zero between them.

 

Once the pattern above is established, the adversary gets a number of consecutive moves while the surgeon only gets one move in a while. If the surgeon chooses to replaces his 1s with 1s then the adversary simply needs to replace his 0s with 0s and continue forever. If the surgeon replaces a 1 with a 0, then he simply removed one 1, but increased the number of moves for the adversary. The adversary can put the 1 back where it's needed to maintain the pattern.

It seems that I disagree as there should always be a way for the surgeon to win.

 

 

Looks like you're right, BMAD. I haven't taken my 9-long worm example far enough to see that the adversary cannot continue to maintain that pattern indefinitely as long as surgeon does the right thing.

 

Choose some 1 in the worm as your anchor. Your goal is get the worm to the state 0000...0001, where that last remaining 1 is the anchor, at which point the last move is to replace it with 0.

At any given time when removing a 1 at the tail of the worm, replace it with 1 at the head, unless the anchor is preceded only by 0s. In other words, if the pattern of the worm is 00..00AXX..XX1, replace that 1 with 0, otherwise with 1.

 

The reason this strategy works as it forces the adversary to insert 1s into the worm slowly closing the gaps between 1s and attaching more and more 1s to the anchor on the right until the entire worm is full of 1s. If the adversary plays the game in the most efficient way it will take a long time, but eventually the surgeon will prevail.

[gavinksong]

I wrote some short Haskell code to verify the surgeon's claim for all worms of a given length.

 

import Data.List

type Worm = [Bool]

idealWorm :: Int -> Worm
idealWorm len = replicate len False

isSafe :: Int -> Bool
isSafe len = (length $ allSafeCases [idealWorm len]) == 2^len

allSafeCases :: [Worm] -> [Worm]
allSafeCases (this:rest) =
	if this `elem` rest then rest
	else
		let updated = allSafeCases (restore this True : this : rest) in
		let prefix = init this in
			if any (prefix `isPrefixOf`) updated
				then allSafeCases (restore this False : updated)
				else updated

restore :: Worm -> Bool -> Worm
restore xs y = y:(init xs) 

 

I have yet to think of an actual proof.

[Molly Mae]

Yes, I believe him.

 

 

Proofs are certainly not my forte, but it's interesting to note that all 1's is just as acceptable for the physician as all 0's.

[phil1882]

10

cut out the zero.

if 1 to the left, simple.

cut 1 replace 0, cut 1 replace 0 and done.

if zero to the left even simpler.

cut out the 1, replace zero and done.

1010

cut zero.

if 1:

cut 1, replace 0. 0110

cut 0

if 1:

cut 1 replace 0,

cut 1 replace 0. 0010

cut 0.

if 1:

cut 1 replace 0. 0100

cut 0 replace 1. 1010

it seems as long as 0 is replaced by 1, the operation will continue forever.

[gavinksong]

1010

cut zero.

if 1:

cut 1, replace 0. 0110

cut 0

if 1:

cut 1 replace 0,

cut 1 replace 0. 0010

cut 0.

if 1:

cut 1 replace 0. 0100

cut 0 replace 1. 1010

it seems as long as 0 is replaced by 1, the operation will continue forever.

 

The first 1 you cut should be replaced with a 1, so that you get 1110. After that, if you just keep replacing with 0, you'll eventually arrive at the desired state, regardless of what the 'adversary' chooses.

[gavinksong]

import Data.List

type Worm = [Bool]

idealWorm :: Int -> Worm
idealWorm len = replicate len False

isSafe :: Int -> Bool
isSafe len = (length $ allSafeCases [idealWorm len]) == 2^len

allSafeCases :: [Worm] -> [Worm]
allSafeCases (this:rest) =
	if this `elem` rest then rest
	else
		let updated = allSafeCases (restore this True : this : rest) in
		let prefix = init this in
			if any (prefix `isPrefixOf`) updated
				then allSafeCases (restore this False : updated)
				else updated

restore :: Worm -> Bool -> Worm
restore xs y = y:(init xs) 

 

Let me explain my code from before. The results it gives suggests that the surgeon's claim is correct.

 

Let's call a unique binary string a "state". We call a state "safe" if it has been determined to be guaranteed to reach the goal state.

 

I have a function that takes a set of safe states and returns the set of all states that are also implied to be safe.

The way it works is that it repeatedly checks if it is possible to expand the set of safe states according to the following rules:

1. If state "abc...z" is safe, then state "bc...z1" is also safe.
2. If state "1bc...z" and "0bc...z" are both safe, then state "bc...z0" is also safe.

Obviously, if we pass it the goal state and it returns a value which contains all the possible states, then the surgeon's claim is validated.

So far, the results have been strongly in favor of the surgeon.

[bubbled]

I think there is a simple strategy that should work every time, though a proof is beyond me.

 

If the right end is a 1, then you look at the left end and put the same number that appears at the left. If the worm is [1,0,1,0,1], the new worm would be [1,1,0,1,0].

 

I can't see a better strategy for the adversary than to do the opposite.

 

I coded up a simple python program to test the strategy. Nothing as elegant as gavinksong.

 

Here is a printout of a 16 segment worm. I started with what appears to be the worst starting state (alternating 0's and 1's) You can see the patterns as it works its way through:

 

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

[0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0]
[0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0]
[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]
[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
[1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1]
[1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]
[1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
success

 

It takes about 2 minutes for my non-optimized program to run on a 22 section worm and it takes 4,194,282 steps. Tried 27 segments and it hadn't finished in 45 minutes

 

 

[gavinksong]

I think there is a simple strategy that should work every time, though a proof is beyond me.

 

If the right end is a 1, then you look at the left end and put the same number that appears at the left. If the worm is [1,0,1,0,1], the new worm would be [1,1,0,1,0].

 

Hmm. Maybe this is trivial, but I have a counterexample.

A string of all 1s would cause your strategy to commit suicide.

Of course, all the surgeon would have to do at that point is print out zeroes, but yeah.

Edited May 7, 2015 by gavinksong

[bubbled]

 

I think there is a simple strategy that should work every time, though a proof is beyond me.

 

If the right end is a 1, then you look at the left end and put the same number that appears at the left. If the worm is [1,0,1,0,1], the new worm would be [1,1,0,1,0].

 

Hmm. Maybe this is trivial, but I have a counterexample.

A string of all 1s would cause your strategy to commit suicide.

Of course, all the surgeon would have to do at that point is print out zeroes, but yeah.

 

Yeah, I put all 1's a stopping condition. Though using my strategy in conjunction with my adversarial strategy, you would never get there unless it was the starting condition as well. 

 

Basically, you always eventually get to all 1's with one 0, and then the win is easy.

 

Can you think of a better adversary strategy to my "doctor's" strategy?

 

I'm going to see if a random adversary strategy does any better. I doubt it. Will post results soon.

[bubbled]

 

 

I think there is a simple strategy that should work every time, though a proof is beyond me.

 

If the right end is a 1, then you look at the left end and put the same number that appears at the left. If the worm is [1,0,1,0,1], the new worm would be [1,1,0,1,0].

 

Hmm. Maybe this is trivial, but I have a counterexample.

A string of all 1s would cause your strategy to commit suicide.

Of course, all the surgeon would have to do at that point is print out zeroes, but yeah.

 

Yeah, I put all 1's a stopping condition. Though using my strategy in conjunction with my adversarial strategy, you would never get there unless it was the starting condition as well. 

 

Basically, you always eventually get to all 1's with one 0, and then the win is easy.

 

Can you think of a better adversary strategy to my "doctor's" strategy?

 

I'm going to see if a random adversary strategy does any better. I doubt it. Will post results soon.

 

I ran a 22 segment worm starting with alternating 1's and 0's, a few dozen times. It took a low of 45 steps and a high of 1124 steps. Given it takes over 4 million steps using my deterministic strategy, that seems better.

[k-man]

Nice puzzle and title, BMAD.

 

There are successful strategies that will work for short worms, but if a worm is of a certain length the adversary can keep the process going forever. I haven't figure out exactly what the absolute minimum length is, but I can keep it going forever with 9.

 

For the surgeon, regardless of his strategy, the worst starting configuration (i.e. the ugliest worm) is 1 followed by all zeros (1000...000). This basically gives the adversary the ability to decide the initial configuration by making the fist n-1 moves.

 

For the adversary, the favorable pattern of the worm is isolated 1s surrounded by long strings of 0s (000010001). The ideal number of 1s in the worm is 2. This basically allows the surgeon to make 2 isolated moves, while the adversary makes the rest of the moves each cycle. The strategy for the adversary is

1) never allow two 1s next to each other

2) maintain more than one 1 in the worm at all times, but ensure that there is at least 1 zero between them.

 

Once the pattern above is established, the adversary gets a number of consecutive moves while the surgeon only gets one move in a while. If the surgeon chooses to replaces his 1s with 1s then the adversary simply needs to replace his 0s with 0s and continue forever. If the surgeon replaces a 1 with a 0, then he simply removed one 1, but increased the number of moves for the adversary. The adversary can put the 1 back where it's needed to maintain the pattern.

[BMAD]

Nice puzzle and title, BMAD.

 

There are successful strategies that will work for short worms, but if a worm is of a certain length the adversary can keep the process going forever. I haven't figure out exactly what the absolute minimum length is, but I can keep it going forever with 9.

 

For the surgeon, regardless of his strategy, the worst starting configuration (i.e. the ugliest worm) is 1 followed by all zeros (1000...000). This basically gives the adversary the ability to decide the initial configuration by making the fist n-1 moves.

 

For the adversary, the favorable pattern of the worm is isolated 1s surrounded by long strings of 0s (000010001). The ideal number of 1s in the worm is 2. This basically allows the surgeon to make 2 isolated moves, while the adversary makes the rest of the moves each cycle. The strategy for the adversary is

1) never allow two 1s next to each other

2) maintain more than one 1 in the worm at all times, but ensure that there is at least 1 zero between them.

 

Once the pattern above is established, the adversary gets a number of consecutive moves while the surgeon only gets one move in a while. If the surgeon chooses to replaces his 1s with 1s then the adversary simply needs to replace his 0s with 0s and continue forever. If the surgeon replaces a 1 with a 0, then he simply removed one 1, but increased the number of moves for the adversary. The adversary can put the 1 back where it's needed to maintain the pattern.

It seems that I disagree as there should always be a way for the surgeon to win.