Denna information skickades ut till tentans deltagare efter att alla inlämningar hade granskats. Tanken är både att ge mer information kring hur man kan tänka när man löser uppgifterna och att sammanfatta vanliga typer av fel som har uppstått under just denna tentaomgång. Vi fokuserar då på de fel som faktiskt har uppstått, inte sådana som teoretiskt kunde ha uppstått, och de fall där felen tyder på specifika tankefel och liknande missar snarare än slumpmässiga misstag eller slarv. Vid omtentor, där det är färre som går upp på tentan, blir det ofta också färre typfel att diskutera. Lösningsförslag kan finnas inbakade i informationen eller i en separat fil. Tänk på att det går att lösa uppgifterna på många olika sätt och att det inte automatiskt är fel bara för att en lösning ser annorlunda ut. ============================================================================= Hur svår en tenta egentligen är beror på både uppgifternas svårighet, poängsättningen, och poänggränserna. Detta betyder att poänggränser inte måste vara samma från tenta till tenta. För denna tenta har vi följande betygsgränser: 14.0p krävs för godkänt / betyg 3. 18.5p krävs för betyg 4. 22.0p krävs för betyg 5. Maximal poäng är 30.0. ============================================================================= Allmän information om uppgift 1 ============================================================================= Första uppgiften är tänkt att vara en enkel test av grundläggande funktionalitet i Python: Listor, iteration, summering, returnera ett resultat från en funktion, och så vidare. Här har de flesta klarat uppgiften utan problem. Ett par implementationer klarar bara listor på formen [1,2,3,...], och ett par klarar inte sekvenser med 1 tal att summera. Några fungerar inte alls. Några olika lösningsförslag: def facit_sums(seq: list[int]): sum_so_far = 0 results = [] for element in seq: sum_so_far += element results.append(sum_so_far) return results def sums_2(seq: list[int]): # Alternativ lösning där man inte har en separat variabel # för att hålla reda på summan results = [0] for n in seq: results.append(results[-1] + n) return results[1:] def sums_3(seq: list[int]): # Alternativ på en rad. Att köra den tar längre tid eftersom # den för varje element skapar en slice och startar om # summeringen från början. return [sum(seq[:i+1]) for i in range(len(seq))] ============================================================================= Allmän information om uppgift 2 ============================================================================= Här testar vi lite mer användning av listor och allmän programmering. Återigen är det många som har löst uppgiften utan några fel, även om det är vissa lösningar som börjar bli mer komplicerade än de egentligen behöver vara. Utöver de lösningar som inte alls fungerar, var det någon lösning som inte klarade att båda listorna var tomma, någon som inte klarade att största elementet fanns i s1 (eller tvärtom), och några andra problem som inte hade något särskilt mönster. Här ser vi en möjlig lösning: def facit_merge(s1: list, s2: list): result = [] while True: if s1 and s2: if s1[0] < s2[0]: result.append(s1[0]) s1 = s1[1:] else: result.append(s2[0]) s2 = s2[1:] elif s1: result.append(s1[0]) s1 = s1[1:] elif s2: result.append(s2[0]) s2 = s2[1:] else: return result Vi har alltså 4 fall: Det finns element kvar i båda listorna, så de behöver jämföras; det finns bara i s1; det finns bara i s2; eller båda listorna har tagit slut. Det finns så klart andra sätt att skriva det här, till exempel genom att använda index, eller att göra result.extend(s1) när bara s1 finns kvar (så tar man hand om hela "svansen" på en gång). Ett alternativ är att köra rekursivt. Då gör vi nästan samma sak men eftersom vi inte har särskilda resultatvariabler blir det lite färre rader. def merge_recursive(s1: list, s2: list): if len(s1) == 0: return s2 if len(s2) == 0: return s1 if s1[0] <= s2[0]: return [s1[0]] + merge_recursive(s1[1:], s2) else: return [s2[0]] + merge_recursive(s1, s2[1:]) ============================================================================= Allmän information om uppgift 3 ============================================================================= I denna uppgift testar vi behandling av nästlade listor. Här visar det sig tydligt att många lämnar in ett resultat när testerna verkar fungera, utan att skapa egna enkla tester -- så här kommer några tips till nästa gång. Eftersom funktionen ska klara av godtyckliga nästlade listor, är det bra om de klarar av även de enklaste möjliga listorna (något som inte fanns med i exemplen i uppgiften eftersom det borde vara relativt uppenbart vad resultatet skulle bli). Här har vi några fall där vi börjar med [1,2,3] och tar bort ett element. without([1,2,3], [1]) # 16 felaktiga svar, 8 exceptions without([1,2,3], [3]) # 20 felaktiga svar, 7 exceptions without([1,2,3], [2]) # 18 felaktiga svar, 5 exceptions Vad händer om vi tar bort alla element, eller inget alls? without([1,2,3], []) # 14 felaktiga svar, 3 exceptions without([1,2,3], [1,2,3]) # 15 felaktiga svar, 8 exceptions Det står i uppgiften att nest kan vara tom, så vad händer om vi testar det? without([], []) # 3 felaktiga svar, 2 exceptions without([], [1]) # 3 felaktiga svar, 2 exceptions Vi kan ha godtyckliga nästlade listor, så vad händer om vi varierar nästlingen? Här är fall där allt skulle tas bort. without([[1], 2, 3], [1, 2, 3]) # 21 felaktiga svar, 11 exceptions without([1, [2], 3], [1, 2, 3]) # 29 felaktiga svar, 9 exceptions without([1, 2, [3]], [1, 2, 3]) # 28 felaktiga svar, 8 exceptions Det står också att nest kan innehålla tomma listor: without([[]], [1]) # 11 felaktiga svar, 4 exceptions without([[[]]], [1]) # 12 felaktiga svar, 4 exceptions without([[], []], [1]) # 14 felaktiga svar, 5 exceptions Och så vidare. Det är dock inte vår uppgift att ge er alla testfall, utan att ge exempel som hjälper er förstå så att ni sedan kan skriva fungerande kod på egen hand. Ett inte helt ovanligt fel är att man returnerar varje gång i en loop, i stil med detta exempel (som i och för sig är taget från en annan uppgift): for div in range(2, int(math.sqrt(n)) + 1): if n % div == 0: return False else: return True Vad händer här? Vi försöker loopa, men i varje iteration ska vi antingen returnera sant eller returnera falskt. Vi returnerar alltså alltid från funktionen redan i första iterationen! Ett rekursivt lösningsförslag: def facit_without(nest: list, to_remove: list): result = [] for element in nest: if isinstance(element, list): result.append(facit_without(element, to_remove)) elif element not in to_remove: result.append(element) return result Vi ska behandla alla element i nest. Om elementet är en lista ska vi gå ner och titta på den, alltså anropa without() rekursivt för att ta bort element i den, och lägga till returvärdet i result. Är det ett element som inte ska tas bort, lägger vi till det i resultatet. ============================================================================= Allmän information om uppgift 4 ============================================================================= Här går vi in lite på högre ordningens funktioner. Till skillnad från många tidigare tentor kräver vi inte att man t.ex. har en funktion som returnerar nya funktioner, utan vi behandlar den lite enklare varianten där en funktion ska ta in en annan funktion som parameter. Samtidigt gör vi ytterligare tester av de allmänna programmeringskunskaperna. I 4a ska man dela upp listor. Lösningsförslag: def facit_split_at(seq, pred): result = [] # Elementen som ska hamna i nästa dellista sublist = [] for element in seq: if pred(element): # Splitta här -- lägg till den nuvarande dellistan # och nollställ den result.append(sublist) sublist = [] else: # Fortsätta bygga upp dellistan sublist.append(element) # Nu har vi en allra sista dellista som ska läggas till # i slutet result.append(sublist) return result Man kan också tänka lite annorlunda: def facit_split_at_2(seq, pred): result = [[]] for element in seq: if pred(element): result.append([]) else: result[-1].append(element) return result Fel vi kan se här är att det inte fungerar för tomma listor, för listor där man ska splitta på alla elementen, när man ska splitta på minst två element i rad i slutet av seq, eller när seq är en annan sorts sekvens än en lista. I 4b kan man göra så här: def facit_add_for_each(seq: list, func): sum_so_far = 0 for element in seq: sum_so_far += func(element) return sum_so_far ============================================================================= Allmän information om uppgift 5 ============================================================================= Primtal kan vi till exempel hitta på något av dessa två sätt. def facit_is_prime(n: int): if n < 2: return False for divisor in range(2, int(math.sqrt(n)) + 1): if n % divisor == 0: return False return True def facit_is_prime_2(n: int): return n >= 2 and all(n % divisor != 0 for divisor in range(2, int(math.sqrt(n)) + 1)) Förra gången vi hade denna uppgift var det för många som testade att dividera med tal upp till n//2 eller n//2+1 istället för int(math.sqrt(n)), vilket gör lösningarna extremt långsamma när vi når upp till stora n. Därför hade vi formulerat uppgiften annorlunda i år, med fler testfall, så detta hände nu väldigt sällan. Ett antal lösningar fungerade inte för udda icke-primtal, som 9. Här kan det hända att man hade en loop som denna: for divisor in range(2, int(math.sqrt(n)) + 1): if n % divisor == 0: return False else: return True Vad händer här? Vi försöker loopa, men i varje iteration ska vi antingen returnera sant eller returnera falskt. Vi returnerar alltså alltid från funktionen redan i första iterationen! Om talet var delbart med 2 returnerar loopen falskt (inte primtal, korrekt) och om det inte var delbart med 2 returnerar loopen sant (säger att det var ett primtal, trots att vi bara har visat att det var udda). Det vi är ute efter är ju att returnera falskt om n är delbart med NÅGON divisor, och sant om n är icke-delbart med ALLA divisorer. Då får man göra som i lösningsförslaget. Primtalsfaktorer kan vi hitta på detta sätt. def facit_prime_factors(n: int): # This isn't efficient for larger numbers, but that wasn't required. # Could also use a sieve to find primes, or more advanced methods. factors = [] prime = 2 while n != 1: if n % prime == 0: factors.append(prime) n /= prime # Iterate and try the same factor again else: # Find next prime prime += 1 while not is_prime(prime): prime += 1 return factors Även här har några lösningar haft problem med att inte iterera tillräckligt långt för att hitta alla tänkbara primtal. Den lösning som föreslås ovan itererar till n==1, och det måste så småningom hända. Man kan också sätta ett villkor på prime istället och testa med primtal upp till och med int(math.sqrt(n)), *om* man också inser att n fortfarande kan vara ett primtal (en faktor till) när loopen är slut -- exempelvis för 22 (iteration upp till 4 hittar faktorn 2, och sedan finns faktorn 11 kvar att behandla). Lösningen kan förkortas: def facit_prime_factors_2(n: int): factors = [] while n != 1: for divisor in range(1, n+1): if n % divisor == 0 and is_prime(divisor): factors.append(divisor) n //= divisor return factors Men detta kan bara hitta en "instans" av varje primtalsfaktor i varje yttre iteration. Därför blir det långsammare för tal som 128 (2*2*2*2*2*2*2), där man måste iterera 7*n gånger. (Även den ursrprungliga lösningen kan optimeras, t.ex. genom att stega upp med 2 i varje steg när man väl har nått fram till divisorn 3, eller genom att på effektivare sätt hitta alla primtal upp till en övre gräns). Rekursiva varianter kan också fungera, men de rent rekursiva har ofta liknande egenskaper -- varje gång en primtalsfaktor hittas sker en rekursion där man börjar om med att leta faktorer från 2. Vissa lösningar hittar först alla primtal upp till en viss gräns och testar sedan vilka av dessa som är divisorer. Det kan också påverka prestanda, speciellt om man testar stora primtal upp till n//2 där detta sedan visar sig inte behövas, men det är samtidigt en bra form av divide and conquer där man kan söka fel i varje problemhalva för sig. Attraktiva tal kan vi till slut hitta på detta sätt: def facit_is_attractive(n: int): return facit_is_prime(len(facit_prime_factors(n)))