Make mathematics with minimal matchsticks

Question

Meta-background

This was set as a question on Puzzling, and the instant reaction was "well, someone will just solve that by computer". There was a debate about just how complex a program to solve this would have to be. Well, "how complex does this program have to be" is pretty much the definition of code-golf, so maybe PPCG can settle the issue?

Background

A matchstick equation is basically a normal mathematical equation, but where the digits and operators are constructed physically by placing matchsticks onto a table. (The main relevant feature of matchsticks here is that they're fairly rigid and have a constant length; sometimes people use other objects instead, such as cotton swabs.)

For this challenge, we don't need to define specific rules for how the matchsticks are arranged (like the linked challenge does); rather, we just care about how many matchsticks we'll need to represent an expression that evaluates to a given number.

The task

Here's an alphabet of digits and mathematical operators you can use, each having a cost in matchsticks:

• 0, costing 6 matchsticks
• 1, costing 2 matchsticks
• 2, costing 5 matchsticks
• 3, costing 5 matchsticks
• 4, costing 4 matchsticks
• 5, costing 5 matchsticks
• 6, costing 6 matchsticks
• 7, costing 3 matchsticks
• 8, costing 7 matchsticks
• 9, costing 6 matchsticks
• +, costing 2 matchsticks
• -, costing 1 matchstick
• ×, costing 2 matchsticks

(You may represent × as * in your program's output if you wish, in order to avoid needing to use non-ASCII characters. In most encodings, × takes up more bytes than *, and so I imagine that most programs will want to take advantage of this leeway.)

You need to write a program that takes a nonnegative integer as input (via any reasonable means), and produces an expression that evaluates to that integer as output (again via any reasonable means). Additionally, the expression must be nontrivial: it must contain at least one operator +, -, or ×. Finally, the expression you output must be the cheapest (or tied for the cheapest) in terms of total matchstick cost, among all outputs that otherwise comply with the specification.

Clarifications

• You can form multiple-digit numbers via outputting multiple digits in a row (e.g. 11-1 is a valid output to produce 10). Just to be completely precise, the resulting number gets interpreted in decimal. This sort of concatenation isn't an operation that works on intermediate results; only on literal digits that appear in the original expression.
• For the purpose of this challenge. +, -, and × are infix operators; they need an argument to their left and to their right. You aren't allowed to use them in prefix position like +5 or -8.
• You don't have parentheses (or any other way to control precedence) available. The expression evaluates according to the typical default precedence rules (multiplications happen first, and then the additions and subtractions are evaluated left to right).
• You don't have access to any mathematical operators or constants other than the ones listed above; "lateral thinking" solutions are often accepted at Puzzling, but it doesn't make sense to require a computer to come up with them itself, and over here on PPCG, we like it to be objective whether or not a solution is correct.
• The usual integer overflow rules apply: your solution must be able to work for arbitrarily large integers in a hypothetical (or perhaps real) version of your language in which all integers are unbounded by default, but if your program fails in practice due to the implementation not supporting integers that large, that doesn't invalidate the solution.
• If you use the same digit or operator more than once, you have to pay its matchstick cost each time you use it (because, obviously, you can't reuse the same physical matchsticks in two different locations on the table).
• There's no time limit; brute-force solutions are acceptable. (Although if you have a solution that's faster than brute force, feel free to post it even if it's longer; seeing how alternative approaches compare is always interesting.)
• Although writing an explanation of your code is never required, it's likely to be a good idea; code-golf solutions are often very hard to read (especially to people not familiar with the language they're written in), and it can be hard to evaluate (and thus vote on) a solution unless you understand how it works.

Victory condition

As a code-golf challenge, answers with fewer bytes are considered better. However, as usual, feel free to post answers with different approaches, or in specific languages even if they're more verbose than certain other languages; the goal of golf is really to see how far you can optimize a particular program, and doing things this way gives us lots of potential programs to optimize. So don't be discouraged if someone submits a solution using a completely different approach, or a completely different language, and gets a much shorter answer; it may well be that your answer is better-optimized and shows more skill, and voters on PPCG often appreciate that.

Answer 1

Python2, 1̶9̶8̶ ̶b̶y̶t̶e̶s̶ 182 bytes thanks to math_junkie

def f(n,c=dict(zip('0123456789+-*',map(int,'6255456376212'))),e=[(0,'')]):
 while 1:
    v=(m,s)=min(e);e.remove(v)
    try:
     if eval(s)==n:return s
    except:0
    e+=[(m+c[x],s+x)for x in c]

This algorithm does nothing to exclude prefix versions of + and -, but they will either be worse than, or equal to and appear later in the search, their infix counterparts. Because it uses the keyword argument e mutably, it will give invalid results if called multiple times per session. To fix this, use f(n, e=[(0,'')]) instead of just f(n). Note that the four-spaced indents represent tabs, so this will only work with Python 2.

I also have an ungolfed and optimized version which runs quickly even for quite large numbers:

from heapq import heappop, heappush

def f(n):
    digits = list('0123456789')
    ops =['+','-','*','']
    costs = dict(zip(digits + ops, [6,2,5,5,4,5,6,3,7,6,2,1,2,0]))
    expressions = [(costs[d], abs(n - int(d)), int(d), d) for d in digits[1:]]
    seen = set()
    while 1:
        cost, d, k, expression = heappop(expressions)
        if d == 0:
            return expression
        for op in ops:
            if op in '+-' and k in seen:
                continue
            for digit in digits:
                if op and digit == '0':
                    continue
                expression1 = expression + op + digit
                k1 = eval(expression1)
                d1 = abs(n - k1)
                if d1 == 0:
                    return expression1
                heappush(expressions, (cost+costs[op]+costs[digit], d1, k1, expression1))
        seen.add(k)

Answer 2

PHP, 241 Bytes

Online Version

function m($i){for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e;}foreach($r=range(0,2*$a=$argv[1])as$v)foreach($r as$w)$x[$v+$w]["$v+$w"]=$x[$v*$w]["$v*$w"]=1+$x[$v-$w]["$v-$w"]=m("$v")+m("$w")+1;echo array_search(min($x[$a]),$x[$a]);

Breakdown

function m($i){
    for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e; #return the count of the matchstick for an integer
}

foreach($r=range(0,2*$a=$argv[1])as$v) # limit to an input to 300 in the online version
foreach($r as$w)
       $x[$v+$w]["$v+$w"]=  #fill the 2D array in the form [result][expression] = count matchsticks
       $x[$v*$w]["$v*$w"]=
       1+$x[$v-$w]["$v-$w"]=
       m("$v")+m("$w")+1;
echo $k=array_search(min($x[$a]),$x[$a]); # Output expression with a minium of matchsticks
echo"\t".$x[$a][$k]; #optional Output of the count of the matchsticks

Way with a little better performance

function m($i){
for(;$s<strlen($i);)
$e+="6255456376"[$i[$s++]];return$e;} #return the count of the matchstick for an integer
foreach($r=range(0,2*$a=$argv[1])as$v)
foreach($r as$w){$c=m("$v")+m("$w")+1;
if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
if($a==$v*$w)$x["$v*$w"]=1+$c;
if($a==$v-$w)$x["$v-$w"]=$c;}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
    echo"\t".$x[$k]; #optional Output of the count of the matchsticks

Support of negative integers

Version with negative integers

function m($i){
    $e=$i<0?1:0; # raise count for negative integers
    for($s=0;$s<strlen($i);)$e+=[6,2,5,5,4,5,6,3,7,6][$i[$s++]];return$e; #return the count of the matchstick for an integer
}
$q=sqrt(abs($argv[1]));
$l=max(177,$q);
$j=range(-$l,$l); # for second loop for better performance
foreach($r=range(min(0,($a=$argv[1])-177),177+$a)as$v) 
foreach($j as$w){$c=m("$v")+m("$w")+1;  
    if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
    if($a==$v*$w)$x["$v*$w"]=1+$c;
    if($a==$v-$w)$x["$v-$w"]=$c;
    if($a==$w-$v)$x["$w-$v"]=$c; # added for integers <0
}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
echo"\t".$x[$k]; #optional Output of the count of the matchsticks