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?
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.
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
* 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
×. 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.
- You can form multiple-digit numbers via outputting multiple digits in a row (e.g.
11-1is 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.
×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
- 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.
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.