Zadanie praktyczne: układmy kafelki Pythonem i JavaScript!

Dzisiaj dostałam przeurocze pytanie Emilii z problemem prawdziwie życiowym

Pomyślałam iż napiszę do Ciebie, bo dzisiaj przyszła mi życiowa potrzeba napisania czegoś, co ułoży w dobrej kolejności kwadratowe płytki w kuchni

5 kolorów, 5 wierszy, 31 kolumn
Płytka nie powinna dotykać drugiej w tym samym kolorze.
Wyjściowo moge dostać tabele z symbolami kolorow.
Podpowiedziałabys mi proszę, czy to jest do zrobienia w Pythonie? Nie pracowałam tam jeszcze z tabelami i nie bardzo wiem czy to ma sens. Będę bardzo wdzięczna za wskazówkę

No pewnie, iż da się to rozwiązać Pythonem!

Ale jesteśmy w wyzwaniu w tygodniu JS-owym, więc zróbmy to na 2 sposoby

Układamy kafelki algorytmicznie

Musimy stworzyć własny algorytm. Podstawowa koncepcja może polegać na wykorzystaniu 2-wymiarowej listy (tablicy) – naszej ściany, gdzie każda komórka tej tablicy reprezentuje jedną płytkę.

Możemy wypełnić tę tablicę losowymi płytkami, upewniając się, iż żadne dwie sąsiednie płytki nie są takie same.

Moje płytki to zbiór 5 emoji: , , , ,

Algorytm mógłby wyglądać mniej więcej tak:

1. Stwórz pustą tablicę o odpowiednich wymiarach
2. Przejdź przez tablicę wiersz po wierszu, kolumna po kolumnie
3. Dla każdej komórki sprawdź dostępne kolory – usuń z dostępnych kolor jeżeli występuje jako emoji w sąsiednich komórkach
4. Wylosuj z pozostałych kolorów
5. Wstaw wylosowane emoji do komórki
6. Powtarzaj kroki 2-5, aż cała tablica będzie wypełniona

Wygląda całkiem prosto i logicznie?

Musimy jednak pamiętać, iż dla dużej tablicy i dużej liczby emoji, ten algorytm może być dość niewydajny.

O złożoności słów kilka tak przy okazji: Pętla po kolumnie (m) i wierszach (n) daje nam złożoność O(m x n) – jeżeli m i n byłyby podobnej wielkości to mamy tu doczynienia z pesymistycznie złożonością kwadratową O(n²). Dla m=1, gdy różnica między n a m jest znaczna można uznać optymistyczne O(n). [Więcej dowiesz się we wpisach: Po co programiście algorytmika? i Jak sie nauczyć algorytmiki? ]

Można go zoptymalizować na wiele sposobów, ale podstawowa wersja powinna działać dla małych tablic i małej liczby emoji-kafelków.

Najpierw Python, a za chwilę pure JS 😉

Kafelki w Pythonie

import random cols = 5 rows = 31 colors = ["", "", "", "", ""] # 1. Tworzymy pustą tablicę board = [] for _ in range(rows): row = [] for _ in range(cols): row.append(None) board.append(row) # 2. Przechodzimy przez każdą komórkę w tablicy for i in range(rows): for j in range(cols): # Tworzymy listę jeszcze dostępnych kolorów available_colors = colors.copy() # 3. Sprawdzamy sąsiadujące komórki i usuwamy ich kolory z dostępnych if i > 0 and board[i-1][j] in available_colors: available_colors.remove(board[i-1][j]) if j > 0 and board[i][j-1] in available_colors: available_colors.remove(board[i][j-1]) # 4. Losujemy kolor z dostępnych i (5) przypisujemy do komórki. board[i][j] = random.choice(available_colors) # Wyświetlamy całość for row in board: print(' '.join(row))

Najtrudniejsza część to ustalić kolor poprzedników i usunąć z listy do losowania.

Najpierw dla krawędzi w wierszu. Litera i iteruje po wierszu, więc i musi być większe od 0 (w wierszu zerowym nie ma poprzednika, więc nie ma sensu go sprawdzać), oraz cofamy się z obecnego wiersza i do poprzedniego czyli 1 krok w tył: i - 1

Analogicznie dla kolumny: Litera j iteruje po kolumnach, więc j chcemy by było większe od 0 (w kolumnie 0 nie ma poprzednika), oraz cofamy się z obecnego obecnej kolumny do poprzedniej tj. sąsiada o 1 czyli 1 krok w tył: i - 1.

if i > 0 and board[i-1][j] in available_colors: available_colors.remove(board[i-1][j]) if j > 0 and board[i][j-1] in available_colors: available_colors.remove(board[i][j-1])

Doszlifujmy ten kod zgodnie z PEP-8:

