Gäller för: HT25

Storseminarium 2.1 - En sak i taget

Innan seminariet ska du ha gått igenom Inför seminariet nedan och gjort tillhörande quiz. Syftet med detta är att du ska bekanta dig med innehållet så eventuella frågor kan redas ut under seminariet.

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

Inför seminariet

Under seminariet

Vi går igenom nedanstående uppgifter tillsammans, det kommer finnas möjlighet till diskussion och frågor. Känn er fria att följa med på uppgifterna på egen dator under seminariet om ni lär er bättre så, men vi kan inte garantera att vi har tid att vänta in alla.

Pythontutor

Använd pythontutor.com för att stega igenom nedanstående kodexempel:

Summa från 0 till något heltal n

1
2
3
4
5
6
7


def sum_0_to_n(n):
    if n == 0:
        return 0
    else:
        return n 0 sum_0_to_n(n-1)

print(sum_0_to_n(3))

Summera lista (från föreläsningen)

1
2
3
4
5
6
7


def sum_list_rec(values):
    if values == []:
        return 0
    else:
        return values[0] + sum_list_rec(values[1:])

print(sum_list_rec([1, 2, 75, 6, 7]))

Telephone game

Målet är att förstå:

Hur man identifierar basfallet (när rekursionen ska sluta)
Hur man definierar det rekursiva fallet (när funktionen ska anropa sig själv)
Hur data förändras steg för steg i en rekursiv kedja

Telephone game (viskleken) är en lek som går ut på att skicka ett meddelande genom en sekvens av personer som återberättar meddelandet så noggrant som möjligt. Detta resulterar oftast i att meddelandet sakta ändrar mening, det kan handla om att ord byts ut till ett annat ord som låter snarlikt, eller att strukturen förändras

Vår uppgift är nu att skriva ett program som använder enkelrekursion för att simulera en sådan lek. Funktionen telephone_game ska vara enkelrekursiv, och tar emot två parametrar; phone_list, som är en lista över namn på kompisar i den ordningen som meddelandet ska berättas; message, är en sträng som representerar meddelandet som varje kompis har uppfattat från tidigare samtal.

Uppgift: Skriv klart funktionen telephone_game i koden som du kan kopiera från i kurskatalogen /courses/729G46/kursmaterial/storsem/2_1 (kopiera hela katalogen med cp -r). En zipfil kan också laddas ner här. Vi ska använda mutate för att förändra meddelandet.

Förslag på lösningsstrategi

Kolla om det är basfallet (inga personer kvar)
Om basfall:
- Returnera meddelande
Annars (rekursivt fall):
- Skriv ut vem som tar emot meddelandet
- Förvanska meddelandet
- Skriv ut vad personen hörde
- Anropa telephone_game med listan utan första namnet och det nya meddelandet

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


#! /usr/bin/env python3
# -*- coding: utf-8 -*-
""" Rekursion och viskleken. """

import sys
from mutate_med import mutate


def telephone_game_iterproc(phone_list, message):
    """Simulates the telephone game using recursion returning the final message.

    Parameters
    ----------
    phone_list : list[str]
        A list of names in the order they will receive the message.
    message : str
        The message that will be passed along.
    """
    # === Steg 0: Basfall — om inga personer är kvar ===
    if not phone_list:  # Påminn om truthiness av tomma listan
        return message

    # === Steg 1: Skriv ut vem som tar emot meddelandet ===
    print(f"{phone_list[0]} hör: ", end="")  # end="" för att undvika ny rad

    # === Steg 2: Förvanska meddelandet ===
    mutated_message = mutate(message)

    # === Steg 3: Skriv ut vad personen hörde ===
    print(mutated_message)  # Skrivs ut på samma rad som vem som hörde

    # === Steg 4: Anropa rekursionen med återstående namn ===
    return telephone_game_iterproc(phone_list[1:], mutated_message)
    # Vi kan säga att vi har "konsumerat" det första namnet i listan och
    # skickar därför bara resten av listan till nästa anrop.


