25
\$\begingroup\$

Using our familiar mathematical symbols: +, x, parenthesis, and any rational number, it's easy to create expressions that evaluates to some desired number. For example: 1+(2x3)=7, (1+2)+(3x6.5)=22.5 and so on. Boring enough.

In this challenge, we'll use a new operator: ±. The use of ± in an expression means you need to evaluate the expression by replacing the ±'s by + or - in all possible ways, and return the set of all possible values. For example:

  • 1±2±3 = {-4,0,2,6} because 1±2±3 can be any of 1+2+3, 1+2-3, 1-2+3 and 1-2-3 and their values are 6,0,2,-4 respectively.
  • (±2)x(2±3) = {-10,-2,2,10} for similar reasons.

Now, as it turns out, given any set of distinct real numbers, it's possible to create an expression with +,x,(,),±, and real numbers that evaluates to the given set.

Task

Your task is to write a program or function in a language of your choice, that takes a sequence (list/array/any convenient format) of integers and outputs an expression (as a string) consisting of +,x,(,),±, and rational numbers that evaluates to the set of the given numbers.

  • Note that the exact character ± doesn't matter; you can use any other character of your choice as long as it's distinguishable from the other characters you're using. But you must mention which character you are using in your submission.
  • The input is allowed to consist of decimal approximations (up to reasonable accuracy) of the rational numbers used.
  • Input and output can be taken in any of the standard ways.
  • Standard loopholes are forbidden.
  • You can assume the given integers will be distinct, and provided in increasing order.
  • Output may contain spaces and newlines.

Winning Criterion

This is , so shortest code in bytes wins.

Examples

Input        |  Possible output
-------------+-----------------------------
[1,2,3]      |  2±0.5±0.5                   
[-7,-3,1,21] |  (1±2)x(3±4)

Idea taken from a question in the Tournament of Towns, Fall 2015.

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to PPCG! Nice first challenge! I think this would attract more answers if it were the other way around (find the set given the expression) because it seems like this is quite a tricky challenge. Good challenge nonetheless! \$\endgroup\$ – HyperNeutrino Apr 17 '17 at 3:05
  • \$\begingroup\$ Welcome again! Adding on to @HyperNeutrino, there will probably be multiple solutions to some of the sets, which could be a problem, when deciding which question is the "best" unless the deciding factor is the conciseness \$\endgroup\$ – David Archibald Apr 17 '17 at 3:07
  • \$\begingroup\$ @HyperNeutrino Thanks! I did apprehend this might turn to be a bit hard, but I fully believe in the superior capabilities of the golfers here; let's see how it turns out. :) \$\endgroup\$ – Ankoganit Apr 17 '17 at 3:08
  • 3
    \$\begingroup\$ Yes. Some of the golfers on this site have amazing superpowers, and we even suspect some are golfing bots >_> :D \$\endgroup\$ – HyperNeutrino Apr 17 '17 at 3:09
  • \$\begingroup\$ @DavidArchibald Yes, the intended output is any solution that works. \$\endgroup\$ – Ankoganit Apr 17 '17 at 3:10
11
\$\begingroup\$

Python 2, 56 bytes

f=lambda h,*t:t and"(.5?.5)*(%s+%%s)+"%f(*t)%-h+`h`or`h`

Try it online!

The ? stands for ±. Example usage:

f(-3,5,20) ->
(.5?.5)*((.5?.5)*(20+-5)+5+3)+-3

The idea is that we can take an expression E and adjoin a new value h to its set of values by doing (.5±.5)*(E+-h)+h.

\$\endgroup\$
  • \$\begingroup\$ Why +-h, and not just -h? That is, why not make the + a - and remove the - that's currently in the program? \$\endgroup\$ – isaacg Apr 17 '17 at 8:57
  • 1
    \$\begingroup\$ @isaacg The spec doesn't allow for a - operator in the expression. \$\endgroup\$ – xnor Apr 17 '17 at 9:05
9
\$\begingroup\$

Haskell, 52 bytes

