# How many ways to cut a number into an equation?

Too bad! I had such a beautiful equation, but I lost all my =+-*, so there is nothing left but a chain of digits, looking like a number: 7512. But was it 7+5=12 or 7-5=1*2 or 7=5*1+2 or 7=5+1*2? Or are there even more valid possibilities?

Your task: For a given positive integer number, return the number of true equations containing the digits of that number in the given order, using plus and minus and multiplication operators.

• dot-before-dash calculation is used, so 1+2*3 is 7, not 9
• plus and minus are only allowed as operators, not as (prefix) sign, so neither negative numbers in the equation nor superfluous plus padding
• no division to keep rules simple
• input numbers are integers ranging from 0 to 999999
• no leading zeroes, neither in input, nor in equations
• operators are allowed to appear several times, but of course only exactly one =
• a single digit as input leads to 0 as output, because you can't do any equation with it
• the smallest number to return 1 is 11 (equation is 1=1)
• don't underestimate the possibilities for higher numbers like 1111 (10possible equations: 11=11 1*1=1*1 1+1=1+1 1-1=1-1 1=1*1*1 1=1-1+1 1=1+1-1 1*1*1=1 1-1+1=1 1+1-1=1
• you are free to use anything from brute force to intelligent algorithms, execution time is irrelevant, just don't use many bytes of code, because we are golfing

Check your code with these examples:

7      --> 0
42     --> 0
77     --> 1
101    --> 3
121    --> 1
1001   --> 12
1111   --> 10
7512   --> 5
12345  --> 5
110000 --> 203
902180 --> 37

• Shouldn't 101 be 3? I get 1+0=1, 1-0=1, 1=01. Sep 11 at 14:51
• @mathscat Thank you, I added to the rules that we don't want things like leading zeroes Sep 11 at 15:10
• I guess using + as a unary prefix operator is also not allowed? Please clarify Sep 11 at 15:15
• @corvus_192 You are right. Is it comprehensible now? Sep 11 at 15:22
• @mathscat: 1=0+1 should be valid, shouldn't it? It was not on your list.
– vsz
Sep 13 at 8:56

# GNU sed -E,  214 200 181 171  169 bytes

For some not-so-obvious reason, I decided to solve this by myself in sed, misusing the shell for expression evaluation with the e flag of the GNU version of the tool:

G:1;s/(\S*[0-9])([0-9]\S*\n)/\1_\2\1==\2\1+\2\1-\2\1*\2/;t1;s/_//g;:2;s/(\n|^)[^=]+\n/\n/;s/\S*=\S+=\S*//;t2;s/\S*/+$((&))/g;s/\S*[ =*+-]0[0-9]\S*//g;s/.*/echo$((&))/e


Try it online!

• G appends the (empty) hold space, so it adds a newline to the end, which is used as a separator
• :1;s/(\S*[0-9])([0-9]\S*\n)/\1_\2\1==\2\1+\2\1-\2\1*\2/;t1 loops to add operators or == between each pair of digits, marking already considered pairs by _
• s/_//g removes the _ markers
• :2;s/(\n|^)[^=]+\n/\n/;s/\S*=\S+=\S*//;t2 removes items without == or with more than one ==
• s/\S*/+$((&))/g turns each equation in to an arithmetic expansion $(())
• s/\S*[ =*+-]0[0-9]\S*//g is needed to remove all equations including a leading zero
• s/.*/echo $((&))/e finally evaluates the whole rubbish • Only pure bash would have been better – Simd Sep 11 at 17:38 • @Simd So give it a try! Complex string manipulation can be tricky. Sep 11 at 17:42 • @Simd here you go 0x0.st/Hf7h.bash Sep 14 at 11:36 • @noname super cool. Which part doesn't work in bash 5.1 and why? I would post it as a an answer too. – Simd Sep 14 at 11:36 • @Simd The & reference in ${h//?/&{+,-,*,==,\}} is a 5.2 feature. Sep 15 at 17:24

# JavaScript (ES6), 107 bytes

-26 bytes (!) thanks to @tsh

f=([c,...a],s,g=o=>f(a,[s]+c+o))=>c?g+g==+g++g-+g*:/^(?!.*\D0\d)[^=]*==[^=]*\d$/.test(s)&&eval(s)  Try it online! ### How? We recursively build all possible expressions obtained by adding "", "==", "+", "-" or "*" after each character. For each expression, we test whether it matches: // .--------------------> no number may start with '0' // | .-------------> left part // | | .---------> comparison operator // | | | .------> right part (except the last character) // | | | | .--> we must end with a digit // _____|___ _|_ | _|_ | // / \/ \/\/ \/\ /^(?!.*\D0\d)[^=]*==[^=]*\d$/


If it does, we can safely eval()'uate it and increment the final result if it's truthy.

• 108 bytes
– tsh
Sep 12 at 2:14
• Very nice! I didn't know JS can become as cryptic as some golfing languages! (-; Sep 12 at 6:26

# Vyxal, 28 bytes

øṖ'⌊=A;ƛṄfð+*-,VΠEƛk-İ⁼]f∑


Attempt This Online! Semi-port of Jonathan Allan's Jelly answer, but much clunkier. The A flag runs testcases.

øṖ                           # Partitions
'   ;                      # Where
A                       # All substrings
=                        # Are equivalent under
⌊                         # Cast to integer
ƛ                 ]   # For each partition
Π          # Cartesian product of
Ṅf                   # Join with spaces and flattening
ð+*-,V           # Then replacing spaces with "+*-,"
Π          # Resulting in all combinations of the operators and strings
E         # Evaluate as Python
ƛ    ]   # Map each to
⁼    # Whether it remains the same under
k-İ     # [x[-1], x] - ensures it is a 2-item list with both items the same
f∑ # Flatten and count truthy values

• I've got to learn this stuff one day. I love this poetry! Sep 12 at 6:30

# Python, 178 bytes

-2 bytes, thanks to corvus_192

lambda s:len({*filter(eval,q(s,"=="))})
q=lambda s,c:[l+c+r for i in range(1,len(s))for l in e(s[:i])for r in e(s[i:])]
e=lambda s:[s]*(s==str(int(s)))+q(s,"+")+q(s,"-")+q(s,"*")


Attempt This Online!

Takes the string representation of the number as input

Generates all possible equations, uses eval to compare the results

The *(s==str(int(s))) part prevents leading zeros

• Nice and fast and forcing me to edit my question (forgot something for 101) Sep 11 at 15:33
• -3 bytes: lambda s:len({*filter(eval,q(s,"=="))}) Sep 11 at 20:16
• Even better now, but my sed approach finally left Python behind! (-; Sep 12 at 6:22

# Jelly,  35 34 32  31 bytes

-3 thanks to Unrelated String! (Filtering leading zero decimals with ḌVÐṀ rather than the somewhat clunky ḌD$ƑƇḌ. Also Ṛṁ2ƊƑ -> .ị$Ƒ)

DŒṖḌVÐṀżFŒV.ị$ƑʋⱮL’“*+,-”ṗƲ$€FS


A monadic Link that accepts a positive integer and yields the count.

Try it online!

### How?

DŒṖḌVÐṀżFŒV.ị$ƑʋⱮL’“*+,-”ṗƲ$€FS - Link: positive integer, N
D                               - get a list of N's digits
ŒṖ                             - all partitions of that list
Ḍ                            - convert each part of each from base ten
: e.g. [0,7,2] -> 72
ÐṀ                         - keep those maximal under:
V                           -   evaluate as Jelly code (e.g. [4,72,1]-> 4721)
€   - for each DecimalisedPartition:
$- last two links as a monad: Ʋ - last four links as a monad: L - length ’ - decrement “*+,-” - "*+,-" ṗ - Cartesian power Ɱ - map across these operator lists with: ʋ - last four links as a dyad: ż - {DecimalisedPartition} zip {Operators} F - flatten ŒV - evaluate as Python code Ƒ - is {X=that} invariant under?:$                  -           last two links as a monad:
.                    -             0.5
ị                   -             index into {X} -> [last(X), first(X)]
: i.e. is exactly two equal values?
F  - flatten
S - sum

• ḌD$ƑƇḌ -> ḌVÐṀ? Sep 11 at 22:05 • Nice golf, thanks. I don't believe I would have thought of that one anytime soon. Sep 11 at 23:03 • Oh, this is insane, but Ṛṁ2Ɗ -> .ị$. Wouldn't be the first time I've forgotten what order that returns in! Sep 12 at 2:46
• I actually thought of using that, I remember rejecting it but I now have no idea why as I think it is fine. (The ordering is easy - 0.5 is between 0 and 1 so you get values from the modular indices [0, 1]) Sep 12 at 18:38

# Charcoal, 61 bytes

⊞υωＦ⮌θ≔ΣＥυ⁺ι⁺⎇∧κ∨⁼κ0∨⌕κ0⁻§κ¹ＩΣ§κ¹⟦+¦-¦*ω==⟧⟦ω⟧κυＩＬΦυ∧⁼²№ι=ＵＶι


Attempt This Online! Link is to verbose version of code. Explanation:

⊞υω


Ｆ⮌θ


Loop over the digits in reverse order.

≔ΣＥυ⁺ι⁺⎇∧κ∨⁼κ0∨⌕κ0⁻§κ¹ＩΣ§κ¹⟦+¦-¦*ω==⟧⟦ω⟧κυ


For each expression so far, prefix this digit, but if the expression is not empty, and it either does not being with 0 or the 0 is not part of a larger number, then also optionally insert an operator.

ＩΣＥΦυ⁼²№ι=ＵＶι


For each expression that contains exactly one equality operator, evaluate that as python, and output the the number of expressions for which everything is true.

# 05AB1E, 33 bytes

.œʒïJQ}ε©…-+*„==ªsg<ãε®s.ιJ]˜.EáO


Explanation:

Step 1: Get all partitions of the input-integer, and remove all partitions that contain parts with leading 0s:

.œ         # Get all partitions of the (implicit) input-integer
ʒ        # Filter the list of lists of parts by:
ï       #  Cast each part to an integer, removing leading 0s
J      #  Join all parts back together
Q     #  Check whether it's equal to the (implicit) input-integer
}        # Close the filter


Try just step 1 online.

Step 2: Create all possible equations of each partition using -,+,*,== delimiters:

ε          # Map over each remaining partition:
©         #  Store the current partition in variable ® (without popping)
…-+*     #  Push string "-+*"
„==ª #  Convert it to a list of characters, and append "==": ["-","+","*","=="]
s        #  Swap so the partition is at the top again
g       #  Pop and push its length
<      #  Decrease it by 1
ã     #  Get the cartesian power of the ["-","+","*","=="] and this length-1
ε        #  Inner map each list of operators by:
®       #   Push partition ®
s      #   Swap so the current list of operators is at the top
.ι    #   Interleave the two lists
J   #   And then join them together to a single string
]          # Close the nested maps
˜         # Flatten the list of list of equation-strings


Try the first two steps online.

Step 3: Evaluate each equation-string as Elixir code: .E.
Try the first three steps online.

Step 4: Count the amount of "true" values, which under the hood are all 1 (05AB1E's truthy value), making it difficult to find a correct and short way of distinguishing "true" from actual 1s. To give some examples of why this works so weird:

1. Counting the amount of "true" in the list results in 0: try it online;
2. Trying to convert it to a flattened list of characters results in an error, since it cannot convert the "false" / "true" items: try it online;
3. Filtering on 05AB1E-truthy values will keep both the 1 and "true": try it online or try it online;
4. Sorting (after the truthy filter) does work correct, although an additional group-by not: try it online;
5. etc.

Eventually I noticed the þ (keep all digits/numbers) and á (keep all letters/words) would correctly distinguish between the two, so I've used that to finish my program that utilizes Elixir-equations and evals:

á          # Keep all letters/words (which will only keep all "false" and "true")
O         # Sum this list together, since they're 0 and 1 under the hood
# (after which this count of "true" items is output implicitly as result)


lambda s:len({q for r in range(len(s)+1)for o in combinations("+-*"*len(s),r)for p in permutations([*s,"==",*o])if match(f"{n}=={n}$",q:="".join(p))and s==sub("\D","",q)and eval(q)}) m="(0|[1-9]\d*)" n=f"{m}(\D{m})*" from itertools import* from re import*  Attempt This Online! • s==sub("\\D","",q:="".join(p)) saves bytes over your findall trick. Sep 11 at 19:55 • @ValueInk Thanks Sep 11 at 20:15 • You'll notice I put sub on the right side of the == in my comment, because the paren will let you remove the space between that statement and the next and compared to what you have. Sep 11 at 22:22 • Could you use "+-*"*r instead of "+-*"*len(s)? Sep 14 at 10:40 # Ruby, 117 113 bytes Takes a string as input. Creates every possible combination of operators and counts which ones have no leading zeroes and eval to true. This is probably the only time in Ruby golfing when do/end will ever be cheaper than the curly brace syntax, since that allows rescue SyntaxError without adding a begin block like it normally would require. (Inline rescue doesn't catch SyntaxError so the longer syntax is needed.) -4 from Dingus. ->s{[p].product(*[%W"#{} == + - *"]*s.size).count do !p==eval(e=_1.zip(s.chars)*'')&&/0\d/!~e rescue$!.class;end}


Attempt This Online!

• So sad the error handling messes the otherwise elegant code. Sep 12 at 6:32
• rescue\$!.class saves 4 bytes. Sep 12 at 11:38

# JavaScript (Node.js), 96 bytes

f=([c,...a],s='',g=t=>f(a,s+t))=>/\b0\d/.test(s+=c)?0:a+a?g++g-+g*+g+g===:eval(s)===!0


Try it online!

Unlike Arnauld who tests if exactly one == exist, I use ===:

1             => 1
1===1         => true
1===1===1     => false
1===1===1===1 => false


so if it results in true it's an equation