NØTTER ("4 int", og flere!)

[teflonpanne]

Lagde et lite program i haskell som lager en uendelig liste med alle tallrekkene som ble postet tidligere i tråden:

 

next prev count [] = count : prev : [] -- dette er hvis vi er på slutten av lista, legg bare til counten og forrige verdi
next prev count list@(x:xs) = if prev == x 
                             then next prev (count + 1) xs -- hvis forrige er like denne, kall funksjonen på nytt men øk counten med 1
                             else count : prev : next x 0 list -- hvis ikke, lag en liste med nåværende verdi, count og kall funksjonen på nytt med neste verdi og en count på 0 

numbers function list = list : numbers function (function (head list) 0 list) -- lag en uendelig liste av lister

 

Sånn funker det hvis du vil ha de 10 første listene:

*Main> take 10 (numbers next [1])
[[1],[1,1],[2,1],[1,2,1,1],[1,1,1,2,2,1],[3,1,2,2,1,1],[1,3,1,1,2,2,2,1],[1,1,1,3,2,1,3,2,1,1],[3,1,1,3,1,2,1,1,1,3,1,2,2,1],
[1,3,2,1,1,3,1,1,1,2,3,1,1,3,1,1,2,2,1,1]]

 

Hvis du vil ha liste nr. 100 skriver du:

drop 99 (take 100 (numbers next [1]))

men det tar sin tid

Endret 21. juni 2007 av teflonpanne

[Frysning]

Det er søndag, og jeg kjeder meg.

En nøtt takk?

[anders02]

Det er søndag, og jeg kjeder meg.

En nøtt takk?

8934500[/snapback]

 

Jeg har en oppgave til deg: Lag et program som løser følgende problem/spill: http://amby.com/go_ghoti/javagame/lights.html

 

Hvor lang tid bruker programmet ditt på å finne en løsning?

[teflonpanne]

Vet du om en algoritme til det der eller er det bare bruteforce?

[anders02]

Vet du om en algoritme til det der eller er det bare bruteforce?

8935899[/snapback]

 

Det finnes grovt sett 3 måter å gjøre det på:

- Brutforce. Det tar altfor lang tid.

- Klikk på en tilfeldig knapp og se om problemet er løst. Hvis det ikke er det klikker du på en ny tilfeldig knapp. Fortsett slik til du har vunnet. Tar vanligvis mye kortere tid enn brutforce, man er ikke sikker på om man finner løsningen.

- En algoritme som er ufattelig mye raskere enn alternativene over.

 

Jeg kan komme med noen flere tips hvis det er ønskelig.

[teflonpanne]

Ja, de to første kunne jeg tenke meg fram til, men det er altså en spesiell algoritme ja Får tenke litt til på den. Burde forøvrig stå XOR i beskrivelsen da.

 

En annen nøtt som kanskje er litt lettere som har blitt postet i en matematikktråd på forumet: på hvor mange måter kan man veksle en 50-lapp?

[teflonpanne]

Ok, kom gjerne med et par tips til algoritmen

[anders02]

Min løsning er en form for bruteforce, men gjøres på en mye, mye mindre del enn det en fullstendig bruteforce vil gjøre.

 

Mitt program finner forøvrig også alle løsninger.

[teflonpanne]

Googlet litt, ser det fins noen algoritmer

[Frysning]

For en nøtt, noen som vil poste en løsning? (a)

[anders02]

Min erfaring med slike problemer er at det ofte kan lønne seg å la slike oppgaver ligge noen dager i bakhodet. Kanskje diskutere det med noen andre, kanskje spille spillet noen ganger.

 

En oppgave man finner svaret på i løpet av kort tid er, etter min mening, en kjedelig oppgave.

 

Jeg lover å komme med en løsning, men den kommer ikke i dag, dessverre.

[teflonpanne]

Fant du ut algoritmen selv? 'Chasing the lights'-algoritmen er rimelig rett frem å programmere, men jeg hadde aldri kommet på den selv.

[anders02]

Fant du ut algoritmen selv? 'Chasing the lights'-algoritmen er rimelig rett frem å programmere, men jeg hadde aldri kommet på den selv.

8937297[/snapback]

 

Jeg vet ikke hvordan Chasing the lights-algoritmen er, jeg vet derfor ikke hvor forskjellig den er fra min, eller om den er mer generell enn min.

 

Årsaken til at jeg løste problemet var at jeg spilte spillet en del ganger uten å vinne. Det var litt kjipt, så jeg laget en bruteforce-løsning for å finne alle løsninger. Den tok litt lang tid, så jeg laget trykk-på-en-tilfeldig-knapp-og-sjekk-svaret-løsning.

 

Etter det brukte jeg en god stund på å tenke ut en løsning som var bedre enn de to ovennevnte. Så ja: Algoritmen jeg bruker har jeg funnet helt selv, og jeg har ikke lest noe om det spillet.

 

Jeg kan forklare hvordan min algoritme tenker i morgen, det er litt for sent for det nå.

 

Selve spillet (ikke løsningen) har forøvrig i en del år vært det første programmet jeg lager når jeg prøver meg på et nytt programmeringsspråk, men det er en annen historie.

[Frysning]

Da er jeg klar for en løsning på den chasing lights greien. ?

[anders02]

Da er jeg klar for en løsning på den chasing lights greien. ?

8945095[/snapback]

 

La meg nummerere spillebrettet som følger, så det blir lettere å henvise til de ulike knappene:

01 02 03 04 05

06 07 08 09 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

 

Det første du gjør er å klikke på et tilfeldig antall av knappene i den øverste raden (01-05). La oss si at knappene i den øverste raden som er lyse når det er gjort er 01, 02 og 05. I tillegg vil noen av knappene på rad to lyse.

 

Det er da gitt hvilke knapper i rad to du må klikke på for at alle knappene i den øverste raden skal lyse. I mitt eksempel vil dette være knapp 08 og 09. Når de to er klikket vil det være gitt hvilke knapper i tredje rad som må klikkes. Fortsett slik til du har klikket på knappene i rad fem som må klikkes. Hvis alle lyser har du funnet løsningen. Hvis ikke nullstiller du brettet og velger et annet utgangspunkt i øverste rad.

 

I stedet for å velge tilfeldige knapper i øverste rad å klikke på velger du heller systematisk å gå gjennom alle valg. Totalt bli det 2^5 = 32 kombinasjoner, et antall som er relativt lite for dataen, og faktisk så lite også at du kan løse spillet uten å kode noe også.

 

Alternativet med bruteforce vil være 2^25 = 33 554 432 muligheter, noe som vil ta over én million ganger lenger tid enn min løsning.

 

Gi beskjed hvis du trenger ytterlige forklaringer. Hvis du skjønte problemet er det din tur til å komme med en ny oppgave.

[Frysning]

Nei, du får komme med enda en nøtt du.

God nøtt. Keep em coming.

Endret 26. juni 2007 av Frysning

[anders02]

Nei, du får komme med enda en nøtt du.

God nøtt. Keep em coming.

8951469[/snapback]

 

Greit sjef, denne gangen tar vi en oppgave der du må lage et program i et C-lignende språk (f.eks. Java eller C#). Jeg eide en gang en programmeringsbok der denne oppgaven stod mot slutten av kapittelet om rekursjon.

 

Tenk at vi har en funksjon som returnerer følgende:

f(1) = 1

f(2) = 2

f(x) = f(x-1) + f(x-2) for x > 2

 

f er bare definert for hele tall > 0, så resten av tallene trenger du ikke bry deg noe om.

 

Din jobb er enkel, finn f(20), f(100) og f(1000).

[Frysning]

Jeg jobber med å få produsert noe kode som prøver å løse den lights greien.

Har du noe ferdig kode?

 

Hvert problem må bare få en skikkelig gjennomgang, så jeg går ikke videre får jeg forstår dette skikkelig og har produsert et stykke effektiv kode som løser dette problemet.

 

Skal få tak i en bok imorgen, "algoritmer og datastrukturer".

 

Jeg kan altfor mye, har lest veldig mye. Men aldri egentlig anvendt noe av dette, lite motivert siden programmering bare er hobby og jeg sjeldent har tid eller motivasjon til å fullføre noe.

 

Uansett, har du noe ferdig kode?

 

(Andre er selvfølgelig velkommen til å løse den andre nøtten som er postet.)

[anders02]

Jeg har dessverre ikke noe kode liggende, jeg tror det er rundt 5 år siden jeg laget den. Det er ikke noe i veien for at jeg kan lage koden på nytt, hvis du vil det.

 

Hvilket språk bruker du?

[Frysning]

Går i C++.

La oss fokusere på "pokeGrid" funksjonen, den som gjør endringer per loop.

Samt "checkGrid" siden den må nesten kjøre etter hver gang jeg pokergriddet, må den være kraftig optimert.