Undirstöður forritunar og rökþrauta

Innan ramma flokksins Ýmislegt mætum við iðulega viðfangsefnum þar sem hvorki er að finna leynda skráarhausa né heldur þörf á sértækum öryggisverkfærum. Okkar er að sýsla með tilteknar reglur, ílagsgögn og eina rannsóknarspurningu. Kjarni úrlausnarinnar hvílir í því að varpa verkefnalýsingunni yfir á form nákvæms reiknirits.

Hér má nefna nokkur dæmi:

• að rekja slóð vélmennis um kortasvæði,
• að líkja eftir starfsemi einfaldrar vélgerðar,
• að láta reyna á tiltekið og afmarkað talnamengi,
• að leiða í ljós hina stystu leið innan reitanets,
• að raða hlutum í samræmi við gefin skilyrði,
• að ráða úr óvenjulegu ílagi og reikna út hið endanlega ástand.

Hafinn er leikurinn jafnan með blaði og blýanti. Verði rannsakandi var við endurtekið mynstur, eða þegar leitarrýmið þenst út, er giftudrjúgt að rita hnitmiðað og prófanlegt tölvuforrit.

Vörpum lýsingu yfir í skýran samning

Löngu áður en lagt er í sjálfa forritunina, skulum við færa eftirfarandi til bókar:

1. Ílag: Hvers konar gögn eru í okkar höndum, og hverju gagnasniði fylgja þau?
2. Frálag: Hverri nákvæmri niðurstöðu er okkur ætlað að skila?
3. Reglur: Hvers má vænta í sérhverju vinnuskrefi?
4. Upphafsástand: Hvar á ferlið upptök sín?
5. Mörk: Hvert er hámarksumfang ílagsgagnanna?
6. Sértilvik: Hvað gerist við tómt ílag, jafntefli eða ógilda skipun?
7. Sýnidæmi: Skyldi raunveruleg túlkun okkar falla að því sýnidæmi sem verkefnið geymir?

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.

hlýtur þá að teljast til eftirfarandi samnings:

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

Hér blasa við nokkur atriði sem orka tvímælis og útheimta úrlausn okkar:

• Hlutast vélmennið til um beygju áður en gangan hefst eða að henni lokinni?
• Telst talan núll vera lögmætur fjöldi?
• Getur hann hæglega verið af neikvæðum toga?
• Samsvarar sérhvert skref nákvæmlega einum reit?
• Er þar hindrunum eða tilteknum mörkum á kortasvæðinu fyrir að fara?

Við skulum síst af öllu hrapa að ályktunum sé þess nokkur kostur að láta sýnidæmi eða höfund verkefnisins varpa ljósi á starfsreglurnar.

Handvirkir útreikningar sem upphafsskref við prófun

Fyrir skipanirnar:

R2,L3,L1

hljótum við eftirfarandi niðurstöðu:

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

|1| + |3| = 4

Þessi hnitmiðaða tafla þjónar svo hlutverki prófunartilviks (e. test case) fyrir tölvuforrit okkar.

Æfing: túlkaðu reglurnar

L2,R1,R3

|1| + |1| = 2

Eftirlíkingar og meðferð ástands

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

Þegar vélmennið á í hlut, skipa eftirfarandi þættir ástandið:

(x, y, stefna)

Okkur er fært að varðveita hinar ólíku áttir í hringrás:

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

Beygja til hægri leiðir til hækkunar á vísinum um eina einingu, á meðan vinstri beygja dregur eina frá, að viðhafðri deilingu með afgangi (e. modulo) við töluna 4:

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

Hér má sjá forritið í heild sinni:

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))

Frálag:

1 3
4

Við skulum gæta þess að styðjast við fullmatch() aðferðina, svo tryggt sé að vafasöm ílög á borð við R2rusl mæti höfnun í stað þess að vera tekin gild sem R2.

Endanleg stöðuvél

Endanleg stöðuvél (e. finite-state machine) einkennist af afmörkuðu mengi stöðva og fastmótuðum reglum um það hvernig ílagi er ætlað að flytja hana á milli þessara sömu stöðva.

Dæmi um hurð:

stöður: LÆST, OPIÐ
ílag: 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 ílag in ["ýta", "lykill", "ýta", "loka"]:
    lykill = (stada, ílag)
    if lykill not in yfirfaerslur:
        raise ValueError(f"Óskilgreint skref: {lykill}")
    stada = yfirfaerslur[lykill]

print(stada)

Taflan varpar skýru ljósi á öll óskilgreind tilvik. Okkar er þá að skera úr um hvort slík tilvik skuli túlkuð sem hrein villuboð, óbreytt ástand eða ef til vill sem tiltekin tapstaða.

Æfing: fylgdu stöðuvélinni

lykill, ýta, loka, ýta, lykill

Þrautleit í litlu leitarrými

Þrautleit (e. brute-force search) byggir á því að láta reyna á alla mögulega frambjóðendur með kerfisbundnum hætti. Sú aðferð telst fyllilega forsvaranleg hvenær sem leitarrýmið er takmarkað og starfsreglurnar útheimta litla fyrirhöfn við 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ð gætum þess að varðveita upphafleg núll með tilstyrk skipunarinnar f"{tala:03d}".

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

Beiting itertools forritasafnsins við samantektir og umröðun

