6
\$\begingroup\$

So this is a programming challenge I saw:

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100. For example 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100.

This is interesting, if useless.

Anyway I have written two scripts in Python 3 to solve the problem, and spoilers ahead!

The results are:

1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89

And the scripts are two-parted, one part to generate expressions and the other to evaluate them.

The evaluation parts of the scripts are the same, but the generation parts are different.

One script uses random numbers to add the fillers, and only append unique expressions to a list.

This script takes less lines (39 lines), but takes a rather long time to generate all the expressions.

The other script uses incremental iteration to generate the expressions, this script takes 57 lines, but it executes significantly faster.

Here are the scripts:

Random

import random, re

lines = []

Fillers = ('+', '-', '')

while len(lines) < 6561:
    expression = ''
    n = 0
    for i in range(17):
        if i % 2 == 0:
            n += 1
            expression += str(n)
        else: expression += Fillers[random.randrange(3)]
    if expression not in lines: lines.append(expression)

lines.remove('123456789')

result = []

for line in lines:
    array = re.split('(\-|\+)', line)
    ops = 'add'
    num = 0
    for a in array:
        if a.isdigit():
            if ops == 'add':
                num += int(a)
            else:
                num  -= int(a)
        elif a in Fillers:
            if a == '+':
                ops = 'add'
            else:
                ops = 'sub'
    if num == 100: result.append(line)
    
result.sort()

print(*result, sep='\n')

Ordered

import re

array = [[0, 0, 0, 0, 0, 0, 0, 0]]
elems = [0, 0, 0, 0, 0, 0, 0, 0]

for n in range(6560):
    copy = elems.copy()
    copy[-1] += 1
    while 3 in copy:
        i = copy.index(3)
        copy[i:] = [0] * (len(copy) - i)
        copy[i - 1] += 1
    array.append(copy)
    elems = copy

lines = []

Fillers = ('+', '-', '')

j = 0

while len(lines) < 6561:
    expression = ''
    i, k = 0, 0
    for n in range(17):
        if n % 2 == 0:
            i += 1
            expression += str(i)
        else:
            expression += Fillers[array[j][k]]
            k += 1
    lines.append(expression)
    j += 1

lines.remove('123456789')

result = []

for line in lines:
    array = re.split('(\-|\+)', line)
    ops = 'add'
    num = 0
    for a in array:
        if a.isdigit():
            if ops == 'add':
                num += int(a)
            else:
                num  -= int(a)
        elif a in Fillers:
            if a == '+':
                ops = 'add'
            else:
                ops = 'sub'
    if num == 100: result.append(line)
    
result.sort()

print(*result, sep='\n')

What improvements can be made to the two scripts?

Here I am asking about two problems:

1, how to make the random generation take less time?

2, how to make the ordered generation take less code while maintaining the same logic?

Any help will be appreciated. (I will upvote any answers.)

\$\endgroup\$
7
\$\begingroup\$

General

  1. Move magic numbers into explicitly named variables. Otherwise it takes the reader a lot of unnecessary work to understand why 6561 and 17 are relevant and / or correct.
  2. Avoid multiple imports in one line (import random, re), prefer one import per line.
  3. Avoid multiple statements in a single line: if num == 100: result.append(line)
  4. The regex '(\-|\+)' can be simplified to '([-+])'. Single character alternation or character class on StackOverflow
  5. Follow PEP8 for naming variables: Fillers -> fillers or probably rather FILLERS
  6. You don't need to evaluate expressions on your own, simply pass the str expression to eval(). Surprisingly, this executes a bit slower on my machine than your manual approach. I'd still prefer it for its readability, adaptability and conciseness.

Random

Note: This brute-force approach might be an interesting exercise, but the ordered approach is undoubtedly preferable for this challenge.

  1. FILLERS[random.randrange(3)] is better expressed as random.choice(FILLERS)
  2. lines.remove('123456789'): I see no reason for manually removing this one single possibility.
  3. Repeated membership checking (if expression not in lines) can get expensive for a list. sets are optimised for membership checking. This change alone provides roughly a 5x speed-up on my machine.
  4. Using a list comprehension together with itertools.chain.from_iterable() is faster than manually constructing the expression.

Suggested code

import random
from itertools import chain

DIGITS = '123456789'
LAST_DIGIT = DIGITS[-1]
NUM_DIGITS = len(DIGITS)

NUM_FILLERS = len(DIGITS) - 1
FILLERS = ('+', '-', '')

TARGET = 100

NUM_POSSIBILITIES = len(FILLERS) ** (NUM_DIGITS - 1)


def make_expression(digits, fillers):
    return ''.join(chain.from_iterable(zip(digits, fillers))) + LAST_DIGIT


def main():
    expressions = set()

    while len(expressions) < NUM_POSSIBILITIES:
        fillers = [random.choice(FILLERS) for _ in range(NUM_FILLERS)]
        expressions.add(make_expression(DIGITS, fillers))

    result = sorted(expr for expr in expressions if eval(expr) == TARGET)

    print(*result, sep='\n')

Ordered

