bonusodev.cpp

/*
 * @AUTHOR: Oleksiy Nehlyadyuk
 * @NUMBER: 182113201
 *
 * NOT: duvarların, yolların ve yıldızın(*) yerini değiştirip programı farklı bir labirentle de çalıştırabilirsiniz

 * Algoritma:
 *
 * 1.  Etraftaki sıfırları saydır
 * 2.  Eğer sıfır sayısı 1 ise:
 * 3.  Sıfır yönüne doğru ilerle ve bulunduğun yeri arttır: goto 1
 * 4.  Eğer sıfırların sayısı 1'den fazlaysa:
 * 5.  Kuzey'den başlayıp saat yönünde müsait bir yere flag koy: goto 1
 * 6.  Eğer etrafta hiç sıfır yoksa:
 * 7.  Önceden yerleştirilen flagi ara
 * 8.  Eğer flag varsa
 * 9.  Flag'e ışınlan: goto 1
 * 10. Kuzey'den başlayıp saat yönünde sıfırdan farklı sayı ara
 * 11. Mevcut pozisyonu, bulunan sayıyının bir fazlası olarak ayarla: goto 1
 * 12. Eğer flag yoksa
 * 13. Gidilemeyen yerleri yani kapalı kalmış 0'ların hepsini 'u' yap
 * 14. Çıkış noktalarını listele
 * 15. Bitir.
 */

 // Yukarıdakinin İmplementasyonu

#define LABYRINTH_SIZE_X 15
#define LABYRINTH_SIZE_Y 16

#include <iostream>
#include <string>
#include <chrono>
#include <thread>

using namespace std::this_thread; // sleep için
using namespace std::chrono; // sleep için
using namespace std;

int flag_position_X, flag_position_Y; // bir diziden iki değer döndüremediğim için bunları global tanımlayıp fonskiyona referans olarak vereceğim
int cursors_current_position_X, cursors_current_position_Y; // imlecin nerede durduğunu tutan x ve y koordinatları
int zero_position_X, zero_position_Y;
int last_path_value = 1; // En son arttırılan değeri tutar. Burada 0'dan da başlayabilirdik ancak fazladan işlem olur
string saved_number_before_flag_is_set = "1"; // yol ayrımındaki en son sayıyı kaydeden değişken (kalınan yeri unutmamak için)

string labyrinth[LABYRINTH_SIZE_X][LABYRINTH_SIZE_Y] = {
{"x","x","x","x","x","x","0","x","x","x","x","x","x","x","x"},
{"x","x","x","x","x","x","0","x","x","x","0","0","0","0","x"},
{"x","x","x","x","0","0","0","0","0","x","x","x","x","x","x"},
{"0","0","0","0","0","x","0","x","x","x","x","x","0","x","x"},
{"0","x","x","x","x","x","0","x","0","x","0","0","0","0","0"},
{"0","x","x","x","x","x","0","x","0","x","0","x","x","x","x"},
{"0","0","*","0","x","x","0","x","x","x","0","x","0","x","x"},
{"0","x","x","0","x","x","0","0","0","0","0","x","0","x","x"},
{"0","x","x","0","x","x","x","x","x","x","0","x","0","x","x"},
{"0","x","x","x","x","x","0","0","0","x","0","x","x","x","x"},
{"0","0","0","x","0","x","x","x","x","x","0","0","0","0","x"},
{"x","x","0","x","0","x","x","x","x","x","0","x","x","0","x"},
{"x","x","x","x","0","x","0","0","0","0","0","x","x","0","0"},
{"x","x","x","x","0","x","0","x","x","x","x","x","x","x","x"},
{"x","x","x","x","x","x","0","x","x","x","x","x","x","x","x"} };

// flagleri queue'de tutacağım
struct queue {
	int A[216]; // çeyrek MB ama lazım :P
	int front = -1;
	int rear = -1;

	bool is_empty()
	{
		if (front == -1 && rear == -1) {
			return true;
		}
		return false;
	}

