Just for fun: Countdown numbers game solver

[wolfram.hinderer at googlemail.com]

On 22 Jan., 23:56, dg.google.gro... at thesamovar.net wrote:
> So anyone got an answer to which set of numbers gives the most targets
> from 100 onwards say (or from 0 onwards)? IsPythonupto the task?

It's (5, 8, 9, 50, 75, 100): 47561 targets altogether (including
negative ones), 25814 targets >= 100.
(BTW, 1226 sets of numbers give all 900 3-digit targets, but the above
one doesn't; 954 and 981 are missing.)

The following (mostly) straightforward program needed about 30 min for
the calculation. I tried to keep all (intermediate) results in a dict
(which turned out later to need too much memory). I wanted to use the
same dict for memoization. So I let the dict fill itself on access.
The disadvantage of this method is that the function needs to know
that it's being memoized. The advantage is that it's easier (I think)
to manipulate/control the dict.


class AutoFillDict(dict):
    """ Values for missing keys are computed on-the-fly """

    def __init__(self, func, *args, **kwargs):
        self.func = func
        super(AutoFillDict, self).__init__(*args, **kwargs)

    def __missing__(self, key):
        self[key] = self.func(self, key)
        return self[key]


def subs_k(dic, (nums, k)):
    """ Return k-subsets of tuple nums, using dic as cache """
    if k == 1:
        return [(i,) for i in nums]
    if k == len(nums):
        return [nums]
    a = nums[:1]
    b = nums[1:]
    return [a + i for i in dic[b, k-1]] + dic[b, k]


def subs_and_complements(dic, nums):
    """ Return subsets and complements of tuple nums, using dic as
cache """
    if not nums:
        return set([((), ())])
    a = nums[:1]
    b = nums[1:]
    res = set([(s, a + c) for s, c in dic[b]])
    res.update([(a + s, c) for s, c in dic[b]])
    return res


subs_and_comps = AutoFillDict(subs_and_complements)


def countdown(dic, nums, sac_dict=subs_and_comps):
    """Return all possible goals for input nums, using dic as cache

    All numbers in nums must be used.

    """
    if len(nums) == 1:
        return nums
    ret = set()
    for s, c in sac_dict[nums]:
        if s and c:
            xs = dic[s]
            ys = dic[c]
            ret.update([x + y for x in xs for y in ys])
            ret.update([x - y for x in xs for y in ys])
            ret.update([x * y for x in xs for y in ys])
            ret.update([x // y for x in xs for y in ys if y != 0 and x
% y == 0])
    return ret


def print_max(results):
    max_goals = max(results.values())
    max_nums = [n for (n, g) in results.items() if g == max_goals]
    max_nums.sort()
    print "Maximal number of reachable goals: %d" % max_goals
    print "Number of tuples: %d" % len(max_nums)
    for n in max_nums:
        print n


if __name__ == "__main__":

    all_nums = range(1, 11)*2 + [25, 50, 75, 100]
    all_nums = tuple(sorted(all_nums))

    subsets_k = AutoFillDict(subs_k)
    d = AutoFillDict(countdown)

    results = {}
    results100 = {}
    for i, nums in enumerate(sorted(set(subsets_k[all_nums, 6]))):
        # result is the union of reachable goals for all subsets
        result = set()
        for s, c in subs_and_comps[nums]:
            result.update(d[s])
        results[nums] = len(result)
        results100[nums] = len([x for x in result if x >= 100])
        # Prevent MemoryError
        if i % 200 == 0:
            d.clear()

    print "Goals: all integers"
    print_max(results)
    print
    print "Goals: integers >= 100"
    print_max(results100)

--
Wolfram