Einföld forritunar- og rökverkefni

Í mörgum Misc-verkefnum er enginn falinn skráarhaus og ekkert sérstakt öryggistól. Við fáum reglur, inntak og spurningu. Lausnin felst í að breyta lýsingunni í nákvæmt reiknirit.

Dæmi:

• fylgja vélmenni eftir korti,
• herma eftir lítilli vél,
• prófa afmarkað mengi talna,
• finna stystu leið í reitaneti,
• raða hlutum samkvæmt skilyrðum,
• lesa sérkennilegt inntak og reikna lokaástand.

Við byrjum gjarnan í höndunum. Þegar mynstrið endurtekur sig eða leitarrýmið stækkar skrifum við lítið, prófanlegt forrit.

Breytum lýsingu í samning

Áður en við forritum skrifum við niður:

1. Inntak: Hvaða gögn fáum við og á hvaða sniði?
2. Úttak: Hvaða nákvæmu niðurstöðu eigum við að skila?
3. Reglur: Hvað gerist í hverju skrefi?
4. Upphafsástand: Hvar byrjar ferlið?
5. Mörk: Hve stórt getur inntakið orðið?
6. Sértilvik: Hvað gerist við tómt inntak, jafntefli eða ógilda skipun?
7. Sýnidæmi: Passar túlkun okkar við dæmið í verkefninu?

Lýsingin:

Vélmenni byrjar í (0, 0) og horfir norður. Hver skipun er beygja L eða R og síðan fjöldi skrefa.

verður að samningi:

R2 = beygja til hægri, ganga síðan tvö skref
L3 = beygja til vinstri, ganga síðan þrjú skref

Möguleg óvissa sem við þurfum að leysa:

• Beygir vélmennið fyrir eða eftir gönguna?
• Má fjöldinn vera 0?
• Má hann vera neikvæður?
• Fer eitt skref yfir einn reit?
• Eru hindranir eða mörk á kortinu?

Við giskum ekki ef sýnidæmi eða verkefnahöfundur getur skýrt regluna.

Handreikningur sem fyrsta próf

Fyrir skipanirnar:

R2,L3,L1

fáum við:

Manhattan-fjarlægðin frá upphafi er:

|1| + |3| = 4

Þessi litla tafla verður prófunartilvik fyrir forritið okkar.

Æfing: túlkaðu reglurnar

L2,R1,R3

|1| + |1| = 2

Eftirlíking og ástand

Eftirlíking (e. simulation) framkvæmir reglur skref fyrir skref á líkani af ástandinu.

Fyrir vélmennið er ástandið:

(x, y, stefna)

Við getum geymt stefnur í hring:

stefnur = ["N", "E", "S", "W"]

Hægri beygja hækkar vísinn um 1 og vinstri lækkar hann um 1, með modulo 4:

stefna = (stefna + 1) % 4   # hægri
stefna = (stefna - 1) % 4   # vinstri

Heilt forrit:

import re

stefnur = ["N", "E", "S", "W"]
hreyfing = {
    "N": (0, 1),
    "E": (1, 0),
    "S": (0, -1),
    "W": (-1, 0),
}

x, y = 0, 0
stefna = 0

for skipun in "R2,L3,L1".split(","):
    m = re.fullmatch(r"([LR])([0-9]+)", skipun)
    if not m:
        raise ValueError(f"Ógild skipun: {skipun!r}")

    beygja, skref_texti = m.groups()
    skref = int(skref_texti)

    stefna = (stefna + (1 if beygja == "R" else -1)) % 4
    dx, dy = hreyfing[stefnur[stefna]]
    x += dx * skref
    y += dy * skref

print(x, y)
print(abs(x) + abs(y))

Úttak:

1 3
4

Við notum fullmatch() svo R2rusl verði ekki samþykkt sem R2.

Endanleg stöðuvél

Endanleg stöðuvél (e. finite-state machine) hefur afmarkað mengi stöðva og reglur um hvernig inntak flytur hana á milli þeirra.

Dæmi um hurð:

stöður: LÆST, OPIÐ
inntak: lykill, ýta, loka

Python:

yfirfaerslur = {
    ("LÆST", "lykill"): "OPIÐ",
    ("LÆST", "ýta"): "LÆST",
    ("OPIÐ", "loka"): "LÆST",
    ("OPIÐ", "ýta"): "OPIÐ",
}

stada = "LÆST"

for inntak in ["ýta", "lykill", "ýta", "loka"]:
    lykill = (stada, inntak)
    if lykill not in yfirfaerslur:
        raise ValueError(f"Óskilgreint skref: {lykill}")
    stada = yfirfaerslur[lykill]

print(stada)

Taflan gerir óskilgreind tilvik sýnileg. Við þurfum að ákveða hvort þau séu villa, engin breyting eða sérstök tapstaða.

Æfing: fylgdu stöðuvélinni

