zadanie z grupowaniem pionków Opcje

[marcus753]

Witam was od tygodnia męczę z piekielnie trudnym zadaniem może ktoś z was mi trochę pomoże...

Zadanie ma taką treść

Jasiu zdenerwowany że przegrał w warcaby wziął n pionków i rzucił nimi na planszę tak że każdy pionek upadł tylko na jedno pole. Jasiu chce teraz pogrupować pionki które leżą obok siebie (czyli ustalić że pionki ułożyły się np. w 5 grup 1 grupa składa się z 3 pionków druga z 2 itd...)

2 pionki zalicza się do tej samej grupy jeśli lezą obok siebie.

mam teraz taki plik wejściowy z współrzędnymi każdego pionka
rząd/kolumna
1:1
2:2
3:3
4:4

czyli pionki ułożyły się na ukos
wynikiem takiego rozłożenia pionków powinno być 1:4 (grupa 1 , składa się z 4 pionków)

gdyby było np
1:1
1:2
2:2
5:5
5:6
wynikiem takiego rozłożenia pionków powinno być 1:3, 2:2 (grupa 1 , składa się z 3 pionków ,grupa 2 , składa się z 2 pionków)

napisałem 2 skyrpty razem z jakies 200 linijek oczywiście nie zadziałały poprawnie dochodzę do momentu w którym zaczynam pisać na nowo ale sam już nie wiem jak to wszystko zrobić ;(

bedę wdzięczny za każdą pomoc sugestie itp. (skrypt nie jest na żaden konkurs gdzie wymagana jest praca indywidualna itp) żeby nie było że wyręczam się tym forum jak chcecie moge zamieścić moje dotychczasowe skrypty ale ja sam już zaczynam się w nich gubić więc nie wiem czy wam by coś dały

POZDRAWIAM

pomysł miałem taki żeby porównać każdy rekord do rekordów leżących obok niego w odległości 1rzedu czyli np. dla danych
1:1
1:2
2:2
5:5
5:6

porównuje 1:1 do 1:2 jeśli leżą obok siebie do nowego pliku zapisuje 1:1:1,1:2:1 (ostatnia cyfra to grupa) następnie porównuje 1:1 do 2:2 w efekcie czego do poprzedniego pliku dopisuje 1:1:1 2:2:1
nastepnie 1:1 do 5:5 jako że 5:5 leży poza najbliższym żędem pobieram kolejną zmienną do porównania czyli 1:2 porownuje do 2:2 i tu już zaczynają się schody teraz przydało by się żeby sprawdzał czy 1:2 ma już jakąś grupe a to oznacza że najpierw musiał bym otworzyć plik aby pobrać dane i na otwartym pliku otwierać go jeszcze raz aby aktualizować nie mam pojecia jak to zrobić albo ominąć...

drugi skrypt miał ignorować takie same rekordy które występują więcej niż jeden raz i zliczać ile rekordów ma tą samą grupe

[emtiej]

na twoim przykładzie:
1:1
1:2
2:2
5:5
5:6

1:1 = 1+1 = 2
1:2 = 1+2 = 3
2:2 = 2+2 = 4
5:5 = 5+5 = 10
5:6 = 5+6 = 11

Załaduj wszystko do tablicy dla ułatwienia, pomyśl i zrobisz ja ci dałem pomysł, to twoja praca domowa więc się męcz, ale powiem że zadanie nie jest aż tak trudne, wystarczy posiedzieć z 10 minut i ruszyć mózgiem


ps. autor tego zadania chyba nigdy nie grał w warcaby, bo grając w warcaby pionki się stawia na polach tego samego koloru chyba ^^

Ten post edytował emtiej 20.01.2010, 00:02:36

[ADeM]

~Emtiej: Twoje rozumowanie sprawdza się dla współrzędnych (1,5);(5,1)?
pozdrawiam
Adem

Ps. Autor pewnie grał w warcaby, ale rzucał także pionkami, które nie zawsze lądują na tych samych kolorach.

Ten post edytował ADeM 20.01.2010, 02:10:33

[thek]

Zdefiniuj sąsiedztwo wpierw. Sąsiad to pionek o wartości od 1 do 8 włącznie, który ma wartości współrzędnych na każdej z osi w zakresie -1,+1 do współrzędnych aktualnego.
Algorytm powinien działać łańcuchowo mniej więcej na zasadzie:
1) Weź pierwszy wolny pionek z puli wszystkich i usuń go stamtąd tworząc z niego nową grupę.
2) Wyszukaj jego sąsiadów najbliższych, dodaj do grupy i też usuń z puli wszystkich.
3) Jeśli pula pusta, możesz zakończyć algorytm.
4) Weź kolejny z tej grupy i znajdź jego sąsiadów z puli, usuń je z puli wszystkich i dodaj do grupy.
5) Powtarzaj kroki od 3) aż dojdziesz do ostatniego elementu, który już nie będzie miał sąsiadów.
6) Wróć do kroku 1)
7) Powtarzaj aż brak będzie pionków w grupie tych wolnych.

