Last active
November 30, 2023 07:13
-
-
Save cjaewon/e94983a92df8843ab4f5d7d0a50fe8e3 to your computer and use it in GitHub Desktop.
very-simple-wfc-algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| 규칙 | |
| 파동 함수 붕괴 알고리즘을 이용하여 실제로 학교 시간표를 결정하는 코드를 작성해보겠다. | |
| 먼저 규정한 규칙은 다음과 같다. | |
| + 물I과 물II는 연속으로 배치되면 안된다. | |
| + 화I과 화II는 연속으로 배치되면 안된다. | |
| + 지I과 지II는 연속으로 배치되면 안된다. | |
| + 생I과 생II는 연속으로 배치되면 안된다. | |
| + 과탐 과목은 각 한 번씩 8 타임 체육, 보건, 정보, 동아리는 각 한 번씩만 배치된다. | |
| """ | |
| import random | |
| class WFC(): | |
| def __init__(self): | |
| self.timetable = [ | |
| [["물I", "물II", "화I", "화II", "생I", "생II", "지I", "지II", "정보", "체육", "보건", "동아리"] for _ in range(4)], # 월 | |
| [["물I", "물II", "화I", "화II", "생I", "생II", "지I", "지II", "정보", "체육", "보건", "동아리"] for _ in range(4)], # 화 | |
| [["물I", "물II", "화I", "화II", "생I", "생II", "지I", "지II", "정보", "체육", "보건", "동아리"] for _ in range(4)], # 수 | |
| ] | |
| def start(self): | |
| i, j = random.randrange(0, 2), random.randrange(0, 4) | |
| self.timetable[i][j] = random.choice(self.timetable[i][j]) | |
| self.spread(i, j) | |
| while True: | |
| i, j = self.find_low_entropy() | |
| if i == None or j == None: | |
| break | |
| self.timetable[i][j] = random.choice(self.timetable[i][j]) | |
| self.spread(i, j) | |
| def spread(self, i, j): | |
| UP, DOWN = (0, 1), (0, -1) | |
| check_list = [UP, DOWN] | |
| if self.timetable[i][j][-1] == "I": | |
| for di, dj in check_list: | |
| if 0 <= i + di < 3 and 0 <= j + dj < 4: | |
| if type(self.timetable[i + di][j + dj]) != list: | |
| continue | |
| if self.timetable[i][j].count("I") == 1 and self.timetable[i][j] + "I" in self.timetable[i + di][j + dj]: | |
| self.timetable[i + di][j + dj].remove(self.timetable[i][j] + "I") | |
| elif self.timetable[i][j].count("I") == 2 and self.timetable[i][j][:2] in self.timetable[i + di][j + dj]: | |
| self.timetable[i + di][j + dj].remove(self.timetable[i][j][:2]) | |
| for k in range(3): | |
| for l in range(4): | |
| if type(self.timetable[k][l]) != list: | |
| continue | |
| if self.timetable[i][j] in self.timetable[k][l]: | |
| self.timetable[k][l].remove(self.timetable[i][j]) | |
| def find_low_entropy(self): | |
| min_possible = (999, 999, 999) | |
| for i in range(3): | |
| for j in range(4): | |
| if type(self.timetable[i][j]) != list: | |
| continue | |
| if len(self.timetable[i][j]) < min_possible[0]: | |
| min_possible = (len(self.timetable[i][j]), i, j) | |
| if min_possible[1] == 999: | |
| return None, None | |
| return min_possible[1:] | |
| def is_contradiction(self): | |
| for i in range(3): | |
| for j in range(4): | |
| if type(self.timetable[i][j]) == list: | |
| return True | |
| return False | |
| while True: | |
| wfc = WFC() | |
| wfc.start() | |
| if not wfc.is_contradiction(): | |
| print(wfc.timetable) | |
| break |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment