16
\$\begingroup\$

Related Challenge: Single Digit Representations of Natural Numbers

Task

Write a program/function that when given a non-negative integer \$n \le 100000\$ outputs an expression which uses all the digits from \$0\$ to \$9\$ exactly once and evaluates to \$n\$

The expression outputted by your program may only use the operations listed below:

  • addition
  • subtraction and unary minus (both must have the same symbol)
  • multiplication
  • division (fractional, i.e. 1/2 = 0.5)
  • exponentiation
  • parentheses

Note: Concatenation is not allowed

Output Format

  • Output can be a string, list of operations and numbers or a list of lists in place of brackets.
  • You may choose the precedence of the operators but it must be consistent for all outputs produced by your program/function
  • Output may be in polish, reverse polish or infix notation but it must be consistent for all outputs produced by your program/function.
  • You can use custom symbols for representing the digits and operations but the symbols used for representing the digits and operations should be distinct.

Scoring

This is so shortest bytes wins

Sample Testcases

0 -> 0 ^ (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)
4 -> (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) / 9
7 -> 0 * (1 + 2 + 3 + 4 + 5 + 6 + 8 + 9) + 7
45 -> 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
29 -> 1 + 2 + 7 + 6 + 5 + 4 + 3 + 0 + (9 - 8)
29 -> (((9 + 8 + 7 + 6) * 0) + 5 + 4) * 3 + 2 * 1
100 -> (9 * 8) + 7 + 4 + 5 + 6 + 3 + 2 + 1 + 0

A proof by exhaustion (also contains program used to generate the proof) that shows that all number less than or equal to \$100000\$ have an expression that uses all the digits.

\$\endgroup\$
11
  • 3
    \$\begingroup\$ Seeing as the very first thing you do is link to a challenge that allows it, I think you should explicitly state that concatenation isn't permitted here. \$\endgroup\$
    – Shaggy
    Jun 16, 2020 at 9:33
  • 1
    \$\begingroup\$ A test case or 2 with input <10 would be handy, too. \$\endgroup\$
    – Shaggy
    Jun 16, 2020 at 9:35
  • 1
    \$\begingroup\$ This challenge is literally just asking people to brute force putting digits and symbols together until the output matches. It is pointless because you made the rules so loose. Either add a time limit per execution or simply state that brute force is not an option because these programs will never fully execute in reasonable time \$\endgroup\$
    – JBernardo
    Jun 16, 2020 at 14:08
  • 2
    \$\begingroup\$ @JBernardo, yes the challenge is just asking for a brute force, that is how i ment this challenge to be. \$\endgroup\$ Jun 16, 2020 at 14:22
  • 2
    \$\begingroup\$ @JBernardo Code golf are usually like that. It's possible to set a time limit condition (either "the program must run in 10 seconds on my machine" or "you must be able to run the program to completion"), but people don't usually do that here. \$\endgroup\$
    – DELETE_ME
    Jun 17, 2020 at 3:19

6 Answers 6

8
\$\begingroup\$

05AB1E, 25 24 bytes

9Ýœ"+-*m"9ãðδšδ.ιJ˜.Δ.VQ

Brute-force approach, so obviously extremely slow.
Outputs in reverse Polish notation, with the characters +-*m for addition, subtraction, multiplication, and exponentiation respectively. Division isn't necessary for the \$[0,100000]\$ range we have to support.

Try it online with additional (first) input to specify the digit-range \$[0,n]\$ instead of \$[0,9]\$, for which I've used 4 right now as example.

Explanation:

9Ý           # Push a list in the range [0,9]
  œ          # Get all possible permutations of this list
"+-*m"       # Push string "+-*m"
      9ã     # Get all possible combinations of size 9 with the cartesian product
         δ   # Map over each string of operations:
        ð š  #  Convert it to a list of characters, and prepend a space
δ            # Apply double-vectorized with both lists of lists:
 .ι          #  Interleave the lists
