[Question]
  [
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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") 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
```
  
[Answer]
# [Python 3.8](https://docs.python.org/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!](https://tio.run/##dY3BboNADETvfIVvWQtT7UISlZXojyAOrhIUS7Cs6KYll/46XShJe2g1suR5npH9LVwGVzz7cZ7bquP@9cTAJJW27G6Kkd0p@@zFqVZxbaWpbTY1mC5uSpXYSlKDtsF2GGECccA4f1ykO4OxSfSeYLgGDxX07NX5nTta6DUofHrznQS1g@wFdogJ@FFciI/iHb9rONeaNjVLTicrMJs1SV1QTvsIijj5HZZUktFU3r15RDQdfuCmFeS/AB0e237t6P9Cx79CXw "Python 3.8 (pre-release) ‚Äì Try It Online")
The idea is to recursively split the array into left and right sections after an explosion.
[Answer]
# [BQN](https://mlochbaum.github.io/BQN/), ~~29~~ 26 bytes[SBCS](https://github.com/mlochbaum/BQN/blob/master/commentary/sbcs.bqn)
Quite inefficient depth-first search.
```
{(‚â†‚åä¬¥1+ùïäÀò)ùï©‚ä∏√óÀòùï©/ùï©<|-‚åúÀú‚Üï‚â†ùï©}
```
[Run online!](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgeyjiiaDijIrCtDEr8J2VisuYKfCdlaniirjDl8uY8J2VqS/wnZWpPHwt4oycy5zihpXiiaDwnZWpfQoKIyBjaGFuZ2UgdGhpcyB0byAxIHRvIGluY2x1ZGUgdGhlIGxhc3QgdHdvIGNhc2VzCiMgdGhpcyB3aWxsIGZyZWV6ZSB0aGUgcGFnZSBmb3Ig4oi+MSBtaW4KcnVuQWxsIOKGkCAwCgo+KOKLiOKfnEYpwqggKMKvMsOXwqxydW5BbGwpIOKGkyDin6gKMOKAvzDigL8w4oC/MOKAvzAKMOKAvzDigL8x4oC/MAoz4oC/MuKAvzTigL8x4oC/M+KAvzHigL8yCjnigL854oC/MTDigL85CjHigL804oC/MeKAvzPigL8x4oC/MOKAvzUKMeKAvzHigL8x4oC/MeKAvzEKMeKAvzHigL8x4oC/MeKAvzHigL814oC/MeKAvzHigL8x4oC/MeKAvzTigL8x4oC/MOKAvzDigL8xCjHigL8x4oC/MeKAvzHigL8x4oC/NeKAvzHigL824oC/MeKAvzHigL804oC/MeKAvzDigL8w4oC/MQrin6k=) or [click here](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgeyjiiaDijIrCtDEr8J2VisuYKfCdlaniirjDl8uY8J2VqS/wnZWpPHwt4oycy5zihpXiiaDwnZWpfQoKYiDihpAgMeKAvzTigL8x4oC/M+KAvzHigL8w4oC/NQp74oCiU2hvd/CdlY9ifcKoIOKfqAoiVGhlIGlucHV0IgogICAgICAgICAgICB7ICAgICAgICAgICAgICDwnZWpfQoiSW5kaWNlcyBvZiB0aGUgaW5wdXQiCiAgICAgICAgICAgIHsgICAgICAgICAgICDihpXiiaDwnZWpfQoiVGFibGUgb2YgYWJzb2x1dGUgZGlmZmVyZW5jZXM7IGRpc3RhbmNlcyB0byB0aGUgZGlhZ29uYWwiCiAgICAgICAgICAgIHsgICAgICAgIHwt4oycy5zihpXiiaDwnZWpfQoiV2Ugd2lsbCBkbyBvbmUgZXhwbG9zaW9uIGluIGVhY2ggcm93IgoiV2hlcmUgaXMgdGhlIHRhYmxlIGxhcmdlciB0aGFuIHRoZSBib21iPyIK4o2J4oiY4omN4oi+4peLPCAgICAgIHsgICAgICDwnZWpPHwt4oycy5zihpXiiaDwnZWpfQoiUmVtb3ZlIHJvd3MgY29ycmVzcG9uZGluZyB0byBzaXplLTAgZXhwbG9zaW9ucyAoQWxzbyBkdXBsaWNhdGVzIG90aGVyIHJvd3MpIgrijYniiJjiiY3iiJgvy5ziiL7il4s8ICAgeyAgICDwnZWpL/Cdlak8fC3ijJzLnOKGleKJoPCdlal9CiJNdWx0aXBseSBlYWNoIHJvdyB3aXRoIHRoZSBpbnB1dCB2ZWN0b3IiCjLigL8x4qWK4oqi4oi+4peLPCAgICB78J2VqeKKuMOXy5jwnZWpL/Cdlak8fC3ijJzLnOKGleKJoPCdlal9CiJOb3cgZG8gYSByZWN1cnNpdmUgY2FsbCBvbiBlYWNoIHJvdywgYW5kIHJldHVybiB0aGUgbWluaW11bSByZXN1bHQgKyAxIgoiSWYgdGhlIG1hdHJpeCB3YXMgZW1wdHksIHJldHVybiBpdHMgbGVuZ3RoICgwKSIKICAgIyDiiaDijIrCtDEr8J2VisuYCuKfqQoKRiBi) for step-by-step results with comments.
[Answer]
# [Julia 1.0](http://julialang.org/), ~~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!](https://tio.run/##dY7BioMwEIbvPkW8lATHktFasKBv0CcQD4FmYWRMRW3Zt3fTrM3upTMM5P/4JsnwYDL4vW0pN8tjlKxaOTRaHQ4jORo9obzFLOUOL3LIGlQ59a84ZHSx7tYDHzNU29d9FiTIidmaG5Ozi1SJ8GVEI5aJaZWkOuwjs0/D8mpXc5zMvFhp1K8/zeRWdtI7rUiNSvwjW6dh717krdBJALhHTLoSCjh5UPop3rCGGlBD/c4YFQ3VH9w7gOIfgCqeTmFHf5LOn6Twx3hTBZEEpfwB "Julia 1.0 ‚Äì Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~31~~ 25 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
[DO√ü_#¬ºŒµƒÅDŒ¥Œ±‚Äπ√∏y*√∏yƒÄ√è}‚Ç¨`}¬æ
```
-6 bytes and sped up substantially by porting [@ovs' BQN answer](https://codegolf.stackexchange.com/a/242908/52210).
Input as a wrapped list. If this is not allowed, a leading `¬∏` can be added.
[Try it online](https://tio.run/##yy9OTMpM/f8/2sX/8Px45UN7zm090uhybsu5jY8adh7eUakFxEcaDvfXPmpak1B7aB9QZbSRjgEQGoJwbCwA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9WeWiHi72SwqO2SQpK9v@jXfwPz49XPrTn3NYjjS7ntpzb@Khh5@EdlVpAfKThcH/to6Y1CbWH9v3X0Tu09X90tIEOFMbqgNmGYJaxjpGOCZBtDMRGQL6ljqWOoYGOJZBpCJcw0DEF86EQma1jCmeZgFUaYJE3wyIPdgBcv6kOXAQmC6SNdAzQRdFxbCwA).
**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)
```
[Answer]
# 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!](https://tio.run/##dZDBaoQwEIbP61MMXjbBcYm6lirYR@gLWCkjG2lAo2ha3Etf3cagbi/LkGHmm38G8g9389Xr5HUYl6UpWurqG8Gck76zmZO@hb@d0qxhc5l3NDMVEgpe8WAlKqAgyive9CMoJFAapP7u5EhG2m3VAPFFdUM/GqDJeFPh@34pcIsKwjcQngPR1kZemWCMVwsS@@IdZphhJDDb@@iQCEwfcAsH4n8A06O6uh3xTPTyTAQC4cipy0fxGDl9Yr/pOVNWSxrVGjmy915LhOkyDa0y7Pyhz5znJ@9EWEMBHQ3MWnSxM2tf@yl/qEVQu3q9avVWPU3Sutkw4kVRL38)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
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!](https://tio.run/##y0rNyan8/98rvkj75PRHjTuOTgpwe7hjvoPPyemH54U83LHI5////9HGOgY6hiAYCwA "Jelly ‚Äì Try It Online")** Or see the [test-suite](https://tio.run/##y0rNyan8/98rvkj75PRHjTuOTgpwe7hjvoPPyemH54U83LHI5//h9kdNa/7/j4420IHCWC4dMMcQwjTWMdIxAXKMgdgIJGCpY6ljaKBjCWIbwqUMdEwhAlCIwtExhbNMwGoNsCkwQ1cQCwA "Jelly ‚Äì Try It Online").
### 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
```
[Answer]
# [Python](https://www.python.org), 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!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY349JscxJzk1ISFRKtEvMqNRI1E_NSdOtyM_M00jSiy2wSk4o1MnVLQKIKFQpp-UUKmToVCpl5Cq5ApbGaIIESnTKYQGaaQpkml6ttal5pbmpRYkkq1JYnBUWZeSUa2kAjDXSgMFZTkwtV2BBd0FjHSMcEKGwMxEaoUpY6ljqGBjqWqKKGcOUGOqboUlCIQ1jHFM4yAes3wK_UDEMpxK-wkAUA)
Simple depth-first search.
---
## [Whython](https://github.com/pxeger/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!](https://ato.pxeger.com/run?1=m728PKOyJCM_b8GCpaUlaboWN8PTbHMSc5NSEhUSrXIz8zTSNKLLbBKTijUydUs0E_NSFCoU0vKLFDJ1KhQy8xRcNRI1YzVBAiU6ZTCBzDSFMk1tQ3sDLlfb1LzS3NSixJJUqPFPCooy80o0tIHGGuhAYaymJheqsCG6oLGOkY4JUNgYiI1QpSx1LHUMDXQsUUUN4coNdEzRpaAQh7COKZxlAtZvgF-pGYZSiF9hQQoA)
Base-case is `ValueError: min() arg is an empty sequence`, which indicates the array is all `0`s.
[Answer]
# [Perl 5](https://www.perl.org/) `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!](https://tio.run/##fZBPa8JAEMXv@RRTuyUbHGWjRjAhNfeWemlPNoSm3ZWlJqb5Qy3iZ4@TmAb04A4Lj9@892A3k/nWqatCwrMuStd9K/UWfn55olNIPvZQVInl1UUVgzokf5zFyHIMtOUHkRfoNYtH5OTEWGyNxywesjz0uaUVy707CnPyLoVrD8@FGTAKReFScRbhWTd1rk4VCiq418da7XJurGEtsJsQ/EcQEOI/tTtmd2yKE5wRndKdXGwWuEBb4OIC2r1ZoHO16aalk2uKTq9mbVrcdM5vOttn9J0O9qT1TRufdTCATvPxGpmkX2eR1yG28RVvegOmrTPMcp2WavAwmhcAcp/Jz1J@ucAk7Ta7ktSGlE6zijTF3tMB0tb3iS/B3H2b4IL5snqF1ZPpGUejPgE "Perl 5 ‚Äì Try It Online")
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~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!](https://tio.run/##dZDBboMwDIbvfYqeSsKckECZyibobbeddqQ9RDR06SgwQlM27dnHUErpLrVlyf702/rlgzBCZ42qW1JWO9n3edzFCft5Fe07PaoSUUo7ehQ1QgYUjhOz5g85uqBznChXEZIY1ywWZ4yfuMcw7p@zqtRVIWlR7VEjP0@qkcjJtYNpI8XuRRXy7avMEAPn1OYri@tCZBJ5m5S6683W28NgI0fSiAJ1eIg@ZTDmdk6SOZtZwMeRz9IAfFgOIBjKv8IIIuAMouvMJwmD8AbHtMD/ByCcuqXdYfdEj/dE1uN0KYSJWEnwW9WtGt7VE92K7INo9S3j6BJ/ "JavaScript (Node.js) ‚Äì Try It Online")
Using fact that `(Infinity | 0) == 0`
DFS
BFS answer deprecated
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 52 bytes
```
^
!¬∂
\d+
*_-$%"
^/^[0,-]*$/m}+`\d*,?_(_*-),?\d*
$1
!
```
[Try it online!](https://tio.run/##K0otycxLNPyvqqHhnvA/jkvx0DaumBRtLq14XRVVJa44/bhoAx3dWC0V/dxa7YSYFC0d@3iNeC1dTR17IIdLxZBL8f9/Ax0o5AKRhkDaWMdIxwTIMgZiIy5LHUsdQwMdSy5DuKCBjimQB4UIlo4pnGUCVmWAIWuGIQu2Eq7XVAcuAgA "Retina ‚Äì 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, `0`s, 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.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 44 bytes
```
‚äûœÖÔº°‚âî‚Å∞Œ∂Ôº∑‚åäÔº•œÖ‚åàŒ∫¬´‚â¶‚äïŒ∂‚âîœÖŒ∑‚âî‚ü¶‚üßœÖÔº¶Œ∑Ôº¶Ôº•Œ∫Ôº•Œ∫‚àß‚Ä∫‚Üî‚ÅªŒæŒºŒªŒΩ‚äûœÖŒª¬ªÔº©Œ∂
```
[Try it online!](https://tio.run/##TU/LqgIxDF07X5FlChVGUDd3NbgQFwPuh1nUsfe22OlIHyqK317TqnATDsnJ45AMSrhhEialffQKI4edPceAjP1Ujff6z2LN4U7sqrSRgK22eowjtuKcp1txK/TEyOBRzaj@2dvZwclR2iCPb4XZp0Fr6h/teg4x89/JASoGJWb9U9YvobFH3DopgnTYHPxkYpD5lOjxxmFkjIMh2HLF9xNDos9q77QNuBE@4J2@SqnrFvzrK8K6ZEtCTb7o@zS/mBc "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Explanation:
```
‚äûœÖÔº°
```
Start with just the input list.
```
‚âî‚Å∞Œ∂
```
Start with 0 explosions.
```
Ôº∑‚åäÔº•œÖ‚åàŒ∫¬´
```
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!](https://ato.pxeger.com/run?1=TU87CsJAEK3NKVarWdiAgopgFSwkRUCwDCnWuJrFZA37UVE8iY2FovfwFLmNo0Zxhsd833xO9zTjOl3z_Hy-OrvwB9Vj4kwGjpFQlc4CpUMvMEYuFbQZ2WO0zWQuCERSycIVEPHy1R3x3TtcURRy8BqYr3mhSrUohLJi_pnQqAvTf3oJq58J1BzGWnArNAQzs86dFa-FzkDJiKKUkQKxQzicd_QmWioLI24s7PHii5mlpn7oFrf8Td5KqmYcd9hXe4j-2-si2qidJPkQng "Charcoal ‚Äì Attempt This Online") Link is to verbose version of code.
]