25
\$\begingroup\$

You've been hired by a bomb defusing company to perform some "controlled" demolition of un-exploded ordnance. You are given a list of bombs represented by non-negative integers.

[3,2,4,0,3,1,2]

Every step you can set up and explode a bomb. When a bomb \$n\$ explodes, it destroys all bombs within \$n\$ places replacing them with zeros

         v
[3,2,4,0,3,1,2]
   * * * * * *
[3,0,0,0,0,0,0]

Once everything is zeros you are done "defusing".

Task

Given a starting non-empty list of bombs output the minimum steps required to clear it.

This is so the goal is to minimize the length of your source code as measured in bytes.

Test cases

[0,0,0,0,0] -> 0
[0,0,1,0] -> 1
[3,2,4,1,3,1,2] -> 1
[9,9,10,9] -> 1
[1,4,1,3,1,0,5] -> 1
[1,1,1,1,1] -> 2
[1,1,1,1,1,5,1,1,1,1,4,1,0,0,1] -> 2
[1,1,1,1,1,5,1,6,1,1,4,1,0,0,1] -> 2
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Suggest case where parallel defuse make difference \$\endgroup\$
    – l4m2
    Feb 16, 2022 at 15:22
  • 1
    \$\begingroup\$ @l4m2 Not sure what you mean by "parallel defuse". \$\endgroup\$
    – Wheat Wizard
    Feb 16, 2022 at 15:23
  • 1
    \$\begingroup\$ 1 0 1 0 1 5 1 1 5 1 0 1 0 1 is 2 or 3? \$\endgroup\$
    – l4m2
    Feb 16, 2022 at 15:25
  • 6
    \$\begingroup\$ This looks more like blowing up than defusing! lol \$\endgroup\$
    – Noodle9
    Feb 16, 2022 at 16:16
  • 2
    \$\begingroup\$ @Noodle9 a bomb that exploded (past tense) is also defused by default. Defusing a bomb without exploding it is the hard part. From the dictionary: 2 : to make less harmful, potent \$\endgroup\$ Feb 17, 2022 at 13:46

11 Answers 11

6
\$\begingroup\$

Python 3.8, 72 bytes

-3 bytes thanks to @loopy walt

Returns False instead of 0.

f=lambda a,i=0:any(a)and-~min(f(a[:i][:-x])+f(a[x+(i:=i+1):])for x in a)

Try it online!

The idea is to recursively split the array into left and right sections after an explosion.

\$\endgroup\$
2
  • \$\begingroup\$ -3, I believe. \$\endgroup\$
    – loopy walt
    Feb 16, 2022 at 21:42
  • \$\begingroup\$ @loopywalt That's a clever one! \$\endgroup\$ Feb 17, 2022 at 4:20
4
\$\begingroup\$

BQN, 29 26 bytesSBCS

Quite inefficient depth-first search.

{(≠⌊´1+𝕊˘)𝕩⊸ע𝕩/𝕩<|-⌜˜↕≠𝕩}

Run online! or click here for step-by-step results with comments.

\$\endgroup\$
1
  • \$\begingroup\$ what a wonderful explanation. \$\endgroup\$
    – Razetime
    Sep 7, 2022 at 13:27
3
\$\begingroup\$

Julia 1.0, 65 62 bytes

!l=sum(l)>(j=0)&&minimum(i->1+!l[1:(j+=1)-i]+!l[j+i:end],l.+1)

Try it online!

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

05AB1E, 31 25 bytes

