◂ 12 décembre 2024 ▸
Garden Groups : Trouver des zones et calculer l'aire, le périmètre et le nombre de côtés.
UUUKKKKZZZZ …
UUKKKKKZZZZ …
UUKKKKKKKZZ …
⋮
- code.py
- code_visualisation.py
- find_4_colors_coloring.py
- colorByLetter.png
- four_colors_plain.png
- multicolors_borders.png
- multicolors_plain.png
- four_colors_terminal_borders.png
import turtle
from random import shuffle, choice
_ = MODE_MIN_COLORS = 0 # apply Welsh-Powell which gives normally 5 or 6 colors
_ = MODE_5_COLORS_MAX = 1 # try Welsh-Powell algorithm until 5 colors is made
_ = MODE_LETTER_COLORS = 2 # same color for same letter regions
_ = MODE_63_COLORS = 3 # cycle through 63 colors for the 622 regions
MODE = MODE_4_COLORS = 4 # use precomputed 4-colors coloring
SIZE_WINDOW = 800
BORDERS = True
DOTS = False
LARGEUR_AFFICHAGE_TERMINAL = 3 # nb caractères de large pour chaque zone, + autant pour l'éventuelle bordure
with open("input.txt", 'r', encoding='utf-8') as f:
grid = [line[:-1] for line in f.readlines()]
W = len(grid[0])
H = len(grid)
def find_region_borders(x, y, region_ids, current_region_id) -> (int, int, int):
region = set()
borders = set()
region_letter = grid[y][x]
to_do = { (x,y), }
DIRECTIONS = ((1,0), (0,1), (-1,0), (0,-1))
while to_do:
x, y = to_do.pop()
region.add((x,y))
region_ids[y][x] = current_region_id
for dx, dy in DIRECTIONS:
nx, ny = x+dx, y+dy
if (nx,ny) not in region: # not already processed
if (0 <= nx < W) and (0 <= ny < H) and (grid[ny][nx] == region_letter) :
to_do.add((nx,ny))
else:
borders.add( ((x,y), (dx,dy)) )
return borders
region_ids = [W*[None] for i in range(H)]
current_region_id = 0
borders = []
for y in range(H):
for x in range(W):
if not region_ids[y][x]: # not already processed
current_region_id += 1
borders.append(find_region_borders(x, y, region_ids, current_region_id))
# coloration par algo de Welsh-Powell
edges = dict( ((i, set())) for i in range(1, len(borders) + 1) )
for region_borders in borders:
for (x,y),(dx,dy) in region_borders:
if 0 <= x+dx < W and 0 <= y+dy < H:
edges[region_ids[y][x]].add(region_ids[y+dy][x+dx])
if MODE in (MODE_MIN_COLORS, MODE_5_COLORS_MAX):
while True:
print('.', end='', flush=True)
degrees = [(len(edges[id]), id) for id in edges.keys()]
degrees.sort(reverse=True)
couleurs_dispo = {0}
couleur_region = dict()
while degrees:
max_deg = degrees[0][0]
id = choice([id for deg,id in degrees if deg==max_deg])
degrees.remove((max_deg, id))
coul_autour = set(couleur_region[id_voisin] for id_voisin in edges[id] if id_voisin in couleur_region)
couleurs_possibles = couleurs_dispo.difference(coul_autour)
if not couleurs_possibles:
coul = max(couleurs_dispo) + 1
couleurs_dispo.add(coul)
else:
coul = choice(list(couleurs_possibles))
couleur_region[id] = coul
if len(couleurs_dispo) <= 4:
print("\nEN", len(couleurs_dispo), "COULEURS !!!!")
print(couleur_region)
break
elif len(couleurs_dispo) <= 5:
print("\nEn 5 couleurs.")
break
elif MODE == MODE_MIN_COLORS and len(couleurs_dispo) == 6:
print("\nEn 6 couleurs.")
break
elif MODE == MODE_4_COLORS:
couleur_region = {622: 0, 572: 1, 545: 0, 494: 1, 528: 2, 504: 0, 552: 3, 560: 2, 561: 1, 406: 2, 482: 0, 417: 1, 360: 0, 377: 1, 316: 2, 315: 0, 288: 1, 246: 0, 286: 2, 287: 3, 245: 1, 185: 2, 216: 1, 167: 0, 152: 1, 99: 0, 110: 2, 122: 3, 93: 0, 120: 1, 85: 1, 51: 2, 100: 1, 111: 0, 78: 2, 26: 0, 46: 3, 74: 2, 70: 1, 12: 2, 71: 0, 68: 1, 27: 0, 62: 2, 86: 1, 55: 0, 94: 2, 105: 1, 124: 3, 130: 0, 133: 2, 134: 0, 126: 3, 146: 1, 145: 3, 155: 2, 144: 3, 177: 3, 157: 0, 189: 2, 188: 0, 186: 2, 210: 1, 135: 1, 175: 3, 181: 1, 159: 0, 201: 1, 200: 0, 129: 2, 81: 1, 102: 3, 178: 2, 59: 2, 16: 1, 13: 3, 41: 3, 47: 2, 40: 3, 18: 0, 69: 3, 53: 2, 89: 0, 72: 1, 60: 0, 82: 3, 114: 1, 147: 0, 148: 2, 83: 2, 107: 3, 142: 0, 168: 1, 173: 3, 176: 0, 184: 1, 204: 0, 199: 1, 218: 3, 171: 1, 195: 0, 212: 3, 198: 2, 196: 3, 235: 1, 209: 2, 228: 3, 217: 1, 214: 0, 224: 2, 220: 1, 230: 0, 225: 3, 251: 3, 242: 2, 234: 1, 237: 0, 254: 1, 260: 2, 248: 2, 259: 3, 277: 1, 291: 0, 304: 3, 255: 0, 261: 1, 257: 0, 187: 3, 165: 1, 138: 2, 267: 2, 274: 0, 297: 2, 302: 1, 320: 3, 322: 2, 347: 1, 335: 3, 294: 1, 328: 0, 346: 0, 359: 1, 372: 2, 387: 2, 280: 1, 298: 2, 310: 3, 318: 2, 338: 1, 337: 2, 308: 2, 355: 0, 351: 1, 365: 3, 366: 1, 381: 0, 379: 2, 382: 0, 386: 0, 415: 3, 405: 1, 407: 1, 408: 2, 433: 3, 432: 2, 434: 1, 426: 2, 452: 0, 427: 1, 443: 1, 445: 0, 459: 0, 460: 2, 487: 3, 502: 2, 531: 3, 465: 0, 484: 1, 492: 2, 511: 3, 512: 3, 517: 1, 495: 2, 500: 1, 501: 3, 515: 3, 507: 0, 456: 2, 479: 0, 510: 0, 516: 3, 539: 3, 532: 0, 546: 1, 556: 2, 564: 1, 513: 1, 521: 2, 529: 1, 534: 0, 535: 2, 563: 0, 579: 2, 599: 3, 584: 0, 585: 1, 580: 3, 595: 3, 597: 0, 594: 1, 609: 1, 592: 3, 610: 0, 586: 1, 5: 0, 10: 1, 54: 3, 52: 2, 7: 2, 32: 1, 6: 1, 9: 0, 15: 0, 17: 2, 23: 1, 50: 3, 84: 3, 4: 2, 25: 3, 3: 0, 44: 2, 91: 1, 119: 3, 39: 0, 98: 3, 2: 1, 30: 1, 42: 3, 19: 2, 20: 0, 22: 1, 29: 1, 31: 1, 33: 1, 34: 1, 35: 1, 37: 2, 43: 2, 45: 1, 48: 1, 49: 2, 38: 1, 24: 2, 21: 1, 56: 1, 57: 1, 58: 1, 63: 1, 64: 0, 61: 1, 65: 1, 66: 0, 76: 1, 77: 1, 79: 1, 88: 1, 87: 2, 92: 1, 95: 0, 96: 2, 101: 0, 104: 2, 106: 1, 108: 1, 113: 1, 115: 1, 116: 0, 127: 3, 117: 2, 118: 1, 123: 0, 125: 0, 128: 0, 132: 2, 136: 2, 137: 1, 140: 2, 141: 0, 143: 0, 150: 0, 166: 1, 164: 0, 190: 0, 149: 2, 151: 0, 153: 0, 154: 0, 156: 2, 158: 0, 160: 1, 162: 0, 163: 0, 170: 1, 172: 0, 174: 0, 179: 0, 182: 1, 191: 1, 192: 0, 193: 1, 197: 0, 202: 0, 203: 0, 206: 1, 208: 0, 211: 0, 213: 3, 222: 0, 223: 0, 227: 1, 229: 0, 231: 0, 244: 2, 232: 0, 233: 0, 238: 0, 240: 0, 241: 1, 249: 0, 250: 2, 253: 0, 256: 0, 258: 0, 264: 0, 270: 1, 271: 0, 272: 1, 273: 0, 284: 2, 263: 1, 275: 0, 276: 1, 278: 0, 282: 2, 285: 0, 292: 1, 247: 2, 221: 0, 243: 1, 236: 2, 252: 0, 266: 3, 219: 1, 226: 2, 268: 1, 293: 0, 295: 0, 299: 2, 301: 2, 306: 2, 311: 0, 317: 0, 319: 1, 321: 0, 323: 0, 330: 3, 307: 2, 324: 2, 352: 3, 357: 1, 344: 3, 358: 0, 356: 3, 325: 1, 327: 0, 331: 1, 332: 1, 333: 3, 362: 3, 361: 1, 363: 0, 334: 0, 336: 0, 339: 2, 340: 0, 390: 2, 341: 2, 342: 0, 345: 1, 349: 0, 353: 0, 354: 1, 364: 1, 368: 2, 370: 1, 371: 2, 374: 1, 375: 1, 376: 2, 380: 1, 383: 0, 384: 0, 385: 0, 388: 2, 389: 1, 391: 0, 404: 3, 393: 2, 395: 2, 396: 2, 397: 1, 398: 0, 428: 1, 412: 2, 429: 3, 435: 1, 441: 3, 496: 3, 524: 1, 367: 1, 410: 2, 399: 1, 400: 1, 402: 2, 413: 1, 414: 2, 416: 2, 419: 2, 420: 0, 422: 0, 423: 2, 476: 3, 409: 0, 424: 2, 431: 0, 436: 0, 446: 3, 438: 1, 437: 0, 439: 2, 440: 0, 442: 2, 454: 2, 455: 0, 457: 0, 468: 2, 485: 0, 461: 2, 463: 2, 467: 0, 470: 0, 471: 2, 472: 2, 473: 2, 474: 2, 475: 2, 488: 0, 498: 2, 503: 0, 477: 0, 480: 1, 483: 2, 486: 2, 490: 1, 491: 2, 493: 1, 497: 0, 499: 2, 505: 0, 506: 2, 508: 2, 509: 1, 514: 2, 518: 0, 519: 1, 520: 0, 523: 0, 526: 1, 527: 0, 530: 2, 533: 0, 536: 2, 537: 2, 540: 0, 541: 0, 569: 3, 557: 1, 570: 2, 614: 2, 542: 1, 547: 0, 548: 0, 549: 1, 550: 1, 553: 1, 559: 2, 562: 2, 567: 0, 578: 3, 568: 1, 573: 1, 574: 0, 587: 2, 602: 1, 571: 2, 551: 0, 558: 2, 566: 1, 575: 2, 576: 2, 577: 0, 581: 2, 582: 2, 583: 2, 588: 0, 589: 3, 593: 1, 596: 1, 598: 1, 603: 1, 604: 0, 606: 2, 608: 0, 611: 1, 616: 0, 618: 1, 1: 0, 8: 0, 11: 0, 14: 0, 28: 1, 36: 1, 67: 0, 73: 0, 75: 1, 80: 0, 90: 0, 97: 0, 103: 0, 109: 1, 112: 0, 121: 0, 131: 0, 139: 0, 161: 0, 169: 0, 180: 0, 183: 0, 194: 0, 205: 0, 207: 0, 215: 0, 239: 0, 262: 0, 265: 1, 269: 0, 279: 1, 281: 0, 283: 1, 289: 0, 290: 0, 296: 0, 300: 0, 303: 0, 305: 1, 309: 0, 312: 1, 313: 0, 314: 0, 326: 0, 329: 0, 343: 0, 348: 0, 350: 0, 369: 0, 373: 0, 378: 0, 392: 0, 394: 0, 401: 0, 403: 0, 411: 0, 418: 0, 421: 0, 425: 0, 430: 0, 444: 0, 447: 0, 448: 0, 449: 0, 450: 0, 451: 0, 453: 0, 458: 0, 462: 1, 464: 0, 466: 0, 469: 0, 478: 0, 481: 0, 489: 0, 522: 0, 525: 0, 538: 0, 543: 1, 544: 1, 554: 1, 555: 0, 565: 0, 590: 1, 591: 0, 600: 0, 601: 0, 605: 0, 607: 0, 612: 1, 613: 0, 615: 0, 617: 0, 619: 1, 620: 1, 621: 0}
num_colors = [W*[None] for _ in range(H)]
for y in range(H):
for x in range(W):
if MODE in (MODE_MIN_COLORS, MODE_5_COLORS_MAX, MODE_4_COLORS):
num_colors[y][x] = couleur_region[region_ids[y][x]]
elif MODE == MODE_LETTER_COLORS:
num_colors[y][x] = ord(grid[y][x]) - ord('A')
else:
num_colors[y][x] = region_ids[y][x]
# Affichage dans le terminal
if True or (MODE in (MODE_MIN_COLORS, MODE_5_COLORS_MAX, MODE_4_COLORS)):
RESET = '\033[0m'
BOLD = '\033[01m'
BLACK = '\033[40m'
DISABLE = '\033[02m'
def term_coloring(text, color_number):
RED = '\033[41m'
GREEN = '\033[42m'
ORANGE = '\033[43m'
BLUE = '\033[44m'
PURPLE = '\033[45m'
CYAN = '\033[46m'
LIGHTGREY = '\033[47m'
TERM_COLORS = [GREEN, BLUE, ORANGE, PURPLE, RED, CYAN, LIGHTGREY]
return TERM_COLORS[color_number % len(TERM_COLORS)] + text + RESET
if BORDERS:
print(BLACK + ((2*W + 1) * LARGEUR_AFFICHAGE_TERMINAL) * ' ' + RESET)
for y in range(H):
for x in range(W):
reg_id = region_ids[y][x]
num_col = num_colors[y][x]
if x > 0 and region_ids[y][x-1] == reg_id:
print(term_coloring((2*LARGEUR_AFFICHAGE_TERMINAL)*' ', num_col), end='')
else:
print(BLACK + LARGEUR_AFFICHAGE_TERMINAL*'|' + term_coloring(LARGEUR_AFFICHAGE_TERMINAL*' ', num_col), end='')
print(BLACK + LARGEUR_AFFICHAGE_TERMINAL*'|' + RESET)
for x in range(W):
reg_id = region_ids[y][x]
num_col = num_colors[y][x]
if x > 0 and region_ids[y][x-1] == reg_id and y < H - 1 and region_ids[y+1][x] == reg_id and region_ids[y+1][x-1] == reg_id:
print(term_coloring(LARGEUR_AFFICHAGE_TERMINAL*' ', num_col), end='')
else:
print(BLACK + LARGEUR_AFFICHAGE_TERMINAL*'-' + RESET, end='')
if y < H-1 and region_ids[y+1][x] == reg_id:
print(term_coloring(LARGEUR_AFFICHAGE_TERMINAL*' ', num_col), end='')
else:
print(BLACK + LARGEUR_AFFICHAGE_TERMINAL*'-' + RESET, end='')
print(BLACK + LARGEUR_AFFICHAGE_TERMINAL*'|')
print(BOLD + BLACK + '+' + ((2*LARGEUR_AFFICHAGE_TERMINAL)*W - 1) * '=' + '+' + RESET)
else: # c'est quand même beaucoup plus simple sans les bords… ><
for y in range(H):
for x in range(W):
reg_id = region_ids[y][x]
num_col = num_colors[y][x]
print(term_coloring(LARGEUR_AFFICHAGE_TERMINAL*' ', num_col), end='')
print()
def make_26_colors():
col_paliers = [0.5, 0.75,1]
couls = [(r,g,b) for r in col_paliers for g in col_paliers for b in col_paliers]
couls.remove((1, 1, 1)) # no white
#shuffle(couls)
return couls
def make_63_colors():
col_paliers = [0.5, 0.5 + 1/6, 0.5 + 2/6, 1]
couls = [(r,g,b) for r in col_paliers for g in col_paliers for b in col_paliers]
couls.remove((1, 1, 1)) # no white
shuffle(couls)
return couls
if MODE == MODE_LETTER_COLORS:
COLORS = make_26_colors()
elif MODE == MODE_63_COLORS:
COLORS = make_63_colors()
else:
COLORS = [[c/255 for c in coul] for coul in ((127,201,127), (190,174,212), (253,192,134), (255,255,153), (56,108,176), (240,2,127))] # thank you https://colorbrewer2.org !
PIXELS = SIZE_WINDOW // (2*max(W,H+00)) * 2
OFFSET_TURTLE = (-W*PIXELS / 2, -H*PIXELS / 2)
turtle.speed(1000)
turtle.tracer(30*W)
turtle.hideturtle()
def draw_square(x, y):
turtle.teleport(x-PIXELS//2, y-PIXELS//2)
turtle.begin_fill()
for _ in range(4):
turtle.forward(PIXELS)
turtle.left(90)
turtle.end_fill()
if MODE == MODE_LETTER_COLORS:
turtle.teleport(OFFSET_TURTLE[0], OFFSET_TURTLE[1] - 20)
#turtle.forward(-2*OFFSET_TURTLE[0])
#turtle.forward(2*OFFSET_TURTLE[0])
turtle.up()
for i,coul in enumerate(COLORS):
turtle.dot(18, 'black')
turtle.dot(16, coul)
turtle.forward(1)
turtle.right(90)
turtle.forward(6)
turtle.write(chr(ord('A') + i), align="center")
turtle.forward(-6)
turtle.left(90)
turtle.forward((-2)*OFFSET_TURTLE[0] / (len(COLORS) - 1) - 1)
turtle.color('black')
for y in range(H):
for x in range(W):
color = COLORS[num_colors[y][x] % len(COLORS)]
if DOTS:
turtle.teleport(OFFSET_TURTLE[0] + x * PIXELS, OFFSET_TURTLE[1] + y * PIXELS)
turtle.dot(PIXELS, color)
else:
turtle.color(color)
draw_square(OFFSET_TURTLE[0] + x * PIXELS, OFFSET_TURTLE[1] + y * PIXELS)
pass # TOO
turtle.update()
if BORDERS:
turtle.down()
turtle.color('black')
for region_borders in borders:
for (x,y),(dx,dy) in region_borders:
if dx < 0 or dy < 0:
continue
vertical = (dx == 0)
if vertical:
turtle.teleport(OFFSET_TURTLE[0] + (x-0.5)*PIXELS, OFFSET_TURTLE[1] + (y+0.5)*PIXELS)
turtle.goto(OFFSET_TURTLE[0] + (x+0.5)*PIXELS, OFFSET_TURTLE[1] + (y+0.5)*PIXELS)
else:
turtle.teleport(OFFSET_TURTLE[0] + (x+0.5)*PIXELS, OFFSET_TURTLE[1] + (y-0.5)*PIXELS)
turtle.goto(OFFSET_TURTLE[0] + (x+0.5)*PIXELS, OFFSET_TURTLE[1] + (y+0.5)*PIXELS)
#turtle.update()
turtle.teleport(OFFSET_TURTLE[0] - PIXELS/2, OFFSET_TURTLE[1] + H * PIXELS - PIXELS/2 - 1)
turtle.goto(OFFSET_TURTLE[0] - PIXELS/2, OFFSET_TURTLE[1] - PIXELS/2)
turtle.goto(OFFSET_TURTLE[0] + W * PIXELS - PIXELS/2, OFFSET_TURTLE[1] - PIXELS/2)
turtle.update()
turtle.done()
