A place for my continued toying with puzzles. 538 puzzles, WACan’t, and others.
Finnegan’s Quaternions
The ever distracting Wolfram Alpha Can't Twitter account, ensnared me a few days ago with this tweet
Which asked for all the is, js, and ks from Finnegan’s wake, to be taken in order to be a quaternionic product. The problem wasn’t the most fascinating, but just silly enough.
Here’s a gist of my solution. I definitely think that the multiplication function could be more elegant, but c’est la vie. I was happy that I thought to use reduce.
Billiards racks
Another distracting Twitter account is solve my maths, who retweeted this little puppy.
This problem was a little meatier. It asks if you can rearrange the pool balls in a billiards rack such that each ball is the difference of the two balls below it(excluding the bottom row). I liked how this problem immediately starts suggesting some data structures.
My mental model for how to construct a rack was to start in the lower-left corner, and add a ball to the bottom row at a time, and stop when it becomes impossible. Then, running through all the ball orderings, will return only the racks that make it all the way.
So I started with a row object, and then a rack object. The rows have append, and the racks have add_ball. The rack needs fill_last because it didn’t cleanly fit into the paradigm of add_ball; also added a print_rack function for obvious reasons.
The logic is straightforward, and starts with two balls:
def __init__(self, leftmost, secondleftmost, operation=delta, rack_size=5):
if (leftmost != secondleftmost and leftmost != 2*secondleftmost and 2*leftmost != secondleftmost):
self.operation=operation
self.rack_size=rack_size
self.rows = [row(rack_size, leftmost)]
self.rows[0].append(secondleftmost)
self.remaining_balls = list(range(1,((rack_size*(rack_size+1))/2)+1))
self.remaining_balls.remove(leftmost)
self.remaining_balls.remove(secondleftmost)
self.fill_last()
else:
raise ValueError("Incorrect Starting Configuration")
That fill_last() is doing the work of moving up a row, and adding the necessary ball in the third position. You’ll see that this function will get called every time a ball is added to the rack, but only for the topmost ball necessary—the top of whatever triangle exists.
def fill_last(self):
current_last_length = self.rack_size+1-len(self.rows)
diff = self.operation(self.rows[-1].elements[0], self.rows[-1].elements[1])
if diff in self.remaining_balls:
self.rows.append(row(current_last_length,diff))
self.remaining_balls.remove(diff)
else:
raise ValueError("Impossible Rack")
So now, we just keep adding balls to the bottom row, and then filling out the rows above, and finishing off with fill_last():
def add_ball(self, value):
if value in self.remaining_balls:
self.rows[0].append(value)
self.remaining_balls.remove(value)
for i in range(1,len(self.rows[0].elements)-1):
diff = self.operation(self.rows[i-1].elements[-1],self.rows[i-1].elements[-2])
if diff in self.remaining_balls:
self.rows[i].append(diff)
self.remaining_balls.remove(diff)
else:
raise ValueError("Impossible Rack")
self.fill_last()
return self.remaining_balls
else:
raise ValueError("Impossible Rack")
This is all well and good, and does yield a solution for the original problem if you iterate through all the possibilities, but I wanted to see the evolution of these solutions, i.e. as you add balls, how many racks are floating around. First, this code does the iteration:
def solve_puzzle(puzzle_size, operation=delta):
if puzzle_size<3 or puzzle_size>7:
raise ValueError("Change your puzzle size")
rack_list = []
number_of_balls = ((puzzle_size*(puzzle_size+1))/2)+1
for i in range(1,number_of_balls):
for j in [x for x in range(1,number_of_balls) if x != i]:
try:
rack_list.append(rack(i, j, operation, puzzle_size))
except ValueError:
pass
And then I got a wild hair and wrote this atrocity:
new_rack = None
some_racks = None
def compute_subracks(new_rack):
some_racks = []
for ball in new_rack.remaining_balls:
try:
sub_rack = copy.deepcopy(new_rack)
sub_rack.add_ball(ball)
some_racks.append(sub_rack)
except ValueError:
pass
return some_racks
def print_rack_tree(root_rack, puzzle_size):
possibility_counts = {3:0,4:0,5:0,6:0,7:0}
for r in compute_subracks(root_rack):
possibility_counts[3]+=1
if puzzle_size>=4:
for s in compute_subracks(r):
possibility_counts[4]+=1
if puzzle_size>=5:
for k in compute_subracks(s):
possibility_counts[5]+=1
if puzzle_size>=6:
for m in compute_subracks(k):
possibility_counts[6]+=1
if puzzle_size>=7:
for n in compute_subracks(m):
possibility_counts[7]+=1
n.print_rack()
else:
m.print_rack()
else:
k.print_rack()
else:
s.print_rack()
else:
r.print_rack()
return possibility_counts
which, OMG, I cannot, for the life of me, refactor to be recursive. I have tried like three times and keep messing it up. It clearly should be recursive, but it’s above my pay-grade.
So now, a little word on these counts:
global_counts = {2:0,3:0,4:0,5:0,6:0,7:0}
for r in rack_list:
global_counts[2]+=1
counts = print_rack_tree(r,puzzle_size)
for val in counts:
global_counts[val]+=counts[val]
return global_counts
Which is going to yield the sequence leading up to a solution. Without further ado:
print solve_puzzle(5)
returns
row 4: [5]
row 3: [4, 9]
row 2: [7, 11, 2]
row 1: [8, 1, 12, 10]
row 0: [6, 14, 15, 3, 13]
Remaining: []
row 4: [5]
row 3: [9, 4]
row 2: [2, 11, 7]
row 1: [10, 12, 1, 8]
row 0: [13, 3, 15, 14, 6]
Remaining: []
{2: 196, 3: 1574, 4: 1734, 5: 2}
I know whatcha thinking, I was thinking it too. What about the racks for larger numbers(the astute reader will have noticed how often I left these functions to take n). Let’s look at 6:
{2: 400, 3: 5516, 4: 25994, 5: 3182, 6: 0}
No solution! Damn! But 3182 racks get to the level 5 before they fail at 6. Take note that the number of balls is larger, so there are more degrees of freedom here. Here are the first four it spits out, it’d be curious to see if there is some common structure, but there are a lot to look at.
row 4: [4]
row 3: [5, 9]
row 2: [7, 12, 3]
row 1: [13, 6, 18, 15]
row 0: [1, 14, 20, 2, 17]
Remaining: [8, 10, 11, 16, 19, 21]
row 4: [5]
row 3: [4, 9]
row 2: [7, 11, 2]
row 1: [13, 6, 17, 15]
row 0: [1, 14, 20, 3, 18]
Remaining: [8, 10, 12, 16, 19, 21]
row 4: [4]
row 3: [5, 9]
row 2: [6, 11, 2]
row 1: [13, 7, 18, 16]
row 0: [1, 14, 21, 3, 19]
Remaining: [8, 10, 12, 15, 17, 20]
row 4: [6]
row 3: [2, 8]
row 2: [9, 11, 3]
row 1: [14, 5, 16, 13]
row 0: [1, 15, 20, 4, 17]
Remaining: [7, 10, 12, 18, 19, 21]
Seven is similarly dissapointing, and so I’m just guessing that 5 is the upper bound for a solution(I’m going to try to prove this at some point, but I’m a bit lazy and uninspired).
Ok, so what about 4?
row 3: [3]
row 2: [4, 7]
row 1: [5, 9, 2]
row 0: [6, 1, 10, 8]
Remaining: []
row 3: [3]
row 2: [5, 2]
row 1: [4, 9, 7]
row 0: [6, 10, 1, 8]
Remaining: []
row 3: [3]
row 2: [2, 5]
row 1: [7, 9, 4]
row 0: [8, 1, 10, 6]
Remaining: []
row 3: [4]
row 2: [2, 6]
row 1: [5, 7, 1]
row 0: [8, 3, 10, 9]
Remaining: []
row 3: [3]
row 2: [7, 4]
row 1: [2, 9, 5]
row 0: [8, 10, 1, 6]
Remaining: []
row 3: [4]
row 2: [5, 1]
row 1: [2, 7, 6]
row 0: [8, 10, 3, 9]
Remaining: []
row 3: [4]
row 2: [1, 5]
row 1: [6, 7, 2]
row 0: [9, 3, 10, 8]
Remaining: []
row 3: [4]
row 2: [6, 2]
row 1: [1, 7, 5]
row 0: [9, 10, 3, 8]
Remaining: []
{2: 80, 3: 262, 4: 8}
And 3(for completeness)?
row 2: [3]
row 1: [5, 2]
row 0: [1, 6, 4]
Remaining: []
row 2: [3]
row 1: [4, 1]
row 0: [2, 6, 5]
Remaining: []
row 2: [2]
row 1: [3, 5]
row 0: [4, 1, 6]
Remaining: []
row 2: [3]
row 1: [2, 5]
row 0: [4, 6, 1]
Remaining: []
row 2: [1]
row 1: [3, 4]
row 0: [5, 2, 6]
Remaining: []
row 2: [3]
row 1: [1, 4]
row 0: [5, 6, 2]
Remaining: []
row 2: [2]
row 1: [5, 3]
row 0: [6, 1, 4]
Remaining: []
row 2: [1]
row 1: [4, 3]
row 0: [6, 2, 5]
Remaining: []
{2: 24, 3: 8}
You may think at this point “Can we stop talking about this?”, or you may think “what about if it was add instead of difference?”
Nope. Not even a little. With enough balls for a rack of size 6, there are only 7 additive 4-racks! Wild!
All of the above discussion and code in this gist.
Letter-place frequencies
This one also originated from Wolfram Alpha Can't, and asks about the most common letter, by place, by length of word.
I just love this question so much. The solution doesn’t take much work, just a little bashy loop:
for i in `seq 1 15`; do
for j in `seq 1 $i`; do
{ cat /usr/share/dict/words | awk "length($1) == $i { print tolower($1) }" | sort | uniq | awk -v j="$j" '{print tolower(substr($0,j,1))}' | sort | uniq -c | awk '{print $2, $1}' | sort -nk2 | tail -1 | awk '{print $1}'; } | tr "\n " " " | tr -d '[:space:]';
done
printf "\n"
done
which has the added fun of making “words” out of the answers.
ao
aae
saae
saaee
sariee
saraiee
sareliee
sereeliee
pereoiaiie
pereooatiie
pnreoooatiie
pnteooiiatiis
pnteoooiianiss
pneeooooiianiss
I got really excited and wanted to look at a slightly more dramatic presentation, so I made this which I think is way cool! Check out those patterns!!!
The 538-multiplication problem
This is one of the 538 Puzzlers, and while I like the official solutions, I also kinda like my work on it:
10k sims:
random_placement: 2321,
mean_method: 1083,
thresh: (4, 4, 3, 1072),
cond_thresh: (4, 4, 3, 1072),
perfect: (4, 4, 3, 875)
And some cool pics.
End matter
All for now, but there will always be more. Let me know if you find a puzzle that I might like, or you have some input on the above.
comments powered by Disqus