7
\$\begingroup\$

This is a game of math in Poker. Two people each have a pile of cards. They then each place 2 cards on the table at the same time. Every card is treated as a number. The players need to find a way to calculate 24 from the numbers. For example, you are given 3 5 4 8, and you can get 24 by (3+8-5) * 4, or 8*4-5-3. This code tries to solve this problem.

Can anyone help me to improve it?

comp()

def comp( nums,i,j,exps,op):
    nums0=[];
    for x in range(0,len(nums)):
        if not (x==i or x==j):
            nums0.append(nums[x])

    if(op=='+'):
        tmp = nums[i]+nums[j];
    elif(op=='*'):
        tmp = nums[i]*nums[j];
    elif(op=='-'):
        tmp = nums[i]-nums[j];
    elif(op=='/'):
        if(nums[j]<0.0001 and nums[j]>-0.0001 ):
            tmp=100000;
        else:
            tmp = nums[i]*1.0/nums[j];
    elif(op=='^'):
        return comp(nums,j,i,exps,'-');
    elif(op=='%'):
        return comp(nums,j,i,exps,'/');

    exps.append(str((nums[i],op,nums[j])));
    nums0.append(tmp);
    return nums0

cal()

def cal(nums, exps):
    if(len(nums)==1):
        return (nums[0]>23.9999 and nums[0]<24.0001);
    pairs = {};
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):
            tmp_key= str((min(nums[i],nums[j]),max(nums[i],nums[j])));
            #print tmp_key
            if(pairs.has_key(tmp_key)):
                continue;
            #print 'put '+tmp_key
            pairs[tmp_key]=''
            for op in ('+','-','*','/','^','%'):
                nums0 = comp(nums,i,j,exps,op)
                if(cal(nums0,exps)):
                    print str(exps);
                exps.pop();

cal([3,9,10,7],[]);

cal([5,5,5,1],[]);

cal([10,9,4,1],[]);
\$\endgroup\$
  • 1
    \$\begingroup\$ It's not clear to me why this has been downvoted. Can someone explain? \$\endgroup\$ – Gareth Rees Mar 24 '15 at 18:27
  • 4
    \$\begingroup\$ @GarethRees The question is now good, but Rev 1 of the question was a code dump with no explanation of purpose. \$\endgroup\$ – 200_success Mar 25 '15 at 2:25
  • \$\begingroup\$ Another nice shortcut you can use: -0.0001 < nums[j] < 0.0001 \$\endgroup\$ – Dan Mar 26 '15 at 1:48
  • \$\begingroup\$ solutions can be grouped by two categories: // ($a, $b) and ($c, $d) or // ((($a, $b), $c), $d) helloacm.com/24 \$\endgroup\$ – justyy Mar 19 '16 at 23:55
4
\$\begingroup\$

A few pieces of feedback:

  • Semi-colons in Python aren't necessary, unless you're trying to issue two commands on one line like a=5;b=6. I couldn't find a pep style guide that specifically bans them, but most Python code doesn't use them, as they are unnecessary.
  • You set temp_key to a str, but that is unnecessary. I'm assuming you added that because you probably had it as a list before and got a "unhashable" error when trying to use a list as a dictionary key. This is a perfect spot to use a tuple, and your code will work if you just remove the str (leaving the ()), because tuples are hashable and immutable.
  • Instead of relying on floating point accuracy, which isn't a problem given the magnitude of your examples, an alternative would be to use the fractions class and all your calculations would be exact.
  • Instead of recursively calling the comp function for your inverse negative and inverse divide, it'd probably be much simpler to just write tmp = nums[j]-nums[i]. I'd suggest it for the inverse divides too.
\$\endgroup\$
1
\$\begingroup\$

The first issue is formatting. Here's your code reformatted to look nice.

def comp(nums, i, j, exps, op):
    nums0 = []
    for x in range(0, len(nums)):
        if not (x == i or x == j):
            nums0.append(nums[x])

    if op == '+':
        tmp = nums[i] + nums[j]
    elif op == '*':
        tmp = nums[i] * nums[j]
    elif op == '-':
        tmp = nums[i] - nums[j]
    elif op == '/':
        if nums[j] < 0.0001 and nums[j] > -0.0001:
            tmp = 100000
        else:
            tmp = nums[i] * 1.0 / nums[j]
    elif op == '^':
        return comp(nums, j, i, exps, '-')
    elif op == '%':
        return comp(nums, j, i, exps, '/')

    exps.append(str((nums[i], op, nums[j])))
    nums0.append(tmp)
    return nums0