	void enqueue(int value)
	{
		if (is_empty()) {
			front++; rear++;
		}
		else {
			rear++;
		}
		A[rear] = value;
	}

	void dequeue(int* destination)
	{
		if (is_empty()) {
			return;
		}
		else if (front == rear) {
			*destination = A[front];
			front = -1;
			rear = -1;
		}
		else {
			*destination = A[front];
			front++;
		}
	}

	// overload referans almadan da dequeue edebilsin
	void dequeue(int destination)
	{
		if (is_empty()) {
			return;
		}
		else if (front == rear) {
			destination = A[front];
			front = -1;
			rear = -1;
		}
		else {
			destination = A[front];
			front++;
		}
	}
}flags_are_saved_here; // flaglari tutmak için bir queue objesi tanımladım

// labirent çıkışlarını da stack'de tutacağım. belli bir amacı yok. sadece stack ve queue'yi aynı projede kullanmak istedim
// sadece push ve dump_stack fonksiyonlarını kullandım çünkü diğerlerine ihtiyaç yok
struct stack {
	int A[300];
	int bp = -1; // stack'in taban pointer (base pointer) ya da top

	// çıkış yolu bulursa push edecek
	void push(int value)
	{
		bp++;
		A[bp] = value;
	}

	// çıkış noktalarını bastırmak için kullanacağız
	void dump_stack()
	{
		int tmp = bp;
		while (tmp != -1) {
			cout << A[tmp] << endl;
			tmp--;
		}
	}

}exit_points; // çıkış noktalarını tutmak için bir stack objesi oluşturuldu

// tüm çıkış noktaları belli bir sayı değerine ulaştıysa bu, labirentin çözüldüğü anlamına gelir.
bool is_labyrinth_solved()
{
	// en üst kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) { if (labyrinth[0][i] == "0") { return false; } }
	// sol kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) { if (labyrinth[i][0] == "0") { return false; } }
	// sağ kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) { if (labyrinth[i][LABYRINTH_SIZE_X - 1] == "0") { return false; } }
	// en alt kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) { if (labyrinth[LABYRINTH_SIZE_X - 1][i] == "0") { return false; } }
	return true; // bütün kenarları kontrol ettikten sonra hiç bir sıfır bulamadıysa demekki çözüldü
}

// labirentin en kenarları tarayıp, 'x' haricindeki sayıları stack'e push ediyor
void get_all_exit_points_and_print()
{
	// en üst kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		if (labyrinth[0][i] != "x") {
			exit_points.push(stoi(labyrinth[0][i]));
		}
	}
	// sol kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		if (labyrinth[i][0] != "x") {
			exit_points.push(stoi(labyrinth[i][0]));
		}
	}
	// sağ kenar kontrol ediliyor
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		if (labyrinth[i][LABYRINTH_SIZE_X - 1] != "x") {
			exit_points.push(stoi(labyrinth[i][LABYRINTH_SIZE_X - 1]));
		}
	}
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		if (labyrinth[LABYRINTH_SIZE_X - 1][i] != "x") {
			exit_points.push(stoi(labyrinth[LABYRINTH_SIZE_X - 1][i]));
		}
	}
	// çözüm stackindeki tüm elemanlar yazdırıyor
	cout << endl;
	cout << "Labirentin tum cikis noktalari:" << endl;
	cout << "-------------------------------" << endl;
	exit_points.dump_stack();
	cout << "-------------------------------" << endl;
}

// labirentte meydana gelen değişimleri göstermek için her update'den sonra bastırıyorum
void print_labyrinth()
{
	//system("clear"); // burası Linux'a özel ekran temizleme komutu
	system("cls"); // windows ekran temizleme komutu // FIXME
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		for (int j = 0; j < LABYRINTH_SIZE_Y; j++) {
			// sayı 2 basamaklıysa tek space koy, değilse 1 tane. sadece güzel gözükmesi için
			if (labyrinth[i][j].length() == 1)
			{
				cout << "  " + labyrinth[i][j];
			}
			else
			{
				cout << " " + labyrinth[i][j];
			}
		}
		cout << endl;
	}
	sleep_until(system_clock::now() + milliseconds(50)); // bekleme süresi
}

