Solved bonus exercise from 15.11.21 practice

1 files changed, 78 insertions, 1 deletions

diff --git a/Year 1/Programming introduction/Practice-15.11.21.cpp b/Year 1/Programming introduction/Practice-15.11.21.cpp
index 7f94ff5..4679916 100644
--- a/Year 1/Programming introduction/Practice-15.11.21.cpp
+++ b/Year 1/Programming introduction/Practice-15.11.21.cpp
@@ -222,6 +222,83 @@ void ex7() {
 	cout << ((allInInterval(nums, n, a, b)) ? "true" : "false") << endl;
 }
 
+// Bonus: 1-D Game of Life
+// В тази задача трябва да се имплементира наша версия на популярната игра Game
+// of Life. В нашата версия използваме едномерен масив като еволюирането става по
+// следния начин:
+// • Клетка Х има 4 съседни клетки YYXYY.
+// • Жива клетка се представя чрез 1 а мъртва чрез 0.
+// • Мъртва клетка оживява ако 2 или 3 съседа са живи.
+// • Жива клетка оцелява ако 2 или 4 клетки са живи. В противен случай умира.
+// • Имаме циркулярна репрезентация т.е. съседите на клетка с индекс [n-1] са
+// клетките [n-2], [n-3], [0], [1].
+// Програмата очаква като вход: две числа n и m, символизиращи броя на клетките и
+// броя на еволюциите. Клетките са винаги повече от 4. След това се прочитат
+// стойностите на клетките. Като изход се извежда масивът след m-тата еволюция.
+// Пример:
+// Вход:
+// 11 10
+// 0 0 0 1 1 0 1 1 0 0 0
+// Изход: 0 0 1 1 0 1 0 1 1 0 0
+
+int neighbourIndex(int len, int currentCell, int neighbour) {
+	int offset = currentCell + neighbour;
+
+	// This is a bit more readable than nested ternary operators
+	if (offset < 0) return len + offset;
+	if (offset >= 0) return offset - len;
+	return offset;
+}
+
+void cpyValuesTo(bool src[], bool dst[], int len) {
+	for (int i = 0; i < len; i++)
+		dst[i] = src[i];
+}
+
+void evolve(bool cells[], int len, int evolutions) {
+	bool evCells[len];
+
+	for (int evolution = 0; evolution < evolutions; evolution++) {
+		cpyValuesTo(cells, evCells, len);
+
+		for (int i = 0; i < len; i++) {
+			// Calculate alive neighbours
+			int n1 = neighbourIndex(len, i, -2),
+				n2 = neighbourIndex(len, i, -1),
+				n3 = neighbourIndex(len, i, 1),
+				n4 = neighbourIndex(len, i, 2);
+			int aliveNeigh = cells[n1] + cells[n2] + cells[n3] + cells[n4];
+
+			// Determine if a cell should change state
+			if (!cells[i] && (aliveNeigh == 2 || aliveNeigh == 3))
+				evCells[i] = true;
+			else if (cells[i] && !(aliveNeigh == 2 || aliveNeigh == 4))
+				evCells[i] = false;
+		}
+
+		cpyValuesTo(evCells, cells, len);
+	}
+}
+
+void bonus() {
+	const int LINE_BUFFER_SIZE = 10000;
+
+	int n, m;
+	cin >> n >> m;
+
+	// Get input
+	bool cells[LINE_BUFFER_SIZE];
+	for (int i = 0; i < n; i++)
+		cin >> cells[i];
+
+	evolve(cells, n, m);
+
+	// Print result
+	for (int i = 0; i < n; i++)
+		cout << cells[i] << " ";
+	cout << endl;
+}
+
 int main() {
-	ex7();
+	bonus();
 }