def cal(nums, exps):
    if len(nums) == 1:
        return nums[0] > 23.9999 and nums[0] < 24.0001;
    pairs = {}
    for i in range(0, len(nums)):
        for j in range(i+1, len(nums)):
            tmp_key = str((min(nums[i], nums[j]), max(nums[i], nums[j])))
            # print tmp_key
            if pairs.has_key(tmp_key):
                continue
            # print 'put ' + tmp_key
            pairs[tmp_key] = ''
            for op in '+', '-', '*', '/', '^', '%':
                nums0 = comp(nums, i, j, exps, op)
                if cal(nums0, exps):
                    print(str(exps))
                exps.pop()

I removed the semicolons, added proper spacing and removed useless parentheses. I also put brackets on the print so it works on Python 3, but that's optional.

Further, there are a lot of trivial non-formatting touch-ups:

  • has_key is long deprecated; use the in operator.
  • range(0, x) is just range(x).
  • for i in range(len(vals)) is better as for i, _ in enumerate(vals)
  • List comprehensions are great.
  • not (x == i or x == j) just looks cleaner as x != i and x != j
  • x < upper_bound and x > lower_bound is just lower_bound < x < upper_bound.
  • x * 1.0 / y is just x / float(y), which is just x / y with from __future__ import division
  • itertools.combinations is your friend
  • (min(x, y), max(x, y)) is tuple(sorted((x, y)))
  • Dead comments are rotting comments. Remove them.
  • pairs is being used as a set, so use a set.
  • Move values down to where they're used; don't leave them hanging... especially if you might just discard them first.
  • Recursion in comp seems to be doing more harm than good. Moving your strange division to another function deals with this better.
  • Throw an error for unknown operators
  • Get rid of tmp in comp by moving the operation to another function
  • Your naming is poor. Try to write meaningful names.
  • exps doesn't need to hold strings. Tuples would do just as well, if not better. The same goes for pairs.
from __future__ import division

from itertools import combinations

def strange_div(lhs, rhs):
    if -0.0001 < rhs < 0.0001:
        return 100000
    else:
        return lhs / rhs

def do_op(op, lhs, rhs):
    if op == '+':
        return lhs + rhs
    elif op == '*':
        return lhs * rhs
    elif op == '-':
        return lhs - rhs
    elif op == '^':
        return rhs - lhs
    elif op == '/':
        return strange_div(lhs, rhs)
    elif op == '%':
        return strange_div(rhs, lhs)
    raise ValueError("Unknown operator: {!r}".format(op))

def compute_step(operands, x_idx, y_idx, method, op):
    method.append((operands[x_idx], op, operands[y_idx]))
    new_operands = [num for x, num in enumerate(operands) if x != x_idx and x != y_idx]
    new_operands.append(do_op(op, operands[x_idx], operands[y_idx]))
    return new_operands

def find_close_calculations(operands, method):
    if len(operands) == 1:
        return 23.9999 < operands[0] < 24.0001

    pairs = set()
    for (i, lhs), (j, rhs) in combinations(enumerate(operands), 2):
        tmp_key = tuple(sorted((lhs, rhs)))
        if tmp_key in pairs:
            continue
        pairs.add(tmp_key)

        for op in '+', '-', '*', '/', '^', '%':
            stepped = compute_step(operands, i, j, method, op)
            if find_close_calculations(stepped, method):
                print(str(method))
            method.pop()

Then we see find_close_calculations is doing

if find_close_calculations(stepped, method):
    print(str(method))

which is really a bit odd as it means find_close_calculations([24], []) won't print anything, it means we have a meaningless return value from calling it and it means we have to pass a strange second argument. Better would be to extract the recursive component out from the result-giving. Another fancier option is to generate operands differently.

def find_close_calculations(operands):
    if len(operands) == 1:
        if 23.9999 < operands[0] < 24.0001:
            yield []
        return

    pairs = set()
    for (i, lhs), (j, rhs) in combinations(enumerate(operands), 2):
        tmp_key = tuple(sorted((lhs, rhs)))
        if tmp_key in pairs:
            continue
        pairs.add(tmp_key)

        for op in '+', '-', '*', '/', '^', '%':
            stepped = compute_step(operands, op, i, j)
            for method in find_close_calculations(stepped):
                method.append((lhs, op, rhs))
                yield method

This gives a generator of methods, rather than printing them, which is much more useful. Printing the output is thus done with

for method in find_close_calculations([3, 9, 10, 7]):
    print(method)

Since new_operands is an expensive copy anyway, you can simplify the chain by just passing a value and deleting more trivially:

def compute_step(operands, op, lhs, rhs):
    new_operands = operands.copy()
    new_operands.remove(lhs)
    new_operands.remove(rhs)
    new_operands.append(do_op(op, lhs, rhs))
    return new_operands

def find_close_calculations(operands):
    ...
    for lhs, rhs in combinations(operands, 2):
        ...
            stepped = compute_step(operands, op, lhs, rhs)
            ...

A little longer, but much more obvious of intent.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.