You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
288 lines
9.1 KiB
288 lines
9.1 KiB
#!/usr/bin/env python3
|
|
#(height, width)
|
|
import random as rnd
|
|
import os
|
|
# import sys
|
|
import itertools
|
|
from enum import Enum
|
|
import time
|
|
import math
|
|
from queue import PriorityQueue as pq
|
|
from intervaltree import IntervalTree as itree
|
|
|
|
# DEBUG=True
|
|
DEBUG=False
|
|
|
|
class SquareType(Enum):
|
|
AISLE = 0
|
|
SEAT = 1
|
|
WALL = 2
|
|
|
|
height=0
|
|
width=0
|
|
|
|
grid=[]
|
|
# entries=[(3,0)]
|
|
entries=[(0,3)]
|
|
# entries=[(7,3),(7,43)]
|
|
# entries=[(7,3)]
|
|
|
|
tickTaken = 0
|
|
|
|
passengers = None
|
|
|
|
class GridSquare:
|
|
#typ: SquareType
|
|
def __init__(self, typ):
|
|
self.typ = typ
|
|
#occupAtTick is an interval tree, stores intervals where the gridSquare is occupied
|
|
#intervals are [a,b), a nice sane choice
|
|
#values are individuals
|
|
self.occupAtTick = itree()
|
|
|
|
class Passenger:
|
|
#dest and curr are both 2-tuples
|
|
def __init__(self, dest, curr):
|
|
self.dest = dest
|
|
self.curr = curr
|
|
self.inter = None
|
|
#Path is composed of tuples: (pos, t)
|
|
self.path = []
|
|
def __str__(self):
|
|
return "(%s|%s)" % (dest, curr)
|
|
|
|
def mooreNeighbourhood(pos):
|
|
return [i for i in [(pos[0]+1, pos[1]), (pos[0], pos[1]+1), (pos[0]-1, pos[1]), (pos[0], pos[1]-1)] if
|
|
i[0] >= 0 and i[1] >= 0 and i[0] < height and i[1] < width]
|
|
|
|
def findPath(passenger, pid, currTick):
|
|
global passengers
|
|
global grid
|
|
|
|
#used when moving into seats
|
|
afterTick = 0
|
|
|
|
dest = passenger.inter
|
|
|
|
#Element format: (Tick at time of movement, Position, Time stayed in previous square)
|
|
q = pq()
|
|
|
|
time=[[10**10 for x in range(0,width)] for y in range(0,height)]
|
|
prev=[[None for x in range(0,width)] for y in range(0,height)]
|
|
|
|
time[passenger.curr[0]][passenger.curr[1]]=currTick
|
|
|
|
q.put((currTick, passenger.curr, 1))
|
|
|
|
while not q.empty():
|
|
u = q.get()
|
|
if u[1] == dest:
|
|
grid[u[1][0]][u[1][1]].occupAtTick.addi(u[0],u[0]+3,pid)
|
|
afterTick = u[0]+2
|
|
# passenger.path.append((u[1], u[0]))
|
|
u=prev[u[1][0]][u[1][1]]
|
|
while prev[u[1][0]][u[1][1]] != None:
|
|
grid[u[1][0]][u[1][1]].occupAtTick.addi(u[0],u[0]+u[2],pid)
|
|
# passenger.path.append((u[1], u[0]))
|
|
u=prev[u[1][0]][u[1][1]]
|
|
# passenger.path.append((passenger.curr, currTick))
|
|
break
|
|
#The Art of Standing Still
|
|
q.put((u[0] + 1, u[1], 1))
|
|
for x in mooreNeighbourhood(u[1]):
|
|
alt = 0
|
|
if grid[x[0]][x[1]].typ == SquareType.SEAT:
|
|
if ( not (grid[u[1][0]][u[1][1]].typ == SquareType.AISLE and u[1][1] != x[1]) and
|
|
len(grid[x[0]][x[1]].occupAtTick[u[0]:u[0]+5-1]) == 0):
|
|
alt = time[u[1][0]][u[1][1]] + 5
|
|
if alt < time[x[0]][x[1]]:
|
|
time[x[0]][x[1]] = alt
|
|
prev[x[0]][x[1]] = u
|
|
q.put((alt, x, 5))
|
|
else:
|
|
continue
|
|
elif grid[x[0]][x[1]].typ == SquareType.AISLE:
|
|
if len(grid[x[0]][x[1]].occupAtTick[u[0]+1:u[0]+1+1]) == 0:
|
|
alt = time[u[1][0]][u[1][1]] + 1
|
|
if alt < time[x[0]][x[1]]:
|
|
time[x[0]][x[1]] = alt
|
|
prev[x[0]][x[1]] = u
|
|
q.put((alt, x, 1))
|
|
else:
|
|
continue
|
|
else:
|
|
continue
|
|
|
|
#Supposed to do the big shuffly once they get to the aisle in front of their seat, doesn't work for innermost?
|
|
dest = passenger.dest
|
|
moveDir = None
|
|
if dest[0] > passenger.inter[0]:
|
|
moveDir = -1
|
|
else:
|
|
moveDir = 1
|
|
mDone=False
|
|
while not mDone:
|
|
mDone = True
|
|
u=passenger.dest
|
|
while u != passenger.inter:
|
|
occup = list(grid[u[0]+moveDir][u[1]].occupAtTick[afterTick:afterTick+5])
|
|
if len(occup) != 0:
|
|
if (moveDir == 1 and passengers[occup[0][2]].dest < u) or (moveDir == -1 and passengers[occup[0][2]].dest > u):
|
|
mDone=False
|
|
occup2 = list(grid[u[0]][u[1]].occupAtTick[afterTick:afterTick+5])
|
|
if len(occup2) != 0:
|
|
grid[u[0]+moveDir][u[1]].occupAtTick.addi(occup[0][0], afterTick, occup[0][2])
|
|
grid[u[0]+moveDir][u[1]].occupAtTick.remove(occup[0])
|
|
grid[u[0]][u[1]].occupAtTick.addi(occup2[0][0], afterTick, occup2[0][2])
|
|
grid[u[0]][u[1]].occupAtTick.remove(occup2[0])
|
|
grid[u[0]+moveDir][u[1]].occupAtTick.addi(afterTick,10**11,occup2[0][2])
|
|
grid[u[0]][u[1]].occupAtTick.addi(afterTick,10**11,occup[0][2])
|
|
else:
|
|
grid[u[0]+moveDir][u[1]].occupAtTick.addi(occup[0][0], afterTick, occup[0][2])
|
|
grid[u[0]+moveDir][u[1]].occupAtTick.remove(occup[0])
|
|
grid[u[0]][u[1]].occupAtTick.addi(afterTick,10**11,occup[0][2])
|
|
u = (u[0] + moveDir, u[1])
|
|
afterTick+=4
|
|
|
|
def printPath(p):
|
|
print("inter: " + str(p.inter))
|
|
print("dest: " + str(p.dest))
|
|
for x in p.path:
|
|
print(str(x[0]) + ": " + str(grid[x[0][0]][x[0][1]].occupAtTick[x[1]]))
|
|
|
|
btime = 3 #passengers board every btime ticks
|
|
delay = 0.01
|
|
|
|
#Precomputation of all paths, later code is just output functionality
|
|
def compute():
|
|
global btime
|
|
global passengers
|
|
global tickTaken
|
|
tick=0
|
|
toadd=0
|
|
#genderequality #blm #blessed #syria
|
|
for (i, prsn) in enumerate(passengers):
|
|
for e in entries:
|
|
if toadd < len(passengers) and len(grid[e[0]][e[1]].occupAtTick[tick]) == 0:
|
|
prsn.curr = (e[0], e[1])
|
|
findPath(prsn, i, tick)
|
|
if DEBUG:
|
|
print("calculating: " + str(i))
|
|
tick += btime
|
|
toadd += 1
|
|
else:
|
|
tick += 1
|
|
|
|
for row in grid:
|
|
for x in row:
|
|
# print(x.occupAtTick)
|
|
if len(x.occupAtTick) != 0:
|
|
# print("list(x.occupAtTick.items)[-1][0]: " + str(list(x.occupAtTick.items())[-1][0]))
|
|
tickTaken = max(tickTaken, list(x.occupAtTick.items())[-1][0])
|
|
print("Time Taken: " + str(tickTaken))
|
|
|
|
def tick(t):
|
|
done=True
|
|
global btime
|
|
global delay
|
|
# print grid
|
|
if DEBUG:
|
|
print(chr(0x3000), end="")
|
|
print(chr(0x3000), end="")
|
|
for x in range(0, width):
|
|
if x % 10 == 0:
|
|
print(chr(0xFF10 + int(x / 10)), end="")
|
|
else:
|
|
print(chr(0x3000), end="")
|
|
print()
|
|
print(chr(0x3000), end="")
|
|
print(chr(0x3000), end="")
|
|
for x in range(0, width):
|
|
print(chr(0xFF10 + (x % 10)), end="")
|
|
print()
|
|
for (i, row) in enumerate(grid):
|
|
if i % 10 == 0:
|
|
print(chr(0xFF10 + int(i / 10)), end="")
|
|
else:
|
|
print(chr(0x3000), end="")
|
|
print(chr(0xFF10 + (i % 10)), end="")
|
|
|
|
for guy in row:
|
|
if len(guy.occupAtTick[t]) != 0:
|
|
print(chr(0x20000 + list(guy.occupAtTick[t])[0][2]), end="")
|
|
elif guy.typ == SquareType.SEAT:
|
|
print("：", end="")
|
|
elif guy.typ == SquareType.WALL:
|
|
print("Ｗ", end="")
|
|
else:
|
|
print("＿", end="")
|
|
print()
|
|
print("---")
|
|
printPath(passengers[2])
|
|
if DEBUG:
|
|
# time.sleep(1.0)
|
|
# time.sleep(0.5)
|
|
# time.sleep(0.1)
|
|
time.sleep(0.05)
|
|
# time.sleep(0.02)
|
|
# time.sleep(0.01)
|
|
# time.sleep(0.001)
|
|
os.system("clear")
|
|
|
|
def init():
|
|
global height
|
|
global width
|
|
global grid
|
|
global passengers
|
|
passengers = []
|
|
arrFile = open("figure2.txt")
|
|
|
|
height=int(arrFile.readline())
|
|
width=int(arrFile.readline())
|
|
print(height)
|
|
print(width)
|
|
|
|
grid = [[GridSquare(SquareType.AISLE) for x in range(0,width)] for y in range(0,height)]
|
|
|
|
for y in range(0,height):
|
|
for x in range(0,width+1):
|
|
char = arrFile.read(1);
|
|
match char:
|
|
case 'S':
|
|
grid[y][x].typ = SquareType.SEAT
|
|
passengers.append(Passenger((y,x),(-1,-1)))
|
|
case 'W':
|
|
grid[y][x].typ = SquareType.WALL
|
|
case '.':
|
|
grid[y][x].typ = SquareType.AISLE
|
|
|
|
for x in passengers:
|
|
sign=(-1)**rnd.randint(0,1)
|
|
for i in range(1,7):
|
|
inc = (-1)**i * sign * math.floor((i+1)/2)
|
|
if (inc + x.dest[0] > 0) and (inc + x.dest[0] < height) and (grid[x.dest[0]+inc][x.dest[1]].typ == SquareType.AISLE):
|
|
x.inter=(inc + x.dest[0], x.dest[1])
|
|
break
|
|
|
|
def run(end):
|
|
t = 0
|
|
while t < end:
|
|
tick(t)
|
|
t += 1
|
|
|
|
def main():
|
|
global passengers
|
|
#boarding order
|
|
|
|
# seediter = int(sys.argv[1])
|
|
for seediter in range(55,2000):
|
|
init()
|
|
print("Seed: " + str(seediter))
|
|
rnd.seed(seediter)
|
|
# passengers.reverse()
|
|
rnd.shuffle(passengers)
|
|
compute()
|
|
# run(tickTaken)
|
|
|
|
if __name__ == "__main__":
|
|
main()
|
|
|