Seminarium 9 - Experimentering

Kapitel som ska ha lästs

Inga kapitel behöver läsas inför detta seminarium. Man kan dock kolla upp datatypen set som kommer att användas i sudoku-uppgiften.

Denna sida visar en del av det som kommer att diskuteras på seminariet. Ofta tar handledarna också upp andra uppgifter som inte behöver något specifikt studentmaterial och då syns dessa uppgifter inte på sidan.

Uppgift: Patrick jagar doktorander

Patrick har ett problem och undrar om vi kan lösa det. Vi ska nu gå genom de första fyra delarna av programutvecklingsprocessen för detta problem: Analys, specifikation, design och implementation.

Analys:

Analysfasen handlar om att förstå vilket problem Patrick egentligen har. Er seminariehandledare ställföreträder Patrick - ställ frågor och diskutera med honom/henne så att ni förstår vad problemet egentligen är! Ni vill dessutom t.ex. veta saker som hur generella problem lösningen ska klara, vad han vill få ut för information och om det finns några specialfall.

Specifikation:

Specifikationsfasen handlar om att beskriva på vilket sätt vi ska lösa problemet. I vårt fall har vi bestämt att vi ska lösa det med hjälp av ett Pythonprogram. Diskutera vad det programmet ska göra.

Design:

I designen är det dags att tänka på hur själva problemet ska lösas. Designa de funktioner och hjälpfunktioner som ni vill använda för att lösa problemet:

• Hur bör informationen representeras?
• Vilka funktioner finns? Vad ska de heta och göra?
• Exakt vilka indata tar funktionerna, och vilka utdata returnerar de?

Om ni vill får ni skriva pseudokod som hjälp till tankeverksamheten, men tanken är inte att ni går vidare hela vägen till implementation - det kommer senare!

Implementation:

Först nu är det dags att skriva den körbara koden. Implementationen görs tillsammans i hela seminariegruppen, efter att en design har diskuterats och justerats.

Uppgift: Sudoku

Johanna har en passion för det japanska sifferpusslet sudoku. Därför vill hon skriva ett program som kontrollerar om hennes sudokulösningar är korrekta. Nu behöver hon lite hjälp att göra klart sin lösning.

Sudoku är ett logikpussel där siffror ska sättas ut på ett bräde. Brädet består av 3 x 3 block som alla innehåller 3 x 3 rutor (totalt 81 rutor). Varje ruta ska innehålla exakt en siffra, och varje rad, kolumn och block ska innehålla siffrorna 1-9 exakt en gång.

Från början är tillräckligt många siffror givna att endast en lösning finns.

Nedan kan ni se koden som Johanna har skrivit. Er uppgift är att skriva klart implementationen.

I sin kod valde Johanna att använda datatypen set för att kontrollera rader. Set lagrar mängder och har de egenenskaper ni känner igen ifrån den diskreta matematiken. Här är några exempel på hur man kan använda set:

>>> a = set()
>>> a.add("Johanna")
>>> a
{'Johanna'}
>>> a.add("Johanna")
>>> a
{'Johanna'}
>>> a.add("Johannas apa")
>>> a
{'Johannas apa', 'Johanna'}
>>> a == {'Johanna', 'Johannas apa'}
True

Johannas implementation:

def is_valid(seen):
    """ Checks if the elements in seen is the numbers 1 through 9 """
    valid = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    return seen == valid


def check_row(board, row):
    """ Checks if a row is a correct sudoku row (it contains numbers 1 through 9) """
    seen = set()
    for col in range(9):
        seen.add(board[row][col])

    return is_valid(seen)


def check_board(board):
    """ Checks if board is a valid sudoku board """
    # Your implementation goes here
    # You will probably need to write more help functions
    pass


if __name__ == "__main__":
    sudoku_board = [
        [2, 9, 5, 7, 4, 3, 8, 6, 1],
        [4, 3, 1, 8, 6, 5, 9, 2, 7],
        [8, 7, 6, 1, 9, 2, 5, 4, 3],
        [3, 8, 7, 4, 5, 9, 2, 1, 6],
        [6, 1, 2, 3, 8, 7, 4, 9, 5],
        [5, 4, 9, 2, 1, 6, 7, 3, 8],
        [7, 6, 3, 5, 2, 4, 1, 8, 9],
        [9, 2, 8, 6, 7, 1, 3, 5, 4],
        [1, 5, 4, 9, 3, 8, 6, 7, 2]
    ]

    bad_sudoku_board = [
        [2, 9, 5, 7, 4, 3, 8, 6, 1],
        [4, 3, 1, 8, 6, 5, 9, 8, 7],
        [8, 7, 6, 1, 9, 2, 5, 4, 3],
        [3, 8, 7, 4, 5, 9, 2, 1, 6],
        [6, 1, 2, 3, 8, 7, 4, 9, 5],
        [5, 4, 9, 2, 1, 6, 7, 3, 8],
        [7, 6, 3, 5, 2, 4, 1, 8, 9],
        [9, 2, 8, 6, 7, 1, 3, 5, 4],
        [1, 5, 4, 9, 3, 8, 6, 7, 2]
    ]

    assert check_board(sudoku_board)
    assert not check_board(bad_sudoku_board)