Perplex City
Last month, TR bought a Perplex City starter kit for my wife and I. What a cool game! There are so many levels you can play at. You can solve puzzle cards by yourself. You can join up with others online and solve cards together (including some really hard cards requiring group efforts). The city itself has a lot of depth, with record companies, pharmaceutical companies, schools, blogs, and newspapers. Some of these “companies” run ads in London newspapers, and puzzles from the game have shown up in newspapers and magazines. Finally, you can hunt for the stolen cube and try to get the $200K reward.
Many of the puzzles make fun programming challenges. I’ve been doing them in python, since that is such a great language for rapid programming. Sweet Dreams (#85) makes an obvious candidate:
#!/usr/bin/env python
a = 1
b = 1
while a < 400000:
c = a + b
a = b
b = c
print c
My wife solved Rickety Old Bridge (#106) much faster than I was able to write the program (although the program found that there are two similar solutions, not just one). This was a good one to learn generators with:
#!/usr/bin/env python
class bridge:
people = { "kurt":2, "scarlett":5, "violet":1, "sente":10 }
states = [ {"near":people.keys(), "far":[], "moves":[]} ]
def move(self, source, dest):
""" yield all new states formed by moving
a person from source -> dest """
for state in self.states:
for person in state[source]:
yield {source: [s for s in state[source] if s != person],
dest: state[dest] + [person],
"moves": state["moves"] + [person] }
def to_far(self):
self.states = [s for s in self.move("near", "far")]
def to_near(self):
self.states = [s for s in self.move("far", "near")]
def score(self, state):
times = [self.people[name] for name in state["moves"]]
total_time = max(times[0], times[1]) + times[2] + \\
max(times[3], times[4]) + times[5] + \\
max(times[6], times[7])
return total_time, state["moves"]
def print_scores(self):
scores = [self.score(s) for s in self.states]
scores.sort()
scores.reverse()
for s in scores:
print s[0], s[1]
def run(self):
self.to_far()
self.to_far()
self.to_near()
self.to_far()
self.to_far()
self.to_near()
self.to_far()
self.to_far()
self.print_scores()
if __name__ == "__main__":
b = bridge()
b.run()
The program I came up with for solving Magic Square (98) takes a long time to run but eventually starts finding candidate solutions about 2.2 million squares into its search:
#!/usr/bin/env python
def comb(nums, n):
if n == 0: yield [], nums
else:
for i in range(len(nums)):
for tail, remaining in comb( nums[:i] + nums[i+1:], n-1):
yield [nums[i]] + tail, remaining
def rows(nums):
if not nums: yield []
else:
for row, remaining in comb(nums, 4):
if sum(row) == 34:
for other_rows in rows(remaining):
yield [row] + other_rows
def check(grid):
magic = True
for i in range(4):
if sum([row[i] for row in grid]) != 34:
magic = False
if sum([grid[i][i] for i in range(4)]) != 34 or \\
sum([grid[i][3-i] for i in range(4)]) != 34:
magic = False
return magic
count = 0
for grid in rows(range(1, 17)):
count += 1
if count % 100000 == 0:
print count / 1000, "K"
if check(grid):
print grid