Ordlek
Sitter helt fast på hur man kan lösa det här. Jag kan testa om en lista är som de vill ha den eller inte, så tänkte att jag kanske kan sätta ihop alla permutationer och testa, men har ingen aning om hur jag skulle få fram alla dem isf.
Du skulle kunna använda rekursion för att söka igenom alla kombinationer.
Alternativ så kan du göra det enkelt för dig och använda permutations i itertools.
Visa spoiler
from itertools import permutations
for perm in permutations(['the','list','of','words']):
print(perm)
Får inte importera saker. Hur hade du gjort med rekursion?
Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.
Först hade jag nog faktiskt skapat en dictionary så att jag snabbt kan se om det finns något ord som passar.
Men typ (pseudokod):
find(list, [])
function find(list, curr_list):
if list is not ok: return false
if list is empty:
return curr_list
for word in list:
move word from list to curr_list
ans = find(list, curr_list)
if ans not false: return ans
move word from curr_list to list
Kan mycket väl ha missat något...
Är listan du kallar list den man får från början och vill möblera om? Den kommer väl nästan alltid vara fel från början så då borde det bara stå falskt jämt om man testar det först?
Är tanken att orden ska byta ordning i for-loopen på något sätt?
Oj, det skulle vara
if curr_list is not ok: return false (det blir väl att kolla att om listan innehåller >= 2 ord så att sista ordet passar med näst sista).
Tanken med for-loopen är att testa alla varianter av ord som är kvar i listan (ju längre ner du kommer i rekursionen, desto färre är kvar i listan, till slut är den tom, om man nu kommer så långt).
Jag kan inte riktigt se vad som händer. Vad är tanken med curr_list?
Nej det brukar vara lite svårt med rekursion att tänka ut exakt vad som händer. Rekommender att du implementerar det och skriver ut för att se.
curr_list är listan av ord i rätt ordning, som flyttats från list. Om du flyttat alla ord från list -> curr_list och curr_list är ok, så är du klar.
(Behövs en return false på slutet förresten, efter for-loopen)
Testade göra, men den kastar inte om någon ordning. Den släpper igenom listor som redan är rätt iaf. Vad har jag klantat till?
def bralista(x):
if len(x)<=1:
return True
t=x[0][-1]
for s in x[1:]:
if not s[0]==t:
return False
t=s[-1]
return True
def hittare(lst,ny):
if bralista(ny)==False:
return False
if not lst:
return ny
for x in lst:
ny += [x]
lst.remove(x)
ans=hittare(lst,ny)
if not ans==False:
return ans
lst+=ny[-1]
return False
print(hittare(['abc','efg','dce'],[]))
Först och främst är det väl inget superbra testfall eftersom det inte finns en lösning där.
Har du testat så att bralista(x) fungerar som du tänker? (ledning: det tror jag inte den gör)
Lägg till print('Listor: ', lst, ny) innan ans=hittare(lst,ny) så kan du se vad som händer.
Använd lista.append(x) när du lägger till i en lista. Sen på slutet måste du ta bort ny[-1] (som ju är samma som x) från ny också, inte bara lägga till i lst.
Om man vill använda en effektiv algoritm kan man titta här: https://en.wikipedia.org/wiki/Eulerian_path.
Mycket jobb för en ynka poäng, tycker jag, även om man bara använder brute force med rekursivitet.
Hur menar du? Tänker du orden som en kant på något sätt, annars blir det inte så bra att besöka en nod mer än en gång.
Åhh, jag älskar grafteori 😍 Men jag har aldrig kombinerat det med programering förut..
Fattar grejen med eulervägen och det, men hur gör man en graf i python? En lista med ordnade par?
Här har kanten en egenskap också, nämligen sitt ord, så man kan använda en lista av tre-tupler, med första bokstaven, sista bokstaven, samt hela ordet. Man kanska vill använda dictionaries i stället.
Fortfarande inte riktigt klart för mig hur det blir effektivt :)
Men problemet går ju bra att formulera som ett grafproblem. Tänker att orden är noder, sen skapa kanter genom att följa regeln med bokstäverna. Gör man DFS (depth first search) blir det ju ungefär som ovan, en BFS (breadth first search) kanske kan vara något effektivare (starta från alla noder), men tveksamt?
Sak samma om det är effektivt, jag har aldrig testat graf så bara det funkar.
Jag tror bralista gör vad jag tänker?
Aha, när jag kopierade inte din kod intenderade jag t=s[-1] fel (går ju inte att skriva kod här alltså, suck).
Men då ser det ju bra ut! Så här ändra jag din for-loop:
for x in lst:
ny.append(x)
lst.remove(x)
ans=hittare(lst,ny)
if not ans==False:
return ans
lst.append(x)
ny.remove(x)
Vad är det för fel på att plussa listor? Och det verkar bli något konstigt efter ett tag, den hoppar över steg..
Ah sorry, det är inte en bra idé att ta bort något från en lista medan det itereras över samma lista.
Du kan lösa det genom att göra en kopia.
iter_list = lst.copy()
for x in iter_list:
...
Nu funkar det ju 😃👏👏
Ska se om jag hittar någon lättare uppgift att öva grafer med, men det måste definitivt testas också. Tack!
emilg skrev:Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.
Går det här att göra utan tillgång till internet?
Micimacko skrev:emilg skrev:Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.
Går det här att göra utan tillgång till internet?
Nja, om du bara har ett standardsystem så lär det väl inte finnas där. Men om du laddade ner källkoden till python och sen kompilerade det själv, ja då har du det på din dator.
(cPython är dock implementerat i C tror jag)
