10
\$\begingroup\$

Objective

Given a nonempty unordered list of positive integers, decide whether they can be added, negated, or multiplied to yield a single zero. Each given number must be used exactly once.

There is a taboo. Do not multiply zero to anything. Adding zero to anything is OK.

Examples

Truthy

List, Solution
[1,1], 1-1
[1,1,2], 2-1-1
[2,3,5], 2+3-5
[2,3,6], 2*3-6
[1,2,3,4], 2-1+3-4
[1,1,3,4], 1*1+3-4
[2,2,3,4], 2*3-2-4
[1,1,2,2,2], (2-1*1)*2-2

Falsy

[1]
[1,2]
[2,3,4]
[1,3,3,4] ((3-3)*1*4 isn't valid because multiplication by zero is taboo)
\$\endgroup\$
3
  • \$\begingroup\$ Suggest truthy cases where brackets are unavoidable \$\endgroup\$
    – l4m2
    Mar 11 at 7:08
  • 2
    \$\begingroup\$ This is essentially 24 game \$\endgroup\$
    – mousetail
    Mar 11 at 14:02
  • 3
    \$\begingroup\$ [1,1,2,2,2] can be solved with 1+1-2+2-2 without parens. A better example might be [1,2,3,9] -> (1+2)*3-9. \$\endgroup\$
    – Bubbler
    Mar 12 at 0:56

5 Answers 5

4
\$\begingroup\$

JavaScript (ES6), 101 bytes

Returns 0 or 1.

f=a=>a==0|a.some((p,i)=>a.some((q,j)=>i<j&&[p+q,p-q,p*q||f].some(v=>f(q,q[i]=v),q=a.filter(_=>j--))))

Try it online!

Commented

f = a =>            // a[] = input array
a == 0 |            // success if a[] == [0]
a.some((p, i) =>    // for each value p at index i in a[]:
  a.some((q, j) =>  //   for each value q at index j in a[]:
    i < j &&        //     abort if i >= j
    [               //     otherwise, compute:
      p + q,        //       addition
      p - q,        //       subtraction
      p * q         //       multiplication, whose result is ...
      || f          //       ... invalidated if it's 0
    ].some(v =>     //     for each value v in the above array:
      f(            //       do a recursive call:
        q,          //         pass q[]
        q[i] = v    //         with q[i] = v
      ),            //       end of recursive call
      q =           //       initialize q[] to ...
      a.filter(_ => //       ... a copy of a[] with ...
        j--         //         ... the j-th element removed
      )             //       end of filter()
    )               //     end of some()
  )                 //   end of some()
)                   // end of some()
\$\endgroup\$
3
  • 1
    \$\begingroup\$ It fails for [4,6,6,9] 6*6-4*9 (suggested by @l4m2) \$\endgroup\$ Mar 11 at 9:27
  • \$\begingroup\$ @Mukundan314 Thanks for reporting this. Should be fixed. (It was a generic bug, not directly related to this specific test case.) \$\endgroup\$
    – Arnauld
    Mar 11 at 9:37
  • 3
    \$\begingroup\$ Neel Shukla: please stop editing this post. Multiplying by 0 is not allowed as per the challenge rules, so 1,2,2,9 is falsy. You can't do (9-1)*(2-2). \$\endgroup\$
    – Arnauld
    Mar 11 at 10:29
3
\$\begingroup\$

Charcoal, 56 bytes

⊞υAFυFLιFκ«≔⟦§ιλ§ικ⟧θFΦ⟦ΠθΣθ↔↨θ±¹⟧∨μν⊞υ⊞OΦι∧⁻ξκ⁻ξλ컬⌈⌊υ

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

⊞υAFυ

Start a breadth-first search with the initial list of integers.

FLιFκ«

Loop over the indices of every pair of integers in the list.

≔⟦§ιλ§ικ⟧θ

Extract the integers.

FΦ⟦ΠθΣθ↔↨θ±¹⟧∨μν

Loop over the sum and the absolute difference, and also the product, if it is nonzero.

⊞υ⊞OΦι∧⁻ξκ⁻ξλμ

Remove the integers from the list and add the new value, then add the new list to the list of lists to search.

»¬⌈⌊υ

Check whether a zero result was obtained.

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

JavaScript (Node.js), 98 bytes

f=(x,a,b)=>[b]<f?x.some((t,i)=>f(x.filter(_=>i--),t,a))|x==a:[a+b,a-b,a*b||f].some(y=>f([...x,y]))

Try it online!

JavaScript (Node.js), 106 bytes

f=(x,a,b)=>1/b?f([...x,a+b])|f([...x,a-b])|a*b*f([...x,a*b]):x+x?x.some((t,i)=>f(x.filter(_=>i--),t,a)):!a

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Your 96-byte version disagrees with your 106-byte version for e.g. [2,2,2,2,2]. \$\endgroup\$
    – Arnauld
    Mar 11 at 11:04
  • \$\begingroup\$ @Arnauld Should be fix if no stringified number is smaller than "(" \$\endgroup\$
    – l4m2
    Mar 12 at 0:38
1
\$\begingroup\$

Python3, 292 bytes

lambda v:0 in[*f(v)]
R=range
def f(v):
 k=[v]
 for i in R(len(v)):
  for j in R(i+1,len(v)+1):
   if j-1>1 and j-i<len(v):
    for t in f(v[i:j]):k+=[v[:i]+[t]+v[j:]]
 for i in k:
  if len(i)==1:yield i[0];continue
  if(V:=i[0]*i[1]):k+=[[V,*i[2:]]]
  for I in[-1,1]:k+=[[i[0]+I*i[1],*i[2:]]]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 387 371 bytes

A port of @Ajax1234's Python answer in scala.

Saved 16 bytes thanks to @ceilingcat


Golfed version (371 bytes). Attempt This Online!

def F(v:List[Int])=f(v).contains(0)
def f(v:List[Int]):LazyList[Int]={val k:LazyList[List[Int]]=LazyList(v)++(for{i<-(0 to v.size-1).to(LazyList);j<-(i+1 to v.size).to(LazyList);if j>2&j-i<v.size;t<-f(v.slice(i,j))}yield v.slice(0,i)++List(t)++v.drop(j));k.flatMap{i=>if(i.size==1)LazyList(i(0))else{LazyList(i(0),i(1),i(0)*i(1))++(i.drop(2):+(i(0)+i(1))):+(i(0)-i(1))}}}

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    println(F(List(1, 1)))
    println(F(List(1, 1, 2)))
    println(F(List(2, 3, 5)))
    //println(F(List(2, 3, 6)))
    println(F(List(1, 2, 3, 4)))
    println(F(List(1, 1, 3, 4)))
    println(F(List(2, 2, 3, 4)))
    println(F(List(1, 1, 2, 2, 2)))
    println("-" * 20)
    println(F(List(1)))
    println(F(List(1, 2)))
    println(F(List(2, 3, 4)))
    //println(F(List(1, 3, 3, 4)))
    //println(F(List(2, 2, 2, 2, 2)))
  }

  def F(v: List[Int]): Boolean = f(v).contains(0)

  def f(v: List[Int]): LazyList[Int] = {
    val k: LazyList[List[Int]] = LazyList(v) ++ (for {
      i <- (0 until v.length).to(LazyList)
      j <- (i + 1 to v.length).to(LazyList)
      if j - 1 > 1 && j - i < v.length
      t <- f(v.slice(i, j))
    } yield v.slice(0, i) ++ List(t) ++ v.drop(j))
    
    k.flatMap { i =>
      if (i.length == 1) LazyList(i.head)
      else {
        val V = i.head * i(1)
        LazyList(i.head, i(1), V) ++ (i.drop(2) :+ (i.head + i(1))) :+ (i.head - i(1))
      }
    }
  }
}
\$\endgroup\$
1

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.