DEV Community

Cover image for Daily Challenge #274 - Aerial Firefighting
dev.to staff
dev.to staff

Posted on

Daily Challenge #274 - Aerial Firefighting

You are an aerial firefighter (someone who drops water on fires from above in order to extinguish them) and your goal is to work out the minimum amount of bombs you need to drop in order to fully extinguish the fire (the fire department has budgeting concerns and you can't just be dropping tons of bombs, they need that money for the annual Christmas party).

The given string is a 2D plane of random length consisting of two characters:
x representing fire
Y representing buildings

Water that you drop cannot go through buildings and therefore individual sections of fire must be addressed separately. Your water bombs can only extinguish contiguous sections of fire up to a width (parameter w). You must return the minimum number of waterbombs it would take to extinguish the fire in the string.

Note: all inputs will be valid.

Examples
"xxYxx" and w = 3 --> 2 waterbombs needed
"xxYxx" and w = 1 --> 4
"xxxxYxYx" and w = 5 --> 3
"xxxxxYxYx" and w = 2 --> 5

Tests
waterbombs("xxxxYxYx", 4)
waterbombs("xxYxx", 3)

Good luck!


This challenge comes from coderors on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (20)

Collapse
 
rafaacioly profile image
Rafael Acioly

Python solution 🐍

import re

def bombs(situation: str, fire_width: int) -> int:
  regex = "x{1,%d}" % fire_width
  matches = re.findall(re.compile(regex), situation)

  return len(matches)
Collapse
 
tbroyer profile image
Thomas Broyer

Regexp was my first thought too

Collapse
 
londyf profile image
Londy • Edited

Javascript:

const waterBombs = (fire, width) => fire
    .split("Y")
    .reduce((a, b) => a + Math.ceil(b.length / width), 0);
Collapse
 
peter279k profile image
peter279k • Edited

Here is the simple solution with Python and it uses math.ceil, a for loop and a string splitting:

import math
def waterbombs(fire, w):
    fire_arr = fire.split('Y')
    counter = 0;

    for fire_x in fire_arr:
        counter += math.ceil(len(fire_x) / w)

    return counter
Collapse
 
vinaypai profile image
Vinay Pai

You can use the built-in sum function to simplify your solution.

import math
def waterbombs(fire, w):
  return sum(math.ceil(len(fr) / w) for fr in fire.split('Y'))
Collapse
 
peter279k profile image
peter279k

Thanks for your simplify code snippets.

But I want to make my code snippets readable :).

Collapse
 
saviourcode profile image
Sourabh Choure

In C with O(n):

#include <stdio.h>

int waterbombs(char *s,int w)
{
    int cntfire = 0;
    int firebombs = 0;
    do{
        if(*(s)=='x'){
            cntfire++;
        }
        else{
            firebombs += cntfire/w;
            if(cntfire%w!=0){
                firebombs++;
            }
            cntfire = 0;
        }
    }while(*(s++)!='\0');
    return firebombs;
}

int main(void)
{
    printf("Test Case 1 = %d\n",waterbombs("xxxxYxYx",4));
    printf("Test Case 2 = %d\n",waterbombs("xxYxx", 3));
    return 0;
}
Collapse
 
jrop profile image
Jonathan Apodaca

Rust:

fn water_bombs(spec: &str, width: usize) -> usize {
    let result = spec.split("Y") // split into sections
        // for each section, see how many bombs it takes to handle:
        .map(|xs| ((xs.len() as f64) / (width as f64)).ceil().trunc() as usize)
        // sum:
        .fold(0, |acc, n| acc + n);
    result
}
fn main() {
   assert_eq!(water_bombs("xxYxx", 2), 2);
   assert_eq!(water_bombs("xxYxx", 1), 4);
   assert_eq!(water_bombs("xxxxYxYx", 5), 3);
   assert_eq!(water_bombs("xxxxYxYx", 2), 4);
   assert_eq!(water_bombs("xxxxxYxYx", 2), 5);
   assert_eq!(water_bombs("xxxxYxYx", 4), 3);
   assert_eq!(water_bombs("xxYxx", 3), 2);
}
Collapse
 
