Hit the target number

Question

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:

• Can the multiplication tile be implemented better?
• How could I implement the bonus tiles effectively?

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 ===========================

Answer 1

We evaluate this for side effects:

 [values.append(val) for val in arg]

I would rather see this stated more explicitly:

 for val in arg:
 values.append(val) 

which would clarify that values.extend(arg) is the natural way to express Author's Intent.

I don't like this assignment:

 values = [val() if (val == X2) else val for val in values]

It is unclear to me what X2 is all about. A more descriptive identifier, or at least a class """docstring""", might have been chosen. Plus, we should see [X2() if ... in that list comprehension.

---

is_better would be clearer, and shorter, if we immediately dispatched the score[0] == ref_score[0] case and returned the [1] comparison. With that dealt with we could simply return score[0] < ref_score[0].

Or, use != on [0] first, then proceed to [1].

---

In permuted_subgroups it appears that what we want is yield from groups.

---

Looks good. Ship it!