#include <iostream>

// Задача първа:
// Напишете функция filter, която приема масив от цели числа, дължината му и
// булева функция с един аргумент цяло число. В масива, елементите които не
// изпълняват условието на булевата функция променят стойността си на -1.
// Пример:
// 
// #include <iostream>
// bool isEven(int n) {
//     return (n % 2) == 0;
// }
// void filter(array, length, predicate) {
//     ...
// }
// int main() {
//     int arr[] = {1, 2, 3, 4, 5};
//     filter(arr, 5, isEven);
//     for(int i = 0; i < 5; i++){
//         std::cout << arr[i] << " ";
//     }
// }
// Изход: -1 2 -1 4 -1

bool isEven(int n) {
	return (n % 2) == 0;
}

void filter(int *array, int length, bool (predicate)(int)) {
	if (length == 0) return;

	if(!predicate(array[0]))
		array[0] = -1;
	filter(array + 1, length - 1, predicate);
}

void ex1() {
	int arr[] = {1, 2, 3, 4, 5};
	filter(arr, 5, isEven);
	for(int i = 0; i < 5; i++){
	std::cout << arr[i] << " ";
	}
}

// Задача втора:
// Напишете функция map, която приема масив от цели числа, дължината му и
// функция, която приема число по референция, и приложете функцията върху всеки
// елемент на масива.
// Пример:
// #include <iostream>
// int plusFive(int& n){
//     n += 5;
// } 
// void map(array, length, func) {
//     ...
// } 
// int main() {
//     int arr[] = {1, 2, 3, 4, 5};
//     map(arr, 5, plusFive);
//     for(int i = 0; i < 5; i++){
//         std::cout << arr[i] << " ";
//     } 
// } 
// Изход: 6 7 8 9 10

void plusFive(int& n){
	n += 5;
}

void map(int *array, int length, void (func)(int&)) {
	if (length == 0) return;

	func(array[0]);
	map(array + 1, length - 1, func);
}

void ex2() {
	int arr[] = {1, 2, 3, 4, 5};
	map(arr, 5, plusFive);
	for(int i = 0; i < 5; i++){
		std::cout << arr[i] << " ";
	}
}

// Задача трета:
// Да се дефинира рекурсивна функция, която заменя всяко срещане на цифрата 5 в
// дадено неотрицателно цяло число с 8.

int replFives(int n) {
	return (n == 5) ? 8 : n;
}

int modifyNum(int n, int (modifier)(int)) {
	int curr = modifier(n % 10);
	if (n == 0) return 0;

	return modifyNum(n / 10, modifier) * 10 + curr;
}

void ex3() {
	int n = 52553847;
	std::cout << modifyNum(n, replFives) << std::endl;
}

// Задача четвърта:
// Да се напише рекурсивна функция, която извършва двоично търсене в
// предварително сортиран масив от цели числа.

int binarySearch(int *arr, int len, int elem) {
	if (len == 0) return -1;

	if (arr[len / 2] == elem)
		return len / 2;
	else if (arr[len / 2] < elem)
		return binarySearch(arr + (len / 2 + 1), len / 2, elem) + (len / 2 + 1);
	else
		return binarySearch(arr, len / 2, elem);
}

void ex4() {
	int nums[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 101 };
	std::cout << binarySearch(nums, 11, 16) << std::endl;
}

// Задача пета:
// Имаме лабиринт, с размери nхm, в който проходимите клетки се бележат с 0 а
// непроходимите с 1. Да се напише програма, която проверява дали съществува път
// от подадени като аргументи начална и крайна точка.

bool insideBoundaries(int x, int y, int n, int m) {
	return x >= 0 && y >= 0 && x < n && y < m;
}

bool pathExists(int lab[][4], int n, int m, int stX, int stY, int endX, int endY) {
	if (stX == endX && stY == endY)
		return true;

	bool res = false;
	if (insideBoundaries(stX + 1, stY, n, m) && lab[stX + 1][stY] == 0) {
		lab[stX][stY] = 2;
		res = pathExists(lab, n, m, stX + 1, stY, endX, endY);
		lab[stX][stY] = 0;
	}
	if (res) return true;

	if (insideBoundaries(stX, stY + 1, n, m) && lab[stX][stY + 1] == 0) {
		lab[stX][stY] = 2;
		res = pathExists(lab, n, m, stX, stY + 1, endX, endY);
		lab[stX][stY] = 0;
	}
	if (res) return true;

	if (insideBoundaries(stX - 1, stY, n, m) && lab[stX - 1][stY] == 0) {
		lab[stX][stY] = 2;
		res = pathExists(lab, n, m, stX - 1, stY, endX, endY);
		lab[stX][stY] = 0;
	}
	if (res) return true;

	if (insideBoundaries(stX, stY - 1, n, m) && lab[stX][stY - 1] == 0) {
		lab[stX][stY] = 2;
		res = pathExists(lab, n, m, stX, stY - 1, endX, endY);
		lab[stX][stY] = 0;
	}

	return res;
}

void ex5() {
	int lab[][4] = {
		{ 0, 1, 1, 1 },
		{ 0, 1, 0, 1 },
		{ 0, 0, 0, 1 },
		{ 1, 1, 0, 1 },
		{ 0, 0, 0, 1 }
	};
	std::cout << pathExists(lab, 5, 4, 0, 0, 4, 0) << std::endl;
}

// Задача шеста:
// Дадена е квадратна матрица с размери n x m от цели числа. Да се намери пътят от
// горния ляв ъгъл до долния десен ъгъл с най - голяма сума от елементите, като
// имаме право да се движим само надолу и надясно.

int main() {
	ex5();
}