This approach desperately needs comments to explain the underlying logic. Adding proper documentation will increase your chances for a proper review significantly. It's unnecessarily hard to figure out what's going on and why for this snippet alone:

array = [[0, 0, 0, 0, 0, 0, 0, 0]]
elems = [0, 0, 0, 0, 0, 0, 0, 0]

for n in range(6560):
    copy = elems.copy()
    copy[-1] += 1
    while 3 in copy:
        i = copy.index(3)
        copy[i:] = [0] * (len(copy) - i)
        copy[i - 1] += 1
    array.append(copy)
    elems = copy

You don't need to manually create and store array as a list of all possible combinations of characters. You can get a memory-efficient generator from itertools.product

Suggested code

from itertools import product, chain

DIGITS = '123456789'
LAST_DIGIT = DIGITS[-1]

NUM_FILLERS = len(DIGITS) - 1
FILLERS = ('+', '-', '')

TARGET = 100


def make_expression(fillers):
    return ''.join(chain.from_iterable(zip(DIGITS, fillers))) + LAST_DIGIT


def main():
    candidates = product(FILLERS, repeat=NUM_FILLERS)

    expressions = [make_expression(candidate) for candidate in candidates]

    result = sorted(expr for expr in expressions if eval(expr) == TARGET)

    print(*result, sep='\n')

I personally prefer this lazy approach for the main logic:

def main():
    candidates = product(FILLERS, repeat=NUM_FILLERS)

    expressions = map(make_expression, candidates)

    result = filter(lambda ex: eval(ex) == TARGET, expressions)

    output = sorted(result)

    print(*output, sep='\n')

Please note that the suggested code executes about 10% slower than your approach (at least on my machine). But it's hard to beat when it comes to conciseness.

\$\endgroup\$
3
  • \$\begingroup\$ My bad, I missed your answer completely. Although I have to disagree with print(*result, sep='\n') being somewhat hackish, I like your approach a lot and learned something new. Thanks for sharing! \$\endgroup\$ Sep 23 at 15:55
  • \$\begingroup\$ Well, I just think that the sep parameter is intended for separators like ', ' or '-' or ''. Not to allow us to do print's job of adding newlines. I'm sure I've done it before myself, perhaps for golfing, but I don't find it clean. Plus I can never remember whether I should be worried about using \n vs \r\n etc. If I just let print do it, I feel satisfied that it'll do the right thing. \$\endgroup\$
    – no comment
    Sep 23 at 16:14
  • \$\begingroup\$ I see your point (and I'm also always unsure about \n vs \r\n, thanks Windows). But I think it's a bit of a stretch to call adding newlines print's job, as the newline is simply the convenient default argument to print's end argument. If you're not already iterating, I personally find using sep=linesep more concise and easier to read compared to for x in y: print(x). Obviously up to some personal preference though. \$\endgroup\$ Sep 23 at 16:45
3
\$\begingroup\$

Your "Ordered" solution doesn't need to sort the expressions. By using the fillers in the order ('+', '-', '') as you do, you already produce all strings in sorted order, as + is smaller than - is smaller than digits:

>>> sorted('123456789-+')
['+', '-', '1', '2', '3', '4', '5', '6', '7', '8', '9']

Not having to sort at the end also means that you can simply print the good strings when you find them, instead of collecting them in a list and using the somewhat hackish print(*result, sep='\n').

You're also reinventing several wheels. We can use itertools.product to build the fillers, printf-style string formatting to build the strings, and eval to evaluate them:

from itertools import product

for p in product(('+', '-', ''), repeat=8):
    s = '%s'.join('123456789') % p
    if eval(s) == 100:
        print(s)

Try it online!

The format-string could be precomputed and stored in a variable, but the whole process takes only ~0.06 seconds anyway, and the eval takes about 90% of the time. No point optimizing the other 10%.

\$\endgroup\$
7
  • \$\begingroup\$ Woah. I had no idea you could use str.join like that (with a different character joining each pair of characters). Could you maybe add an explanation about how that works with the string formatting? \$\endgroup\$ Sep 22 at 23:36
  • 2
    \$\begingroup\$ @AlexWaygood Well, it's not really the join that does it. That only produces the string '1%s2%s3%s4%s5%s6%s7%s8%s9' with the same joining string. And then it's the % operator that fills in the different fillers. \$\endgroup\$
    – no comment
    Sep 22 at 23:40
  • 1
    \$\begingroup\$ @AlexWaygood Almost. You'd need to unpack p. \$\endgroup\$
    – no comment
    Sep 23 at 1:06
  • 1
    \$\begingroup\$ Or as a one-liner: print('\n'.join(s for s in ('%s'.join('123456789') % p for p in product(('+', '-', ''), repeat=8)) if eval(s) == 100)) \$\endgroup\$ Sep 23 at 10:32
  • 2
    \$\begingroup\$ @TobySpeight Eight characters shorter by using walrus: print('\n'.join(s for p in product(('+', '-', ''), repeat=8) if eval(s := '%s'.join('123456789') % p) == 100)). But I think neither is appropriate for this site :-) \$\endgroup\$
    – no comment
    Sep 23 at 10:36

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.