Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Вода между стен
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
Iron Bug
Попалась тут забавная задачка :)
Задача:
http://qandwhat.apps.runkite.com/i-failed-...tter-interview/
Дя тех, кто не очень хорошо понимает по-английски, задача вкратце:
Представлен последовательный набор чисел. Числа указывают "высоту стен", стоящих рядом. Задача: посчитать количество воды, которая может накопиться в таком резервуаре, если пройдёт дождь. Вода через низкие препятствия утекает, как и полагается воде. С краёв она тоже утекает.
ilyabvt
Решил так:
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }
//    if (left == right) { return 0; }

    level = std::min(x[left], x[right]);

    for (int i=left; i<right; ++i) {
        if (level-x[i] > 0) { result += level-x[i]; }
    }

    return result;
}
Iron Bug
а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?
ilyabvt
Цитата
а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?

Возвращает 10. Т.е. правильно обрабатывает.
P.S. Убрал в коде избыточную проверку.
Алексей1153
просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

(не тестировал, мне лень :D , тут только алгоритм)

Раскрывающийся текст
    {
        //блоки для каждой координаты X
        std::vector<int> wall;
        int volume=0;

        //тестовые значения
        wall.push_back(3);
        wall.push_back(1);
        wall.push_back(2);
        wall.push_back(5);

        if(wall.size())
        {
            //найдём максимальный и минимальный уровень
            int min_level=0;
            int max_level=0;
            {
                std::vector<int> mm=wall;
                std::sort(mm.begin(),mm.end());
                min_level=*mm.begin();
                max_level=*mm.rbegin();
            }

            if(min_level>=1 && max_level>min_level)
            {
                //сканируем уровни, начиная снизу
                for(int level=min_level;level<=max_level;level++)
                {
                    //на текущем слева направо:
                    
                    //ищем первую стенку
                    int x1=0;
                    for(; x1!=wall.size(); x1++)
                    {
                        if(wall[x1]>=level)break;
                    }

                    //ищем последнюю стенку
                    int x2=wall.size()-1;
                    for(; x2>x1+1; x2--)
                    {
                        if(wall[x2]>=level)break;
                    }

                    //между стенами должен быть хотя бы 1 блок
                    if(x1+1<x2)
                    {
                        //сканируем пространство между x1 и x2 и считаем пустоту
                        for(int x=x1+1; x<x2-1; x++)
                        {
                            if(wall[x]<level)volume++;
                        }
                    }
                }
            }
        }

        //volume - результат
    }
Iron Bug
Цитата(ilyabvt @ 8.5.2014, 23:40) *
Цитата
а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?

Возвращает 10. Т.е. правильно обрабатывает.
P.S. Убрал в коде избыточную проверку.

а для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправильно считает.


Цитата(Алексей1153 @ 12.5.2014, 11:11) *
просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

я также решила: только я на каждом уровне строила интегральные столбики с "весами", схлапывая уже "заполненные" уровни.
Iron Bug
у меня идея в том, чтобы "срезать" нижний слой и схлапывать одинаковые столбики (для простоты суммирования). при схлапывании увеличивается "вес" столбика.
написала программку. может, не совсем оптимально, но идея понятна.
на каждом шаге пишет полученную последовательность (чисто для наглядности)

Раскрывающийся текст
#include <iostream>
#include <vector>

using namespace std;

typedef struct _data
{
    int level;
    int weight;
    _data(int h,int w) : level(h), weight(w) {}
}
data;

int calcVolume(int count, int *x)
{

    if (count<3) return 0;

    vector<data> v;
    int x_min = x[0];
    int current_level = x[0];
    int current_weight = 1;

    for(int i=1;i<count;i++)
    {
        if(x[i]<x_min) x_min = x[i];
        if(x[i]!=current_level)
        {
            v.push_back(data(current_level,current_weight));
            current_level = x[i];
            current_weight = 1;
        }
        else
        {
            current_weight++;
        }
     }
     v.push_back(data(current_level,current_weight));

    size_t size = v.size();
    for(size_t i=0; i<size; i++)
    {
        v[i].level-=x_min;
    }

    int volume = 0;
    vector<data> v_new;

    while(size>2)
    {
        for(size_t i=0; i<size; i++)
        {
            cout << v[i].level << "(" << v[i].weight << "), ";
        }
        cout << endl;

        current_level = v[0].level;
        current_weight = v[0].weight;
        for(size_t i=1; i<size; i++)
        {
            if(i != size-1)
            {
                if((v[i].level==0)&&(v[i-1].level>0)&&(v[i+1].level>0))
                {
                    volume += v[i].weight;
                    v[i].level += 1;
                }
            }
            if(v[i].level != current_level)
            {
                v_new.push_back(data(current_level-1,current_weight));
                current_level = v[i].level;
                current_weight = v[i].weight;
            }
            else
            {
                current_weight += v[i].weight;
            }
        }
        if(current_level>0)
        {
              v_new.push_back(data(current_level-1,current_weight));
        }
        v = v_new;
        size = v.size();
        v_new.clear();
    }
    return volume;
}

int main()
{
    int x[] = { 3, 1, 2, 1, 4, 1, 2, 1, 4 };
    cout << "Volume is " << calcVolume(sizeof(x)/sizeof(int),x) << endl;
    return 0;
}
Влад
Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 3, -1, -2, 8, -3, -1, 2, 0, -3 } ?
Iron Bug
Цитата(Влад @ 16.5.2014, 15:14) *
Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 3, -1, -2, 8, -3, -1, 2, 0, -3 } ?

этот случай сводится к положительному добавлением модуля минимального значения ко всем элементам. для алгоритма это не существенно.

поправила мелкий косячок в своём коде. а так, он и с отрицательными значениями работает: потому что всё равно сначала "выравнивает" минимальные значения на ноль.

на самом деле, можно ещё оптимизировать маленько, сразу отрезав "скаты" по краям:
Раскрывающийся текст
#include <iostream>
#include <vector>

using namespace std;

typedef struct _data
{
    int level;
    int weight;
    _data(int h,int w) : level(h), weight(w) {}
}
data;

int calcVolume(int count, int *x)
{

    if (count<3) return 0;

    int start = count-1;
    for(int i=0;i<count-1; i++)
    {
        if(x[i]>x[i+1])
        {
            start = i;
            break;
        }
    }
    int stop = 0;
    for(int i=count-1;i>0; i--)
    {
        if(x[i]>x[i-1])
        {
            stop = i;
            break;
        }
    }

    vector<data> v;
    int x_min = x[start];
    int current_level = x[start];
    int current_weight = 1;

    for(int i=start;i<=stop;i++)
    {
        if(x[i]<x_min) x_min = x[i];
        if(x[i]!=current_level)
        {
            v.push_back(data(current_level,current_weight));
            current_level = x[i];
            current_weight = 1;
        }
        else
        {
            current_weight++;
        }
     }
     v.push_back(data(current_level,current_weight));

    size_t size = v.size();
    for(size_t i=0; i<size; i++)
    {
        v[i].level-=x_min;
    }

    int volume = 0;
    vector<data> v_new;

    while(size>2)
    {
        for(size_t i=0; i<size; i++)
        {
            cout << v[i].level << "(" << v[i].weight << "), ";
        }
        cout << endl;

        current_level = v[0].level;
        current_weight = v[0].weight;
        for(size_t i=1; i<size; i++)
        {
            if(i != size-1)
            {
                if((v[i].level==0)&&(v[i-1].level>0)&&(v[i+1].level>0))
                {
                    volume += v[i].weight;
                    v[i].level += 1;
                }
            }
            if(v[i].level != current_level)
            {
                if(current_level>0)
                {
                    v_new.push_back(data(current_level-1,current_weight));
                }
                current_level = v[i].level;
                current_weight = v[i].weight;
            }
            else
            {
                current_weight += v[i].weight;
            }
        }
        if(current_level>0)
        {
            v_new.push_back(data(current_level-1,current_weight));
        }
        v = v_new;
        size = v.size();
        v_new.clear();
    }
    return volume;
}

int main()
{
    int x[] = {   3, -1, -2, 8, -3, -1, 2, 0, -3  };
    cout << "Volume is " << calcVolume(sizeof(x)/sizeof(int),x) << endl;
    return 0;
}



update: ещё маленько добавила проверку - для пущей оптимальности.
Алексей1153
я щас глянул - исправил у себя явный глюк - вместо "x2--" было "x2++"

Iron Bug, а вчера абсолютно внезапно посетил твой город :D Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза
ilyabvt
Цитата
а для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправильно считает.

Обновил код, теперь правильно:
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle<right;  ++middle) {
            if (x[middle] >= x[left]) { break; }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}
Iron Bug
Цитата(Алексей1153 @ 18.5.2014, 14:28) *
Iron Bug, а вчера абсолютно внезапно посетил твой город :D Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза

да уж где тут равнина? почти все улицы вверх или вниз идут :) уральские горы, однако. конечно, не Кавказ, но и равниной назвать трудно.
Iron Bug
Цитата(ilyabvt @ 18.5.2014, 21:40) *
Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 } :)
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.
Алексей1153
Iron Bug, наверное, в самом городе из-за зданий не видать. Но на окраинах - поле поле поле, а там лес. Некуда бечь :D



я ещё алгоритм придумал - пусть некий муравей ползёт через всю стену слева направо. Он запоминает координату (Di), где он начал спускаться вниз. Также он связывает с каждой Di координату Ui, где он шёл вверх и уровень был равен равен или меньше Di. После прохождения всей стены берём все группы D-U и интегрируем пустое место под ними

Можно оптимизировать - группы не собирать, а завершённые интегрировать сразу
Алексей1153
ещё оптимизация для муравья - ему не обязательно спускаться на дно ям, он может их переплывать на глубине 1 блок
ilyabvt
Цитата(Iron Bug @ 19.5.2014, 23:07) *
Цитата(ilyabvt @ 18.5.2014, 21:40) *
Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 } :)
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

Обновил еще :)
На этот раз тоже проверял на случайных последовательностях.
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle < right;  ++middle) {
            if (x[middle] > x[middle-1]  &&  x[middle+1] <= x[middle]) {
                bool needbreakCycle = true;
                for (int i=middle+1; i<=right; ++i) {
                    if (x[i] > x[middle]  &&  x[middle] <= x[left]) {
                        middle = i-1;       //-1 т.к. на каждой итерации ++middle
                        needbreakCycle = false;
                        break;
                    }
                }
                if (needbreakCycle) { break; }
            }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}


Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2018 IPS, Inc.