◂ 23 décembre 2023 ▸
A Long Walk : Trouver parcours le plus long sans repasser par le même chemin
#.################## …
#.#...#...#......... …
#.#.#.#.#.#.#######. …
#.#.#...#.#.......#. …
#.#.#####.#######.#. …
#.#.#.....#...#...#. …
#.#.#.#####.#.#.###. …
#.#.#...#...#.#...#. …
#.#.###.#.###v###.## …
#...###.#.###.>.#... …
#######.#.###v#.###. …
#.......#.#...#...#. …
⋮
- code.py
- code1_lent.py
- soluceGraphe1.png
- soluceGraphe2.png
- grapheurCodePourri.py
import time, math
from random import random
from itertools import pairwise
auto = False
from tkinter import *
fen = Tk()
HEIGHT=900
WIDTH=1000
ZOOM = 3
canvas = Canvas(fen, bg='white', height=HEIGHT, width=WIDTH)
canvas.pack(side=TOP)
outline='black'
width=2
color='black'
def line(q1, q2):
global canvas, width, color
canvas.create_line(q1[0], q1[1], q2[0], q2[1], width=width, fill=color)
def texte(p, texte):
global canvas
canvas.create_text(p[0] - 20, p[1] - 10, anchor=W, font="Purisa", text=texte)
def cercle(centre, rayon):
global canvas, width, color, outline
q = centre
canvas.create_oval(q[0] - rayon, q[1] - rayon, q[0] + rayon, q[1] + rayon, width=width, fill=color, outline=outline)
def effacerCanvas():
global canvas
canvas.delete(ALL)
verts = set()
#for i,j in pairwise( [0, 4, 12, 16, 23, 25,37,33, 34, 26, 29, 22, 20, 15, 7, 11, 2, 3, 6, 8, 13, 24, 19, 14, 9, 5,36,10, 17, 21, 28, 30, 27, 31, 35, 32, 1]):
for i,j in pairwise( [0,4,12,16,23,25,37,33,34,26,20,22,18,15,7,11,2,3,6,8,13,24,19,14,9,5,36,10,17,21,28,30,27,31,35,32,1] ):
verts.update([(i,j), (j,i)])
fixes = {0:(60,160), 1:(300,160)}
base = {
0:[(101, 4)],
1:[(147, 32)],
2:[(174, 11), (194, 3), (100, 4)],
3:[(152, 7), (172, 6), (194, 2)],
4:[(280, 12), (101, 0), (100, 2)],
5:[(164, 9), (264, 36), (102, 6)],
6:[(108, 8), (102, 5), (172, 3)],
7:[(180, 15), (152, 3), (48, 8), (232, 11)],
8:[(154, 13), (108, 6), (166, 9), (48, 7)],
9:[(112, 14), (164, 5), (112, 10), (166, 8)],
10:[(240, 17), (264, 36), (112, 9)],
11:[(172, 18), (174, 2), (232, 7), (62, 12)],
12:[(184, 16), (280, 4), (62, 11)],
13:[(194, 24), (154, 8), (104, 14), (138, 15)],
14:[(78, 19), (112, 9), (88, 17), (104, 13)],
15:[(168, 20), (180, 7), (138, 13), (156, 18)],
16:[(230, 23), (184, 12), (114, 18)],
17:[(206, 21), (240, 10), (88, 14)],
18:[(110, 22), (172, 11), (156, 15), (114, 16)],
19:[(140, 30), (78, 14), (60, 21), (320, 24)],
20:[(84, 26), (168, 15), (76, 24), (130, 22)],
21:[(116, 28), (206, 17), (60, 19)],
22:[(94, 29), (110, 18), (130, 20), (86, 23)],
23:[(194, 25), (230, 16), (86, 22)],
24:[(76, 27), (194, 13), (320, 19), (76, 20)],
25:[(201, 37), (194, 23), (182, 29)],
26:[(166, 34), (84, 20), (80, 27), (88, 29)],
27:[(130, 31), (76, 24), (136, 30), (80, 26)],
28:[(104, 32), (116, 21), (164, 30)],
29:[(204, 33), (94, 22), (88, 26), (182, 25)],
30:[(104, 35), (140, 19), (164, 28), (136, 27)],
31:[(130, 27), (298, 35), (72, 34)],
32:[(147, 1), (104, 28), (188, 35)],
33:[(204, 29), (266, 34), (201, 37)],
34:[(166, 26), (72, 31), (266, 33)],
35:[(104, 30), (188, 32), (298, 31)],
36:[(264,5), (264,10)],
37:[(201,25), (201,33)],
}
aretes = {}
distances = {}
for k, v in base.items():
aretes[k] = [s for _,s in v]
distances[k] = dict([(s,d) for d,s in v])
noms = list(aretes.keys())
aretes2 = []
points = []
k = 0
listeNoms = []
for nom in noms:
k += 1
voisins = aretes[nom]
aretes2 += [ [ noms.index(voisins[i]) for i in range(len(voisins)) ] ]
points += [ [ WIDTH / 2 / ZOOM + WIDTH/2.2 / ZOOM * math.cos(2*math.pi * k / len(noms)), HEIGHT / 2 / ZOOM + HEIGHT/2.2/ZOOM * math.sin(2*math.pi * k / len(noms)) ] ]
if nom < 2:
nomV = ('START', 'END')[nom]
elif nom < 28:
nomV = chr(ord('A') + nom - 2)
else:
nomV = chr(ord('a') + nom - 28)
#listeNoms += [ nomV ]
#listeNoms += [ nom ]
listeNoms += [ '' ]
aretes = aretes2
points[0] = (10,10)
def zoom(p, x=None):
if x is not None:
p = [p, x]
return [v*ZOOM for v in p]
def dessiner(points, aretes, listeNoms):
global color
effacerCanvas()
for i in range(len(aretes)):
a = aretes[i]
for a2 in a:
color = 'red'
d = distances[i][a2]
global width
width = max(3, 2+int( (d-70) / 20 ))
if (i,a2) in verts:
color = 'green'
else:
color = 'red'
line(zoom(points[i]), zoom(points[a2]))
texte(zoom((points[i][0] + points[a2][0]) / 2, (points[i][1] + points[a2][1]) / 2), d)
for i in range(len(points)):
#for p in points:
p = zoom(points[i])
cercle(p, 5)
texte(p, listeNoms[i])
dessiner(points, aretes, listeNoms)
def animer():
global points, aretes, listeNoms, canvas, color, STOP
if STOP:
return
bouge = True
points2 = [ ]
bouge = False
for i in range(len(points)):
if i in fixes:
points2.append(fixes[i])
continue
dx = 0
dy = 0
px = points[i][0]
py = points[i][1]
for j in range(len(points)):
if i == j:
continue
dpx = (px - points[j][0])
dpy = (py - points[j][1])
d = dpx**2 + dpy**2 + 0.0000001
#print("aretes:", aretes[i])
if (j in aretes[i]):
f = min(50, max(0, (1*d - 150))) / 10
m = (dpx == 0 and 1 or (dpy * 1. / dpx))
fx = f * (dpx > 0 and 1 or -1 ) / math.sqrt(1+m*m)
#line((px, py), (px-fx, py-fx*m))
dx -= fx
dy -= m * fx
f = min(5, max(0, (2000 - d)))
m = (dpx == 0 and 1 or (dpy * 1. / dpx))
fx = f * (dpx > 0 and 1 or -1 ) / math.sqrt(1+m*m)
color='green'
line((px, py), (px+fx, py+fx*m))
dx += fx
dy += m * fx
if dx*dx + dy*dy > 2:
bouge = True
#print(i, "bouge de", dx, dy, ". Bouge :", (bouge and 'oui' or 'non'))
points2 += [ [ px + dx, py + dy] ]
points = points2
color='black'
dessiner(points, aretes, listeNoms)
if bouge:
canvas.after(1, animer)
bou = Button(fen, text='Quitter', command=fen.destroy)
bou.pack(side=LEFT)
affichage = Label(fen, text='Couleur : ', fg='Black')
affichage.pack()
def clic(event):
global points, clicPoint, auto
if event.x > WIDTH - 100 and event.y > HEIGHT - 100:
for i,p in enumerate(points):
points[i] = grille(*p)
dessiner(points, aretes, listeNoms)
return
if auto:
animer()
return
clicPoint = trouverPoint(points, event.x, event.y)
#if clicPoint == None:
# clicPoint = ajouterPoint(points, event.x, event.y)
def mouseDouble(event):
global points, clicPoint, STOP
if STOP:
STOP = False
animer()
else:
STOP = True
#clicPoint = trouverPoint(points, event.x, event.y)
#if clicPoint != None:
# points.pop(clicPoint)
# clicPoint = None
# rafraichir(points)
def dist(x1, y1, x2, y2):
return math.sqrt((x1-x2)**2 + (y1-y2)**2)
def trouverPoint(points, x, y):
for i in range(len(points)):
if dist(points[i][0]*ZOOM, points[i][1]*ZOOM, x, y) < 8:
return i
return None
def grille(x,y):
return [ round(v/20)*20 for v in (x,y)]
clicPoint = None
def mouseMoved(event):
global points, aretes, listeNoms, clicPoint, auto
if auto:
return
if clicPoint == None:
return
points[clicPoint] = grille(event.x/ZOOM, event.y/ZOOM)
### while (clicPoint > 1 and points[clicPoint][0] < points[clicPoint-1][0]):
### (points[clicPoint], points[clicPoint - 1]) = (points[clicPoint - 1], points[clicPoint])
### clicPoint -= 1
### while (clicPoint < len(points) - 1 and points[clicPoint][0] > points[clicPoint+1][0]):
### (points[clicPoint], points[clicPoint + 1]) = (points[clicPoint + 1], points[clicPoint])
### clicPoint += 1
#rafraichir(points)
dessiner(points, aretes, listeNoms)
def mouseReleased(event):
global clicPoint
clicPoint = None
canvas.bind("<Button-1>", clic)
canvas.bind("<Motion>", mouseMoved)
canvas.bind("<ButtonRelease-1>", mouseReleased)
canvas.bind("<Double-Button-1>", mouseDouble)
STOP = True
fen.mainloop()
if auto:
animer()