bherrero profile image
Borja Herrero • Edited

JS solution with just a regular expression:

function waterbomb(plane, width) {
    const pattern = `x{1,${width}}Y*`;
    const regex = new RegExp(pattern, 'g');

    return plane.match(regex).length;
}
Collapse
 
amarjeet94 profile image
amarjeet singh

It seems to be a simple yet interesting also..
The idea to find the minimum number of waterbombs can be found by :
say Test: waterbombs("xxxxYxYx", 4)
step1 : split first param by 'Y'
step2: set second param as width
step3: find the mod of length of substring by width value
step4: sum up the mod value that is your minimum number of waterbombs

Collapse
 
darthbob88 profile image
Raymond Price • Edited

Step 3 is not quite correct, I think; you'd need to get the ceiling of the width of the string divided by the width of the bomb. ("xxxxx", 2) is 3, since two bombs will take out 4 squares of fire and leave 1 more to mop up.

E: My JS solution

var waterbombs = (fireString, bombWidth) => {
    const fires = fireString.split("Y");
    let bombsNeeded = 0;
    for (let fire in fires) {
        bombsNeeded += Math.ceil(fire.length / bombWidth);
    }
    return bombsNeeded;
}
Collapse
 
amarjeet94 profile image
amarjeet singh

yes, you are right brother

Collapse
 
rafaacioly profile image
Rafael Acioly

Talk is cheap, show me the code ;)

Collapse
 
rachit995_97 profile image
Rachit Sharma

JS Solution:

function waterbombs(data, width){
    return data
    .split('Y')
    .map((building)=> building.match(new RegExp(`.{1,${width}}`,"g")))
    .reduce((acc, val) => acc.concat(val), [])
    .length
}
Collapse
 
imjoseangel profile image
Jose Angel Munoz

Quite more complex Python, although I love the regex option

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
import re
import unittest


class TestWaterbombsFunction(unittest.TestCase):
    @staticmethod
    def test_waterbombs():
        assert waterbombs('xxxxYxYx', 4) == 3
        assert waterbombs('xxYxx', 3) == 2


def waterbombs(pattern: str, water: int) -> int:
    count = 0
    fire = (pattern.split('Y'))
    for item in fire:
        if item:
            try:
                if (len(item) / water).is_integer():
                    count += int(len(item) / water)
                else:
                    count += int(len(item) / water) + 1
            except ValueError as value_error:
                print("ValueError: {0}".format(value_error))
            except TypeError as value_error:
                print("TypeError: {0}".format(value_error))
    return count


def main():
    pass


if __name__ == '__main__':
    main()
Collapse
 
aminnairi profile image
Amin • Edited

C

Assuming the input for the fire area is always correct.

#include <math.h>

int getWaterBombsNeeded(const char* area, unsigned int tank) {
    const char BUILDING = 'Y';
    unsigned int fire = 0;
    double bombs = 0;

    for (const char* current = area; *current; current++) {
        if (BUILDING == *current) {
            bombs += ceil(fire / (float) tank);
            fire = 0;
        } else {
            fire++;
        }
    }

    if (fire) {
        bombs += ceil(fire / (float) tank);
    }

    return bombs;
}

Test

Collapse
 
harrisgeo88 profile image
Harris Geo 👨🏻‍💻

Javascript solution

const waterbombs = (town, w) => {
   return town.split('Y')
     .map(t => Math.ceil(t.length / w))
     .reduce((a,b) => a + b)
}
Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️
local function waterbombs(fire, load)
    local bombs = 0
    for strip in fire:gmatch("x+") do
        bombs = bombs + math.ceil(#strip / load)
    end
    return bombs
end
Collapse
 
qm3ster profile image
Mihail Malo

2D plane
xxYxx

this is a 1D plane

Collapse
 
bb4l profile image
bb4L

Nim:

import sequtils, math, strutils

proc waterbombs*(ground: string, bombLength: int): int =
    return ground.split("Y").foldl(a+ceil(len(b)/bombLength).toInt(), 0)