23
\$\begingroup\$

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

10 Answers 10

13
\$\begingroup\$

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
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Only pure bash would have been better \$\endgroup\$
    – Simd
    Sep 11, 2023 at 17:38
  • 4
    \$\begingroup\$ @Simd So give it a try! Complex string manipulation can be tricky. \$\endgroup\$
    – Philippos
    Sep 11, 2023 at 17:42
  • 1
    \$\begingroup\$ @Simd here you go 0x0.st/Hf7h.bash \$\endgroup\$
    – noname
    Sep 14, 2023 at 11:36
  • 1
    \$\begingroup\$ @noname super cool. Which part doesn't work in bash 5.1 and why? I would post it as a an answer too. \$\endgroup\$
    – Simd
    Sep 14, 2023 at 11:36
  • 1
    \$\begingroup\$ @Simd The & reference in ${h//?/&{+,-,*,==,\}} is a 5.2 feature. \$\endgroup\$ Sep 15, 2023 at 17:24
7
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I've got to learn this stuff one day. I love this poetry! \$\endgroup\$
    – Philippos
    Sep 12, 2023 at 6:30
5
\$\begingroup\$

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

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

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
\$\endgroup\$
4
  • \$\begingroup\$ ḌD$ƑƇḌ -> ḌVÐṀ? \$\endgroup\$ Sep 11, 2023 at 22:05
  • 1
    \$\begingroup\$ Nice golf, thanks. I don't believe I would have thought of that one anytime soon. \$\endgroup\$ Sep 11, 2023 at 23:03
  • \$\begingroup\$ Oh, this is insane, but Ṛṁ2Ɗ -> .ị$. Wouldn't be the first time I've forgotten what order that returns in! \$\endgroup\$ Sep 12, 2023 at 2:46
  • 1
    \$\begingroup\$ 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]) \$\endgroup\$ Sep 12, 2023 at 18:38
2
\$\begingroup\$

Charcoal, 61 bytes

⊞υωF⮌θ≔ΣEυ⁺ι⁺⎇∧κ∨⁼κ0∨⌕κ0⁻§κ¹IΣ§κ¹⟦+¦-¦*ω==⟧⟦ω⟧κυILΦυ∧⁼²№ι=UVι

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

⊞υω

Start with an empty expression.

F⮌θ

Loop over the digits in reverse order.

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

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.

IΣEΦυ⁼²№ι=UVι

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ s==sub("\\D","",q:="".join(p)) saves bytes over your findall trick. \$\endgroup\$
    – Value Ink
    Sep 11, 2023 at 19:55
  • \$\begingroup\$ @ValueInk Thanks \$\endgroup\$
    – corvus_192
    Sep 11, 2023 at 20:15
  • \$\begingroup\$ 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. \$\endgroup\$
    – Value Ink
    Sep 11, 2023 at 22:22
  • \$\begingroup\$ Could you use "+-*"*r instead of "+-*"*len(s)? \$\endgroup\$
    – gsitcia
    Sep 14, 2023 at 10:40
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ So sad the error handling messes the otherwise elegant code. \$\endgroup\$
    – Philippos
    Sep 12, 2023 at 6:32
  • 1
    \$\begingroup\$ rescue$!.class saves 4 bytes. \$\endgroup\$
    – Dingus
    Sep 12, 2023 at 11:38
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.