p1/09_kontrola/naloga.py
2023-12-28 11:51:59 +01:00

198 lines
5.3 KiB
Python

from itertools import groupby
import operator
from os import path
from collections import Counter
import re
def preberi_zemljevid(ime_dat: str):
directory = path.dirname(path.abspath(__file__))
file = open(path.join(directory, ime_dat))
return file.read().strip().split("\n")
def check(x: int, y: int, c: str, zemljevid: list[str], prepovedani: set = None):
if prepovedani is None:
prepovedani = set()
return (
(x, y) not in prepovedani
and 0 <= y < len(zemljevid)
and 0 <= x < len(zemljevid[0])
and (c == "" and zemljevid[y][x] != "." or zemljevid[y][x] == c)
)
def najblizji_distance(x: int, y: int, c: str, zemljevid: list[str], prepovedani: set = None):
d = 1
max_d = len(zemljevid) + len(zemljevid[0])
while d <= max_d:
x -= 1
ry = 0
ry_inc = 1
for rx in range(d * 2 + 1):
if check(x + rx, y - ry, c, zemljevid, prepovedani):
return x + rx, y - ry, d
if check(x + rx, y + ry, c, zemljevid, prepovedani):
return x + rx, y + ry, d
if ry == d:
ry_inc = -1
ry += ry_inc
d += 1
def najblizji(x: int, y: int, c: str, zemljevid: list[str], prepovedani: set = None):
if prepovedani is None:
prepovedani = set()
res = najblizji_distance(x, y, c, zemljevid, prepovedani)
if res is None:
return
return res[0], res[1]
def najpogostejsi(x, y, d, zemljevid):
chars = []
for y2, line in enumerate(zemljevid):
for x2, val in enumerate(line):
if abs(x - x2) + abs(y - y2) <= d and val != ".":
chars.append(val)
if len(chars) == 0:
return None
m, _ = max(Counter(sorted(chars)).items(), key=operator.itemgetter(1))
return m
def vsi_najpogostejsi(x, y, d, zemljevid):
chars = []
for y2, line in enumerate(zemljevid):
for x2, val in enumerate(line):
if abs(x - x2) + abs(y - y2) <= d and val != ".":
chars.append(val)
if len(chars) == 0:
return set()
a = [(k, list(v)) for (k, v) in
groupby(sorted(Counter(chars).items(), key=operator.itemgetter(1)), key=operator.itemgetter(1))]
_, c = max(sorted(a))
return set(k for (k, v) in c)
def angelca(x, y, znamenitosti, zemljevid):
prepovedani = set()
distance = 0
for znam in znamenitosti:
res = najblizji_distance(x, y, znam, zemljevid, prepovedani)
if res is None:
return distance
prepovedani.add((x, y))
x, y, d = res
distance += d
return distance
def johanca(x, y, pot, zemljevid):
znamenitosti = []
obiskane = set()
for match in re.finditer("([0-9]*)([<>v^])", pot):
dist, dir = match.groups()
dist = int(dist) if dist != "" else 1
match dir:
case "^":
y -= dist
case "v":
y += dist
case "<":
x -= dist
case ">":
x += dist
if (
(x, y) not in obiskane
and 0 <= y < len(zemljevid)
and 0 <= x < len(zemljevid[0])
and zemljevid[y][x] != "."
):
obiskane.add((x, y))
znamenitosti.append(zemljevid[y][x])
return "".join(znamenitosti)
def najboljsa_cetrt(a: int, zemljevid: list[str]):
x_len = len(zemljevid[0]) - a + 1
y_len = len(zemljevid) - a + 1
y_len = y_len if y_len > 0 else 1
max_count = 0
max_x = 0
max_y = 0
for x in range(x_len):
for y in range(y_len):
count = 0
for ry in range(a):
for rx in range(a):
if zemljevid[y + ry][x + rx] != ".":
count += 1
if count > max_count:
max_count = count
max_x = x
max_y = y
return max_x, max_y
def dosegljive(x, y, max_d, max_n, zemljevid):
def dosegljive_r(x, y, n, prepovedani):
if zemljevid[y][x] == "*":
n = max_n
else:
prepovedani.add((x, y))
prepovedani = prepovedani.copy()
accessible = set()
for d in range(1, max_d + 1):
x -= 1
ry = 0
ry_inc = 1
for rx in range(d * 2 + 1):
xx = x + rx
y1 = y - ry
y2 = y + ry
if check(xx, y1, "", zemljevid, prepovedani) and (zemljevid[y1][xx] != "*" or n < max_n):
accessible.add((xx, y1))
if check(xx, y2, "", zemljevid, prepovedani) and (zemljevid[y2][xx] != "*" or n < max_n):
accessible.add((xx, y2))
if ry == d:
ry_inc = -1
ry += ry_inc
if n == 0:
if any(zemljevid[y][x] == "*" for x, y in accessible):
accessible = {(x, y) for x, y in accessible if zemljevid[y][x] == "*"}
else:
return set()
points = set(accessible)
for x, y in accessible:
points.update(dosegljive_r(x, y, n - 1, prepovedani))
return points
tocke = dosegljive_r(x, y, max_n, set())
return {(x, y) for x, y in tocke if zemljevid[y][x] != "*"}