# "Defuse" the bombs

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".

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

• Suggest case where parallel defuse make difference
– l4m2
Feb 16, 2022 at 15:22
• @l4m2 Not sure what you mean by "parallel defuse". Feb 16, 2022 at 15:23
• 1 0 1 0 1 5 1 1 5 1 0 1 0 1 is 2 or 3?
– l4m2
Feb 16, 2022 at 15:25
• This looks more like blowing up than defusing! lol Feb 16, 2022 at 16:16
• @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 Feb 17, 2022 at 13:46

# 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.

• -3, I believe. Feb 16, 2022 at 21:42
• @loopywalt That's a clever one! Feb 17, 2022 at 4:20

# BQN, 29 26 bytesSBCS

Quite inefficient depth-first search.

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


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

• what a wonderful explanation. Sep 7, 2022 at 13:27

# 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!

# 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.

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)


# 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!

• Why [0]*a+[0]+[0]*a1 than [0]*(2*a+1)?
– l4m2
Feb 16, 2022 at 15:57
• 90 bytes Feb 16, 2022 at 16:06
• @MarcMush Thanks, updated Feb 16, 2022 at 16:08
• 84
– l4m2
Feb 16, 2022 at 16:10
• 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? Feb 16, 2022 at 16:13

# 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
L - length


# 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.

# Perl 5List::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!

# JavaScript (Node.js), 8979 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

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

# 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.

# Charcoal, 44 bytes

⊞υＡ≔⁰ζＷ⌊Ｅυ⌈κ«≦⊕ζ≔υη≔⟦⟧υＦηＦＥκＥκ∧›↔⁻ξμλν⊞υλ»Ｉζ


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

⊞υＡ


≔⁰ζ


Ｗ⌊Ｅυ⌈κ«


Repeat until a fully cleared list is found.

≦⊕ζ


Increment the number of explosions.

≔υη≔⟦⟧υ


Temporarily save the list of lists.

ＦηＦＥκＥκ∧›↔⁻ξμλν⊞υλ


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).

»Ｉζ


Output the number of explosions needed.

23 bytes using the newer version of Charcoal on ATO:

⊞υＡ≔⁰ζＷ⌊Ｅυ⌈κ«≦⊕ζ≔ΣＥυＥκＥκ∧›↔⁻πνμξυ»Ｉζ
`

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