// labirentteki yıldızı(*) bularak programın hangi koordinattan başlayacağını bulup
// imlecin x ve y değerlerini günceller
// ayrıca yukarıdaki labirent dizisindeki yıldızın karakterinin yerini değiştirmek de mümkün
void find_starting_point(int* cursor_coor_x, int* cursor_coor_y) {
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		for (int j = 0; j < LABYRINTH_SIZE_Y; j++) {
			if (labyrinth[i][j] == "*") {
				*cursor_coor_x = i;
				*cursor_coor_y = j;
			}
		}
	}
}

// mevcut konum etrafındaki (kuzey,doğu,güney ve batı) tüm sıfırları sayıp gönderir
int count_zeros_around(int current_position_X, int current_position_Y)
{
	int amount_of_zeros = 0; // etraftaki sıfırların sayısı

	// bakılacak olan yönlerin dizisi
	string directions_to_look[4] = {
	labyrinth[current_position_X + 1][current_position_Y], // kuzey
	labyrinth[current_position_X][current_position_Y + 1], // doğu
	labyrinth[current_position_X - 1][current_position_Y], // güney
	labyrinth[current_position_X][current_position_Y - 1] }; // batı

	//  sıfır aranıyor
	for (auto i : directions_to_look) {
		if (i == "0") {
			amount_of_zeros++; // bakılan tarafta 0 varsa arttır
		}
	}
	return amount_of_zeros; // 0'ları saydıktan sonra gönder
}

// konumdan sıfırı silip yerine gerekli sayıyı yazdırır
void update_current_location(int zero_position_X, int zero_position_Y) {
	int int_value = stoi(labyrinth[zero_position_X][zero_position_Y]); // labirent bir string dizisi. int cast yap
	int_value = last_path_value; // burada 0 sayısı değiştiriliyor
	labyrinth[zero_position_X][zero_position_Y] = to_string(int_value); // değişen değer string olarak yerine konuyor
	last_path_value++; // arttırmaya kalınan yerden devam edilsin diye counterı 1 arttırıyoruz
}

// istenilen yöndeki 0'ın yerine, daha sonra buraya geri dönebilmek amacıyla bayrak koyan fonksiyon
// bu fonksiyonu for döngüsüyle yazmaya kalktığım an hata veriyor.. o yüzden böyle yaptım
void place_a_flag(int current_position_X, int current_position_Y)
{
	if (labyrinth[current_position_X - 1][current_position_Y] == "0") {
		labyrinth[current_position_X - 1][current_position_Y] = "F"; // bakılan yönde 0 yer alıyorsa oraya F(lag) koy
		saved_number_before_flag_is_set = to_string(last_path_value); // en son durumu kaydet. last_path_value bir integer olduğundan cast et
		flags_are_saved_here.enqueue(current_position_X - 1);
		flags_are_saved_here.enqueue(current_position_Y);
	}
	else if (labyrinth[current_position_X][current_position_Y + 1] == "0") {
		labyrinth[current_position_X][current_position_Y + 1] = "F";
		saved_number_before_flag_is_set = to_string(last_path_value);
		flags_are_saved_here.enqueue(current_position_X);
		flags_are_saved_here.enqueue(current_position_Y + 1);
	}
	else if (labyrinth[current_position_X + 1][current_position_Y] == "0") {
		labyrinth[current_position_X + 1][current_position_Y] = "F";
		saved_number_before_flag_is_set = to_string(last_path_value);
		flags_are_saved_here.enqueue(current_position_X + 1);
		flags_are_saved_here.enqueue(current_position_Y);
	}
	else if (labyrinth[current_position_X][current_position_Y - 1] == "0") {
		labyrinth[current_position_X][current_position_Y - 1] = "F";
		saved_number_before_flag_is_set = to_string(last_path_value);
		flags_are_saved_here.enqueue(current_position_X);
		flags_are_saved_here.enqueue(current_position_Y - 1);
	}
	flags_are_saved_here.enqueue(last_path_value);
}