J            # Then join each inner list together to a string
.Δ           # Find the first string which is truthy for:
  .V         #  Evaluate/execute the string as 05AB1E code
    Q        #  And check if the result is equal to the (implicit) input-integer
             # (after which the found result is output implicitly)

If we are allowed to output all possible results instead of just one, the (find first) could be ʒ (filter) for -1 byte. Although in that case it would become even slower than it already is..

\$\endgroup\$
6
  • \$\begingroup\$ @Downvoter: care to explain why? I don't mind being downvoted, but I'd like to know why so I can improve and keep this in mind in the future. \$\endgroup\$ Jun 16, 2020 at 14:49
  • \$\begingroup\$ there's been a spate of downvotes on solutions in golfing languages this week. \$\endgroup\$
    – Shaggy
    Jun 16, 2020 at 17:17
  • \$\begingroup\$ @Shaggy Ah, it's that time of year again. \$\endgroup\$ Jun 16, 2020 at 18:20
  • \$\begingroup\$ division isn't actually required. plus, minus, multiply and exponentiation are enough to get all number from 0 to 100000 \$\endgroup\$ Jun 17, 2020 at 2:15
  • \$\begingroup\$ @Mukundan314 Is it also true that all numbers can be achieved by executing each operation in turn i.e. you never have to do e.g. (a+b)*(c+d)? \$\endgroup\$
    – Neil
    Jun 17, 2020 at 10:06
5
\$\begingroup\$

R, 249 244 234 224 220 200 bytes

Or R+arrangements library, 237 232 222 212 208 188 bytes (and somewhat faster)

Multiple edits: -15 bytes thanks to Mukundan314 (no division needed), -4 bytes thanks to 'my pronoun is monicareinstate', -10 bytes by outputting in Polish (prefix) notation, and (latest) -20 bytes by outputting as error message

function(n){apply(gtools::permutations(10,10)-1,1,function(k)apply(expand.grid(rep(list(1:4),9)),1,function(l){for(m in 10:1)F=c(`+`,`-`,`*`,`^`)[[c(l,1)[m]]](F,k[11-m])
if(F==n)stop(letters[l],k)}))}

Try it online!

Outputs as error message, in Polish notation using 'a' to denote plus, 'b' to denote minus, 'c' to denote multiply, and 'd' to denote exponentiation.

Commented version before golfing (with more-readable output that can be copy-pasted to directly check):

make_number=function(n,with=0:9) {
    i=arrangements::permutations(with)          # all the permutations of the digits 0..9
    j=as.matrix(expand.grid(rep(list(1:5),length(with)-1))) 
                                                # all the combinations of 1..5 (for the 5 operators)
    o=c("+"=`+`,"-"=`-`,"*"=`*`,"/"=`/`,"^"=`^`)
                                                # the 5 operators that we can use
    for(k in 1:nrow(i)){for(l in 1:nrow(j)){    # cycle through the permutations of digits & operators
        t=i[k,1]                                # total starts as first digit
        for(m in 2:length(with)-1){t=o[[j[l,m]]](t,i[k,m+1])}
                                                # apply all the operators using each next digit
        if(!is.na(t)&&(t==n)){                  # if we get the answer we're looking for...
                                                # return a string with the calculation
            return( paste0( paste0(rep("(",ncol(j)),collapse=""),paste0(c("",names(o)[j[l,]]),i[k,],collapse=")"))) 
        }
    }}
}

> make_number(1)
[1] "(((((((((0)-1)-2)-3)*4)-5)+6)+7)+8)+9"
> make_number(99)
[1] "(((((((((0)+1)/2)+3)+4)+5)*6)+7)+8)+9"
> make_number(1234)
[1] "(((((((((0)*1)+2)+3)^4)/5)+6)+7)*9)-8"

