Cat in a Box

Another week, another puzzle. This one comes from MindYourDecisions on YouTube as suggested by a friend. Here’s the problem:

catproblem-e1520311636896.png

While I was able to logic out a solution that would find the cat in 7 steps the program I wrote was able to do it in 6. That solution is:

#Round 0 I select box 2
#Possible boxes the cat can be in: [1, 0, 1, 1, 1]
#Round 1 I select box 3
#Possible boxes the cat can be in: [0, 1, 0, 1, 1]
#Round 2 I select box 4
#Possible boxes the cat can be in: [1, 0, 1, 0, 1]
#Round 3 I select box 4
#Possible boxes the cat can be in: [0, 1, 0, 0, 0]
#Round 4 I select box 3
#Possible boxes the cat can be in: [1, 0, 0, 0, 0]
#Round 5 I select box 2
#Possible boxes the cat can be in: [0, 0, 0, 0, 0]

The benefit of this program is that it is easily able to find solutions for cases where there are more than five boxes, the cat can move one or two, etc.

Of course his explanation was cleaner but its a little nice to be able to say you exhaustively searched all the cases šŸ™‚

import random
import copy
def select_box(sel_box,boxes):
#Input a box, it does the proceeding logic
old_boxes = copy.deepcopy(boxes)
for i in range(0,len(boxes)):
if old_boxes[i] > 0:
if (i>0) : boxes[i-1] += 1
if (i 0) for x in boxes] #reduces all non-zero box values to one
return boxes

def print_history(path,box_hist):
for i in range(0,len(path)):
print("Round " + str(i) + " I select box " + str(path[i]+1)) #plus one because the problem uses 1-indexing
print("Possible boxes the cat can be in: " + str(box_hist[i]))

def find_path(thresh):
#set base values
boxes = [1,1,1,1,1] #A 1 indicates the cat can be in the box
min_cat_spots = len(boxes)
path = []
box_hist = []

#Select a random box, check state after each selection. Repeat until finished or it won't work
while min_cat_spots !=0 and len(path) < thresh:
selection = random.randint(0,len(boxes)-1)
path.append(selection)
box_hist.append(boxes)
boxes = select_box(selection,boxes)
cat_spots = sum(boxes)
if cat_spots < min_cat_spots:
min_cat_spots = cat_spots
return [len(path),path,box_hist]

#Search for paths while the the search has a chance to be the new low-score
thresh = 14 #any large number
for i in range(0,10000):
results = find_path(thresh)
if results[0] < thresh:
thresh = results[0]
print_history(results[1],results[2])

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s