Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ Вода между стен

Автор: Iron Bug 7.5.2014, 21:46

Попалась тут забавная задачка
Задача:
http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
Дя тех, кто не очень хорошо понимает по-английски, задача вкратце:
Представлен последовательный набор чисел. Числа указывают "высоту стен", стоящих рядом. Задача: посчитать количество воды, которая может накопиться в таком резервуаре, если пройдёт дождь. Вода через низкие препятствия утекает, как и полагается воде. С краёв она тоже утекает.

Автор: ilyabvt 8.5.2014, 20:13

Решил так:

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

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 8.5.2014, 20:28

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

Автор: ilyabvt 8.5.2014, 20:40

Цитата

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

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

Автор: Алексей1153 12.5.2014, 8:11

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

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

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

    {
        //блоки для каждой координаты 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 15.5.2014, 20:58

Цитата(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 15.5.2014, 22:24

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

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

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

Автор: Влад 16.5.2014, 12:14

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

Автор: Iron Bug 16.5.2014, 17:16

Цитата(Влад @ 16.5.2014, 15:14)

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

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

на самом деле, можно ещё оптимизировать маленько, сразу отрезав "скаты" по краям:

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

#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 18.5.2014, 11:28

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

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

Автор: ilyabvt 18.5.2014, 18:40

Цитата

а для { 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 19.5.2014, 19:31

Цитата(Алексей1153 @ 18.5.2014, 14:28)

Iron Bug, а вчера абсолютно внезапно посетил твой город

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

да уж где тут равнина? почти все улицы вверх или вниз идут

уральские горы, однако. конечно, не Кавказ, но и равниной назвать трудно.

Автор: Iron Bug 19.5.2014, 20:07

Цитата(ilyabvt @ 18.5.2014, 21:40)

Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 }

я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

Автор: Алексей1153 20.5.2014, 6:53

Iron Bug, наверное, в самом городе из-за зданий не видать. Но на окраинах - поле поле поле, а там лес. Некуда бечь

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

Можно оптимизировать - группы не собирать, а завершённые интегрировать сразу

Автор: Алексей1153 20.5.2014, 7:47

ещё оптимизация для муравья - ему не обязательно спускаться на дно ям, он может их переплывать на глубине 1 блок

Автор: ilyabvt 20.5.2014, 18:24

Цитата(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;
}