lykill, ýta, loka, ýta, lykill

Þrautleit í litlu leitarrými

Þrautleit (e. brute-force search) prófar frambjóðendur kerfisbundið. Hún er skynsamleg þegar leitarrýmið er lítið og reglurnar ódýrar í prófun.

Þriggja stafa PIN frá 000 til 999 hefur aðeins 1.000 möguleika. Segjum að reglurnar séu:

• stafirnir þrír eru ólíkir,
• summa þeirra er 12,
• fyrsti stafur er tvöfaldur sá síðasti,
• talan er deilanleg með 7.

lausnir = []

for tala in range(1000):
    texti = f"{tala:03d}"
    a, b, c = map(int, texti)

    if len({a, b, c}) != 3:
        continue
    if a + b + c != 12:
        continue
    if a != 2 * c:
        continue
    if tala % 7 != 0:
        continue

    lausnir.append(texti)

print(lausnir)

['462']

Við látum fremstu núll ekki hverfa með f"{tala:03d}".

Æfing: rétt eða of stórt leitarrými?

itertools fyrir samantektir og umröðun

Python getur myndað frambjóðendur án margra handskrifaðra lykkja.

Allar fjögurra bita runur:

from itertools import product

for bitar in product("01", repeat=4):
    print("".join(bitar))

Allar raðanir þriggja ólíkra stafa:

from itertools import permutations

for rod in permutations("ABC"):
    print("".join(rod))

• product() leyfir endurtekningu,
• permutations() velur röð án endurtekningar.

Við veljum fallið eftir reglum verkefnisins. Að nota permutations() þegar endurtekning er leyfð sleppir gildum lausnum.

Skilyrðagátur

Segjum að Anna, Bjarni og Katla sitji í sætum 1–3:

• Anna situr ekki í sæti 1,
• Katla situr hægra megin við Bjarna,
• Bjarni situr ekki í sæti 2.

Við getum prófað allar sex raðanir:

from itertools import permutations

for rod in permutations(["Anna", "Bjarni", "Katla"]):
    saeti = {nafn: nr for nr, nafn in enumerate(rod, start=1)}

    if saeti["Anna"] == 1:
        continue
    if saeti["Katla"] <= saeti["Bjarni"]:
        continue
    if saeti["Bjarni"] == 2:
        continue

    print(rod)

Úttakið getur innihaldið fleiri en eina röð ef skilyrðin ákvarða ekki einkvæma lausn. Það er mikilvæg niðurstaða: við finnum ekki upp nýtt skilyrði til að fá eitt svar.

Leiðir í reitaneti

Kort:

S..#
.#..
..#G
....

• S er upphaf,
• G er mark,
• # er veggur,
• . er opinn reitur.

Ef hvert skref upp, niður, vinstri eða hægri kostar eitt finnum við stystu leið með þverleit (e. breadth-first search, BFS).

Þverleit skoðar fyrst alla reiti í fjarlægð 1, síðan fjarlægð 2 og svo framvegis. Fyrsta skipti sem hún nær markinu hefur hún fundið stystu leið í óvigtuðu neti.

from collections import deque

kort = [
    "S..#",
    ".#..",
    "..#G",
    "....",
]

haed = len(kort)
breidd = len(kort[0])

for y, lina in enumerate(kort):
    for x, stafur in enumerate(lina):
        if stafur == "S":
            upphaf = (x, y)
        elif stafur == "G":
            mark = (x, y)

rod = deque([(upphaf, 0)])
sed = {upphaf}

while rod:
    (x, y), fjarlagd = rod.popleft()

    if (x, y) == mark:
        print(fjarlagd)
        break

    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx, ny = x + dx, y + dy

        if not (0 <= nx < breidd and 0 <= ny < haed):
            continue
        if kort[ny][nx] == "#":
            continue
        if (nx, ny) in sed:
            continue

        sed.add((nx, ny))
        rod.append(((nx, ny), fjarlagd + 1))
else:
    print("Engin leið")

Úttak:

5

Mengið sed kemur í veg fyrir að við heimsækjum sama reit endalaust.

Æfing: má nota þverleit?

Lesum óvenjulegt inntak

CTF-inntak getur verið:

robot=A;start=(2,-1);moves=R2|L10|R0

