Vamshi Jandhyala - Can You Randomly Move The Tower?

Riddler Express

For your first weekly CrossProduct, there are five three-digit numbers - each belongs in a row of the table below, with one digit per cell. The products of the three digits of each number are shown in the rightmost column. Meanwhile, the products of the digits in the hundreds, tens and ones places, respectively, are shown in the bottom row. Can you find all five three-digit numbers and complete the table?

Computational Solution

from z3 import *

class MysteriousNumbersSolver:
    def __init__(self):
        self.X = [[Int("self.X_%s_%s" % (i, j)) for j in range(3)]
                      for i in range(5)]
        self.s = Solver()
        self.s.add([And(0 <= self.X[i][j], self.X[i][j]<= 9) for i in range(5) for j in range(1,3)])
        self.s.add([And(0 <= self.X[i][0], self.X[i][0]<= 9) for i in range(5)])

    def set_constraints(self):   
        self.s.add(self.X[0][0]*self.X[0][1]*self.X[0][2]==135)
        self.s.add(self.X[1][0]*self.X[1][1]*self.X[1][2]==45)
        self.s.add(self.X[2][0]*self.X[2][1]*self.X[2][2]==64)
        self.s.add(self.X[3][0]*self.X[3][1]*self.X[3][2]==280)
        self.s.add(self.X[4][0]*self.X[4][1]*self.X[4][2]==70)
        self.s.add(self.X[0][0]*self.X[1][0]*self.X[2][0]*self.X[3][0]*self.X[4][0]==3000)
        self.s.add(self.X[0][1]*self.X[1][1]*self.X[2][1]*self.X[3][1]*self.X[4][1]==3969)
        self.s.add(self.X[0][2]*self.X[1][2]*self.X[2][2]*self.X[3][2]*self.X[4][2]==640)

    def output_solution(self):
        m = self.s.model()
        for i in range(5):
            print(" ".join([str(m.evaluate(self.X[i][j])) for j in range(3)]))

    def solve(self):
        self.set_constraints()
        if self.s.check() == sat:
            self.output_solution()
        else:
            print(self.s)
            print("Failed to solve.")

s = MysteriousNumbersSolver()
s.solve()

Here is the solution

Riddler Classic

Cassius the ape (a friend of Caesar’s) has gotten his hands on a Lucas’ Tower puzzle (also commonly referred to as the “Tower of Hanoi”). This particular puzzle consists of three poles and three disks, all of which start on the same pole. The three disks have different diameters — the biggest disk is at the bottom and the smallest disk is at the top. The goal is to move all three disks from one pole to any other pole, one at a time, but there’s a catch. At no point can a larger disk ever sit atop a smaller disk. It turns out that Cassius couldn’t care less about solving the puzzle, but he is very good at following directions and understands a larger disk can never sit atop a smaller disk. With each move, he randomly chooses one among the set of valid moves.

On average, how many moves will it take for Cassius to solve this puzzle with three disks?

Solution

The analytical solution for the case of \(n\) disks has been provided in this paper. Here is my computational solution:

Computational Solution

from random import choice

runs, n, total_cnt = 100000, 3, 0
other_towers = [[1,2],[0,2],[0,1]]
for _ in range(runs):
    cnt, towers = 0, [list(range(n,0,-1)),[],[]]
    while towers[2] != list(range(n,0,-1)):
        moves = []
        for i in [0,1,2]:
            for j in other_towers[i]: 
                if towers[i] and (not towers[j] or towers[j][-1]>towers[i][-1]):
                    moves.append((i,j))
        f, t = choice(moves)
        towers[t].append(towers[f].pop())
        cnt += 1
    total_cnt += cnt
print(total_cnt/runs)

On average it will take Cassius \(\bf{141.45}\) moves to solve the puzzle with \(\bf{three}\) disks.