Python-málið er í lófa lagið að móta mögulega frambjóðendur, án þess að rannsakandi þurfi að rita fjöldann allan af lykkjum á eigin spýtur.

Sérhver fjögurra bita runa:

from itertools import product

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

Sérhver röðun þ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. Beiting permutations() fallsins, þar sem endurtekning gilda er í raun heimiluð, leiðir óhjákvæmilega til þess að gengið er fram hjá 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.

Okkur er fært að láta reyna á allar sex mögulegar 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)

Niðurstaðan kann hæglega að hýsa fleiri en eina röð, sé því svo farið að skilyrðin kveði síst á um eina og einkvæma lausn. Þetta telst í sjálfu sér veigamikil niðurstaða; okkur ber engan veginn að töfra fram ný skilyrði einvörðungu til þess að knýja fram eitt stakt svar.

Leit að leiðum innan reitanets

Kort:

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

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

Reynist sérhvert vinnuskref — hvort sem haldið er upp, niður eða til hliðanna — kosta eina einingu, reynist okkur farsælast að leita uppi hina stystu leið með tilstyrk þverleitar (e. breadth-first search, BFS).

Þverleitin hlutast til um að rannsaka fyrst alla þá reiti sem hvíla í einnar einingar fjarlægð, síðan þá sem eru tveimur einingum fjarri, og svo koll af kolli. Undireins og markinu er náð í fyrsta sinn, liggur fyrir að stysta leiðin innan hins óvigtaða nets hefur verið leidd í ljós.

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ð")

Frálag:

5

Notkun mengisins sed tryggir að við eyðum síst orku í að vitja sama reitsins hvað eftir annað.

Æfing: reynist þverleit fýsilegur kostur?

Rýni í framandi ílagsgögn

CTF-ílag getur verið:

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

Mörgum reynist tamt að láta sér nægja að beita uppskiptingu á ;, =, ( og | í mörgum skrefum. Beiting reglulegra segða eða hnitmiðaðs þáttara (e. parser) getur hins vegar reynst okkur mun skýrari leið:

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 ílag")

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(). Sú staðreynd að ytri runan heimili bókstafi og tölustafi færir okkur síst af öllu sönnur á að runan R2L3 teljist ein og sér gild skipun.

Vandaðar prófanir á hnitmiðuðum forritum

Hnitmiðuð forrit í gagnaglímum öðlast mikinn styrk með tilstyrk nokkurra assert-fyrirmæla:

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

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

Við skulum láta reyna sérstaklega á:

• hið lágmarksmengda ílag,
• hið rýmsta heimilaða ílag,
• núll,
• neikvæð gildi ef þau eru leyfð,
• jafntefli,
• óaðgengilegt mark,
• ógilda línu,
• sýnidæmi verkefnisins.

Þótt prófun færi okkur engan veginn fulla vissu fyrir því að forritið sé hafið yfir allan vafa, þá leiðir hún engu að síður iðulega í ljós hversdagslega hnökra við túlkun og margvísleg jaðartilvik (e. edge cases).

Hvenær þenst leitarrýmið út yfir öll velsæmismörk?

Tímaflækjustig (e. time complexity) varpar grófu ljósi á það með hvaða hætti vinnuálagið þenst út í takt við umfang ílagsins.

• Einstök lykkja sem farið er með yfir n atriði flokkast gjarnan undir O(n).
• Tveimur samofnum lykkjum, þar sem önnur hvílir innan þeirrar fyrri, er iðulega skipað í flokkinn O(n²).
• Sérhver röðun n atriða lýtur lögmálinu n! og þenst slíkt álag út á ógnarhraða.
• Sérhverri tvíundarrunu af lengd n er sömuleiðis sniðinn stakkurinn 2ⁿ.

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

Þrautleit sem reynist okkur leikur einn þegar tíu hlutir eiga í hlut, getur þannig hæglega reynst okkur með öllu óvinnandi vegur þegar fjöldinn nær 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 höfum við kynnst því hvernig á að:

• varpa verkefnalýsingunni yfir á skýran samning um ílag, frálag, starfsreglur og tilskilin mörk,
• leysa úr smágerðum sýnidæmum handvirkt löngu áður en lagt er í forritunina,
• varðveita einvörðungu það ástand sem sjálf eftirlíkingin útheimtir,
• gera grein fyrir afmörkuðum ferlum í formi endanlegra stöðuvéla,
• beita þrautleit einvörðungu þegar leitarrýmið telst raunhæft til úrvinnslu,
• velja product() eða permutations() eftir því hvort endurtekning er leyfð,
• hafa uppi á hinni hagstæðustu leið innan óvigtaðs nets með tilstyrk þverleitar,
• færa sönnur á framandi ílagsgögn með skýrum og vönduðum þáttara,
• varast beitingu eval() á ílagsgögn sem síst telst traust,
• láta reyna á jaðartilvik með tilstyrk hnitmiðaðra og kunnuglegra sýnidæma,
• leggja mat á hvort lausn, sé lýtur lögmálum á borð við O(n), O(n²), 2ⁿ eða n!, teljast raunhæf til framkvæmda.

Í eftirfarandi kafla munum við beina sjónum okkar að opinni heimildaleit (e. OSINT); þar munum við rýna í hvernig unnt er að leiða í ljós og færa sönnur á opinberar upplýsingar, án þess þó að stíga yfir siðferðileg eða lagaleg mörk persónuverndar.