Another week, another puzzle. This one comes from MindYourDecisions on YouTube as suggested by a friend. Here’s the problem:
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 < thresh: thresh = results print_history(results,results)