24
\$\begingroup\$

Task

Write a program/function that when given a positive integer \$n\$ and a digit \$d\$ which is not 0 outputs a way to represent \$n\$ using only addition, subtraction, multiplication, exponentiation, division, concatenation, parenthesis and the digit \$d\$.

Examples

n =  6, d = 1  =>  (1 + 1) * (1 + 1 + 1)
n =  6, d = 1  =>  1 + 1 + 1 + 1 + 1 + 1
n = 10, d = 1  =>  1 || 1 - 1
n = 12, d = 1  =>  1 || (1 + 1)
n = 64, d = 2  =>  2 ^ (2 + 2 + 2)
n =  1, d = 9  =>  9 / 9

Note: In the examples || represents concatenation

Output Format

  • Concatenation must be explicit with a separate operator
  • 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 , Your score will be

100*B + S

Where B is the number of bytes in the program/function, and S is the sum of the number of times the digit \$d\$ appears in the representation of \$n\$ with the digit \$d\$ as returned by your program/function for all \$n \le 1000\$ and all \$d\$ from 1 to 9

Lowest score wins

Example: if your program is abcd and all representation of \$n\$ returned by your program has 5 occurrences of \$d\$ then its score will be (4 * 100) + (5 * 1000 * 9) = 45400

Rules

  • Your program/function should run deterministically, so that it always returns the same representation for a given \$n\$ and \$d\$ (and hence always gets the same score).
  • Your answer must include not only your submission, but also the code you used to calculate the S part of its score. This need not be written in the same language as your submission, and will not be counted towards its byte count. You are encouraged to make it readable.
  • Your answer must include the precedence of the operators needed to evaluate the outputs produced by your program/function
  • You must actually run your test program and calculate/verify your score before submitting your entry. If your submission runs too slowly for you to verify its score then it is not qualified to compete, even if you know what its score would be in principle.

Inspired by this video

\$\endgroup\$
  • 6
    \$\begingroup\$ arxiv.org/pdf/1502.03501.pdf \$\endgroup\$ – J42161217 Feb 27 at 3:28
  • \$\begingroup\$ @J42161217 Wow, that looks like an exhaustive list, apart from the fact that this challenge allows concatenation later on (e.g. it lists 21,1 as 11+11-1, when the optimal answer here would be (1+1)||1) \$\endgroup\$ – Jo King Feb 27 at 3:36
  • 1
    \$\begingroup\$ Is the precedence of || after those of + and -? \$\endgroup\$ – petStorm Feb 27 at 5:40
  • \$\begingroup\$ @a'_' precedence of the operators is up to you but it must be consistent for all outputs produced by your function and should be stated in you submission \$\endgroup\$ – Mukundan Feb 27 at 5:49
  • \$\begingroup\$ Does the / operator represent integer division? \$\endgroup\$ – RootTwo Feb 27 at 23:26
7
\$\begingroup\$

Python 3, 210 bytes · 100 + 59045 digits = 80045