def telephone_game_recproc(phone_list, original_message):
    # Basfallet är detsamma
    if not phone_list:
        return original_message
    # Här gör vi rekursionen först, innan vi muterar och skriver ut.
    # Vi bearbetar listan baklänges för att få samma ordning på utskriften som
    # i den andra versionen.
    previous_message = telephone_game_recproc(
        phone_list[:-1], original_message
    )
    # Notera att vi inte skickar med ett muterat meddelande till nästa anrop
    # utan istället orginalmeddelandet. Först när det anropet är klart muterar
    # vi det meddelande som returnerades och skriver ut det.
    new_message = mutate(previous_message)
    # Vi gör all utskrift efter att vi fått meddelandet från det rekursiva
    # anropet och muterat det. Gör vi inte det så kommer utskriften inte bli
    # korrekt.
    print(f"{phone_list[-1]} hör: " + new_message)
    # Det muterade meddelandet returneras vidare upp i anropskedjan.
    return new_message


def telephone_game_acc(phone_list, message):
    """Simulates the telephone game using recursion and returning all steps.

    Parameters
    ----------
    phone_list : list[str]
        A list of names in the order they will receive the message.
    message : str
        The message that will be passed along.
    """
    # === Steg 0: Basfall — om inga personer är kvar ===
    if not phone_list:
        # Eftersom vi vill samla alla rader i en tupel returnerar vi en tom
        # tupel här som sedan kan byggas på i de tidigare anropen.
        return tuple()
    mutated_message = mutate(message)
    return (mutated_message,) + telephone_game_acc(
        phone_list[1:], mutated_message
    )


def telephone_game_acc_iterproc(phone_list, message, result=tuple()):
    """Simulates the telephone game using recursion.

    Parameters
    ----------
    phone_list : list[str]
        A list of names in the order they will receive the message.
    message : str
        The message that will be passed along.
    """
    if not phone_list:
        # Eftersom vi byggt upp resultatet vid varje anrop så returnerar vi det
        # bara när vi når basfallet.
        return result
    mutated_message = mutate(message)
    return telephone_game_acc_iterproc(
        phone_list[1:], mutated_message, result + (mutated_message,)
    )


def telephone_game_acc_recproc(phone_list, original_message):
    if not phone_list:
        return tuple()
    previous_result = telephone_game_acc_recproc(
        phone_list[:-1], original_message
    )
    if previous_result:
        return previous_result + (mutate(previous_result[-1]),)
    else:
        return previous_result + (mutate(original_message),)


def telephone_game_closed(phone_list, message):
    """Simulates the telephone game on a closed list of players using recursion
    and returning the final message.

    Parameters
    ----------
    phone_list : list[str]
        A list of names in the order they will receive the message.
    message : str
        The message that will be passed along.
    """
    # Eftersom vi betraktar listan med personer som sluten, dvs. ingen person
    # före eller efter listan ingår i spelet, så är basfallet när det bara
    # finns en person kvar i listan.
    if len(phone_list) <= 1:
        # Den sista personen ropar meddelandet så som de hörde det.
        print(f"{phone_list[0]} ropar: {message.upper()}")
        return message
    # Vi skriver ut vem som viskar meddelandet och vad de viskar, här har dock
    # ingen mutering skett än.
    print(f"{phone_list[0]} viskar: {message}")
    # Vi anropar funktionen rekursivt med återstående namn och muterar
    # meddelandet vid anropet, vilket innebär att förvanskningen sker mellan
    # personerna.
    return telephone_game_closed(phone_list[1:], mutate(message))


def main(message, phone_list):
    """Main function for this module.

    Parameters
    ----------
    message : str
        The initial message for the telephone game.
    phone_list : list[str]
        The list of participants in the order they will receive the message.
    """
    print("Welcome to the telephone game!")
    print(f"Original message: {message}")
    print("Phone list:")
    for name in phone_list:
        print(f"  {name}")
    print("\n--- Game starts ---\n")

    final = telephone_game(phone_list, message)

    print("\nThe game is over. The final message was:\n")
    print(f"\n\"{final}\"")
    print("\nThanks for playing!")


