# Fill grid with Bs

Here is a letter grid:

Here are the rules as to how to manipulate the letters in the grid:

• A marker starts at the first square.
• For each move you can move the marker one square either up, down, left or right without passing the boundaries of the grid.
• If the square you land on has an even letter (B, D, F, H, etc.) in it, the letter will be divided by 2.
• If the square you land on has an odd letter (A, C, E, G, etc.) in it, 1 will be added to that letter.

Below shows an example as to how a we control the marker up, down, left and right and how the letters change. The first one is me doing it at normal speed, and the second one is the time lapse. On that particular example I used 51 moves.

## Is it possible to fill the grid with Bs in under 51 moves?

I programmed the app/tool/game in the above example, and here is the code so you can also have access to it.
Simply run the code. To control the marker, use the arrow keys.

import pygame

# You can change the numbers & size to whatever you like, as long as the numbers remain rectangular
numbers = [[25, 15, 21],
[3, 1, 14],
[23, 9, 14]]

size = 80

pygame.init()
pygame.font.init()
w, h = 600, 600
wn = pygame.display.set_mode((w, h))

class Marker():

def __init__(self, x, y, color, size, line=6):
self.x = x
self.y = y
self.size = size
self.color = color
self.line = line

def go_up(self, distance):
self.y -= distance

def go_down(self, distance):
self.y += distance

def go_left(self, distance):
self.x -= distance

def go_right(self, distance):
self.x += distance

def draw(self):
x, y, w, h = self.x+self.line//2, self.y+self.line//2, self.size-self.line, self.size-self.line
pygame.draw.rect(wn, self.color, (x, y, w, h//6))
pygame.draw.rect(wn, self.color, (x, y+h*5//6+1, w, h//6))
pygame.draw.rect(wn, self.color, (x, y, w//6, h))
pygame.draw.rect(wn, self.color, (x+w*5//6+1, y, w//6, h))

class Square():
def __init__(self, x, y, w, h, num):
self.x, self.y, self.w, self.h, self.num = x, y, w, h, num

def draw(self):
color = (255, 255, 150) if self.num % 2 else (150, 150, 255)
pygame.draw.rect(wn, color, (self.x, self.y, self.w, self.h))

class Grid():
def __init__(self, marker, x, y, size, line=6):
self.numbers = []
self.x = x
self.y = y
self.size = size
self.line = line
self.font = pygame.font.SysFont('Arial', size*2//3)
self.marker = marker
self.squares = []

def add(self):
for i, row in enumerate(self.numbers):
for j, num in enumerate(row):
x, y, w, h = self.x + j*self.size+self.line//2, self.y + i*self.size+self.line//2, self.size-self.line, self.size-self.line
self.squares.append(Square(x, y, w, h, num))

def draw(self):
for square in self.squares:
square.draw()
wn.blit(self.font.render(chr(square.num+64), True, (0, 0, 0)), (square.x+self.size//3.3, square.y+self.size//20))

def show_moves(num, grid):
moves = f'{num} move' if num == 1 else f'{num} moves'
text = grid.font.render(moves, True, (255, 255, 255))
wn.blit(text, (0, len(grid.numbers)*grid.size))

head = Marker(0, 0, (0, 255, 0), size)
grid = Grid(head, 0, 0, size)
grid.numbers = numbers
grid.add()
moves = 0
while True:
grid.draw()
head.draw()
show_moves(moves, grid)
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
elif event.type == pygame.KEYDOWN:
moved = False
if event.key == pygame.K_UP:
if head.y > 0:
head.go_up(size)
moved = True
elif event.key == pygame.K_DOWN:
if head.y < head.size * (len(grid.numbers)-1):
head.go_down(size)
moved = True
elif event.key == pygame.K_LEFT:
if head.x > 0:
head.go_left(size)
moved = True
elif event.key == pygame.K_RIGHT:
if head.x < head.size * (len(grid.numbers[0])-1):
head.go_right(size)
moved = True
if moved:
moves += 1
for square in grid.squares:
if (head.x, head.y) == (square.x-grid.line//2, square.y-grid.line//2):
if square.num % 2:
square.num += 1
else:
square.num = square.num // 2
pygame.display.update()
wn.fill((0, 0, 0))


The rules relates to the Collatz Conjecture (credits to @Moti for pointing that out!).

• It seems the letters are just stand-ins for their A1-Z26 values. Why didn't you just use numbers? Nov 2 '20 at 4:18
• Do you have any reason to believe that there is a 'nice' solution to the optimization? Otherwise, this seems more like a programming challenge to bruteforce the optimal solution (or a game to compete to find the best solution so far), rather than a puzzle that can be solved with an aha moment.
– Deusovi
Nov 2 '20 at 4:19
• Are you aware that this operation relates to the Collatz Conjecture? Some credit to the guy?
– Moti
Nov 2 '20 at 7:08
• @bobble To spread the good news. Nov 2 '20 at 13:56
• @Deusovi Actually I do, no offense to anyone... Nov 2 '20 at 13:56

## 1 Answer

Proof that 51 moves is optimal

First let us look at each of the cells in isolation with the modified Collatz conjecture and ask what is the minimum number of moves required to reduce this cell to a B. For example, a Y reduces to a B in 7 moves as follows $$Y \rightarrow Z \rightarrow M \rightarrow N \rightarrow G \rightarrow H \rightarrow D \rightarrow B$$ Now let us replace each cell in the grid with the minimum number of moves required to reduce this cell to a B. This will look like the following


7 4 7
2 1 4
6 6 4


The procedure then simplifies to reducing the value by 1 each time we make a move into a new cell. If the cell has a 0 in it already then we change it to a 1 (because $$B \rightarrow A \rightarrow B$$).
Now let us imbue the grid with a chessboard pattern so that the corner and middle cells become black cells and the edge cells become white. Then each move consists of changing the colour of your cell. Notice that the sum of the entries in the black cells is $$7+7+1+6+4 = 25$$. This means we must visit the black cells at least $$25$$ times on our path.
Since the first visited cell will be a white cell, we must also visit the white cells at least $$25$$ times. However, because each of the white cells contains an even value ($$4,4,2,6$$) this means that we must visit the white cells an even number of times which implies that we must visit the white cells at least $$26$$ times.

Hence, overall, we must make $$25 + 26 = 51$$ moves and because we already know that this is achievable, this is the minimum.