Við getum freistast til að skipta bara á ;, =, ( og | í mörgum skrefum. Regluleg segð eða lítill þáttari getur verið skýrari:

import re

lina = "robot=A;start=(2,-1);moves=R2|L10|R0"

m = re.fullmatch(
    r"robot=(?P<robot>[A-Z]);"
    r"start=\((?P<x>-?[0-9]+),(?P<y>-?[0-9]+)\);"
    r"moves=(?P<moves>[LR0-9|]+)",
    lina,
)

if not m:
    raise ValueError("Ógilt inntak")

x = int(m.group("x"))
y = int(m.group("y"))
skipanir = m.group("moves").split("|")

Síðan staðfestum við hverja skipun með öðru fullmatch(). Það að ytri runan leyfi stafi og tölur sannar ekki að R2L3 sé gild ein skipun.

Prófanir fyrir smáforrit

Lítið CTF-forrit græðir mikið á nokkrum assert-línum:

def manhattan(x, y):
    return abs(x) + abs(y)

assert manhattan(0, 0) == 0
assert manhattan(1, 3) == 4
assert manhattan(-2, 1) == 3

Prófum sérstaklega:

• minnsta inntak,
• stærsta leyfða inntak,
• núll,
• neikvæð gildi ef þau eru leyfð,
• jafntefli,
• óaðgengilegt mark,
• ógilda línu,
• sýnidæmi verkefnisins.

Prófun sannar ekki að forritið sé rétt, en hún finnur mörg algeng túlkunar- og jaðartilvik.

Hvenær verður leit of stór?

Tímaflækjustig (e. time complexity) lýsir gróflega hvernig vinnan vex með stærð inntaks.

• Ein lykkja yfir n atriði er oft O(n).
• Tvær fullar lykkjur hvor inni í annarri eru oft O(n²).
• Allar raðanir n atriða eru n! og vaxa mjög hratt.
• Allar tvíundarunur af lengd n eru 2ⁿ.

10! = 3.628.800
20! ≈ 2,43 × 10^18

Þrautleit sem er þægileg fyrir tíu hluti er því ómöguleg fyrir tuttugu. Notum skilyrði snemma, betra reiknirit eða stærðarmörk úr lýsingunni.

Lokaverkefni: vélmennið og talnarunan

start=0,0,N
moves=R2;L3;L1
data=99,99,127,118,107,111,112,108,118,101,113,112,121

import re

gogn = {}

with open("thraut.txt", encoding="utf-8") as f:
    for nr, lina in enumerate(f, start=1):
        lina = lina.strip()
        if not lina:
            continue
        if lina.count("=") != 1:
            raise ValueError(f"Ógild lína {nr}")
        lykill, gildi = lina.split("=", 1)
        if lykill in gogn:
            raise ValueError(f"Tvítekinn lykill: {lykill}")
        gogn[lykill] = gildi

if set(gogn) != {"start", "moves", "data"}:
    raise ValueError("Vantar lykil eða óþekktur lykill fannst")

m = re.fullmatch(r"(-?[0-9]+),(-?[0-9]+),([NESW])", gogn["start"])
if not m:
    raise ValueError("Ógilt start")

x, y = int(m.group(1)), int(m.group(2))
upphaf = (x, y)
stefnur = ["N", "E", "S", "W"]
stefna = stefnur.index(m.group(3))
hreyfing = [(0, 1), (1, 0), (0, -1), (-1, 0)]

for skipun in gogn["moves"].split(";"):
    m = re.fullmatch(r"([LR])([0-9]+)", skipun)
    if not m:
        raise ValueError(f"Ógild hreyfing: {skipun!r}")

    beygja, skref = m.group(1), int(m.group(2))
    stefna = (stefna + (1 if beygja == "R" else -1)) % 4
    dx, dy = hreyfing[stefna]
    x += dx * skref
    y += dy * skref

fjarlagd = abs(x - upphaf[0]) + abs(y - upphaf[1])

tolur = [int(gildi) for gildi in gogn["data"].split(",")]
if any(not 0 <= tala <= 255 for tala in tolur):
    raise ValueError("Data-gildi utan bætabils")

texti = bytes(tala ^ fjarlagd for tala in tolur).decode("ascii")

print("Lokastaða:", (x, y))
print("Fjarlægð:", fjarlagd)
print("Texti:", texti)

Lokastaða: (1, 3)
Fjarlægð: 4
Texti: gg{rokthraut}

Samantekt

Í þessum kafla lærðum við að:

• breyta verkefnalýsingu í samning um inntak, úttak, reglur og mörk,
• reikna lítið dæmi í höndunum áður en við forritum,
• geyma aðeins það ástand sem eftirlíking þarf,
• lýsa afmörkuðum ferlum sem endanlegum stöðuvélum,
• nota þrautleit aðeins þegar leitarrýmið er raunhæft,
• velja product() eða permutations() eftir því hvort endurtekning er leyfð,
• finna stystu leið í óvigtuðu neti með þverleit,
• staðfesta sérkennilegt inntak með skýrum þáttara,
• forðast eval() á ótraustu inntaki,
• prófa jaðartilvik með litlum, þekktum dæmum,
• áætla hvort O(n), O(n²), 2ⁿ eða n! lausn sé raunhæf.

Í næsta kafla förum við í opna heimildaleit: hvernig við finnum og staðfestum opinberar upplýsingar án þess að fara yfir persónuleg eða lagaleg mörk.