TransWikia.com

Hit the target number

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:

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP