How many ways to cut a number into an equation?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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)
                                  : i.e. those that had no leading zero digit
                            €   - 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

Answer 4

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[1]] - ensures it is a 2-item list with both items the same
                          f∑ # Flatten and count truthy values

Answer 5

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

Answer 6

Charcoal, 61 bytes

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

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

⊞υω

Start with an empty expression.

Ｆ⮌θ

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.

Answer 7

05AB1E, 33 bytes

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

Try it online or verify all test cases.

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)

Answer 8

Python, 255 bytes

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!

Answer 9

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!

Answer 10

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