def f(n,d):
 m={d:d},
 while{n}-{*m[0]}:m={z:(p[x],o,q[y])for p,q in zip(m,m[::-1])for x in p for y in q for z,o in zip([x+y,x-y,x*y,y<9and x**y,x%y<1and x//y,int(f"{x}{y}")],"+-*^/|")if z>0},*m
 return m[0][n]

Try it online!

Scoring

Scoring goes much faster using this modified version that solves 1 through 1000 all at once:

def f_gen(d):
 m={d:d},
 while 1:yield from m[0].items();m={z:(p[x],o,q[y])for p,q in zip(m,m[::-1])for x in p for y in q for z,o in zip([x+y,x-y,x*y,y<9and x**y,x%y<1and x//y,int(f"{x}{y}")],"+-*^/|")if z>0},*m

def size(expr):
    return 1 if isinstance(expr, int) else size(expr[0]) + size(expr[2])

score = 0
for d in range(1, 10):
    s = set(range(1, 1001))
    for n, expr in f_gen(d):
        if n in s:
            s -= {n}
            score += size(expr)
            print(n, expr)
            if not s:
                break
print(score)
|improve this answer|||||
\$\endgroup\$
6
\$\begingroup\$

JavaScript (Node.js), Score:  87900 ... 83274  82574

229 bytes x 100 + 59674 digits

Takes input as (d)(n). Returns a string. Uses | for concatenation.

d=>n=>[0,v=[d],F={[d]:d},s={[d]:0}].map(_=>v.map(x=>v.map(y=>[x+y,x-y,x*y,x/y,x**y,[x]+y].map((z,o)=>z<0|z>1e4||z%1?0:(!F[z]&&V.push(+z))|(S=s[x]-~s[y])<s[z]?F[s[z]=S,z]=`(${F[x]+'+-*/^|'[o]+F[y]})`:0)),V=[])&&v.push(...V))&&F[n]

Try it online!

Scoring

Because the golfed version is quite slow, the total score was computed with the following ungolfed version which, given \$d\$, computes the formulas for all \$n\in[1..1000]\$ at once.

Although it works on TIO, the output is too long. So the link below is an example for \$d=9\$.

Try it online!

const OP = ['+', '-', '*', '/', '^', '||'];

function solve(d) {
  let value = [ d ],
      formula = { [d] : d },
      size = { [d] : 0 },
      total = 0;

  for(let i = 0; i < 4; i++) {
    let newValue = [];

    value.forEach(x => {
      value.forEach(y => {
        [0, 1, 2, 3, 4, 5].forEach(o => {
          let v;

          switch(o) {
            case 0: v = x + y; break;
            case 1: v = x < y ? null : x - y; break;
            case 2: v = x * y; break;
            case 3: v = x % y ? null : x / y; break;
            case 4: v = x ** y; break;
            case 5: v = +(x.toString() + y.toString()); break;
          }

          if(v !== null && v <= 10000) {
            let sz = size[x] + size[y] + 1;

            if((formula[v] === undefined && newValue.push(v)) || sz < size[v]) {
              formula[v] = '(' + formula[x] + OP[o] + formula[y] + ')';
              size[v] = sz;
            }
          }
        });
      });
    });
    value.push(...newValue);
  }

  for(let n = 1; n <= 1000; n++) {
    console.log(n, size[n] + 1, formula[n]);
    total += size[n] + 1;
  }
  console.log('-->', total);
  return total;
}

let score = 0;

for(let d = 1; d <= 9; d++) {
  score += solve(d);
}
console.log('Final score:', score);
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ why is this happening? \$\endgroup\$ – J42161217 Feb 27 at 9:06
  • \$\begingroup\$ @J42161217 Your input is too large. \$\endgroup\$ – petStorm Feb 27 at 9:09
  • 1
    \$\begingroup\$ @J42161217 This gives (((3+(3*3))^3)/3) on my laptop. The number of computed formulas is especially large for \$d=3\$, so there might be a heap memory overflow on TIO. \$\endgroup\$ – Arnauld Feb 27 at 9:12
  • \$\begingroup\$ -5 bytes by changing concatenation operator to |. Try it online! \$\endgroup\$ – Mukundan Feb 28 at 9:33
  • \$\begingroup\$ @Mukundan Ah, I didn't notice we were allowed to use custom symbols. Thanks for the heads up. \$\endgroup\$ – Arnauld Feb 28 at 9:37
4
\$\begingroup\$

Wren, 107 bytes, score: 138373

Thanks to @Mukundan for the golfing so far!

(This answer was written before @GammaFunction did so.)

Fn.new{|n,d|"%(n)".map{|i|Num.fromString(i)}.map{|i|i<1?[d,-d]:[d]*(i/d).floor+["%(d)/%(d)"]*(i%d)}.join()}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Doesn't handle n with 0 as a digit (e.g.: 601) \$\endgroup\$ – GammaFunction Feb 27 at 8:06
  • \$\begingroup\$ @Mukundan In your OP you represent 10 as 1 || 1 - 1. Is 1 || allowed? \$\endgroup\$ – GammaFunction Feb 27 at 8:13
  • \$\begingroup\$ @GammaFunction, no representing 10 as 1 || is not allowed \$\endgroup\$ – Mukundan Feb 27 at 8:34
4
\$\begingroup\$

Brainfuck, 30 bytes * 100 + 9009000 = 9012000

Uses the fact that n = (d/d)*n:

,>,>+<<->.>.<.<[->>>.<<.>.<.<]

In that program, the character representing division is ASCII 1 and the character representing addition is ASCII 0, so the output isn't very readable.

With this TIO link I include a brief header making the output readable. There is still the minor inconvenience that input are ASCII characters (the link has a new line, ASCII 10, in the input, hence the program prints

9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9

To make 10. If instead you use this interpreter, you can type easier to understand input, using \ to insert the values of the ascii characters, instead of using the ascii characters. So, using \10\57 as input in this program gives the same result as the program on TIO.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ How do I input n greater than 256? \$\endgroup\$ – Mukundan Feb 28 at 4:26
  • \$\begingroup\$ @Mukundan unfortunately, you don't. But the program works in theory for any n and d and that is how I computed the score, under that assumption \$\endgroup\$ – RGS Feb 28 at 7:08
4
\$\begingroup\$

Zsh, 89 81 75 bytes, score: 135173

(total digit count is 127673)

for c (${(s::)1})(repeat c/$2 s+=($2);repeat c%$2 s+=($2/$2);<<<${s=$2-$2})

Try it online!

(This generates the same operations that @a'_''s method does. I thought of it independently, then saw his score using it, then implemented it.)

You can use custom symbols for representing the digits and operations [...]

We take advantage of that here; concatenation is represented by a newline and addition is represented by space. Concatenation has lower precedence than addition, which has lower precedence than division.

for c (${(s::)1})(          # for each digit c in n
                            # repeat $x expands $x in arithmetic mode
    repeat c/$2 s+=($2)     # append d to $s, c/d times
    repeat c%$2 s+=($2/$2)  # append d/d to $s, c%d times 
    <<<${s=$2-$2}           # if $s is still unset, set it to d-d
                            # <<< prints $s, implicitly joined on spaces
)                           # exit the subshell, effectively unsetting $s
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 150 bytes × 100 + 81773 digits = 96773

⪫Eθ§⪪§⪪”}∧⟦NJgYZG;|⪫v4⌈-LiςΠg➙∨C⊕⊙Nψ≧Fδ∨↧↧«3Y!‴2ⅈ⸿⟦⁰J◨(⁴⦄4b¶¤⦄→₂⊞GςG⸿≡←ε⭆R?ρq&Σ<×HJ⁶�⧴Q<"k~3Vu⌊+LΠ↓1βπt“P³∨R▶A↓ⅉs▷"«‖κ-σ_←U/V!U⊕⁷↙U3M⁼³RVV¤HQ:”;Iη,Iι&

Try it online! Link is to verbose version of code. Uses & (low precedence) as concatenation and # to represent the input digit. Explanation: Simply looks up all of the digit patterns in a (compressed) hand-crafted lookup table and concatenates the relevant digits together. Proof of digit count.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I had a look at your lookup table. Do you then recursively use different patterns until you get to the input number? Or how does it work? \$\endgroup\$ – RGS Feb 28 at 16:21
  • \$\begingroup\$ @RGS It's exactly as described... let's say you want 64 using 2s, then it would look up the patterns for 6 and 4 in the table, and output them with concatenation, giving #+#+#&#+# i.e. 2+2+2&2+2=6&4=64. \$\endgroup\$ – Neil Feb 28 at 17:06
1
\$\begingroup\$

W n, 22 bytes * 100 + 127673 = 129 873

A blatant rip-off of my Wren answer.

☺◘Y╔û çτ◘↑═uon↕I6≡ÿÑ°t

Uncompressed:

1,             % Split number to chunks of 1
  c}           % Construct the list [input]
    ac/*       %   Repeat that input/current times
  c:{          % The list [input,input]
     '/,       % The string input/input
        }      % The list [input/input]
         acm*  %   Repeat that list input%current times
             + % Join these two lists
      |        % If that's the empty list:
  c:_{         %   Yield the list [input,-input]
       M       % Do that for every thing in the input
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Explanation and TIO? \$\endgroup\$ – Mathgeek Feb 27 at 14:22
1
\$\begingroup\$

Ruby, Score: 127,473 (178 bytes * 100 + 109,673)

->n,d{n.to_s.chars.map{|c|g=d.to_s;c<?1?g+?-+g:(i=c.to_i)==d ?d:(d*d==i)?g+?*+g:i%d<1?([d.to_s]*(i/d))*?+:i>d ?g+?++f[i-d,d]:(i+1==d&&i>1)?g+?-+f[d-i,d]:[d==1?d:g+?/+g]*i*?+}*?|}

Try it online!

This uses | as concatenation. It could also definitely be cleverer. I just kept adding cases to try to minimse the occurences of d.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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