Seminarium 8 - Experimentering

Kapitel som ska ha lästs

• Problemlösning
• Cellulära automater (extra avsnitt) Frivillig läsning

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: Översätta pseudokod till programkod

Översätt följande pseudokod till python-kod!

Cocktail shaker sort
input:
  seq: a list of sortable items
output:
  nothing, this function modifies the given list
repeat
  # First loop
  for each element e in seq except the last
      if e is greater than the element after e then
          swap e and the next element
      end if
  end for
  if we did not swap in the loop above then
      break outer loop
  end if

  # Second loop
  for each element e in seq except the last, going backwards
      if e is greater than the element after e then
          swap e and the next element
      end if
  end for
until no swaps took place in the second loop

Uppgift: Listmultiplikation

def create_grid(width, height):
    """ Returns a two dimensional list with given width and height """
    grid = []
    for row in range(height):
        grid.append([])
        for col in range(width):
            grid[row].append(False)
    return grid


def create_grid2(width, height):
    """ Returns a two dimensional list with given width and height """
    grid = []
    for i in range(height):
        grid.append([False] * width)
    return grid


def create_grid3(width, height):
    """ Returns a two dimensional list with given width and height """
    return [[False] * width] * height


def create_grid4(width, height):
    """ Returns a two dimensional list with given width and height """
    return [[False for i in range(width)] for i in range(height)]


def create_grid5(width, height):
    """ Returns a two dimensional list with given width and height """
    return [[False] * width for i in range(height)]

Multiplikation av listor fungerar precis som multiplikation av strängar, men det faktum att listor är muterbara ställer till problem då multiplikation används.

Till skillnad från en lista uppbyggd med hjälp av listbyggare så kommer en multiplicerad lista innehålla flera referenser till samma element.

Givet är fem funktioner som alla skapar en 2d-lista.

1. Vad är skillnaden i hur listorna är lagrade? Rita gärna en bild.
2. Vilken av funktionerna anser du är snyggast? Vilken är tydligast?

Listmultiplikation fortsättning

List-multiplikation är något man ska använda med stor försiktighet, då det kan leda till problematiskt beteende. Varför då?

Visa ett exempel på en operation på en lista skapad av create_grid3 som ger oönskat beteende.

Sammanfatta när list-multiplikation är säkert att använda och när det inte är det. Finns det någon av funktionerna ovan som inte bör användas?

Uppgift: Cellulära Automater

def pred1(a, b, c):
    """ Example predicate """
    return a

def next_state(seq, pred):
    """
    Returns the next state of the automaton based on the rules defined by
    the predicate function.
    TODO: Implement this.
    """
    return seq

def print_state(seq):
    """
    Prints a state with 'x' representing living cells
    and ' ' representing dead cells.
    """
    state = ""
    for alive in seq:
        if alive:
            state += "x"
        else:
            state += " "
    print(state)

if __name__ == "__main__":
    seq = [i == 40 for i in range(80)]

    print_state(seq)
    for i in range(39):
        seq = next_state(seq, pred1)
        print_state(seq)

Denna kod är en 1-dimensionell cellulär automat som i nuläget ej fungerar. next_state är en funktion som tar in listan som representerar automaten, och returnerar hur den ska se ut efter nästa uppdatering baserat på en predikatsfunktion. I sitt nuvarande tillstånd uppdateras inte automaten då next_state returnerar samma lista som den får in.

Start-tillståndet är en lista där alla celler utom den mittersta är 0a.

Er uppgift är att utöka next_state så att den, med hjälp av predikatsfunktionen, returnerar nästa generation av automaten. Hur funktionen hanterar hörnfall är upp till er, ni bör dock kunna förklara hur kanter hanteras, varför ni valt att hantera dem så, samt vilka problem eran lösning kan orsaka.

Predikatsfunktionen tar tre argument a, b och c, där a och c är grannar till b. Med hjälp av dessa ska predikatsfunktionen avgöra om b ska leva nästa generation eller inte. Om b ska leva ska predikatsfunktionen returnera True, annars False.

Ett exempel på en predikatsfunktion är pred1, som säger att b ska leva nästa tillstånd om och endast om a lever nu.

För mer information om endimensionella automater, se studiematerialet för cellulär automata.

Cellulär automat forts.

Skriv en predikatsfunktion som uppfyller följande:

där 0 är död och 1 är levande.

Det snyggaste sättet att göra detta på är att beskriva det med ett booleskt uttryck.

När funktionen är klar, testa att skicka in den till next_state och se vilket mönster som bildas.

Bonusfråga: Vad är det matematiska namnet på mönstret som bildas?

Extrauppgift: Cellulär automat

I en 1-dimensionell cellulär automat finns det totalt 256 olika regler (försäkra er om att så är fallet). Reglerna är namngivna så att de i binär kod ger en etta om resultatet lever och annars en nolla. Det översta fallet i tabellen ovan representeras av den minst signifikanta biten, medan det sista fallet representeras av den mest signifikanta biten.

Vilken regel uppfyllde predikatfunktionen given i exempelkoden?

Ni ska nu skriva en funktion, predicate_factory, som tar in en parameter n och returnerar en predikatfunktion som implementerar regel nr. n.

Tips: För att få ut den n-te biten (0-indexerat) ur ett tal x, beräkna x mod 2**(n+1) // 2**n eller använd funktionen bin() för att få en strängrepresentation.

För att kontrollera att den fungerar kan ni testa att generera en funktion baserat på regel 126 och 129. Detta är den regel som vi gick igenom i uppgift 2 samt negationen av den.