Constructing a New Puzzle Using Python¶
This puzzle was inspired by this puzzle from the MIT Puzzle Hunt:
Our Crew is Replaceable, Your Package is Not¶
http://web.mit.edu/puzzle/www/2009/puzzles/our_crew_is_replaceable_your_package_isnt/PUZZLE/
The Teleporter Puzzle¶
There are three camps: Alpha, Beta, and Gamma
Each camp has a teleporter and can swap items with other camps.
The teleporters can only exchange items; something has to be loaded into two teleporters for the teleportation process to work.
There are two items at each camp.
Each item has an attribute and a destination.
Initially, the items are positioned as follows:
ALPHA CAMP
- Squid Ink (Toxic, belongs at Gamma)
- Pointy Rock Tied to a Stick (Terrifying, belongs at Gamma)
BETA CAMP
- Quantum Stirwand (Placebo, belongs at Beta)
- Ramen Noodles (Edible, belongs at Beta)
GAMMA CAMP
- Tinfoil Hat (Neutral, belongs at Alpha)
- Sonic Screwdriver (Helpful, belongs at Alpha)
RULES
- {Terrifying and Toxic} conflict with {Helpful and Edible}
- Conflicting items cannot be together at a camp.
- Conflicting items may pass each other in the teleporter.
- {Neutral and Placebo} do not conflict with anything.
The goal is to move each item to it's destination while following the conflict rules¶
In [1]:
import itertools
Camps = ["Alpha","Beta","Gamma"]
Items = ["Ink","Rock","Hat","Wand","Sonic","Ramen"]
State0 = (0,1,2,3,4,5) # First two items are at Alpha, second two items are at Beta, last two at Gamma
GoalState = (2,4,3,5,0,1) # keep items sorted ascending order within camp
visited = set() # do not return to already visited states
# Terrifying and Toxic conflict with Helpful and Edible
ConflictLookup = {0:[2,4],1:[2,4],2:[0,1],3:[],4:[0,1],5:[]}
print("ConflictLookup",ConflictLookup)
In [2]:
def printState(State):
for c in range(3):
print(Camps[c],end=": ")
print(Items[State[2*c]],"and",Items[State[2*c+1]])
printState(State0)
In [3]:
# only allow item swaps between camps, not within the same camp
candidateSwaps = []
badSwaps = set([(0,1),(2,3),(4,5)])
for swap in itertools.combinations(range(6),2):
if swap in badSwaps:
continue
candidateSwaps.append(swap)
print(candidateSwaps)
In [4]:
def checkGoal(tostate):
if tostate == GoalState:
return True
else:
return False
In [5]:
def ValidState(tostate):
if tostate in visited:
return False
if checkGoal(tostate):
print("*** GOAL ACHIEVED ***")
a,b,c,d,e,f = tostate
# check each camp for conflicts
if a in ConflictLookup[b] or c in ConflictLookup[d] or e in ConflictLookup[f]:
return False
return True
In [6]:
# Keep items sorted within camps -- so that we can recognize visited states and the goal state
# (1,2,3,4,5,6) is the same state as (2,1,3,4,5,6), so only store the sorted representation
def sortCamps(tostate):
newlist = []
a,b,c,d,e,f = tostate
if a>b:
newlist.append(b)
newlist.append(a)
else:
newlist.append(a)
newlist.append(b)
if c>d:
newlist.append(d)
newlist.append(c)
else:
newlist.append(c)
newlist.append(d)
if e>f:
newlist.append(f)
newlist.append(e)
else:
newlist.append(e)
newlist.append(f)
return(tuple(newlist))
In [7]:
# print layer 0
print("Possible States After 0 Swaps")
print(State0)
visited.add(State0)
In [8]:
# print layer 1
print("Possible States After 1 Swap")
print("Parent State",State0)
layer1 = []
for a,b in candidateSwaps:
StateList = list(State0)
t = StateList[a]
StateList[a]=StateList[b]
StateList[b] = t
StateTup = sortCamps(tuple(StateList))
if not ValidState(StateTup):
continue
print(" ",StateTup,checkGoal(StateTup))
visited.add(StateTup)
layer1.append(StateTup)
In [9]:
# print layer 2
print("Possible States After 2 Swaps")
layer2 = []
for State1 in layer1:
print("Parent State",State1)
for a,b in candidateSwaps:
StateList = list(State1)
t = StateList[a]
StateList[a]=StateList[b]
StateList[b] = t
StateTup = sortCamps(tuple(StateList))
if not ValidState(StateTup):
continue
print(" ",StateTup,checkGoal(StateTup))
visited.add(StateTup)
layer2.append(StateTup)
In [10]:
# print layer 3
print("Possible States After 3 Swaps")
layer3 = []
for State2 in layer2:
print("Parent State",State2)
for a,b in candidateSwaps:
StateList = list(State2)
t = StateList[a]
StateList[a]=StateList[b]
StateList[b] = t
StateTup = sortCamps(tuple(StateList))
if not ValidState(StateTup):
continue
print(" ",StateTup,checkGoal(StateTup))
visited.add(StateTup)
layer3.append(StateTup)
In [11]:
# print layer 4
print("Possible States After 4 Swaps")
layer4 = []
for State3 in layer3:
print("Parent State",State3)
for a,b in candidateSwaps:
StateList = list(State3)
t = StateList[a]
StateList[a]=StateList[b]
StateList[b] = t
StateTup = sortCamps(tuple(StateList))
if not ValidState(StateTup):
continue
print(" ",StateTup,checkGoal(StateTup))
visited.add(StateTup)
layer4.append(StateTup)
In [12]:
# print layer 5
print("Possible States After 5 Swaps")
layer5 = []
for State4 in layer4:
print("Parent State",State4)
for a,b in candidateSwaps:
StateList = list(State4)
t = StateList[a]
StateList[a]=StateList[b]
StateList[b] = t
StateTup = sortCamps(tuple(StateList))
if not ValidState(StateTup):
continue
print(" ",StateTup,checkGoal(StateTup))
visited.add(StateTup)
layer5.append(StateTup)
In [13]:
# looking back up the tree and chaining the parents together
chain = [(0, 1, 2, 3, 4, 5),(0, 1, 2, 4, 3, 5),(1, 3, 2, 4, 0, 5),(3, 5, 2, 4, 0, 1),(2, 5, 3, 4, 0, 1),(2, 4, 3, 5, 0, 1)]
In [14]:
for idx,state in enumerate(chain):
print("\nSTATE",idx)
printState(state)
