Code Review Asked by Mixopteryx on November 19, 2021
After I played the game "The Mesh" for a while I figured that I wanted to make a solver in Python. See the video on the website for a quick intro, I also explain the rules below.
The Mesh rules
We start with a number of tiles with integers on them. The target is to combine the integers by addition or subtraction to get a target number. There are also multiply/divide by 2 tiles and some integer tiles come with bonuses attached. You get an extra multiplication tile or in game bonuses if you reach the target using such a tile.
Please note that the solution is not unique.
My code
My implementation only account for the default and multiplication tiles.
I am specifically interested in feedback on how to improve the readability and flexibility of the code, but appreciate all comments. Two specific questions:
My program is the following (mesh.py):
import copy
import itertools
import sys
inf = sys.maxint
def mesh(target, values, *arg):
if len(arg) > 0:
values = [values]
[values.append(val) for val in arg]
# Instantiate x2 if not done
values = [val() if (val == X2) else val for val in values]
return solve(target, values)
def solve(target, values):
# Find optimal grouping of tiles. Returned as tuples
best_set = None
best_score = (inf, 0)
for subset in permuted_subgroups(list(values)):
# Find best sign composition for each subgroup
for counter, group in enumerate(subset): # Do for each set
best_group = None
best_group_score = (inf, 0)
for signed_group in signs_group(group):
try: # Try to calculate score
group_score = scoring(target, [signed_group])
except (X2OddError, X2MultiplySelfError): # If set is invalid, skip to next loop
continue
if is_better(group_score, best_group_score):
best_group_score = group_score
best_group = signed_group
subset[counter] = best_group
# Score each full set separately
try: # Try to calculate score
score = scoring(target, subset)
except (X2OddError, X2MultiplySelfError): # If set is invalid, skip to next loop
continue
if is_better(score, best_score):
best_score = score
best_set = subset
return best_set, best_score
def scoring(target, sets):
# Take sets that should be combined and calculate:
# Number of tiles lost
# Number of points scored
# Totals per set
results = [sum(tup) for tup in sets]
# Points and penalties
points = 0
tiles = 0
for val in results:
if isinstance(val, X2):
pass # No effect on points/tile loss
elif abs(val) == target:
points += 1
else:
tiles += abs(val)
return tiles, points
def is_better(score, ref_score):
# Return true if score1 is better than score 2
if score[0] > ref_score[0]:
return False
elif score[0] < ref_score[0]:
return True
else:
return score[1] > ref_score[1]
def signs(number):
# Return an iterable that returns all sign combinations of length number
return itertools.product([-1, 1], repeat=number)
def signs_group(my_list):
# Return an iterator over all sign combinations for the list
if len(my_list) == 1:
yield my_list
else:
for sign in signs(len(my_list)):
this_set = [v * s for (v, s) in zip(my_list, sign)]
yield this_set
class X2OddError(Exception):
# Raised if x2 tries to divide an odd number
pass
class X2MultiplySelfError(Exception):
# trying to multiply x2 with x2
pass
class X2(object):
# Multiplication/division tile
def __init__(self, mode=1):
self.mode = mode
def __add__(self, num):
# For joining tiles
if num == 0:
return self
elif isinstance(num, X2):
raise X2MultiplySelfError('Tried to merge x2 with x2')
elif self.mode == 1:
return 2 * num
else:
if not num % 2 == 0:
raise X2OddError('Cannot divide odd number by 2')
return num / 2
def __radd__(self, num):
return self.__add__(num)
def __mul__(self, num):
# For switching mode from multiply to divide
assert abs(num) == 1
return X2(self.mode * num)
def __rmul__(self, num):
return self.__mul__(num)
def __str__(self):
if self.mode == 1:
return '*2'
else:
return '/2'
def __repr__(self):
return self.__str__()
# %% The following is retrieved from # http://stackoverflow.com/questions/19368375/set-partitions-in-python
def slice_by_lengths(lengths, the_list):
for length in lengths:
new = []
for i in range(length):
new.append(the_list.pop(0))
yield new
def partition(number):
return {(x,) + y for x in range(1, number) for y in partition(number - x)} | {(number,)}
def subgroups(my_list):
partitions = partition(len(my_list))
permed = []
for each_partition in partitions:
permed.append(set(itertools.permutations(each_partition, len(each_partition))))
for each_tuple in itertools.chain(*permed):
yield list(slice_by_lengths(each_tuple, copy.deepcopy(my_list)))
def permuted_subgroups(my_list):
for subset in itertools.permutations(my_list, len(my_list)):
groups = subgroups(list(subset))
while True:
try:
yield groups.next()
except StopIteration:
break
def permuted_subgroups_u(my_list):
for subset in itertools.permutations(my_list, len(my_list)):
groups = subgroups(list(subset))
while True:
try:
yield groups.next()
except StopIteration:
break
# %% End Stackexchange
# Algorithm_u by Donald Knuth, via Adeel Zafar Soomro at Stackexchange
# http://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions
def algorithm_u(ns, m):
# Generate all methods of partition ns into m subsets
# Example: for {1,2,3,4} a 3-subset is {{1,2},{3},{4}}
def visit(n, a):
# noinspection PyUnusedLocal
ps = [[] for i in xrange(m)]
for j in xrange(n):
ps[a[j + 1]].append(ns[j])
return ps
def f(mu, nu, sigma, n, a):
if mu == 2:
yield visit(n, a)
else:
for v in f(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
yield v
if nu == mu + 1:
a[mu] = mu - 1
yield visit(n, a)
while a[nu] > 0:
a[nu] -= 1
yield visit(n, a)
elif nu > mu + 1:
if (mu + sigma) % 2 == 1:
a[nu - 1] = mu - 1
else:
a[mu] = mu - 1
if (a[nu] + sigma) % 2 == 1:
for v in b(mu, nu - 1, 0, n, a):
yield v
else:
for v in f(mu, nu - 1, 0, n, a):
yield v
while a[nu] > 0:
a[nu] -= 1
if (a[nu] + sigma) % 2 == 1:
for v in b(mu, nu - 1, 0, n, a):
yield v
else:
for v in f(mu, nu - 1, 0, n, a):
yield v
def b(mu, nu, sigma, n, a):
if nu == mu + 1:
while a[nu] < mu - 1:
yield visit(n, a)
a[nu] += 1
yield visit(n, a)
a[mu] = 0
elif nu > mu + 1:
if (a[nu] + sigma) % 2 == 1:
for v in f(mu, nu - 1, 0, n, a):
yield v
else:
for v in b(mu, nu - 1, 0, n, a):
yield v
while a[nu] < mu - 1:
a[nu] += 1
if (a[nu] + sigma) % 2 == 1:
for v in f(mu, nu - 1, 0, n, a):
yield v
else:
for v in b(mu, nu - 1, 0, n, a):
yield v
if (mu + sigma) % 2 == 1:
a[nu - 1] = 0
else:
a[mu] = 0
if mu == 2:
yield visit(n, a)
else:
for v in b(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
yield v
n = len(ns)
a = [0] * (n + 1)
for j in xrange(1, m + 1):
a[n - m + j] = j - 1
return f(m, n, 0, n, a)
I also have written a few tests for pytest (test_mesh.py):
import pytest
import mesh
from mesh import X2
@pytest.mark.parametrize("target,sets,expected", [
(1, (5, -5, -6, 7), [(7, -6), (5, -5)]), # level 1
(1, (4, -2, 3, -3), [(4, -3), (3, -2)]), # lvl 1
(1, (4, 2, 3, 3), [(4, -3), (3, -2)]), # lvl 1 - need sign change
(5, (9, 9, 4, 1), [(9, -9), (4, 1)]),
(7, (5, 2, 3, 1, X2()), [(5, 2), (3, X2(), 1)]),
(10, (5, 4, 7, 9, X2()), [(5, -7, 9, X2(), -4)]),
(2, (4, X2()), [(4, X2() * -1)]),
])
def test_first_mesh(target, sets, expected):
# Ensure that the score for solution is as good as mine
score = mesh.scoring(target, mesh.mesh(target, sets)[0])
expected_score = mesh.scoring(target, expected)
assert score == expected_score
@pytest.mark.parametrize("target,sets,expected", [
(1, [(7, -6), (5, -5)], (0, 1)),
(1, [(4, -3), (3, -2)], (0, 2)),
(5, [(7, -6), (5, -5)], (1, 0)),
(4, [(4, -3), (3, -2)], (2, 0)),
])
def test_scoring(target, sets, expected):
assert mesh.scoring(target, sets) == expected
@pytest.mark.parametrize("score,ref_score,expected", [
((0, 1), (1, 2), True),
((1, 3), (0, 1), False),
((0, 2), (0, 1), True),
((0, 1), (0, 1), False),
((3, 1), (3, 2), False),
])
def test_is_better(score, ref_score, expected):
assert mesh.is_better(score, ref_score) == expected
def test_x2():
a = X2()
# Check that addition (multiplication) works as expected:
assert a + 1 == 2
assert 1 + a == 2
# Switch to division mode, check both left and right mode switch
b = X2(-1)
c = -1 * X2()
assert b + 2 == 1
assert 2 + b == 1
assert c + 2 == 1
assert 2 + c == 1
# Check that multiplication creates a new object
b = a * -1
assert a != b
Example usage from python prompt:
import mesh
target = 1
tiles = (5, -5, -6, 7)
mesh.mesh(target, tiles)
# Yields ([[-5, 5, 6, -7]], (0,1))
# -5+5+5-7 = -1 gives zero lost tiles and 1 point
# (Sign doesn't matter)
target = 10
tiles = (5, 4, 7, 9, mesh.X2())
mesh.mesh(target, tiles)
# Yields ([(-5, -4, 7, /2, -9)], (0, 1))
# (-5-4+7)/2-9 = -10 gives zero lost tiles and 1 point
Test output:
$ pytest
============================= test session starts ==============================
platform darwin -- Python 2.7.11, pytest-3.0.5, py-1.4.31, pluggy-0.4.0
rootdir: /Users/Mixopteryx/TheMesh, inifile:
collected 17 items
test_mesh.py .................
========================== 17 passed in 1.60 seconds ===========================
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP