Python - Hvilken framgangsmåte, problemløsning

[Axxxy]

Hei!

Driver å øver meg på å lage algoritmer med å løse problemer/oppgaver på denne siden her: https://projecteuler.net/problems

 

For øyeblikket står oppgave 31 for tur: https://projecteuler.net/problem=31

 

Jeg sitter litt fast da jeg er usikker på hvilken framgangsmåte jeg skal bruke, og hvordan jeg eventuelt skal få maskinen til å gjøre jobben.

 

Ser for meg at dette er den "enkleste" måten å gjøre det på (brute force)

from itertools import product

lst = [1, 2, 5, 10, 20, 50, 100, 200]
count = 0

for num in product(lst, repeat=200):
    if sum(num) == 200:
        count += 1

print "Ans: ", count

Her har vi 2'916'315'611'091 kombinasjoner vi må iterere over. Med laptopen jeg sitter med for øyeblikket vil dette ta ca 270 dager, noe som er helt på trynet. Vi trenger noe bedre.

 

Hvordan hadde dere villet gått fram for å løse ett slikt problem? (oppg. 31, link ovenfor)

 

Jeg tenker en slik metode:

Vi begynner med det største tallet(200). Siden 200 er svaret vi skal fram til, er dette den eneste kombinasjonen vi har der 200 er en del av formelen, derfor stryker vi den fra listen.

Vi går videre til det neste tallet, og bruker de største tallene vi har tilgjengelig for å oppnå 200. Altså:

100 + 100

Vi fortsetter med å bruke 100 som det første tallet, og må legge til nye tall:

100 + 50 + 50

Neste blir da:

100 + 50 + 20 + 20 + 10

100 + 50 + 20 + 20 + 5 + 5

100 + 50 + 20 + 20 + 5 + 2 + 2 + 1

100 + 50 + 20 + 20 + 5 + 2 + 1 + 1 + 1

osv

Når vi har fått med alle kombinasjonene som inneholder 100 (det største tallet for øyeblikket), fjerner vi det fra listen og går over til neste:

50 + 50 + 50 + 50

50 + 50 + .....

 

Dette var den første algoritmen jeg kom på som virket aktuell å bruke, da vi vil begrense kombinasjoner der vi oppnår ett produkt som er større enn 200, ved å ikke summere i stigende rekkefølge.

Men jeg vet for øyeblikket ikke hvordan jeg skal få dette til.

Noen som ser en løsning på min algoritme?
Noen som har en bedre algoritme?

Og ja, googler du, så finner du løsninger der. Tenkte der var lettere å få en bedre forståelse på slike problemer med feedback.

 

Noen andre som også bruker ProjectEuler?

Endret 29. oktober 2014 av Axxxy

[hemuline]

Ooooh, kul side. Kan godt prøve å hjelpe deg, men vet ikke om jeg får tid idag.

[Axxxy]

Ooooh, kul side. Kan godt prøve å hjelpe deg, men vet ikke om jeg får tid idag.

Ja, en veldig kul side indeed. Du registrerer deg for å holde styr på hva du har klart. Når du har logget deg inn, og du tror du har løsningen, så får du muligheten til å poster svaret ditt, og du vil får en tilbakemelding på om det var rett eller galt. Når du har fått rett svar, får du tilgang til ett forum som omhandler oppgaven du nettopp løste. Der kan du se hvordan andre løste oppgaven.

Det gøye er at du kan bruke hvilket som helst språk.

[zotbar1234]

Ser for meg at dette er den "enkleste" måten å gjøre det på (brute force)

Brute force er *alltid* feil hos projecteuler.

 

De aller fleste oppgavene kan løses på <1 sekund uansett språkvalget.

 

 

from itertools import product

lst = [1, 2, 5, 10, 20, 50, 100, 200]
count = 0

for num in product(lst, repeat=200):
    if sum(num) == 200:
        count += 1

print "Ans: ", count

 

denne vil prøve på kandidater som 50 + 50 + 50 + ... + 50, hvorpå det er opplagt etter den 3. +-en at det ikke kan være flere løsninger når de første 4 denominasjonene er 50. Jeg må dog belønne enkeltheten. En annen svakhet er at du vil prøve å generere løsninger for samme restbeløp på nytt (hvis 1GBP er igjen, vil du regne på nytt alle muligheter når 1GBP fås vha 1GBP-mynt eller 2 50pence-mynter).

 

Hvis du ikke bruker product(), men istedet satser på en rekursiv løsning, vil du kunne slippe *veldig* billig unna ved å bruke memoization (det første svaret i kjøreeksempelet under). Imidlertid er dette litt juks og uelegant (det er litt som å regne fibonacci-tall rekursivt og gjøre svaret raskt vha memoization)

 

Her har vi 2'916'315'611'091 kombinasjoner vi må iterere over.

Nei.

 

Du har rundt 2^600 kombinasjoner å gjøre en lineær sum over. 270 dager er et *VELDIG* optimistisk estimat (len(product(seq, repeat=N)) er len(seq)**N).

 

Jeg tenker en slik metode: (...)

Men jeg vet for øyeblikket ikke hvordan jeg skal få dette til.

Noen som ser en løsning på min algoritme?

Ideen er å bruke din forklaring rett fram:

 

for A in range(200, -1, -200):   # take 0, 1 2GBP coins. A is remaining sum to cover.
    # calculate the remaining solutions
    for B in range(A, -1, -100): # assuming A 2GBP coins are taken, take 0, 1, 2 1GBP coins
        # calculate the remaining solutions 
        # ... and so on

... veldig ikke-pent, men ganske kjapt:

 

$ python problem31.py 
puzzle problem31.py, solution: X (in 0.024274s)
puzzle problem31.py, solution: X (in 0.251700s)   <--
puzzle problem31.py, solution: X (in 0.094067s)
puzzle problem31.py, solution: X (in 0.000185s)

(det 2. tallet). Det overrasket meg nå at den rekursive varianten av denne ideen brukte mindre tid enn løkkene (men kanskje er navneoppslag veldig krevende i nestede løkker).

 

Noen som har en bedre algoritme?

 

Definer "bedre". Jeg synes den aller peneste algoritmen utnytter den følgende ideen:

 

Vi kan generere summen S ved å legge 1 til summen (S-coin) for alle coin \in (200, 100, 50, 20, 10, 5, 2, 1). Altså, gitt en liste over partielle løsninger med alle mynter m_0, .., m_k, vil vi få løsninger for sum S som involverer mynt m_{k+1} ved å legge til løsninger for sum (S - m_{k+1}) til (de partielle vi allerede har) løsninger for sum S. Dette vil tilsvarede alle kombinasjoner der m_{k+1} er med samt de kombinasjonene der m_{k+1} ikke er med.

 

Vi vil naturligvis måtte regne ut alle summene fra 0 til 200 i dette tilfellet, men minneforbruket er svært svært lavt.

 

Det vakre her er at man kan eksperimentere med vilkårlige (heltallige) denominasjoner i myntesystemet svært svært enkelt.

 

Noen andre som også bruker ProjectEuler?

Etter å ha løst alle de "enkle" problemene, har det gått veldig sakte

[hemuline]

 

Ooooh, kul side. Kan godt prøve å hjelpe deg, men vet ikke om jeg får tid idag.

Ja, en veldig kul side indeed. Du registrerer deg for å holde styr på hva du har klart. Når du har logget deg inn, og du tror du har løsningen, så får du muligheten til å poster svaret ditt, og du vil får en tilbakemelding på om det var rett eller galt. Når du har fått rett svar, får du tilgang til ett forum som omhandler oppgaven du nettopp løste. Der kan du se hvordan andre løste oppgaven.

Det gøye er at du kan bruke hvilket som helst språk.

 

Ja, det er nice Takk for tipset!

 

Ser at mange av oppgavene vi har fått på øvinger og prøver er tilnærmet identiske med noen av oppgavene på siden. Oppg. 1, blant annet.

[etse]

Jeg ville løst oppgaven rekursivt. Tenkt noe i den duren her:

 

def finnAntallMuligeKombinasjoner(rest_beløp):
    kombinasjoner = 0
    for hver myntenhet lavere enn rest_beløp:
        kombinasjoner += finnAntallMuligeKombinasjoner(rest_beløp - myntenheti)
    return kombinasjoner

Selvfølgelig med litt modifikasjoner. Viktig å sørge for at den ikke tester samme kombinasjoner flere ganger. I naiv implementersjon ville f.eks. sett på

 

50p + 50p + 100p som noe annet enn 100p + 50p + 50p. Og ville derfor testet ut mange flere kombinasjoner enn strengt tatt nødvendig. (og kommet til feil svar).

 

En justering ville da kanskje vært:

1: Velg en mynt fra mulige myntenheter med lavere verdi enn restbeløpet

2: Finn alle mulige kombinasjoner med kun mynter av lavere eller samme verdi som mynten du valgte.

 

psaudo-kode i spoiler:

 

 

def finnKombinasjonerForMynter(restverdi, mulige_mynter):
    hvis restverdi er 0:
        returner 1
    
    for hver mynt i mulige_mynter med verdi lavere eller lik restverdi:
        antallKombinasjoner += finnKombinasjonerForMynter(restverdi-myntverdi, [mynter med lavere verdi enn mynt])
    return antallKombinasjoner

 

Endret 29. oktober 2014 av etse

[Axxxy]

Det var litt tungt det her. Har jo løsningen, men sliter med å få det over til kode. Hjelper jo på med deres eksempel, men er ikke i mål enda.

 

Du har rundt 2^600 kombinasjoner å gjøre en lineær sum over. 270 dager er et *VELDIG* optimistisk estimat (len(product(seq, repeat=N)) er len(seq)**N).

Selvfølgelig.. glemte å ta med at rekkefølgen var viktig.

8(n) mulig tall, der 200® blir brukt = n^r = 8^200 = 2^600. Universet er borte når det er løst.

 

 

 

Noen som har en bedre algoritme?

Definer "bedre".

Bedre: raskere, finere, kortere eller enklere, osv

 

 

Vi kan generere summen S ved å legge 1 til summen (S-coin) for alle coin \in (200, 100, 50, 20, 10, 5, 2, 1). Altså, gitt en liste over partielle løsninger med alle mynter m_0, .., m_k, vil vi få løsninger for sum S som involverer mynt m_{k+1} ved å legge til løsninger for sum (S - m_{k+1}) til (de partielle vi allerede har) løsninger for sum S. Dette vil tilsvarede alle kombinasjoner der m_{k+1} er med samt de kombinasjonene der m_{k+1} ikke er med.

Må innrømme jeg ikke skjønner så alt for mye av dette her, men det er derfor jeg øver. Kanskje det vil komme seg over natten.

 

 

Jeg ville løst oppgaven rekursivt. Tenkt noe i den duren her

Ditt eksempelet var litt mer overkommelig. Prøvde meg på det nå nettopp, men ble avbrutt av maximum recursion depth exceeded. Selv når jeg hadde skrevet:

import sys
sys.setrecursionlimit(10000)

Så det er noe jeg har gjort feil.

 

I mellomtiden prøvde jeg selv på å løse oppgaven med for/while loops, der formler skulle regne seg fram til en forandrende index.

-Er det mulig, bruk samme tall

-Er summen over 200, trekk i fra forrige tall og prøv det neste i rekken.

Det ble for mye, og jeg falt av.

 

Takk for feedbacken jeg har fått så lang forresten!

Endret 29. oktober 2014 av Axxxy

[etse]

Du burde lære deg rekursjon. det er en fantastisk måte å løse slike problemer enkelt på. Selve problemet kan lett visualiseres som en form for tre. Hvor du hele tiden nedover i treet får et valg mellom ulike valg (hvor du får velge mellom alle gjenstående mynter). Og målet er å telle antall løvnøder i dette treet.

 

Bare for å ha det nevnt, så er rekursjonsløsningen jeg beskrev en veldig forenklet variant av noe som kalles et dybde først søk i "graftoeri"

 

-----------

 

Men se på det på denne måten.

Sett opp en liste med tilgjengelige mynter. Og gi deg selv et valg hvor du kan velge en vilkårlig mynt - om du velger en mynt kan du ikke på senere tidspunkt velge en mynt med høyere verdi.

 

La oss se på et enkelt alternativ med myntene 1, 2, 3 og 5, hvor du ønsker å lage opp til verdien 10. (forenkling). Og vi følger reglene at etter du har valgt en mynt kan du aldri velge en mynt med høyere verdi. Da kan man presentere alle mulige valg som et tre som ligner dette: (du begynner på toppen, og gjør valg for å komme deg nedover.)

 

Du begynner altså med 4 valg, som er myntene 1, 2, 3, 5.

Hvis du velger mynten med 1 som verdi får du ikke lov (grunnet regelen vi satt) til å velge noen mynter med høyere verdi - og du blir derfor tvunget til å kun velge denne helt til du når verdien 5 som var vår ønsket verdi.

 

Du backtracker så tilbake til den forrige plassen du kunne gjøre et valg - og velger nå en annen mynt. Nå velger vi 2.

 

Siden vi valgte 2 først, kan vi nå velge mellom 1 eller 2. Selv om 2+3 ville gitt oss 5 får vi ikke lov til å ta dette valget siden 3 er større enn 2 som vi valgte først. Og dette valget blir uansett testet når man kommer til å velge 3 først, for så å ta 2 etterpå.

 

Til slutt har man da gått alle mulige veier gjennom "treet", og som du kan se av tegningene finner man da totalt 6 forskjellige stier man kan gå. Dette betyr da at det er 6 forskjellige måter man kan brukte mynter av verdiene 1,2,3,5 til å danne verdien 5.

[Axxxy]

Du burde lære deg rekursjon. det er en fantastisk måte å løse slike problemer enkelt på.

Takk for ett godt eksempel! Forstår konseptet av rekursjon, men det å visualisere seg at man går dypere og dypere i det samme mønsteret, for så å returnere svarene bakover, sitter ikke helt på greip hos meg. Ditt eksempel derimot åpnet opp for en ny forståelse av temaet. Takk skal du ha

[etse]

Om du ønsker å se et eksempel på mulig løsning har jeg laget en med masse kommentarer hvor jeg prøver å forklare hva jeg tenker i hvert steg. Denne er rekursiv - og håper det kan hjelpe deg litt med å forstå rekursjon.

 

http://pastie.org/9684331

 

-------------

 

For å hjelpe deg med å komme i gang med å lære rekursjon kan det være en god øvelse å gjøre noen oppgaver. La oss starte med noen eksempler: Sortering. La oss først ta en veldig primitiv algoritme for sortering.

 

La oss si du har en liste med tall du skal sortere. Hva om definerer sortering som følgende algoritme:

1: Hvis listen har kun 1 tall, returner listen som den er. Den er sorterter.

2: Hvis listen har mer enn 1 tall: Ta ut det minste tallet.

3: Sett det minste tallet først i en ny liste, sorter restene av tallene og putt de bak.

 

I python blir dette noe som dette:

def sort(list):
    if len(list) is 1:
        return list
    lowest = min(list)
    list.remove(lowest)

    return [lowest] + sort(list)

Det som skjer her er at du hele tiden velger det minste elementer og putter det først, og lar resten av listen bare være rot - og ber deg selv sortere denne delen. Som betyr at du på neste steg vil sette det nest-minste elementet (det som nå er det minste siden du fjernet det andre) først i den nye listen - som du setter bak det minste elementet. På denne måten vil du hele tiden få sortert et og et element.

 

Man har også en variant som heter QuickSort. Denne bruker litt prinsippet som den forrige, med litt forbedringer.