// daha önceden yerleştirilmiş flagi bul ve o noktaya ışınlan
void find_flag_and_teleport_there(int* current_position_X, int* current_position_Y, int* las_path_value) {

	// queue'de kayıtlı olan değerler gerekli yerlere atanıyor
	flags_are_saved_here.dequeue(current_position_X);
	flags_are_saved_here.dequeue(current_position_Y);
	flags_are_saved_here.dequeue(&last_path_value);

	// yol ayrımında program nerde kaldıysa oradan devam etmesi için kayıtlı değeri mevcut pozisyona koyuyorum
	labyrinth[*current_position_X][*current_position_Y] = to_string(last_path_value);
	last_path_value++; // haliyle kayıtlı değeri arttırıyorum
}

// imleci bulunan ilk sıfıra getir
void find_first_zero_and_move_there(int* current_position_X, int* current_position_Y)
{
	// eğer 0 kuzeydeyse
	if (labyrinth[*current_position_X + 1][*current_position_Y] == "0") {
		*current_position_X += 1;
	}
	// doğudaysa
	else if (labyrinth[*current_position_X][*current_position_Y + 1] == "0") {
		*current_position_Y += 1;
	}
	// güneydeyse
	else if (labyrinth[*current_position_X - 1][*current_position_Y] == "0") {
		*current_position_X -= 1;
	}
	// batıdaysa
	else if (labyrinth[*current_position_X][*current_position_Y - 1] == "0") {
		*current_position_Y -= 1;
	}
}

// tüm çıkmaz sokakları 'u' karakterine çevir
void convert_all_dead_ends_to_character_u()
{
	for (int i = 0; i < LABYRINTH_SIZE_X; i++) {
		for (int j = 0; j < LABYRINTH_SIZE_Y; j++) {
			if (labyrinth[i][j] == "0") {
				labyrinth[i][j] = "u";
			}
		}
	}
}

// her şeyin başlayıp bittiği yer
int main(void) {
	find_starting_point(&cursors_current_position_X, &cursors_current_position_Y); // yıldızı bul ve konumunu kaydet
	int z = 0; // sıfır sayısını tutacak olan değişken

	// labirent tamamlanana kadar aşağıdaki işlemleri uygula
	while (true) {
		z = count_zeros_around(cursors_current_position_X, cursors_current_position_Y); // etraftaki sıfırları say (aslında yol ayrımı var mı diye bakıyor)
		if (z == 1) { // eğer sadece bir sıfır var ise (tek yol varsa)
			find_first_zero_and_move_there(&cursors_current_position_X, &cursors_current_position_Y); // sıfırnın üstüne gel
			update_current_location(cursors_current_position_X, cursors_current_position_Y); // sıfırı değiştir ve gerekli sayıyı yerleştir
		}
		else if (z > 1) { // eğer yol ayrımı varsa
			place_a_flag(cursors_current_position_X, cursors_current_position_Y); // geri dönebilmek için yol ayrımıda bir yere işaret (Flag) koy
			// işaretin görsel olarak labirente görünmesi istenmiyorsa, "F" stringinin atandığı yer silinebilir
		}
		else if (z == 0) // eğer çıkmaz sokağa girdiysek
		{
			if (is_labyrinth_solved()) { // labirent tamamlanmış mı diye bak. eğer tamamsa while'ı kır
				break;
			}
			// labirent tamamlanmadıysa, queue'den bir flag çek ve oraya ışınlan
			find_flag_and_teleport_there(&cursors_current_position_X, &cursors_current_position_Y, &last_path_value);
		}
		print_labyrinth(); // neler olup bittiğine bakmak için labirenti her iterasyonda bastır
	}
	system("cls"); // burası işletim sistemi spesifik. windowsda "cls"
	convert_all_dead_ends_to_character_u(); // çıkmaz sokakların hepsini bul ve 'u' karakterine çevir
	print_labyrinth(); // final'de oluşan labirenti bastır
	get_all_exit_points_and_print(); // stack'den bütün pushlanmış çıkış noktalarını çek
	return 0;
}