Jane Street current puzzle: https://www.janestreet.com/puzzles/current-puzzle/
I wrote a program to simulate the process of filling in elements.
If anyone is interested, copy the code into Notebook and after that,
you can update each cell by m[i, j].update(new_val). Setting a cell to -1 means to shade it.
import numpy as np
import seaborn as sns
from typing import List, Optional
import matplotlib.colors as colors
from matplotlib import pyplot as plt
# b is the board, each number represent a connected region, must be filled with the same number
b = [
[ 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4],
[ 1, 5, 5, 5, 2, 2, 3, 4, 4, 4, 6],
[ 1, 5, 5, 2, 2, 2, 3, 4, 4, 4, 6],
[ 1, 5, 5, 2, 2, 7, 7, 4, 6, 6, 6],
[ 1, 5, 2, 2, 4, 4, 7, 4, 6, 9, 6],
[ 1, 4, 4, 4, 4, 4, 4, 4, 9, 9,10],
[11, 4, 4, 4, 4,12,12, 4, 9, 9, 9],
[11,11,13, 4,13,12,12, 4, 4, 9, 4],
[11,11,13,13,13,12,12, 4, 4, 4, 4],
[11,13,13,11,11,11,12, 4, 4, 4,14],
[11,11,11,11,11,12,12,12, 4, 4,14],
]
def sieve_of_eratosthenes(limit):
# Create a boolean array "prime[0..limit]" and initialize
# all entries it as true. A value in prime[i] will
# finally be false if i is Not a prime, else true.
prime = [True for _ in range(limit + 1)]
p = 2
while (p * p <= limit):
# If prime[p] is not changed, then it is a prime
if prime[p]:
# Updating all multiples of p to not prime
for i in range(p * p, limit + 1, p):
prime[i] = False
p += 1
prime[0], prime[1] = False, False # 0 and 1 are not primes
# Collecting all prime numbers
primes = [p for p, is_prime in enumerate(prime) if is_prime]
return primes
square = lambda x: int(x**0.5)**2 == x
one_more_than_a_palindrome = lambda x: str(x-1) == str(x-1)[::-1]
sum_of_digit_is_7 = lambda x: sum(int(i) for i in str(x)) == 7
multiple_of_37 = lambda x: x % 37 == 0
palindrome_multiple_of_23 = lambda x: x % 23 == 0 and str(x) == str(x)[::-1]
product_of_digits_ends_in_1 = lambda x: np.prod([int(i) for i in str(x)]) % 10 == 1
multiple_of_88 = lambda x: x % 88 == 0
one_less_than_a_palindrome = lambda x: str(x+1) == str(x+1)[::-1]
def fibonacci(x):
if x in {1, 2, 3, 5, 8, 13, 21, 34, 55, 89}:
return True
x1 = x * 5**0.5
q = np.log(x1) / np.log((1 + 5**0.5) / 2)
q = np.round(q)
x2 = (((1+5**0.5)/2)**q - ((1-5**0.5)/2)**q) / 5**0.5
return np.allclose(x, x2)
primes = sieve_of_eratosthenes(10**6)
pop = set()
for i in primes:
for j in primes:
if i**j >= 10**12:
break
pop.add(i**j)
def prime_raised_to_a_prime_power(x):
return x in pop
rules = [
square,
one_more_than_a_palindrome,
prime_raised_to_a_prime_power,
sum_of_digit_is_7,
fibonacci,
square,
multiple_of_37,
palindrome_multiple_of_23,
product_of_digits_ends_in_1,
multiple_of_88,
one_less_than_a_palindrome
]
def valid_rules(m):
valid = [[True] * 11 for _ in range(11)]
words = []
for i in range(11):
s = ""
st = 0
for j in range(11):
cell = m[i, j]
if cell.m == 1:
words.append([i, st, j, s])
s = ""
st = j+1
else:
s += str(cell.v)
words.append([i, st, 11, s])
words = [i for i in words if i[-1] != ""]
for (i, st, ed, s) in words:
if len(s) == 1 or s[0] == '0' or not rules[i](int(s)):
for j in range(st, ed):
valid[i][j] = False
return valid
def plot_map(m):
# plot heatmap, color based on m.c, annotate with m.val
annot = [[str(m[i, j].v) if m[i, j].v != -1 else "" for j in range(11)] for i in range(11)]
colors = [[m[i, j].c if m[i, j].m != 1 else 15 for j in range(11)] for i in range(11)]
valid = [[m[i, j].valid() for j in range(11)] for i in range(11)]
valid2 = valid_rules(m)
plt.figure(figsize=(12, 12))
plt.rcParams.update({'font.size': 15})
ax = sns.heatmap(colors, annot=annot, fmt="s", cmap='tab20', vmin=0.5, vmax=20.5, cbar_kws={"ticks": list(range(21))}, square=True)
ax.xaxis.tick_top()
def x(ax, i, j):
ax.plot([i, i+1], [j, j+1], color='red', linewidth=2)
ax.plot([i, i+1], [j+1, j], color='red', linewidth=2)
def xx(ax, i, j):
ax.vlines(i+0.5, j, j+1, color='red', linewidth=2, alpha=0.2)
ax.hlines(j+0.5, i, i+1, color='red', linewidth=2, alpha=0.2)
for i in range(11):
for j in range(11):
if not valid[i][j]:
x(ax, j, i)
if not valid2[i][j]:
xx(ax, j, i)
class Cell:
def __init__(self, i, j) -> None:
self.m = 0 # mask
self.c = -100 # color
self.v = 0 # value
# neighbor cells
self.u = None # type: Optional[Cell]
self.l = None # type: Optional[Cell]
self.d = None # type: Optional[Cell]
self.r = None # type: Optional[Cell]
self.i = i
self.j = j
def valid(self) -> bool:
if self.m == 1:
for nbr in [self.u, self.l, self.d, self.r]:
if nbr and nbr.m == 1:
return False
return True
for nbr in [self.u, self.l, self.d, self.r]:
if nbr is None or nbr.m == 1:
continue
elif nbr.c == self.c and nbr.v != self.v:
return False
elif nbr.c != self.c and nbr.v == self.v:
return False
return True
def update_and_plot(self, new_val):
if new_val != -1:
self.m = 0
self.update_val(new_val)
else:
self.m = 1
self.v = -1
plot_map(m)
def update(self, new_val):
return self.update_and_plot(new_val)
def update_val(self, new_val, visited=None):
if visited is None:
visited = set()
if self.m == 1:
return
self.v = new_val
visited.add(self)
for neighbor in [self.u, self.l, self.d, self.r]:
if neighbor and neighbor not in visited and neighbor.m == 0 and neighbor.c == self.c:
neighbor.update_val(new_val, visited)
def __str__(self): return "-1" if self.m else str(self.v)
def __repr__(self): return "-1" if self.m else str(self.v)
m = np.array([[Cell(i, j) for j in range(11)] for i in range(11)])
init_val = {i: np.random.randint(0, 10) for i in range(1, 15)}
# fill color
for i in range(11):
for j in range(11):
m[i, j].c = b[i][j]
m[i, j].v = init_val[b[i][j]]
m[i, j].m = int(np.random.rand() > 0.999)
if m[i, j].m:
m[i, j].v = -1
# set neighbors
if i > 0: m[i, j].u = m[i-1, j]
if j > 0: m[i, j].l = m[i, j-1]
if i < 10: m[i, j].d = m[i+1, j]
if j < 10: m[i, j].r = m[i, j+1]
plot_map(m)