[F#] Algoritme geeft verkeerde waarde

[Hyperz]

Ene goede morgen .

Ik wil de F# syntax beter onder de knie krijgen. Om wat te oefenen ben ik bezig met een zéér simpel AS3 algoritme over te typen naar F#. He gaat om dit AS3 script (de dfs en solve function). Dit is wat ik er van gemaakt heb:

F#:

let S n =
    let limit = 1 <<< n
    let buffer = Array.create<int> limit 0
    let current = ref 0u
    let acc = ref 0L
    let rec loop d u =
        if d = limit then int64(!current >>> (n - 1))
        else
            for c in [0u; 1u] do
                let idx = (u <<< 1) ||| c
                if buffer.[int idx] = 0 then
                    buffer.[int idx] <- 1
                    current := (!current <<< 1) ||| c
                    acc := !acc + int64(loop (d + 1) (idx &&& (uint32(limit - 1) >>> 1)))
                    current := !current >>> 1
                    buffer.[int idx] <- 0
            !acc

    buffer.[0] <- 1; loop 1 0u

printfn "Result: %i" (S 5)

De output is:

code:

Result: 7855368599302507774

Dit is een te hoge waarde, het zou 209110240768 moeten zijn. Ik vermoed dat mijn probleem te maken heeft met een van de bitwise operaties maar na welgeteld 7 uren prutsen aan dit stukje code ben ik er nog niet achter. Wiskunde is één van mijne zwakke punten dus dat helpt ook niet echt . Iemand die het probleem ziet?

[ Voor 0% gewijzigd door Hyperz op 06-04-2010 07:31 . Reden: typo ]

[cfern]

De bitwise shifts hebben niets met je probleem te maken, kijk maar:

code:

let rec loop d u =
    if d = limit then int64(!current >>> (n - 1))
    else
        acc := 0L (* deze was je vergeten *)
        for c in [0u; 1u] do
            ... rest van code ...

Heb je al geprobeerd om probleem 265 zelf op te lossen? Hij is namelijk best te brute forcen met wat gebruik van bit shifts voor snelheid. Als je zelf met project euler aan de slag gaat kan ik je de blogserie Yet Another Project Euler Series (hier) aanraden. Hier wordt op een mooi heldere manier door een paar project Euler problemen heengelopen met F#.

[Hyperz]

Nou, nu voel ik me wel héél dom . Bedankt voor de oplossing!

Ik had gelezen dat hij te brute forcen was idd maar ik was niet echt aan het zoeken naar een oplossing voor 265. Ik had gewoon iets nodig om me te kunnen bezig houden. Heb het wel geprobeerd maar ik denk dat ik de opdracht niet helemaal snap. Ben dan ook geen pro .

Maar ik neem aan dat de bruteforce versie makkelijker is dan wat ik nu heb staan? Ben wel benieuwd eigenlijk.

[cfern]

Brute force is alle mogelijke 32-bits ringen maken en van elke ring bepalen of deze geldig is. Nu is 2^32 ringen nagaan niet echt handig om binnen de 1-minuut regel te blijven. Gelukkig geldt voor elke ring dat een aantal bits van te voren al vast staat, deze hoef je dus niet te variëren. Dit betekent dat het aantal overgebleven mogelijkheden nu wel brute force is door te rekenen.

Zo heb ik het opgelost en ik deed daar geloof ik zo'n 40 seconden over gebruik makend van bitmanipulaties.
Een recursieve oplossing is natuurlijk veel slimmer (zoals het stuk code wat je postte), maar daar heb ik zelf niet over na gedacht, want lui.

[Soultaker]

Wat je nu doet is gewoon een klein beetje geoptimaliseerde variant van bruteforcen hoor.

Overigens vind ik 't wel lelijk om in een functionele taal de helft van je state als parameters door te geven en de andere helft in globale variabelen die destructief geüpdatet worden. Daar krijg je ook van dat soort fouten met die vergeten accumulator van. Dat moet met wat creativiteit mooier kunnen.

Ik zou verwachten dat het met cfern's fix nog steeds niet werkt (of is dat getest?) omdat je de accumulator dan nog steeds globaal gebruikt, terwijl je 'm juist lokaal moet hebben (let acc = ref 0 in..). Maar dan lijkt een lijstcomprehensie met een sum-operatie me een stuk mooier.

[cfern]

Wat ik beschreef is nog steeds brute force, maar (een klein beetje) slimmere brute force is altijd nog beter dan brute force waar je een uur op zit te wachten (als het al niet meer is).

Ik heb mijn fix getest en werkend bevonden. Het enige wat ik deed is een stukje vergeten vertaling toe te voegen. Ik moet wel toegeven dat de F# code zoals het er nu staat mijn ogen doet bloeden, maar zo ziet het er nou eenmaal uit als je letterlijk een imperatief algoritme vertaalt. Dat moet inderdaad een stuk netter kunnen. Ik vind zelf het gebruik van globals eigenlijk best wel angstaanjagend, zeker in een functionele programmeertaal.

Dat vind ik zelf wel geestig aan F#: zodra je met mutable waardes gaat werken lijkt het alsof je iets vies aan het doen bent. Ofwel je gebruikt ref cells, of je gebruikt mutable, waarna je waardes moet aanpassen als 'x <- x+1'. Je code wordt er nooit fraaier op.

[ Voor 5% gewijzigd door cfern op 06-04-2010 11:01 ]

[Hyperz]

Soultaker schreef op dinsdag 06 april 2010 @ 10:34:
Ik zou verwachten dat het met cfern's fix nog steeds niet werkt (of is dat getest?) omdat je de accumulator dan nog steeds globaal gebruikt, terwijl je 'm juist lokaal moet hebben (let acc = ref 0 in..). Maar dan lijkt een lijstcomprehensie met een sum-operatie me een stuk mooier.

Ja het werkt hoor . Overigens is de accumulator niet globaal, strikt genomen dan. Het "in" keyword heb ik nog niet gebruikt. F# (en functioneel programmeren) is nieuw voor mij. Normaal doe ik alles in C#.

Pure imperatieve code ziet er inderdaad niet uit in F#. Ik had eerst een "mooie" functie geschreven met List.* en pipeline operators maar de waarden die daar uit kwamen waren gereed voor een X-Files aflevering . Na een paar uur sukkelen heb ik uit frustratie dan toch maar besloten om gewoon die AS3 code te porten.

'k moet wel zeggen dat F# me redelijk bevalt. Het is simpel (= niet veel bloat/noise), er moet minder code geschreven worden en parallel/async programmeren lijkt wel kinderspel .

[cfern]

Ik vind ook dat F# code best fraai en compact kan worden, als je een beetje gewend bent aan functioneel programmeren: folds, aggregates, pipes, recursie, etc. Juist door te klooien met F# ben ik ook LINQ meer gaan snappen en dat indirecte voordeel pak ik mooi mee voor mijn werk.

Met het async {..} pattern heb ik zelf nog niet zoveel gestoeid (ben voornamelijk bezig geweest met rekendingetjes), maar het lijkt er sterk op dat het een hoop vervelende boilerplate code van je overneemt. Zie bijvoorbeeld de stukjes code in deze twee blog posts. Het zijn behoorlijk pro-F# posts (de schrijver zit in het F# team), maar dat neemt niet weg dat de code er best fraai en handig uit ziet.

P.S. hier is een iets schonere versie van het algoritme, de ref cell 'current' geef ik nu als recursieparameter mee en in plaats van een lopende som, spuug ik de te sommeren waarden uit in een sequence die ik pas op het eind sommeer.

code:

let S2 n =
    let limit = 1 <<< n
    let buffer = Array.create<bool> limit false

    let rec loop curr d u =
        seq {
            if d=limit then yield int64(curr >>> (n-1))
            else
                for c in 0u..1u do
                    let idx = (u <<< 1) ||| c
                    if not buffer.[int idx]  then
                        buffer.[int idx] <- true
                        yield! loop ((curr <<< 1) ||| c) (d+1) (idx &&& (uint32(limit-1) >>> 1))
                        buffer.[int idx] <- false
        }

    buffer.[0] <- true
    loop 0u 1 0u |> Seq.sum

Hmm. Ziet er eigenlijk nog steeds niet zo fraai uit...