Праздное любопытсво
От: _Dinosaur Россия  
Дата: 06.03.03 12:20
Оценка: 26 (3)
задачка

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

Есть у кого-нибудь идеи?


06.03.03 16:37: Перенесено модератором из 'Алгоритмы' в Этюды — ХД
Завидую людям, которые могут себе позволить никуда не спешить.
Re: Праздное любопытсво
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 14:06
Оценка: 15 (2)
Здравствуйте, _Dinosaur, Вы писали:

D>задачка


D>Поигрался и подумал, что, наверняка,

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

D>Есть у кого-нибудь идеи?


Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать
Re[2]: Праздное любопытсво
От: _Dinosaur Россия  
Дата: 06.03.03 14:32
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать


а что из себя представляет волновой алгоритм
Завидую людям, которые могут себе позволить никуда не спешить.
Re[3]: Праздное любопытсво
От: mSerg Украина  
Дата: 06.03.03 14:45
Оценка: 3 (1)
Здравствуйте, _Dinosaur, Вы писали:

D>Здравствуйте, Pushkin, Вы писали:


P>>Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать


D>а что из себя представляет волновой алгоритм


Запроси в Гугле "волновой алгоритм". Первые 15-20 ссылок — то что тебе нужно.

WBR, Serg Matskov.
... << RSDN@Home 1.0 beta 6a >>
WBR, Serg Matskov
Re[3]: Праздное любопытсво
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 14:51
Оценка:
Здравствуйте, _Dinosaur, Вы писали:

D>а что из себя представляет волновой алгоритм


Стыдно, да?
На самом деле шут бы с ним, как он называется, но можно сделать типа заливки области
Автор: Pushkin
Дата: 03.03.03

Просто под "точками" надо понимать позиции а под "границами" — невозможные переходы.
Re[4]: Праздное любопытсво
От: _Dinosaur Россия  
Дата: 06.03.03 15:00
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, _Dinosaur, Вы писали:


D>>а что из себя представляет волновой алгоритм


P>Стыдно, да?

P>На самом деле шут бы с ним, как он называется, но можно сделать типа заливки области
Автор: Pushkin
Дата: 03.03.03

P>Просто под "точками" надо понимать позиции а под "границами" — невозможные переходы.

Стыдно, конечно,
с алгоритмами заливки разбирался еще в школе лет 13 назад,
только вот название "волновой" услышал в первый раз

Большое спасибо!
Завидую людям, которые могут себе позволить никуда не спешить.
Re[4]: Праздное любопытсво
От: _Dinosaur Россия  
Дата: 06.03.03 15:16
Оценка:
Здравствуйте, Pushkin, Вы писали:

Да, кстати, волновой алгоритм не самый
эффективный среди алгоритмов заливки
Завидую людям, которые могут себе позволить никуда не спешить.
Re[5]: Праздное любопытсво
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 15:26
Оценка:
Здравствуйте, _Dinosaur, Вы писали:

D>Да, кстати, волновой алгоритм не самый

D>эффективный среди алгоритмов заливки

Зато волновой
Re[6]: Праздное любопытсво
От: _Dinosaur Россия  
Дата: 06.03.03 15:39
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, _Dinosaur, Вы писали:


D>>Да, кстати, волновой алгоритм не самый

D>>эффективный среди алгоритмов заливки

P>Зато волновой

ага

Блин, засел на 33 уровне, никак не могу пройти
Завидую людям, которые могут себе позволить никуда не спешить.
Re[7]: Праздное любопытсво
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 16:28
Оценка:
Здравствуйте, _Dinosaur, Вы писали:


D>Блин, засел на 33 уровне, никак не могу пройти


Вот уж точно маньяк Я поле 5-го заленился.
Хотя забавная. Дизайн только на любителя.
Re[8]: Праздное любопытсво
От: VVV Россия  
Дата: 06.03.03 17:17
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, _Dinosaur, Вы писали:


P>

D>>Блин, засел на 33 уровне, никак не могу пройти

P>Вот уж точно маньяк Я поле 5-го заленился.

P>Хотя забавная. Дизайн только на любителя.

Вот как она выглядит в "железном виде" http://www.binaryarts.com/OurProducts/BA/01p_rushhour.htm — купил бы ребёнку, да что-то не видел у нас. Дошёл пока до 25-го
Re: Генератор
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 17:42
Оценка:
Здравствуйте, _Dinosaur, Вы писали:

D>Поигрался и подумал, что, наверняка,

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

Имхо существенно более трудная и интересная задача
написать ГЕНЕРАТОР таких позиций.
Случайная может а) не сойтись б) сойтись слишком просто

Научная работа:
найти позицию, которая сойдётся за максимальное число перемещений.
Re: Праздное любопытсво
От: Кодт Россия  
Дата: 06.03.03 23:54
Оценка: 9 (1)
Здравствуйте, _Dinosaur, Вы писали:

D>задачка


YES! Я ее уделал. Там всего 40 уровней. На 41 мне показали белый квадрат.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[9]: А самому сделать?
От: Pushkin Россия www.linkbit.com
Дата: 07.03.03 06:57
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>Вот как она выглядит в "железном виде" http://www.binaryarts.com/OurProducts/BA/01p_rushhour.htm — купил бы ребёнку, да что-то не видел у нас.


Имхо сделать можно.
И будет даже лучше, чем машинки.
Н так наглядно, но можно играть в метро.

На тонкой но хорошей фанере рисуется сетка 6х6.
Вырезается из другого куска 36 квадратов чуть меньше, чем клетка, и со скруглёнными углами.
Из третьего куска вырезается ещё 36 квадратов совсем маленьких.
Клеим самые маленькие на клетки доски, а на них побольше. Получили ПОЛЕ.
Выглядит как бумага в клетку, но вместо линий щели.
Всё жёстко, один неразборный кусок дерева, но внутри хитрой формы.

Теперь машинки. Из той же фанеры прямоугольник — это верх, его можно лаком покрыть.
Прямоугольник поменьше это низ — он внутри поля ездит.
Между ними — очень узкий прямоугольний (типа карандаша) — перемычка. Всё склеивается.

В итоге машинки в щели вставляются через края доски, края закрываются заглушками,
и дальше машинки уже могут ходить только вдоль себя. Снял заглушки — сменил позицию.
Re[2]: Праздное любопытсво
От: orangy Россия
Дата: 07.03.03 07:11
Оценка:
Здравствуйте, Кодт, Вы писали:

D>>задачка


К>YES! Я ее уделал. Там всего 40 уровней. На 41 мне показали белый квадрат.

Да, довольно просто всё. Некоторые, конечно, заставляли задуматься, но в среднем не больше минуты на уровень получилось... Однако на 40овой я попух Сходу не получилось. Через перерыв попробую снова
А вот и баг, кстати:
http://www.tacklesoft.com/bug.gif
В правом нижнем углу фигурки пересекаются
... << RSDN@Home 1.0 beta 6a | Сейчас пятница, 13:03, слушаю 02 — The Four Horsemen >>
"Develop with pleasure!"
Re[2]: Праздное любопытсво
От: orangy Россия
Дата: 07.03.03 09:53
Оценка:
Здравствуйте, Кодт, Вы писали:

D>>задачка

К>YES! Я ее уделал. Там всего 40 уровней. На 41 мне показали белый квадрат.
Ну вот и мне показали Ура.
... << RSDN@Home 1.0 beta 6a | Сейчас пятница, 15:03, слушаю 02 — The Four Horsemen >>
"Develop with pleasure!"
Re[10]: А самому сделать?
От: Pushkin Россия www.linkbit.com
Дата: 07.03.03 11:25
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Имхо сделать можно.


[skip]

Во нагородил-то!
Можно проще в сто раз.
Машинки снизу имеют шип вдоль длины.
А в поле канавки сеткой.
Факт сделаю
Re[7]: Праздное любопытсво
От: _Dinosaur Россия  
Дата: 07.03.03 11:53
Оценка:
D>Блин, засел на 33 уровне, никак не могу пройти

YES!!!!
БЕЛЫЙ КВАДРАТ!
Завидую людям, которые могут себе позволить никуда не спешить.
Re: Код авторешалки
От: Pushkin Россия www.linkbit.com
Дата: 24.03.03 08:38
Оценка: 102 (6)
Здравствуйте, _Dinosaur, Вы писали:

D>задачка


D>Поигрался и подумал, что, наверняка,

D>можно придумать алгоритм нахождения
D>последовательности перемещений блоков,
D>приводящий к решению задачи.
D>Есть у кого-нибудь идеи?

Прошу прощения, что поднимаю сильно утонувшую тему...
Но что-то захотелось мне таки сделать то, о чём писал автор топика.

Всё оказалось совсем не сложным. Я даже не стал пытаться ничего оптимизировать. Вот так например моя радость меньше чем за секунду нашла гарантированно кратчайший путь на восьмом уровене

http://www.rsdn.org/File/13542/Screen.jpg

А вот собственно код (его можно откомпилить). Так как это по сути моё первое поюзание STL (стыдно ужасно ) прошу сильно не пинать, но если не лень, указать на очевидные проколы.