[DOß_#¼εāDδα‹øy*øyĀÏ}€`}¾

-6 bytes and sped up substantially by porting @ovs' BQN answer.

Input as a wrapped list. If this is not allowed, a leading ¸ can be added.

Try it online or verify all test cases.

Explanation:

[         # Loop indefinitely:
 D        #  Duplicate the current list of lists
          #  (which will be the implicitly input in the first iteration)
  Oß_     #  Check if there is an inner list of only 0s:
  O       #   Sum each inner list in the duplicate
   ß      #   Pop and push the minimum
    _     #   Check if this is equal to 0
          #  If it's truthy:
     #    #   Stop the infinite loop
  ¼       #  Increase `¾` by 1 (0 by default)
  ε       #  Map over each inner list `y`:
   āDδα   #   Create a matrix of the same length with 0 as main diagonal, and
          #   with each adjacent diagonal 1 higher than the previous:
   ā      #    Push a list in the range [1,length] (without popping `y`)
    D     #    Duplicate it
     δ    #    Apply double-vectorized:
      α   #     Absolute difference
   ‹      #   Check for all values in a row if it's smaller than the value at the
          #   same position in list `y` that's was still on the stack
    øy*ø  #   Multiply each column to the corresponding value in list `y`:
    ø     #    Zip/transpose; swapping rows/columns
     y*   #    Multiply each row by the same positioned value in list `y`
       ø  #    Zip/transpose the row/columns back
    yĀÏ   #   Remove the rows for which the corresponding value in `y` is 0:
    y     #    Push list `y` again
     Ā    #    Check for each value if it's NOT 0
      Ï   #    Only leave the rows at the truthy positions
   }€`    #  After the inner map: flatten one level down
}¾        # After the infinite loop: push the counter variable `¾`
          # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Python3, 84 bytes:

f=lambda x:any(x)and-~min(f(x[:max(i-a,0)])+f(x[i+a+1:])for i,a in enumerate(x)if a)

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Why [0]*a+[0]+[0]*a1 than [0]*(2*a+1)`? \$\endgroup\$
    – l4m2
    Feb 16, 2022 at 15:57
  • \$\begingroup\$ 90 bytes \$\endgroup\$
    – MarcMush
    Feb 16, 2022 at 16:06
  • \$\begingroup\$ @MarcMush Thanks, updated \$\endgroup\$
    – Ajax1234
    Feb 16, 2022 at 16:08
  • \$\begingroup\$ 84 \$\endgroup\$
    – l4m2
    Feb 16, 2022 at 16:10
  • \$\begingroup\$ Oh I just realized that you updated your answer with the same approach as mine :P. I suppose it's alright if I keep it? \$\endgroup\$ Feb 16, 2022 at 16:13
2
\$\begingroup\$

Jelly, 17 bytes

J_r+ɗ⁸ŒPFḟ@LɗÞTḢL

A monadic Link accepting a list of non-negative integers that yields a non-negative integer.

Try it online! Or see the test-suite.

How?

I think brute force is tersest for this one, but maybe not...

J_r+ɗ⁸ŒPFḟ@LɗÞTḢL - Link: bombs
J                 - range of length of bombs -> I = [1,2,...]
    ɗ⁸            - last three links as a dyad - f(I, bombs)
 _                -   I subtract bombs (vectorises)
   +              -   I add bombs (vectorises)
  r               -   inclusive range -> list of blast zones
                                         (includes out of bounds, but that's OK...)
      ŒP          - powerset
              T   - truthy indices of bombs -> T = indices we need to affect
             Þ    - sort the powerset by:
            ɗ     -   last three links as a dyad - f(set, T)
        F         -     flatten the set
         ḟ@       -     filter those values out of T
           L      -     length
               Ḣ  - head
                L - length
\$\endgroup\$
1
\$\begingroup\$

Python, 94 bytes

f=lambda a:any(a)and-~min(f([v<abs(i-t)and x for i,x in E(a)])for t,v in E(a)if v)
E=enumerate

Attempt This Online!

Simple depth-first search.


Whython, 87 bytes

f=lambda a:min(f([v<abs(i-t)and x for i,x in E(a)])for t,v in E(a)if v)+1?0
E=enumerate

Attempt This Online!

Base-case is ValueError: min() arg is an empty sequence, which indicates the array is all 0s.

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

Perl 5 List::Util, 109 bytes

sub f{my($b,$r,@i)=@_;@i[$b-min($r,$b)..$b+$r]=()if$r;!sum(@i)?0:1+min map $i[$_]?f($_,$i[$_],@i):inf,0..$#i}

Try it online!

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

JavaScript (Node.js), 89 79 67 bytes

-7 bytes from Arnauld

f=x=>0|Math.min(...x.map((v,i)=>v?1+f(x.map(w=>i*i-->v*v&&w)):1/0))

Try it online!

Using fact that (Infinity | 0) == 0

DFS

BFS answer deprecated

\$\endgroup\$
3
  • \$\begingroup\$ Python method not good, 1+f(x.slice(0,i>v&&i-v))+f(x.slice(v+i)) is too long \$\endgroup\$
    – l4m2
    Feb 16, 2022 at 16:16
  • \$\begingroup\$ /[1-9]/.test(x) is not interesting for flat arrays. You can just do x.some(v=>v). \$\endgroup\$
    – Arnauld
    Feb 16, 2022 at 17:58
  • 1
    \$\begingroup\$ (w,j)=>(i-j)**2 can be turned into w=>i*i--. \$\endgroup\$
    – Arnauld
    Feb 16, 2022 at 18:01
1
\$\begingroup\$

Retina, 52 bytes

^
!¶
\d+
*_-$%"
^/^[0,-]*$/m}+`\d*,?_(_*-),?\d*
$1
!

Try it online!

Explanation

^
!¶

Prepend a new line with a single ! to keep track of number of steps


\d+
*_-$%"

For each nonnegative integer, duplicate the whole line but with the number replaced by that many _s followed by a -. For example, 3,2,4,1,3,1,2 becomes

___-,2,4,1,3,1,2
,__-,4,1,3,1,2
3,,____-,1,3,1,2
3,2,,_-,3,1,2
3,2,4,,___-,1,2
3,2,4,1,,_-,2
3,2,4,1,3,,__-
3,2,4,1,3,1,

The _s represents a "blast wave" which destroys other bombs.

Some of the numbers next to the "defused" bomb are also deleted along the way. This does not affect the result because

  • if the "defused" bomb is positive, that number would have been blown up anyway
  • if the "defused" bomb is 0, then it is not the optimal move anyway as long as there are still positive bombs (which is guaranteed by the looping condition)

Also note that the original line (with the last number removed) is kept, effectively giving the option of actually defusing the last bomb (without blowing it up). But since that won't ever be better than just blowing it up, we can just leave it.


+`\d*,?_(_*-),?\d*
$1

Propagate the blast waves repeatedly until it no more propagation is possible

To propagate a blast wave,

  1. Delete the adjacent spaces.
  2. Reduce the blast wave by 1

This compresses the entire "blast zone" to one space, but it is fine because there is no need to keep track of how large a blast zone was.

A - is left behind in that space and it act as a barrier to prevent blast waves from later steps from propagating through an old blast zone. If a blast wave from a later step wants to cross an old blast zone, then either:

  • it doesn't have enough power to cross the whole blast zone anyway, so the barrier didn't prevent the new blast wave from destroying any bombs
  • it has enough power to cross the whole blast zone, which means the new blast wave covers the entire old blast zone, so "defusing" that new bomb first is a more optimal move anyway

^/^[,0-]+$/m}

Loop all the above until there is a line with only ,s, 0s, and/or -s (i.e. a finished state)


!

Count the number of !s marked. That is the number of steps taken to reach the finished state.

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

Charcoal, 44 bytes

⊞υA≔⁰ζW⌊Eυ⌈κ«≦⊕ζ≔υη≔⟦⟧υFηFEκEκ∧›↔⁻ξμλν⊞υλ»Iζ

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

⊞υA

Start with just the input list.

≔⁰ζ

Start with 0 explosions.

W⌊Eυ⌈κ«

Repeat until a fully cleared list is found.

≦⊕ζ

Increment the number of explosions.

≔υη≔⟦⟧υ

Temporarily save the list of lists.

FηFEκEκ∧›↔⁻ξμλν⊞υλ

Make a new list of lists of the results of exploding each entry in each list (including zero entries, which have no effect on the list).

»Iζ

Output the number of explosions needed.

23 bytes using the newer version of Charcoal on ATO:

⊞υA≔⁰ζW⌊Eυ⌈κ«≦⊕ζ≔ΣEυEκEκ∧›↔⁻πνμξυ»Iζ

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

\$\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.