if __name__ == "__main__":
    TELEPHONE_LIST = ["Anna", "Erik", "Björn", "Mattias", "Peter"]

    if len(sys.argv) >= 2:
        main(sys.argv[1], TELEPHONE_LIST)
    else:
        message = "Ha nått kul meddelande här!"
        main(message, TELEPHONE_LIST)

Att diskutera

Uttrycker vi en iterativ processlösning eller en rekursiv processlösning? Varför?

Lösningen beskriven i telephone_game_iterproc är troligtvis den mest naturliga och uttrycker en iterativ processlösning eftersom vi i varje steg utför alla beräkningar för en person innan vi gör det rekursiva anropet. Ett annat sätt att se detta är att returvärdet för alla rekursiva anrop kommer vara detsamma, dvs. den slutgiltiga formen av meddelandet.

Kan vi konvertera till den andra typen och hur skulle det se ut?

Lösningen beskriven i telephone_game_recproc uttrycker en rekursiv processlösning eftersom vi utför operationerna för vad en viss person hör först efter att vi gjort det rekursiva anropet. Ett annat sätt att tänka på det är att returvärdet från varje rekursivt anrop kommer vara mer och mer muterat tills vi är tillbaka vid det första anropet, snarare än att argumentet till varje anrop kommer vara mer och mer muterat.

Hur kan vi modifiera lösningen för att samla alla versioner av meddelandet i en tupel istället för att skriva ut dem?

Lösningen beskriven i telephone_game_acc samlar delstegen i en tupel utan att göra några utskrifter själv. Notera att den här lösningen inte uttrycker en rent iterativ processlösning eftersom vi utför konkateneringen av av tuplerna först efter att vi gjort det rekursiva anropet. Anropet står efter +-tecknet, men själva konkateneringsoperationen kan inte utföras förrän båda operanderna har beräknats, så rekursionen kommer att utföras först.

Samtidigt sker ju muteringen före det rekursiva anropet och dess resultat skickas vidare så vi skulle kunna säga att genereringen av meddelandena följer en iterativ process medan genereringen av tuplerna följer en rekursiv process. Detta kan såklart bli förvirrande så en rent iterativ processlösning finns i telephone_game_acc_iterproc. (Det finns också en rent rekursiv processlösning i telephone_game_acc_recproc, men den är inte vacker och vad den mest illustrerar är att man nog inte ska göra på det sättet.)

Hur fungerar den verkliga situation som motsvarar vår lösning? Är den första personen i listan den som säger det ursprungliga meddelandet, eller är hen den första som hör det ursprungliga meddelandet och vad innebär det för i vilken ordning saker sker i simuleringen? Kan vi ändra vår tolkning och behöver vi i så fall modifiera koden?

I de absolut första lösningarna är det uppenbart att någon utanför listan med namn viskar det ursprungliga meddelandet till den första personen i listan eftersom vi uttryckligen skriver ut att den första personen hör ett muterat meddelande. Det fortsätter dock att vara sant eftersom vi i samtliga lösningar har 5 namn och 5 stegvis muterade versioner av ursprungsmeddelandet.

Det måste inte vara så dock. Vi skulle kunna anta att den första personen i listan säger ursprungsmeddelandet och den sista personen ropar vad de hörde. Vi kan säga att vi betraktar listan som sluten eftersom ingen implicit extra person ingår kedjan och både den första och sista personen ingår. Kod för att modellerad det finns i telephone_game_closed ovan.

Kan vi modifiera lösningen för att skicka meddelandet i motsatt riktning genom listan av personer utan att ändra typen av lösning? Hur?

Vi bara ändrar i vilken ordning vi konsumerar elementen i phone_list. Dvs. istället för att behandla phone_list[0] och skicka phone_list[1:] till nästa anrop så behandlar vi phone_list[-1] och skickar phone_list[:-1] till nästa anrop.

Sidansvarig: Johan Falkenjack
Senast uppdaterad: 2024-07-26

IDA - Institutionen för datavetenskap