Как решить задачку про скопление воды в ландшафте?

#javascript #алгоритм

Дан массив чисел:

1 2 3 4 6 3 2 4 7 3 4 6 1 2 1

Каждое число в этом массиве обозначает высоту. Совокупность высот образует двумерный
ландшафт.



Представим, что идёт дождь и в ямках этого ландшафта скапливается вода. Нужно посчитать
сколько ячеек заполняет вода.


Идеальное решение этой задачи предполагает проход по массиву один раз.

Реализовать на js с вводом массива чисел и схематической визуализации ландшафта,
а также выводом результата.

Вывод графика сделал через chart.js http://prntscr.com/mthgtk

Вот решение такой 

HTML




    
    
    
    
    



    


    




JS

window.onload = () => {
    const app = document.getElementById('app');
    const coors = [1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1];

    const highest = coors.map(v => v).sort().reverse()[0];

    for (const el of coors) {
        let col = createColumn();

        for (let i = 0; i < el; i++) {
            const cube = createCube();
            cube.innerHTML = i + 1;

            col.appendChild(cube);
        }

        for (let j = 0; j < highest - el; j++) {
            const cube = createWater();
            cube.innerHTML = j + 1;
            col.appendChild(cube);
        }

        app.appendChild(col);
    }

    var colums =  Array.from(app.getElementsByClassName('column'));

    var copy = Object.assign({}, colums);

    for (let index = 0; index < colums.length; index++) {

        if (colums[index - 1]) {
            const groundLeft = colums[index - 1].getElementsByClassName('cube').length;
            const groundCenter = colums[index].getElementsByClassName('cube').length;

            if ((groundLeft > groundCenter)) {
                Array
                    .from(colums[index].getElementsByClassName('water'))
                    .forEach(v => colums[index].removeChild(v));
            }
            if ((groundLeft < groundCenter)) {
                Array
                    .from(colums[index - 1].getElementsByClassName('water'))
                    .forEach(v => colums[index - 1].removeChild(v));

            }
        }

    }


    let picks =  colums.map((v, i, a) => {
        const ind = Array.from(v.children).findIndex(z => z.classList.contains('water'));
        if ( ind> -1) {
            return {
                index: i,
                height: v.getElementsByClassName('cube').length
            };
        }
    });


    const picksAll = picks.filter(v => v).map((v, i, array) => {
        return {
            first: array[i],
            next: array[i + 1]
        }
    }).filter(v => v.first && v.next);


    for (const pick of picksAll) {
        const height = pick.first.height > pick.next.height ? pick.next.height :
pick.first.height; 

        const start = pick.first.index + 1;
        for (let i = start; i < pick.next.index; i++) {
            const need = height - copy[i].children.length;


            for (let j = 0; j < need; j++) {
                copy[i].appendChild(createWater());
            }
        }


        Array.from(copy[pick.first.index].children).forEach((v, i, a) => {
            if (v.classList.contains('water')) {
                copy[pick.first.index].removeChild(v);
            }
        });

        Array.from(copy[pick.next.index].children).forEach((v, i, a) => {
            if (v.classList.contains('water')) {
                copy[pick.next.index].removeChild(v);
            }
        });
    }








}

function createColumn() {
    const column  = document.createElement('div');
    column.className = 'column';
    return column;
}

function createCube() {
    const column  = document.createElement('div');
    column.className = 'cube';
    return column;
}

function createWater() {
    const column  = document.createElement('div');
    column.className = 'water';
    return column;
}



    

Ответы

Ответ 1

Решение на С++ (но в целом это не важно, код +/- одинаковый). В качестве демонстрации
только вывожу ответ (заполнить понятно чем). Запускаемый пример https://ideone.com/M9QHpf

int v[] = {1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1};
int count = 0;
for (int l=0,r=sizeof(v)/sizeof(v[0]),lM = v[0], rM = v[sizeof(v)/sizeof(v[0])]; 
                l < r; 
                lM = max(lM,v[l]), rM = max(rM,v[r]))
    if(lM >= rM)
        count += rM - v[r--];
    else
        count += lM - v[l++];
cout << count<
Ответ 2

Привожу пример реализации на JS с комментариями:



let array = prompt('Введите цифры через пробел:', '1 2 3 4 6 3 2 4 7 3 4 6 1 2 1').replace(/
+/g, ' ').trim().split(' '); // вводим массив

const height = Math.max(...array); // минимальная высота сетки
const width = array.length; // минимальная ширина сетки

const air = '–'; // символ воздуха
const land = '='; // символ земли
const water = '≈'; // символ воды

const regExp = `(?${land}(${land}${air}+${land}))`; // регулярное выражение, при
котором вода упирается в землю по бокам

const grid = []; // инициализируем сетку

for (let i = height - 1; i >= 0; i--) { // пробегаем по рядам
  grid[i] = []; // инициализируем ряд

  for (let j = 0; j < width; j++) grid[i][j] = (array[j] > 0) ? land : air; // пробегаем
по колонкам

  let string = grid[i].join(''); // преобразовываем массив в строку без запятых

  let samples = []; // инициализируем вхождения

  string.replace(new RegExp(regExp, 'g'), (m, g) => samples.push(g)); // собираем
совпадения в общий массив (совпадения могут накладываться друг на друга в строке)

  if (samples.length > 0) { // если совпадения по регулярному выражению найдены, то...
    samples.forEach((el) => { // для каждого совпадения...
      string = string.replace(el, el.replace(new RegExp(air, 'g'), water)); // меняем
воду на воздух

      grid[i] = Array.from(string); // сохраняем строку в виде массива
    });
  }

  array = array.map((el) => (el > 0) ? --el : 0); // с каждым рядом уменьшаем на
1 каждое значение в исходном массиве (но не ниже 0)
}


for (const el of grid) document.body.innerHTML += `
${el.join('').replace(new RegExp(land,
'g'), ' ').replace(new RegExp(air, 'g'), '
').replace(new RegExp(water, 'g'), ' ')}
`; //
отрисовываем
p {
  font-family: monospace;
  /* делаем символы в шрифте одинакового размера */
  margin: 0;
  /* убираем отступы */
  white-space: pre;
  /* позволяем пробелам отображаться */
}

.air {
  background-color: lightblue;
  /* цвет воздуха */
}

.land {
  background-color: green;
  /* цвет земли */
}

.water {
  background-color: blue;
  /* цвет воды */
}




P.S. До майнкрафта ещё далеко... :)