• wyciągnijmy stałe na górę skryptu – rozmiary tablicy oraz dostępne kolory
• podzielmy kod na funkcje, pamiętajmy o funkcji main()
• dodajmy list comprehension

List comprehension jeszcze nie było, więc szybkim słowem wprowadzenia

– to składnia, która pozwala tworzyć listy w sposób bardziej zwięzły, niż klasyczna pętla for, którą spotkacie w kurs Python cz. 7: Pętla FOR

board = [] for _ in range(rows): row = [] for _ in range(cols): row.append(None) board.append(row)

możemy zapisać

empty_row = [None for _ in range(cols)] board = [list(empty_row) for _ in range(rows)]

lub zagnieżdżając empty_row

board = [[None for _ in range(cols)] for _ in range(rows)] import random COLS = 5 ROWS = 31 COLORS = ["", "", "", "", ""] def create_board(): return [[None for _ in range(COLS)] for _ in range(ROWS)] def assign_colors(board): for i in range(ROWS): for j in range(COLS): available_colors = COLORS.copy() if i > 0 and board[i-1][j] in available_colors: available_colors.remove(board[i-1][j]) if j > 0 and board[i][j-1] in available_colors: available_colors.remove(board[i][j-1]) board[i][j] = random.choice(available_colors) return board def display_board(board): for row in board: print(' '.join(row)) def main(): board = create_board() assign_colors(board) display_board(board) if __name__ == "__main__": main()

Kafelki w JavaScript

Główny algorym pozostaje bez zmian opisany wyżej.

Zaczniemy jak wyżej od prostrzej wersji 😉

script.js

const cols = 5; const rows = 31; const colors = ["", "", "", "", ""]; // 1. Tworzymy pustą tablicę let board = []; for (let i = 0; i < rows; i++) { let row = []; for (let j = 0; j < cols; j++) { row.push(null); } board.push(row); } // 2. Przechodzimy przez każdą komórkę w tablicy for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { // Tworzymy listę jeszcze dostępnych kolorów let availableColors = [...colors]; // Sprawdzamy sąsiadujące komórki i usuwamy ich kolory z dostępnych if (i > 0 && availableColors.includes(board[i-1][j])) { availableColors.splice(availableColors.indexOf(board[i-1][j]), 1); } if (j > 0 && availableColors.includes(board[i][j-1])) { availableColors.splice(availableColors.indexOf(board[i][j-1]), 1); } // Losujemy kolor z dostępnych i (5) przypisujemy do komórki board[i][j] = availableColors[Math.floor(Math.random() * availableColors.length)]; } } board.forEach(row => console.log(row.join(' ')));

To szlifujemy jak poprzednio!

• zastosujemy const tam, gdzie to możliwe,
• czas na wyodrębnienie logiki do funkcji
• lepsze nazewnictwo i wprowadzenie stałych
• zwróć też uwagę na użycie Array.from

const ROWS = 31; const COLS = 5; const COLORS = ["", "", "", "", ""]; function createBoard(rows, cols) { return Array.from(Array(rows), () => Array(cols).fill(null)); } function getAvailableColors(board, i, j) { let availableColors = [...COLORS]; if (i > 0 && availableColors.includes(board[i-1][j])) { availableColors.splice(availableColors.indexOf(board[i-1][j]), 1); } if (j > 0 && availableColors.includes(board[i][j-1])) { availableColors.splice(availableColors.indexOf(board[i][j-1]), 1); } return availableColors; } function fillBoard(board) { for (let i = 0; i < ROWS; i++) { for (let j = 0; j < COLS; j++) { let availableColors = getAvailableColors(board, i, j); let colorIndex = Math.floor(Math.random() * availableColors.length); board[i][j] = availableColors[colorIndex]; } } } let board = createBoard(ROWS, COLS); fillBoard(board); board.forEach(row => console.log(row.join(' ')));

Co dalej?

Kilkam możliwych rozszerzeń:

• Może warto dodać np. policzenie ile kafelków, którego typu zostanie użyte? 😉
• Moglibyśmy wprowadzić też dodatkowe zasady utrudniające sprawdzanie (może nie koniecznie życiowe), takie jak ograniczenie, iż płytki tego samego koloru nie mogą być sąsiadami, choćby na przekątną, lub iż żadne dwie płytki tego samego koloru nie mogą być oddzielone tylko przez jedną płytkę innego koloru.
• Zamiast emoji użyć symbolu „█” i pozwalać na zmianę koloru na dowolny wybrany przez użytkownika wprowadzony w hex, dzieki czemu użytkownik będzie widział też, jak kolory się koło siebie ułożą np: █ █ █ █ █
• Może zamiast symbolu układać kafelki jako małe div w DOM z wykorzystaniem flexbox lub grid (nasz pierwszy tydzień wyzwania #FlyNerdSummerOfCode)