Вода между стен, забавный тест от программистов твиттера Опции

[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;
}

Сообщение отредактировал ilyabvt - 8.5.2014, 20:39

[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]

просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

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

Раскрывающийся текст

    {
        //блоки для каждой координаты 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 - результат
    }

Сообщение отредактировал Алексей1153 - 18.5.2014, 11:13

[Iron Bug]

а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?

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

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

просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

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

[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;
}

Сообщение отредактировал Iron Bug - 16.5.2014, 18:16

[Влад]

Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 3, -1, -2, 8, -3, -1, 2, 0, -3 } ?

[Iron Bug]

Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 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: ещё маленько добавила проверку - для пущей оптимальности.

Сообщение отредактировал Iron Bug - 19.5.2014, 19:53

[Алексей1153]

я щас глянул - исправил у себя явный глюк - вместо "x2--" было "x2++"

Iron Bug, а вчера абсолютно внезапно посетил твой город Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза