Кајгана CodeOpen. Reopened!
- Креатор на темата back_rest
- Време на започнување
- Статус
Спремајте ги тастатурите.
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
Задача 2: Лавиринт
Коонечно време за втората задача.
Прво бидејќи мислам дека доста се задржав јавно се извинвам за доцнењето. Малку бев зафатен ама еве конечно најдов време да ја поставам.
Малку предговор
Некое време се мислев за тежината на задачата и разгледвав неколку задачи. Меѓутоа судејќи според првата задача некои од задачите кои ги имав во план би ги решиле малкумина. Бидејќи се работи за почеток на CodeOpen се одлучив да поставам прилично лесна задача за да останат скоро сите во конкуренција. Подоцна ќе има и позаебани (ксило спремај се и ти).
И коооонечно задачата: (ЛАВИРИНТ)
- Задачата се состои од тоа дека вие треба да го најдите најкраткиот пат во лавиринтот и да го испечатите. (толку кратко и јасно) (во однос наона најкраткиот да не ме препрашва некој, да можи да има два пата кои даваат решение ама различни по должина, ваша задача е да го најдите најкраткиот.)
Сега да не почните да ми мешате различни формати малку да го стандардизирам проблемот. Лавиринтот ќе биди со ваков облик
#######
# # # #
# # #
# # #
#######
Значи било која матрица со димензии m и n. Елементи на матрицата можат да бидат зид ("#") и слободен простор (" "). За да ве поштедам малку од пишење на тест услови рабовите на матрицата секогаш ќе бидат направени од зид. Исто така ќе се зададени и две точки П и К (демек почеток и крај). Пример за претходната мапа П=(1,1) и К=(1,5) (матриците почнуваат од 0, координатен систем имате нацртан сметам дека е убав). То би биле овие точки:
<---y---->
^ #######
| #П# #К#
x # # #
| # # #
V #######
Вие треба да дефинирате функција со следната декларација.
public static String najdiPat(char[][] mapa, int px, int py, int kx, int ky);
За мапата мислам дека доволно објаснував од каков формат е. Останатите аргументи се доволно дескриптивни шо можи да значат. Резултатот е малку чуден ама ако ми го следите форматот нема да имате мака. (за сите оние шо ги знат структурите во јава извинете ама мора да се рамноправни сите, барем во дефинирањето на интерфејсот)
значи стрингот треба да има формат {(1,1),(2,1),(2,2),(2,3),...,(1,5)}. Мислам дека сфативте (празни места не смеете да клавате). Во тест примерите ќе се потрудам да нема два пата исти по должина.
Тестирање на точност (ги земам вашите алгоритми и ги копи пејстирам во мојот тест проект.) Значи решенијата мораат да се во согласност со интерфејсот кој го наведов инаку ги сметам за неточни. Резултатот кој го враќате ќе го тестирам со equals и исто треба да го запазите форматот.
Оценување: За неточни решенија => 0 Поени. За Најбрзото (по извршвање, не по праќање) точно решение 3 поени. За второто 2 поени. За сите останати точни решенија 1 поен.
Испраќање на решенијата исклучиво по ПП (ПРИВАТНА ПОРАКА ДО МЕНЕ) секој кој ќе објави решение како пост на темава е дисквалификуван од оваа рунда. Ми праќате само дефиниција на функцијата и помошни функции (ако користите такви). НЕСАКАМ тест примери, јас ќе направам неколку различни услови и ќе тестирам.
Крајниот рок за праќање на решенијата е до утревечер (Среда) 11h. (Значи имате цел ден).
Ко ќе го затвориме циклусот ЈАС ќе ги објавам вашите решенија јавно.
Ко ќе ги тестирам ќе ги објавам вашите резултати (Точна/Неточна и време на извршвање за моите тест примери) како и МОИТЕ ТЕСТ ПРИМЕРИ.
Со среќа програмирањето.
Коонечно време за втората задача.
Прво бидејќи мислам дека доста се задржав јавно се извинвам за доцнењето. Малку бев зафатен ама еве конечно најдов време да ја поставам.
Малку предговор
Некое време се мислев за тежината на задачата и разгледвав неколку задачи. Меѓутоа судејќи според првата задача некои од задачите кои ги имав во план би ги решиле малкумина. Бидејќи се работи за почеток на CodeOpen се одлучив да поставам прилично лесна задача за да останат скоро сите во конкуренција. Подоцна ќе има и позаебани (ксило спремај се и ти).И коооонечно задачата: (ЛАВИРИНТ)
- Задачата се состои од тоа дека вие треба да го најдите најкраткиот пат во лавиринтот и да го испечатите. (толку
кратко и јасно) (во однос наона најкраткиот да не ме препрашва некој, да можи да има два пата кои даваат решение ама различни по должина, ваша задача е да го најдите најкраткиот.) Сега да не почните да ми мешате различни формати малку да го стандардизирам проблемот. Лавиринтот ќе биди со ваков облик
#######
# # # #
# # #
# # #
#######
Значи било која матрица со димензии m и n. Елементи на матрицата можат да бидат зид ("#") и слободен простор (" "). За да ве поштедам малку од пишење на тест услови рабовите на матрицата секогаш ќе бидат направени од зид. Исто така ќе се зададени и две точки П и К (демек почеток и крај). Пример за претходната мапа П=(1,1) и К=(1,5) (матриците почнуваат од 0, координатен систем имате нацртан сметам дека е убав). То би биле овие точки:
<---y---->
^ #######
| #П# #К#
x # # #
| # # #
V #######
Вие треба да дефинирате функција со следната декларација.
public static String najdiPat(char[][] mapa, int px, int py, int kx, int ky);
За мапата мислам дека доволно објаснував од каков формат е. Останатите аргументи се доволно дескриптивни шо можи да значат. Резултатот е малку чуден ама ако ми го следите форматот нема да имате мака. (за сите оние шо ги знат структурите во јава извинете ама мора да се рамноправни сите, барем во дефинирањето на интерфејсот)
значи стрингот треба да има формат {(1,1),(2,1),(2,2),(2,3),...,(1,5)}. Мислам дека сфативте (празни места не смеете да клавате). Во тест примерите ќе се потрудам да нема два пата исти по должина.
Тестирање на точност (ги земам вашите алгоритми и ги копи пејстирам во мојот тест проект.) Значи решенијата мораат да се во согласност со интерфејсот кој го наведов инаку ги сметам за неточни. Резултатот кој го враќате ќе го тестирам со equals и исто треба да го запазите форматот.
Оценување: За неточни решенија => 0 Поени. За Најбрзото (по извршвање, не по праќање) точно решение 3 поени. За второто 2 поени. За сите останати точни решенија 1 поен.
Испраќање на решенијата исклучиво по ПП (ПРИВАТНА ПОРАКА ДО МЕНЕ) секој кој ќе објави решение како пост на темава е дисквалификуван од оваа рунда. Ми праќате само дефиниција на функцијата и помошни функции (ако користите такви). НЕСАКАМ тест примери, јас ќе направам неколку различни услови и ќе тестирам.
Крајниот рок за праќање на решенијата е до утревечер (Среда) 11h. (Значи имате цел ден).
Ко ќе го затвориме циклусот ЈАС ќе ги објавам вашите решенија јавно.
Ко ќе ги тестирам ќе ги објавам вашите резултати (Точна/Неточна и време на извршвање за моите тест примери) како и МОИТЕ ТЕСТ ПРИМЕРИ.
Со среќа програмирањето.
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
Морам да си реплицирам оти неможам да го попрам претходниот пост.
СЕга видов дека форумов крати ако има појке празни места. Значи наместо празните места ставив . за да биди појасен примерот. За кодирање ви останва упте да гледате дека има бланко на тие места.
Мислам дека имам решение.
Ајде утре сабајлечки да го истестирам и ти го праќам
Ајде утре сабајлечки да го истестирам и ти го праќам
deXterche
тадаммм
Хм...ок е задачава али дајте нешто поконкретно, не класични алгоритми за пребарување, секој ќе погугла и ќе најде решение (дијкстра, а*...). ОК е се али баш би сакал нешто поинтересно, каде што гугл не ќе може да помогне
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
@hsilomedus: Ne znam so kje vi se test primeri bilo kakva mapa mozi da bidi kako vlez so bilo koi 2 tocki pomegju koi ima nekakov pat. Znaci bilo koj random koj gi zadovolva uslovite koi gi navedov treba da go ispolnuva vasata zadaca. E sega samite natprevaruvaci neka razmislat za mozni problemi vo algoritmot koj go implementiraat.
@ deksterce, ako nesto znajs i mislis deka e ispravno slobodno implementirajgo, i nemoj da pisis nikakvi predlozi na tema dodeka traj nekoja runda. Za vakva rabota bi trebalo da te diskvalifikuvam, ama ajde napisav deka vazi samo za gotovi resenija i zato kje ti prostam. Znaci so mislis napisi i pratimi, ako si vo pravo mozebi kje dobies 3 poeni. Koga ja postaviv zadacata na nekolku navrati napisav koja mi e celta so vakva zadaca i zosto postavvam vakva zadaca. Za sleden krug kje ima i poteska ako se pokazite dobri vo ovaj krug.
@ deksterce, ako nesto znajs i mislis deka e ispravno slobodno implementirajgo, i nemoj da pisis nikakvi predlozi na tema dodeka traj nekoja runda. Za vakva rabota bi trebalo da te diskvalifikuvam, ama ajde napisav deka vazi samo za gotovi resenija i zato kje ti prostam. Znaci so mislis napisi i pratimi, ako si vo pravo mozebi kje dobies 3 poeni. Koga ja postaviv zadacata na nekolku navrati napisav koja mi e celta so vakva zadaca i zosto postavvam vakva zadaca. Za sleden krug kje ima i poteska ako se pokazite dobri vo ovaj krug.
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
CodeOpen - Round 2 Резултати
CodeOpen - Round 2 Closed
Дечки ко ја поставив задачата очекував дека ќе добијам неколку добри решенија и дека ќе имам мака со тестирање кое е најбрзо. Арно ама добив две „решенија“ кои не ме импресионираја воопшто. Се надевам дека за наредните рунди ќе се обидите да се подобрите малку. Поставив прилично лесен проблем како што кажа декстерче шо лесно се наоѓа на нет (не ти требаше дијкстра), ама и таков не го решивте како шо треба.
Ај да не замарам по многу шо направивте направивте па да видат и останатите.
deXterce:
Како шо кажа и самиот во пораката шо ми ја прати не е многу ефикасно решение, ниту пак е точно за секој услов. Знам дека во вистински лавиринт постои само еден пат и дека за таков услов ќе функционира алгоритмов ама кога го дефинирав проблемов оставив можност да можи дасе распоредат било како зидовите шо значи дека можи да има повеќе патишта до крајната точка. За да ти го побијам решението еве ти тест пример на кој не работи:
Влезна матрица
#######
#.....#
#...#.#
#.#...#
#######
Почеток и крај исти. (1,1) и (1,5)
твојот резултат е:
{(1,1),(2,1),(2,2),(2,3),(3,3),(3,4),(3,5),(2,5),(1,5)}
=> Неисправно решение
CodeOpen - Round 2 Closed
Дечки ко ја поставив задачата очекував дека ќе добијам неколку добри решенија и дека ќе имам мака со тестирање кое е најбрзо. Арно ама добив две „решенија“ кои не ме импресионираја воопшто. Се надевам дека за наредните рунди ќе се обидите да се подобрите малку. Поставив прилично лесен проблем како што кажа декстерче шо лесно се наоѓа на нет (не ти требаше дијкстра), ама и таков не го решивте како шо треба.
Ај да не замарам по многу шо направивте направивте па да видат и останатите.
deXterce:
Код:
public class Main {
public static int rez[] = new int[100];
public static int brojac = 0;
public static String niza = "{";
public static String najdiPat(char[][] mapa, int px, int py, int kx, int ky) {
if (px == kx && py == ky) {
for (int r = 0; r < brojac; r = r + 2) {
niza += "(" + rez[r] + "," + rez[r + 1] + ")";
if (r + 2 == brojac) {
niza += "}";
} else {
niza += ",";
}
}
} else {
//dolu
if (mapa[px + 1][py] == ' ') {
px = px + 1;
mapa[px][py] = '?';
rez[brojac] = px;
rez[brojac + 1] = py;
brojac = brojac + 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//desno
if (mapa[px][py + 1] == ' ') {
py = py + 1;
mapa[px][py] = '?';
rez[brojac] = px;
rez[brojac + 1] = py;
brojac = brojac + 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//gore
if (mapa[px - 1][py] == ' ') {
px = px - 1;
mapa[px][py] = '?';
rez[brojac] = px;
rez[brojac + 1] = py;
brojac = brojac + 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//levo
if (mapa[px][py - 1] == ' ') {
py = py - 1;
mapa[px][py] = '?';
rez[brojac] = px;
rez[brojac + 1] = py;
brojac = brojac + 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//levo se vraka
if (mapa[px][py - 1] == '?') {
py = py - 1;
brojac = brojac - 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//desno se vraka
if (mapa[px][py + 1] == '?') {
py = py + 1;
brojac = brojac - 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//dolu se vraka
if (mapa[px + 1][py] == '?') {
px = px + 1;
brojac = brojac - 2;
najdiPat(mapa, px, py, kx, ky);
} else {
//gore se vraka
if (mapa[px - 1][py] == '?') {
px = px - 1;
brojac = brojac - 2;
najdiPat(mapa, px, py, kx, ky);
}
}
}
}
}
}
}
}
}
return niza;
}
public static void main(String[] args) {
char mapa[][] = {{'#', '#', '#', '#', '#', '#', '#'}, {'#', ' ', '#', ' ', '#', ' ', '#'}, {'#', ' ', ' ', ' ', '#', ' ', '#'}, {'#', ' ', '#', ' ', ' ', ' ', '#'}, {'#', '#', '#', '#', '#', '#', '#'}};
int px = 1;
int py = 1;
int kx = 1;
int ky = 5;
rez[brojac] = px;
rez[brojac + 1] = py;
brojac = brojac + 2;
System.out.println(najdiPat(mapa, px, py, kx, ky));
}
}Влезна матрица
#######
#.....#
#...#.#
#.#...#
#######
Почеток и крај исти. (1,1) и (1,5)
твојот резултат е:
{(1,1),(2,1),(2,2),(2,3),(3,3),(3,4),(3,5),(2,5),(1,5)}
=> Неисправно решение
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
CodeOpen - Round 2 Резултати
/* Морам во нов пост, форумов не дозволвал многу знаци во една порака :nesvest:. ЌЕ се жалам кај ацид.*/
Сега назад на работа:
Решението на Димитар:
1. Закасни со решението. простено
2. Користиш c++. простено (напамет го анализирав кодот)
3. Не се придржваш кон поставените барања за влез и излез. ова не ти е простено
4. Како шо кажа и самиот ти вади грешки. (размисли зошто )
5. Зошто го користиш ова: "if( (row>0 && row<red) && (col>0 && col<kolona))" нели реков рабовите ќе бидат зидови. Тој услов го ставив да ве поштедам од вакви тестирања.
_______________________
Резултати:
deXterce: 0
Димитар: 0
Бидејќи никој не ја реши задачата незнам на кој да му го предам мандатот за следна. Еве нека биди декстерче оти имаше нешто подобар обид.
/* Морам во нов пост, форумов не дозволвал многу знаци во една порака :nesvest:. ЌЕ се жалам кај ацид.*/
Сега назад на работа:
Решението на Димитар:
Код:
#include <iostream>
using namespace std;
int broj=0;
const int red=10;
const int kolona=10;
char Lavirint[red][kolona] =
{
{'#','#','#','#','#','#','#','#','#','#'},
{'#',' ',' ',' ',' ',' ','#',' ',' ','#'},
{'#',' ','#','#','#',' ','#',' ','#','#'},
{'#','P',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#',' ','#','#','K','#'},
{'#',' ',' ',' ',' ',' ',' ','#',' ','#'},
{'#',' ','#','#',' ','#','#','#',' ','#'},
{'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
{'#',' ','#',' ',' ',' ','#',' ','#','#'},
{'#','#','#','#','#','#','#','#','#','#'}
};
void cistenje();
void barajLavirint(int, int);
int main()
{
for (int i=0;i<red;i++)
for (int j=0;j<kolona;j++)
if(Lavirint[i][j]=='P')
{
barajLavirint(i,j);
}
cout<<endl;
return 0;
}
void barajLavirint(int row, int col)
{
if( (row>0 && row<red) && (col>0 && col<kolona)) {
if( Lavirint[row][col] == 'K' )
{
cout<<broj<<endl;
}
if((Lavirint[row][col] == ' ')||( Lavirint[row][col] == 'P')){
Lavirint[row][col]='*';
broj++;
barajLavirint(row, col-1);
barajLavirint(row, col+1);
barajLavirint(row+1, col);
barajLavirint(row-1, col);
}
}
}2. Користиш c++. простено (напамет го анализирав кодот)
3. Не се придржваш кон поставените барања за влез и излез. ова не ти е простено
4. Како шо кажа и самиот ти вади грешки. (размисли зошто )
5. Зошто го користиш ова: "if( (row>0 && row<red) && (col>0 && col<kolona))" нели реков рабовите ќе бидат зидови. Тој услов го ставив да ве поштедам од вакви тестирања.
_______________________
Резултати:
deXterce: 0
Димитар: 0
Бидејќи никој не ја реши задачата незнам на кој да му го предам мандатот за следна. Еве нека биди декстерче оти имаше нешто подобар обид.
deXterche
тадаммм
Јас, знаеш дека воопшто не обрнав внимание на најкраткиот пат Како што разгледував алгоритми за пребарување во 2 димензионални полиња за кои имаше и доста добри имплементации ама беа огромни и некако ме мрзеше да ги анализирам до крај се решив за имплементација на "Depth first search" кој е доста прост, правилно решение а и најбрзо ќе даде во овој случај A* кој е малце изменета варијанта на depth first search и го дава најкраткиот пат.
Еве доста добар пример http://www.codeproject.com/KB/recipes/mazesolver.aspx
Ако мене ми паѓа мандатот за наредната рунда ќе оставам 3-4 дена одмор па идеме со нареден проблем
Како што разгледував алгоритми за пребарување во 2 димензионални полиња за кои имаше и доста добри имплементации ама беа огромни и некако ме мрзеше да ги анализирам до крај се решив за имплементација на "Depth first search" кој е доста прост, правилно решение а и најбрзо ќе даде во овој случај A* кој е малце изменета варијанта на depth first search и го дава најкраткиот пат. Еве доста добар пример http://www.codeproject.com/KB/recipes/mazesolver.aspx
Ако мене ми паѓа мандатот за наредната рунда ќе оставам 3-4 дена одмор па идеме со нареден проблем
- Член од
- 22 февруари 2007
- Мислења
- 7.076
- Поени од реакции
- 1.941
Декстерче пребарување во длабочина не е решение за овај проблем. Како шо виде и ти и димитар си имавте мака со ограничвање на поминати полиња и почнавте да додавате непотребен код за да ги ограничите. Проблемот е шо треба постепено да ги пребарваш сите длабочини (значи да пребарваш по ширина значи breadth-first search). Прво откриваш до кои полиња стигнуваш за 1 чекор, па до кои за два ... и така натаму се дури не стигнип до решението. Еве истото ги имаш и во текстот од кодепројецт шо ми го прати
Следниот пат разгледај ги малку овие решенија.
Следниот пат разгледај ги малку овие решенија.
back_rest
ex mod coder
- Член од
- 19 јули 2006
- Мислења
- 1.590
- Поени од реакции
- 107
Две оптимални решенија постојат за овој проблем. Или изменет Dijkstra со меморизација на патот за секоја состојба, или класичен flood-fill (што може да го порамните со bread-first search) исто така со меморизација на патот за секоја состојба. Бидејќи станува збор за 2Д поле односно граф со степен 4, и двете решенија би дале слично на перформанси решение. Сепак, поради големата меморизација, за поголеми полиња перформансите би биле crappy!
Е сега, напомена за декстерче (пошо нели има мандат за наредна задача) и за наредните кои ќе постираат задача, придржувајте се на обликот кој го зададов во првиот пост. Значи со детален опис и неколку тест примери. Исто така пробајте со тест примерите да зафатите што е можно поголем процент од функциите на задачата и на тој начин истата да биде што е можно подобро истестирана. Ју гет д поинт.
И да, побрзо со ова задачите, нека има барем на 2 дена по една задача.
Е сега, напомена за декстерче (пошо нели има мандат за наредна задача) и за наредните кои ќе постираат задача, придржувајте се на обликот кој го зададов во првиот пост. Значи со детален опис и неколку тест примери. Исто така пробајте со тест примерите да зафатите што е можно поголем процент од функциите на задачата и на тој начин истата да биде што е можно подобро истестирана. Ју гет д поинт.
И да, побрзо со ова задачите, нека има барем на 2 дена по една задача.
- Статус