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.5p krävs för godkänt / betyg 3. 19.5p krävs för betyg 4. 24.5p krävs för betyg 5. ============================================================================= Allmän information om uppgift 1 ============================================================================= En uppgift som går ut på att hantera värden i listor. def facit_datause(seq: list): result = [] acc = 0 for mb in seq: if mb is None: # Separator anger slut på en månad; börja på nästa result.append(acc) acc = 0 else: # Fortsätt på samma månad acc += mb # Sista månaden måste också läggas till result.append(acc) result.append(max(result)) return result Här var det relativt vanligt att misslyckas när seq är tom. Uppgiften nämner att 'Om listan dessutom är helt tom gäller den en enda månad då inget laddades ned, vilket innebär att resultatet också behöver innehålla en månad utan konsumtion'. Detta innebär då också att denna månad var den som hade högst konsumtion, så att resultatet ska bli [0,0]. Hanteringen av flera None i rad var problematisk i vissa lösningar. Det enklaste är att som ovan alltid behandla ETT element ur seq i taget, och låta None trigga början på en ny månad. Att försöka ta hand om både None och elementet före/efter i samma iteration leder lätt till trassel. Det fanns många varianter på detta problem, som att felet uppstår enbart för [None], för minst 2 None i rad, för minst 3 None i rad, för alla kombinationer av 0 eller flera None då andra element saknas helt. Hanteringen av 0 var också problematisk i vissa fall. Vissa lösningar försöker titta om ett element är det sista genom att testa om element==seq[-1]. Som vi har varnat fungerar detta inte om samma element finns flera gånger i seq, exempelvis [15,20,15]. Hanteringen av maximum kan ske på många olika sätt. I lösningen ovan tar vi max(result), vilket alltid ger korrekt resultat då result redan innehåller alla månadsvärden. Man kan också ha en variabel som representerar "max hittills" och som hela tiden uppdateras för varje ny månad, men då måste man också se till att den uppdateras för alla månader. I vissa fall missades detta t.ex. för den allra sista månaden, som ofta blir ett specialfall efter att en loop har avslutats. ============================================================================= Allmän information om uppgift 2 ============================================================================= Lösningsförslag för 2a: def facit_rle_i(seq): result = [] # This is a version that handles one element at a time. for element in seq: if result and result[-1][1] == element: # Something was already added to result, # and our current element is the same as the last one added # So: We need to increment the count for the last tuple # But: Tuples can't be modified, so we must create a new tuple last_count = result[-1][0] last_element = result[-1][1] result[-1] = (last_count + 1, last_element) else: # This element is either the first one, or different from # the previous one. We have now found ONE such element. result.append((1, element)) return result Här var det relativt många som hade problem när det bara fanns 1 kopia av det sista elementet i sekvensen, som i [4,4,4,7,7,6]. Ett par klarade inte att seq innehöll None, och någon klarade inte att seq innehöll 0. Lösningsförslag för 2b: def facit_rle_r(seq): if not seq: return [] else: first_element = seq[0] rest = facit_rle_r(seq[1:]) if rest and rest[0][1] == first_element: # Our element is the same as the next element # For example, first_element = "hello", # and rest == [(2, "hello"), (4, "world")] # Should return [(3, "hello"), (4, "world")] return [(rest[0][0] + 1, first_element)] + rest[1:] else: # The next element in 'rest' was a different element return [(1, first_element)] + rest Här fanns inga uppenbara mönster i problemen. ============================================================================= Allmän information om uppgift 3 ============================================================================= Denna uppgift följer standardmönstret för traversering av nästlade listor: def facit_lookup_nested(seq: list, table: dict): result = [] for element in seq: if isinstance(element, list): # Rekursera ner i listor för att behandla deras element result.append(facit_lookup_nested(element, table)) else: result.append(table.get(element, None)) return result Exemplet ovan använder dict.get(nyckel, defaultvärde-om-nyckel-saknas). Det går också utmärkt att explicit testa om 'element in table' (if/else). Inga specifika problemmönster. ============================================================================= Allmän information om uppgift 4 ============================================================================= Här testas användning av högre ordningens funktioner. Lösningsförslag: def facit_pairwise_apply(f): def pairwise(l1, l2): result = [] for index in range(min(len(l1), len(l2))): result.append(f(l1[index], l2[index])) return result return pairwise Som ett alternativ kan man använda zip för att iterera över två eller flera listor på samma gång: def facit_pairwise_apply_2(f): def pairwise(l1, l2): result = [] for pair in zip(l1, l2): result.append(f(*pair)) return result return pairwise Några lösningar klarar inte att seq1 är längre än seq2 (men däremot att seq2 är längre än seq1), eller klarar inte motsatsen. Lösningsförslag för 4b: facit_pairwise_multiply = facit_pairwise_apply(lambda e1, e2: e1 * e2) ============================================================================= Allmän information om uppgift 5 ============================================================================= Detta är en lite längre uppgift, som bland annat går ut på att följa detaljerna i en beskrivning av en algoritm. Man ska dock tänka på att en stor del av koden upprepas två gånger "spegelvänt", genom att vi först tittar i seq1 för att hoppa i seq2 och sedan tittar i seq2 för att hoppa i seq1. Lösningsförslag: def facit_alternating_jumps(seq1, seq2, max_jumps): pos1 = 0 # Position in seq1 pos2 = 0 # Position in seq2 jumps = [] while len(jumps) < max_jumps: # How far would we jump, and where would we end up? jump = seq1[pos1] pos2 += jump # We're about to jump (before step C). Can we actually do this, # or would this result in a new position that is outside of # the borders of the sequence? if pos2 < 0 or pos2 >= len(seq2): # No, would go too far return ("out-of-bounds", jumps) # Step C: OK, we can perform the jump. jumps.append(jump) # Right after step C, did we reach the last element of both sequences? if pos1 == len(seq1) - 1 and pos2 == len(seq2) - 1: # Yes! We're done. return ("success", jumps) # Did we already reach the max number of jumps without reaching the # last element of both sequences? if len(jumps) == max_jumps: return ("no-more-jumps", jumps) # ------------------------------------------------------------------ # To avoid complications, let's just repeat what we did above, # but with the other sequence. # How far would we jump, and where would we end up? jump = seq2[pos2] pos1 += jump # We're about to jump (before step D). Can we actually do this, # or would this result in a new position that is outside of # the borders of the sequence? if pos1 < 0 or pos1 >= len(seq1): # No, would go too far return ("out-of-bounds", jumps) # Step D: OK, we can perform the jump. jumps.append(jump) # Right after step D, did we reach the last element of both sequences? if pos1 == len(seq1) - 1 and pos2 == len(seq2) - 1: return ("success", jumps) # Did we already reach the max number of jumps without reaching the # last element of both sequences? Then we'll just fall out of the loop if len(jumps) == max_jumps: return ("no-more-jumps", jumps) # We can't actually reach this point, because when len(jumps) == max_jumps, # we will *return* out of the while loop pass Här gäller det att verkligen följa alla delar av instruktionerna. För att maximera chanserna har vi uttryckligen diskuterat detta, lagt till konkreta exempel på sådant som kan vara frestande att ändra, och förklarat varför detta inte är en bra idé. Tyvärr har detta ofta inte lyckats. Exempel: "Kanske du vill testa ett villkor strax före ett hopp istället för när vi just har hoppat, eller ändra ordning på tester för att det ser bättre ut? Då löper du stor risk att ändra på algoritmen så den inte alls gör vad den ska, och att du inte har tillräckligt många testfall för att upptäcka det." Ett antal fel har uppstått för att man testar out-of-bounds *efter* att man försökte genomföra hoppet, vilket kan leda till IndexError eller att man får med för många element i svaret (jumps). "Tänk på att seq1 och seq2 kan innehålla samma värde flera gånger." Flera lösningar håller inte reda på positioner, utan bara på vilka element som finns. Att anropa seq.index(element) fungerar inte då seq==[2,2,2,2,2,2]. "Tänk på att slutvillkoren måste testas vid varje hopp, inte bara efter att två hopp har gjorts". Vissa lösningar får fel då man uppnår maxjumps efter ett udda antal hopp, eller ska lyckas efter ett udda antal hopp (eventuellt bara då detta antal är lika med maxjumps), eller liknande. ============================================================================= Allmän information om uppgift 6 ============================================================================= Lösningsförslag: def facit_make_deque(): return list() def facit_length(deque): return len(deque) def facit_front(deque): if facit_length(deque) > 0: return deque[0] else: return None def facit_back(deque): if facit_length(deque) > 0: return deque[-1] else: return None def facit_push_front_d(deque, elt): deque.insert(0, elt) def facit_pop_front_d(deque: list): if facit_length(deque) > 0: deque.pop(0) def facit_push_back_d(deque, elt): deque.append(elt) def facit_pop_back_d(deque): if facit_length(deque) > 0: deque.pop() def facit_push_front_f(deque, elt): deque2 = list(deque) facit_push_front_d(deque2, elt) return deque2 def facit_pop_front_f(deque): deque2 = list(deque) facit_pop_front_d(deque2) return deque2 def facit_push_back_f(deque, elt): deque2 = list(deque) facit_push_back_d(deque2, elt) return deque2 def facit_pop_back_f(deque): deque2 = list(deque) facit_pop_back_d(deque2) return deque2 Vissa hade problem med att stoppa in något i början av en lista, destruktivt. Här finns t.ex. funktionen seq.insert(0, element) som kan användas för detta syfte (hittas i dokumentationen). Man kan också göra seq[0:0] = [element]. Långsammare lösningar är t.ex. att lägga till ett element i slutet och sedan iterera för att flytta tidigare element ett steg "åt höger", eller att kopiera listan, nollställa den med seq.clear(), lägga till det nya första elementet, och till slut lägga till de gamla elementen igen. En sats som 'deque = deque[1:]', där deque är en lista, skapar en *ny* lista som innehåller färre element. Detta ändrar alltså inte på den existerande listan destruktivt, vilket testerna också visar. Detta kan lösas genom t.ex. deque.pop(0), en funktion som hittas i dokumentationen för listor (tillgänglig på nätet). Man kan också använda del deque[0] eller det lite mer obskyra deque[:1] = [], eller på liknande sätt som ovan, kopiera den gamla listan, nollställa deque med deque.clear(), och kopiera tillbaka de element man behövde.