TDDE44. DAT1. 2hp. 2025-08-22 kl. 14.00-18.00 - Lösningsförslag
Själva tenta-PDF:en och bifogade filer finns här. Notera att lösningsförslagen nedan inte är uttömmande utan representerar en eller några få möjliga lösningar. Det finns ofta flera olika lösningar med olika för och nackdelar.
Del 1
Uppgift 1.1
Uppgift 1.1.1 - lös med lämplig loop
En for-loop är lämplig eftersom vi har en given struktur att iterera över.
1
2
3
4
5
|
def mult_as_rep_add(factor1, factor2):
res = 0
for _ in factor1:
res += factor2
return res
|
Uppgift 1.1.2 - lös med lämplig loop
En while-loop är lämplig eftersom vi inte vet hur många iterationer som krävs innan villkoret är uppfyllt.
1
2
3
4
5
6
7
|
def years_to_cutoff(start_val, rate, cutoff):
num_years = 0
cur_val = start_val
while cur_val <= cutoff:
cur_val += cur_val * rate
num_years += 1
return num_years
|
Uppgift 1.2 - lös med rekursion
Exempel på en lösning med en funktion och användning av extraparameter n med defaultvärde 0:
1
2
3
4
5
|
def polyval(coeffs, x, n=0):
if n == len(coeffs):
return 0
else:
return coeffs[n] * (x ** n) + polyval(coeffs, x, n+1)
|
Uppgift 1.3
Eftersom vi kan anta att vi inte har några tak som hänger i luften utan några hus under så behöver vi bara hitta det första taket uppifrån:
1
2
3
4
5
6
|
def get_height_of_tallest_skyscraper(skyline):
skyheight = len(skyline)
offset = 0
while 1 not in skyline[offset]:
offset += 1
return skyheight - offset
|
Det går självklart också att tänka sig många andra lösningar som att t.ex. transponera representationen så att raderna representerar enskilda skyskrapor och sedan beräkna den maximala radsumman.
Uppgift 1.4
1
2
3
4
5
6
7
8
9
10
11
|
class PlayerCharacter:
def __init__(self, name):
self.name = name
self.health = 100
def is_dead(self):
return self.health <= 0
def take_damage(self, damage):
self.health -= damage
|
Uppgift 1.5
Ett vanligt misstag här var att dela upp tokenized_text i separata ord genom att skriva tokenized_text.split(" ") vilket innebar att man blev tvungen att hantera radbrytningar manuellt, något som rörde till det för många. Hade man utelämnat argumentet till split så sker uppdelningen på alla former av “whitespace”, exempelvis mellanslag, tab-tecken och radbrytning.
Ett annat någorlunda vanligt fel var lösningar som gjorde något i stil med detta:
1
2
3
|
words = tokenized_text.split()
for word in words:
frequencies[word] = words.count(word)
|
Metoden count måste nödvändigtvis gå igenom samtliga element i listan words för att räkna förekomster. Det innebär att för varje ord i listan så söks hela listan igenom, vilket innebär en tidskomplexitet på $O(n^2)$. En sådan lösning är inte rimlig när man istället för att anropa count på ett ord, helt enkelt kan räkna ordet som i lösningen nedan med linjär tidskomplexitet ($O(n)$):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def calculate_word_frequencies(tokenized_text) -> dict:
freqs = dict()
for token in tokenized_text.split():
if token.isalpha():
add_occurence(token.lower(), freqs)
return freqs
def add_occurence(token, frequencies) -> None:
if token in frequencies.keys():
frequencies[token] += 1
else:
frequencies[token] = 1
def count_file(filename):
""" Used for testing only."""
with open(filename) as infile:
content = infile.read()
return calculate_word_frequencies(content)
|
Del 2
Uppgift 2.1 (5p)
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
|
def is_parking_ok(carpark):
# gå igenom alla parkeringsplatser
for row_index, row in enumerate(carpark):
for col_index, _ in enumerate(row):
if not check_space(carpark, row_index, col_index):
return False
return True
def check_space(carpark, row_index, col_index):
# kolla på grannar, endast om parking_space är upptagen
if carpark[row_index][col_index]:
# kolla grannplatser öster och söder om aktuell plats
if not (ok_east(carpark, row_index, col_index)
and ok_south(carpark, row_index, col_index)):
return False
return True
def ok_east(carpark, row_index, col_index):
# Platsen är ok om ingen plats finns till öster eller platsen till
# öster är tom
return (col_index == len(carpark[row_index])-1
or carpark[row_index][col_index+1] == 0)
def ok_south(carpark, row_index, col_index):
# Platsen är ok om ingen plats finns till söder eller platsen till
# söder är tom
return (row_index == len(carpark)-1
or carpark[row_index+1][col_index] == 0)
|
Uppgift 2.2 (5p)
Kan lösas på flera olika sätt, här är ett av dem:
1
2
3
4
5
6
7
8
9
10
11
12
|
def unique(l):
return len(l) == len(set(l))
def subsequences_without_duplicates(values):
result = []
last_index = len(values)+1
for start_index in range(len(values)):
for length in range(1, last_index-start_index):
candidate = values[start_index:start_index+length]
if candidate not in result and unique(candidate):
result.append(candidate)
return result
|
Uppgift 2.3 (5p)
Uppgiften har den förenklande egenskapen att varje valör är en faktor i alla större valörer, så det går att bara kolla största till minsta valören utan felaktiga svar.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def pay_even(wallet, price):
if sum(wallet) < price:
return "kan inte"
wallet = sorted(wallet, reverse=True)
total = 0
used_coins = []
for coin in wallet:
if total + coin > price:
continue
total += coin
used_coins.append(coin)
if total == price:
return used_coins
return "vill inte"
|
Lite knöligare lösning men bör fungera i det generella fallet även när varje valör inte är en faktor i alla större valörer. Rent algoritmiskt så letar vi oss igenom ett träd där varje nod kan sägas representera en summa och vägen från roten till en viss nod representerar de mynt som ingår i den summan. Oputsad och kan antagligen snyggas till och renodlas ytterligare. Inkom gärna med motbevis om det skulle visa sig att den här lösningen inte fungerar för det generella fallet.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def pay_even_rec(wallet, price):
def inner(wallet, selection):
current_sum = sum(selection)
if current_sum == price:
return selection
if not wallet:
return False
res = inner(wallet[1:], selection + wallet[0:1])
if res:
return res
else:
return inner(wallet[1:], selection)
if sum(wallet) < price:
return "kan inte"
else:
result = inner(tuple(sorted(wallet, reverse=True)), tuple())
if result:
return result
else:
return "vill inte"
|
English web site