Przykład wezmę Twój:
1:1, 1:2, 2:2, 5:5, 5:6
Biorę 1:1 i tworzę grupę usuwając go z puli, mam więc:
Grupa 1 -> 1:1
Pula -> 1:2, 2:2, 5:5, 5:6

Szukam sąsiadów i znajduję 1:2, 2:2, więc dodaję do grupy i usuwam z puli, mam więc:
Grupa 1 -> 1:1, 1:2, 2:2
Pula -> 5:5, 5:6

Biorę element kolejny z grupy 1 -> 1:2 Pula ma coś więc szukam sąsiadów w puli, ale ich brak, więc biorę kolejny 2:2, sprawdza ilość w puli jeszcze coś mającej tyle że tu też brak, więc szukanie się dla grupy kończy. Jeśli coś by doszło z tych szukań to automatycznie miałbym kolejne szukanie, co chyba jest logiczne

Biorę następny element z puli i tworzę grupę 2, więc mam:
Grupa 1 -> 1:1, 1:2, 2:2
Grupa 2 -> 5:5
Pula -> 5:6
Szukam sąsiadów, znajduję 5:6, usuwam z puli i dodaję do grupy.

Grupa 1 -> 1:1, 1:2, 2:2
Grupa 2 -> 5:5, 5:6
Pula -> pusta

Pula jest pusta, czyli algorytm się kończy.

Banał...

EDIT: W sumie nawet krok 7) nie jest potrzebny, bo krok 3) tak naprawdę zawsze zakończy Ci algorytm Kwestia Twojego przemyślenia to jedynie format zapisu współrzędnych pionów. Implementacja algorytmu już mając strukturę pionów to pryszcz.

Ten post edytował thek 20.01.2010, 10:50:10

[marcus753]

Wielkie dzięki THEK
Faktycznie teraz jak tak patrze na to zadanie to wcale nie jest trudne ja poprostu się w nim poplątałem bo postanowiłem zrobić je w biegu i nie rozpisałem sobie krok po kroku co mam robić tylko od razu zacząłem pisać...

w sumie pionek nie musisz porównywać do wszystkich pionków w około a tylko do tych na dole i pobokach bo u góry już zostały porównane przez wcześniejszy pionek

Pozdrawiam i jeszcze raz dzięki

[thek]

Niekoniecznie Zależy czy masz je posortowane czy nie. Jeśli tak, to masz rację i olewamy wszystkie mające mniejszą pierwszą współrzędną oraz równą pierwszą i mniejszą drugą na zasadzie:
olej olej olej
olej baza może
może może może
Brak sortowania wymusza na Tobie sprawdzenie wszelkich możliwości.

PS: Posortowana PULA to zawsze szukanie i tak od pierwszego elementu, gdyż nigdy nie trafisz na element mniejszy Stąd posortowanie puli na samym początku według pierwszego elementu, a jeśli jest kilka takich samych to wedle drugiego, może być dobrym pomysłem na optymalizację algorytmu, gdyż przerywasz szukanie po osiągnięciu przez skrypt w puli wolnych określonej wartości współrzędnych większej niż (baza +1, baza+1).

EDIT: Ciekawostką jest fakt, że takie rozwiązanie problemu pozwala na uznanie za grupę także pionków stojących na tym samym polu w wyniku rzucenia. Kto powiedział, że na jednym polu może stać tylko jeden? W wyniku rzutu może się okazać normą, że na jedno pole spadnie więcej niż jeden pion.
A na przyszłość zanim zaczniesz robić coś "z biegu" zastanów się nad założeniami bazowymi bo jak widzisz dobre przemyślenie sprawy ułatwia proces ze stopnia "nie wiem co dalej" do "to trywialne". Tutaj jednak najlepsze wyniki mają osoby myślące bardzo abstrakcyjnie i praktycy, bo to oni najszybciej wynajdują algorytm. Ja zacząłem od definicji "sąsiada". Gdy to już miałem reszta poszła gładko.

Ten post edytował thek 20.01.2010, 12:54:07

[marcus753]

mam dosyć napisałem taki skrypcik i oczywiście nie działa...
sam już nie wiem co robie zle