Note that this algorithm will always find first (and stop at) a solution with the smallest rearrangment of the digits from the starting order of 0..9.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ division isn't actually required. plus, minus, multiply and exponentiation are enough to get all number from 0 to 100000 \$\endgroup\$ Jun 17, 2020 at 6:45
  • 1
    \$\begingroup\$ Is there really any reason to stop at 262144 and not simply iterate until 1e9? (I don't know R) \$\endgroup\$ Jun 17, 2020 at 16:02
  • \$\begingroup\$ That number is the columns in the matrix of permutations of operators. There are 4 operators, assigned to 9 positions, so 4^9=262144. This saves a character compared to writing ncol(j). It's an inner loop, so it needs to terminate correctly. \$\endgroup\$ Jun 17, 2020 at 16:53
  • \$\begingroup\$ But it's a good suggestion for the outer loop (currently ncol(i)), which should never go beyond the end because it should have already found a solution. Thanks! \$\endgroup\$ Jun 17, 2020 at 16:54
  • \$\begingroup\$ It works for me (on the only test case) if I replace 262144 with 3e5. \$\endgroup\$ Jun 18, 2020 at 4:37
3
\$\begingroup\$

Charcoal, 84 bytes

Nθ≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε≔VεηW¬ω«≔⭆◧Iηχ§εΣκζ≦⊕η¿⬤ε№ζκFX⁴¦⁹«≔⭆⁹§”y⁺×⁻X”÷κX⁴λδ¿⁼V⁺δ⪫ζ´¦θ≔δω»»ωζ

Don't try it online! Link is to verbose version of code. Outputs prefix notation using Charcoal operators and digits (note that it's not valid Charcoal code due to the omission of ¦ separators between the digits, and it still wouldn't be useful without the cast operator). Explantion:

Nθ

Input n.

≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε

Assign the list of Charcoal's digits.

≔⁰η

Start checking starting at 0000000000 and working up.

W¬ω«

Repeat until we have an answer.

≔⭆◧Iηχ§εΣκζ

Convert the current trial index to a 10-digit number in Charcoal digits.

≦⊕η

Increment the trial index.

¿⬤ε№ζκ

If this is a permutation of the 10 digits, then...

FX⁴¦⁹«

Loop over all operator combinations,

≔⭆⁹§”y⁺×⁻X”÷κX⁴λδ

convert each into a string of operators,

¿⁼V⁺δ⪫ζ´¦θ

compare the value with n,

≔δω

and set the result if it matches.

»»ωζ

Output the resulting operator string and digits.

96-byte version that can actually finish in under a minute on very simple examples:

Nθ≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε≔VεηW¬ω«≔⭆◧Iηχ§εΣκζ≦⊖ι≦⊕η¿⬤ε№ζκW∧¬ω‹ιX⁴¦⁹«≔⭆⁹§”y⁺×⁻X”÷ιX⁴λδ¿⁼V⁺δ⪫ζ´¦θ≔δω≦⊕ι»»ωζ

Try it online! Link is to verbose version of code.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 21 26 bytes

+5 bytes for a fix based on Kevin Cruijssen

“+×*_”ṗ9
⁵ḶŒ!p¢ż/€Ẏ€V=¥ƇḢḢ

Brute force, like the 05AB1E answer, so it is also extremely slow.

Outputs in infix notation with +×*_ to represent addition, multiplication, exponentiation, and subtraction respectively. All operators have equal precedence. Similarly to my Python answer, this generates an expression and evals it to find what it evaluates to.

Try it online (in a version that allows you to enter the number of digits) The value for n should be provided as the first argument, while the input should consist of two lines: the first equal to the number of digits; the second less by one.

Explanation (going to update soon, I should be able to golf a bit off):

“+×*_”ṗ9           # literal string "+×*_" (Jelly arithmetic symbols) Cartesian power 9

⁵ḶŒ!p¢ż/€Ẏ€V=¥ƇḢḢ
⁵Ḷ                 # lowered_range(10): [0,1,2,3,...,9]
  Œ!               # all permutations of these digits
    p              # Cartesian product with
     ¢             # the list of all permutations of 9 arithmetic symbols
      ż/€Ẏ€        # zip and tighten each to squeeze together (golfportunity?)
           V=¥Ƈ    # Filter for those that evaluate to
               Ḣ   # n (surely there is a way around this)
                Ḣ  # get the first one

If no string works (which could occur if n is too large or the number of digits is decreased), then it outputs 0.

\$\endgroup\$
4
  • \$\begingroup\$ @KevinCruijssen working on fixing the duplicate number, but 80 was the first test case I tried that worked well with 4 digits \$\endgroup\$ Jun 18, 2020 at 6:22
  • 1
    \$\begingroup\$ @KevinCruijssen Fixed the issue (80 is slightly-humorously unobtainable with 4 digits). The 26-byte version involved almost completely rewriting from scratch, but I have a 28-byte version that is less-modified from the previous attempt: tio.run/##y0rNyan8///… \$\endgroup\$ Jun 18, 2020 at 6:59
  • \$\begingroup\$ Looks good. +1 from me, and I've deleted my comments. :) Looking forward seeing that updated explanation. PS: Jelly doesn't have a find_first builtin, instead of the filter + head? I indeed couldn't find one on the Wiki page, but maybe I looked past it. \$\endgroup\$ Jun 18, 2020 at 7:31
  • \$\begingroup\$ @KevinCruijssen Good idea. There is # for find_first_n, which should save me 1 byte \$\endgroup\$ Jun 18, 2020 at 8:12
3
\$\begingroup\$

Python 3, 200 194 186 178 bytes

-6, -2, -6, -8 bytes, and a test runner thanks to @Mukundan314.

lambda n:next(s for o in product(*[[*"+-*","**"]]*9)for l in permutations("0123456789")if eval(s:="("*8+l[9]+')'.join(o[i]+str(l[i])for i in range(9)))==n)
from itertools import*

Try it online! (5 digits case)

Outputs in infix notation with parentheses, using +-* respectively for addition, subtraction, and multiplication; uses ** and exponentiation. The program generates Python code that gets eval'd to check for equivalence to n.

Slightly more-readable version with a variable for the number of digits:

L=9
import itertools as i
def g(n):
    for l in i.permutations(map(str,range(1,L+1))):
        for o in i.product("+-*m",repeat=L-1):
            s=l[L-1]
            for j in range(L-1):
                s='('+s+o[j]+l[j]+')'
            s=s.replace("m","**")
            if eval(s)==n:
                return s
\$\endgroup\$
7
  • \$\begingroup\$ @Mukundan314 incorporated those last two edits and saved an extra 2 bytes by rewriting into a one-liner \$\endgroup\$ Jun 19, 2020 at 2:34
  • \$\begingroup\$ In your current code 0**<negative number> is possible this throws an error halting the program \$\endgroup\$ Jun 19, 2020 at 2:37
  • \$\begingroup\$ My code only proves that all number till be 100k can be formed with expression of the form <9 operators><a permutation of 0123456789> in polish notation . it does not prove that all number till 100k can be formed with expression of the form alternating digit and operator in polish notation \$\endgroup\$ Jun 19, 2020 at 2:46
  • \$\begingroup\$ @Mukundan314 Oh, I see. I happened to change it from left-associative infix to right-associative infix, which switched polish and reverse polish notation. I switched association order now, so it is now fixed and raises StopIteration for unobtainable n (the 0**<negative number> only happened in rare cases because it only reached that state after 0+(...), which could normally yield a solution). \$\endgroup\$ Jun 19, 2020 at 3:40
  • \$\begingroup\$ Wow, the 3.8 assignment expr is going to be very useful; it seems like it was made for golfing \$\endgroup\$ Jun 19, 2020 at 5:14
0
\$\begingroup\$

Pyth, 23 bytes

hfqQ.vjdsT*^"+-*^"9.pUT

Try it online! (5 digit case)

Explanation

hfqQ.vjdsT*^"+-*^"9.pUT
h                        : first element of
 f                       : filter on
          *              : cartesian product of
           ^"+-*^"9      : all 9 length string that can be formed with the chars +, -, * and ^
                   .pUT  : and all permutations of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  qQ                     : for equality of input and
    .vjdsT               : evaluated result of operators and permutation joined with spaces
\$\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.