// Gridlock.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stack>


//main structure and simple functions /////////////////////////
#define NY 6
#define NX 6
#define EXIT_Y 2
#define EXIT_X (NX-1)
#define EXIT_DIR 0 //0 means that exit is in hor direction (1 - ver directio)

const char space=' ';
const std::string cars[]= {"-=", "|#"};

struct grid
{
    char board[NY][NX];

    grid()
        {memset(board,0,sizeof(board));}
    bool operator<(const grid& g) const
        {return memcmp(board,g.board,sizeof(board))<0;}
    bool operator==(const grid& g) const
        {return memcmp(board,g.board,sizeof(board))==0;}
    grid& operator=(const grid& g) 
        {memcpy(board,g.board,sizeof(board)); return *this;}
};

std::istream& operator>>(std::istream& in,grid& g)
{
    for(int y=0;y<NY;y++)
    {
        char is[80];in.getline(is,80);
        memset(g.board[y],' ',NX);
        memcpy(g.board[y],is,strlen(is));
    }

    return in;
}

#define end_of_out grid()
std::ostream& operator<<(std::ostream& out,const grid& g)
{
    static std::string os[NY];

    if(    os[0].length()+NX+3>80 || //not enough space in line
        g==end_of_out)    
    {
        for(int y=0;y<NY;y++)
            out<<os[y]<<"\n",os[y]="";
        out<<"\n\n";

        if(g==end_of_out)
            return out;
    }

    for(int y=0;y<NY;y++)
        os[y].append(g.board[y],NX), os[y]+="   ";
    
    return out;
}

// main function //////////////////////////////////////////////////////
bool find_path(const grid& start,std::stack<grid>& theStack)
{
    std::map<grid, grid> theMap;
    theMap[start]=start;//fill index with something

    std::queue<grid> theQueue;
    for(theQueue.push(start);!theQueue.empty();theQueue.pop())
    {
        grid& g=theQueue.front();

        for(int y=0;y<NY;y++)    //scan every square
        for(int x=0;x<NX;x++)    //in rectangle
        if(g.board[y][x]==space) //can move car to here
        for(int dir=0;dir<4;dir++)//find car to move - left-up-right-down
        {
            grid gg=g; //try to move car and change position
            
            char cur=space;
            int x1=x,y1=y,x2=x,y2=y,n;
            while(1)
            {
                dir==0? x2--:dir==1? y2--:dir==2? x2++:y2++;                
                if(x2<0 || y2<0 || x2>=NX || y2>=NY)
                    break;
                
                if(cur==space)
                {
                    if(gg.board[y2][x2]==space)
                        continue;
                    
                    cur=gg.board[y2][x2];                    
                    
                    n=cars[dir%2].find(cur);
                    if(n==-1) 
                        break;
                    n+=2; //n=2 or n=3 - a length of the car
                }

                if(gg.board[y2][x2]!=cur || n--==0) //end of car
                    break;

                gg.board[y1][x1]=cur;
                gg.board[y2][x2]=space;
                
                dir==0? x1--:dir==1? y1--:dir==2? x1++:y1++;                
            }

            if(!(gg==g) && theMap.find(gg)==theMap.end()) //new position
            {
                theMap[gg]=g;        //we come to gg from g
                theQueue.push(gg);    //now where can we go from gg?

                if(dir%2==EXIT_DIR && y==EXIT_Y && x==EXIT_X) //we find path!
                {
                    while(1)
                    {
                        theStack.push(gg);
                        if(gg==start)
                            return true;
                        gg=theMap[gg];
                    }
                }
            }
        }
    }

    return false;
}


main()
{
    std::cout<<"Enter a grid ("<<NY<<" lines)x("<<NX<<" columns).\n"<<
        "Use simbol '-' to construct 2-square-horizontal-cars\n"
        "Use simbol '=' to construct 3-square-horizontal-cars\n"
        "Use simbol '|' to construct 2-square-vertical-cars\n"
        "Use simbol '#' to construct 3-square-vertical-cars\n"
        "Empty space means empty space.\n"
        "Any other simbols means 'stones'.\n\n";

    while(1)
    {    
        grid g;
        std::cin>>g;
        std::cout<<"\n\n";

        std::stack<grid> path;
        if(find_path(g,path))
        {
            for(;!path.empty();path.pop())
                std::cout<<path.top();
            std::cout<<end_of_out;
        }
        else
        {
            std::cout<<"Fails to find path\n\n";
        }

        std::cout<<"Enter a grid\n\n";
    }
    return 0;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.