[PHP] pobierz, plaintext 
<?
$a=0;
$c=0;
$baza= 'baza.txt';
$wiersz = file($baza);
 
 
 
while (!empty($wiersz[$a])){
//bierzemy pierwszy pionek
  $baza= 'baza.txt';
  $wiersz = file($baza);
 
  $tuser = explode('|',$wiersz[$a]);
  $rzad = $tuser[0];
  $kolumna = $tuser[1];
	$grupa = $tuser[2];
 
	$b=0;
 
 
while (!empty($wiersz[$b])){
//bierzemy drugi pioten (na poczatku bedzie to ten sam )
  $baza= 'baza.txt';
  $wiersz1 = file($baza);
 
	$tuser = explode('|',$wiersz1[$b]);
	$rzadn = $tuser[0];
  $kolumnan = $tuser[1];
	$grupan = $tuser[2];
 
 
	$wartosc=0;
 
	$rzad1 = $rzad;
  $rzad2 = $rzad+1;
	$kolumna1 = $kolumna-1;
	$kolumna2 = $kolumna;
	$kolumna3 = $kolumna+1;
 
	//porownujemy wpolrzedne pionka 1 i 2
 
	if (($rzad1==$rzadn) AND ($kolumna1==$kolumnan)){$wartosc=1;}	
	if (($rzad1==$rzadn) AND ($kolumna2==$kolumnan)){$wartosc=1;}	
	if (($rzad1==$rzadn) AND ($kolumna3==$kolumnan)){$wartosc=1;}	
	if (($rzad2==$rzadn) AND ($kolumna1==$kolumnan)){$wartosc=1;}	
	if (($rzad2==$rzadn) AND ($kolumna2==$kolumnan)){$wartosc=1;}	
	if (($rzad2==$rzadn) AND ($kolumna3==$kolumnan)){$wartosc=1;}	
 
	if ($wartosc==1){
 
	if ($grupa==0){$grupa=$c+1;}
	//zapisujemy w transfer zawartosc pliku baza przy ()czym pionkowi 2 zmieniamy grupe )
	$plik_transferu = fopen('transfer.txt','a');
	flock($plik_transferu, LOCK_EX);
	$d=0;
 
	while (!empty($wiersz1[$d])){
	$baza= 'baza.txt';
  $wiersz2 = file($baza);
 
	$tuser = explode('|',$wiersz[$d]);
  $rzad5 = $tuser[0];
  $kolumna5 = $tuser[1];
	$grupa5 = $tuser[2];
 
	if(($rzad5==$rzadn) AND ($kolumna5==kolumnan)){$grupa5=$grupa;}
 
 
	$dane=$rzad5."|".$kolumna5."|".$grupa5."\n";
	$d=$d+1;
	}
 
  fwrite($plik_transferu, $dane);
 
	flock($plik_transferu, LOCK_UN);
 
	fclose($plik_transferu);
 
//przekopiowanie danych z transferu do bazy	
 
	$file = "baza.txt";
	$fp = fopen($file, "w");
	flock($fp, 2);
 
	$lista1 = file('transfer.txt');
 
foreach ($lista1 as $userek1){
 
  $tuser = explode('|',$userek1);
  $rzad10 = $tuser[0];
  $kolumna10 = $tuser[1];
	$grupa10 = $tuser[2];
 
$dane=$rzad10."|".$kolumna10."|".$grupa10."\n";
fwrite($fp, $dane);
 
 
	}
flock($fp, 3); 
fclose($fp);
 
 
	}}}
 
 
echo "zakonczono dzialanie skryptu "
 
 
 
?>
[PHP] pobierz, plaintext 

[thek]

Na początek radzę sobie sensownie wszystkie pionki do tablicy wrzucić. Przykładowo bierzesz plik z danymi w którym masz jakąś strukturę opisującą rzucone piony i musisz utworzyć taką, która będzie tablicą z współrzędnymi pionów choćby w postaci:

[PHP] pobierz, plaintext 
$pula = array( [0] => array([x] => 2, [y] => 5), [1] => array([x] => 2, [y] => 7), [2] => array([x] => 4, [y] => 8) )
[PHP] pobierz, plaintext 

i tak dalej kolejne. Dopiero na tym bazując powinieneś wykonywać grupowanie.

W tej chwili skaczesz z pobieraniem danych z pliku tak, że gubisz się z aktualnym położeniem wskaźnika i nawet nie wiesz gdzie oraz kiedy się znajdujesz w określonym miejscu skryptu. Masz po prostu chaos, którego nie ogarniasz. Uporządkuj go wpierw.