1: Om listen er tom eller kun har et element så er den sortert, returner derfor listen og ikke gjør de andre stegene

2: Ta et tilfeldig element ut av listen

3: La 2 lister "større_enn" og "mindre_enn".

4: Gå gjennom alle tallene i listen, putt alle tallene som er større enn elementet i listen med større_enn, og alle de andre i mindre_enn. (ikke bry deg om rekkefølgen).

5: Sorter mindre_enn

6: sorter større_enn.

7: returner mindre_enn + [tallet_jeg_valgte] + [større_enn]

 

def sort(listToSort):
    if len(list) <= 1:
        return list

    my_number = list.pop()
    bigger = list()
    smaller = list()

    for number in listToSort:
        if number < my_number:
            smaller.append(number)
        else:
            bigger.append(number)

    bigger = sort(bigger)
    smaller = sort(smaller)
    return smaller + [my_number] + bigger

Denne koden kan visualiseres på følgende måte:

La oss si du har en bunke med tøy som du ønsker å sortere etter størrelse. Fra minst til størst. Og definerer sortering på følgende måte:

 

Velg et tilfeldig plagg.

Putt alle plagg som er større i en bunke til høyre

Putt alle plass som er mindre i en bunke til venstre

Sorter bunkene på hver sin side med samme algoritme.

 

Når du har delt opp bunken mange nok ganger vil du sitter igjen med mange små bunker med kun et plagg hver. Og alle bunkene vil nå ligge i rekkefølge fra minst til størst -så da er det bare å slå sammen alle bunkene til en stor bunke.

[Axxxy]

Om du ønsker å se et eksempel på mulig løsning har jeg laget en med masse kommentarer hvor jeg prøver å forklare hva jeg tenker i hvert steg. Denne er rekursiv - og håper det kan hjelpe deg litt med å forstå rekursjon.

 

http://pastie.org/9684331

Har dessverre ikke hatt tid til å se på posten din enda. Skal se om jeg får gjort det i kveld, så kjapt på det, og du beskriver godt, takk for det!

 

Fikk en åpenbæring her nå nettopp. Dette er siste gangen jeg prøver på denne oppgaven slik. Vil gå gjennom rekursjon for å se om det faktisk gjør jobben lettere, eller bare koden mer "oversiktelig" i slike situasjoner.

http://pastebin.com/kZbMEGfC

Er jeg på rett vei? Har jo ikke fått testet scriptet, verken for funksjon(er jo ikke ferdig) eller skrivefeil/error. Slik jeg tror det så mangler jeg bare en sjekk på linjenr. 36-37.

Denne skal sjekke om det fortsatt er mulig med flere kombinasjoner med det nåværende max tallet(200). Har vi gått gjennom alle kombinasjonene med nåværende max tall, så fjerner vi det(200), og står igjen med en liste med ett mindre tall (der 100 er nåværende max tall).

Usikker på hvordan jeg skal sjekke dette.

Bør jeg f.eks lage en set(), lagre alle kombinasjonene i en tuple, for deretter å legge tuplen til settet. Om jeg da har prøvd å legge til samme kombinasjon i sette før, så vet jeg at vi er på siste kombinasjon med nåværende max tall?

s = set()

kode..
..
../kode

>>> currentComb = (100, 50, 50)

#Combination already in set
if currentComb in set:
    <remove max value in current lst>
else:
    set.add(currentComb)

Endret 1. november 2014 av Axxxy

[slacky]

def combos_that_sums_to(sum, choices): 
  nways = [1] + [0]*sum
  upper = sum+1;
  for item in choices: 
    for i in range(item, upper):
      nways[i] += nways[i-item]
  return nways[sum]

 
print combos_that_sums_to(200, [1,2,5,10,20,50,100,200])

>>> 73682

 

Burde være rimelig kjapp måte å telle antall komboer som adder til en gitt verdi.

 

Edit: Ser jeg er litt sent ute.

Endret 4. november 2014 av slacky