f(h:t)=shows h"+(.5?.5)*("++f[x-h|x<-t]++")"
f e="0"

Try it online!

Uses ? for ±. Example:

f [1,3,7] ->
1+(.5?.5)*(2+(.5?.5)*(4+(.5?.5)*(0)))

The function shows does shows a b=(show a)++b, a trick I learned from Lynn.

shows 12 "abc" ->
"12abc"
\$\endgroup\$
5
\$\begingroup\$

Haskell, 58 bytes

Using # for ±, as it's one less byte.

f takes a list of integers and returns a string.

f[x]=show x
f(x:r)=show x++"+(.5#.5)x("++f((-x+)<$>r)++")"

Result is of the form n+(.5#.5)x(rest), where n is the first element of the list and rest is the representation of all the others with n subtracted from each.

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Jelly, 29 bytes

“(¤)”j.⁾+×j;”(
I;@Ḣj¢;”)ẋ⁸L¤¤

Prints v+(0.5¤0.5)×(i1+(0.5¤0.5)×((i2+(0.5¤0.5)×(...(in)...))) where v is the first number in the input array and in is the nth incremental difference between elements of the input array.

Try it online!

How?

“(¤)”j.⁾+×j;”( - Link 1, adjoining list: no input
“(¤)”          - literal     ['(','¤',')']
      .        - literal     0.5
     j         - join        ['(',0.5,'¤',0.5,')']
       ⁾+×     - literal     ['+','×']
          j    - join        ['+',['(',0.5,'¤',0.5,')'],'×']
            ”( - literal     '('
           ;   - concatenate ['+',['(',0.5,'¤',0.5,')'],'×','(']

I;@Ḣj¢;”)ẋ⁸L¤¤ - Main link: list a               e.g. [-1,5,2]
I              - incremental differences(a)           [6,-3]
   Ḣ           - head(a)                              [-1]
 ;@            - concatenate (rev @rgs)               [-1,6,-3]
     ¢         - last link (1) as a nilad             ['+',['(',0.5,'¤',0.5,')'],'×','(']
    j          - join                                 [-1,['+',['(',0.5,'¤',0.5,')'],'×','('],6,['+',['(',0.5,'¤',0.5,')'],'×','('],-3]
             ¤ - nilad followed by link(s) as a nilad
            ¤  -     nilad followed by link(s) as a nilad
          ⁸    -         link's left argument, a
           L   -         length                       3
       ”)      -     literal ')'
         ẋ     -     repeat                           [')',')',')']
      ;        - concatenate                          [-1,['+',['(',0.5,'¤',0.5,')'],'×','('],6,['+',['(',0.5,'¤',0.5,')'],'×','('],-3,')',')',')']
               - implicit print                       -1+(0.5¤0.5)×(6+(0.5¤0.5)×(-3))
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 25 bytes

0¸«¥X;D"+(ÿ±ÿ)*("ý¹g<')×J

Try it online!

Explanation

0¸«                        # prepend a 0 to input list
   ¥                       # calculate delta's
    X;D                    # push 0.5 twice
       "+(ÿ±ÿ)*("          # push this string and interpolate 0.5 where "ÿ" is
                 ý         # merge the list of delta's with this string as a separator
                  ¹g<')×J  # add the closing parenthesis

Building the expression from the right unfortunately ends up at that the same byte count with
0¸«¥¤s¨RvX;Dy"ÿ+(ÿ±ÿ)*(ÿ). The 8 bytes used for the setup is the big waste here.

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

Haskell, 54 bytes

f[]="0"
f(x:s)=show x++"+(.5?.5)*("++f(map(-x+)s)++")"

the +- sign is '?'. example:

f[1,2,3,4] = "1+(.5#.5)*(1+(.5#.5)*(1+(.5#.5)*(1+(.5#.5)*(0))))"
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 56 51 bytes

f=([v,...a],x=v)=>x?x+`+(.5@.5)*(${f(a,a[0]-v)})`:0

Based on @JonathanAllan's formula. @ stands for ±.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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