Archief - Project Euler

Jerre Muesli · 3 mrt 2009

Ik stootte plots op deze website: Project Euler . Het is vooral bedoeld om je programming skills te verbeteren door al doende na te denken over problemen/opgaven.
Je krijgt een opgave en je moet gewoon de uitkomst ingeven. Dus in eenders welke taal kan je je berekening doen voor jezelf.
Vanaf 25 solutions ben je een 'Level 1' en door meer solutions te vinden kan je t.e.m. level 5 gaan.
Is er iemand mee bekend?
Ik heb me ingeschreven en de eerste 5 gedaan en het is wel een leuk initialief. Wel lijkt het allemaal wat op schoolwerkjes en het is helaas allemaal wiskunde gerelateerd. (Ik haat wiskunde)
Kennen jullie zo nog andere websites?

Een voorbeeld van zo'n op te lossen probleem is dan bvb:

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A first exceeds ten is 17.

Find the least value of n for which A first exceeds one-million.

Tyfius · 3 mrt 2009

Project Euler bestaat al een tijdje. Ik heb die ooit eens allemaal doorlopen en ik denk zelfs dat dat ooit hier op het forum al eens heeft gestaan. Leuk voor een avondje prutsen maar meer ook niet

JelleSampleThis · 3 mrt 2009

Ik ben er wel even mee zoet, ligt het aan mijn skills of ligt het aan de site, maar ik raak er toch niet snel door.

Parnakra · 3 mrt 2009

Project Euler heeft dan ook minstens evenveel met (niet al te gemakkelijke) wiskunde te maken als met programmeren.

forloRn_ · 3 mrt 2009

Zelfde genre als de puzzels op Facebook, blijkbaar.

Mijn wiskunde-skillzorz (ehum) zijn fameus gedegradeerd sinds ik 2,5 jaar geleden afgestudeerd ben en ik vind dat ferm spijtig. Tijd om die boeken nog eens boven te halen.

Messias. · 4 mrt 2009

Heb een heel deel van die oefeningen ooit gemaakt in Haskell (en ook een aantal in Scala, en Ruby). Heel plezant tijdverdrijf en een geweldige manier om nieuwe programmeerparadigma's te leren kennen. Maar vanaf een bepaald niveau gaat het toch zwaar mijn petje te boven en merk ik dat mijn wiskunde/logisch redeneervermogen zwaar achter blijft. Zelfs met de nodige research...

tha_rippa1be · 31 mei 2009

Ik zit met een probleempje bij het interpreteren van de opgave van Problem 18
De opgave is als volgt:
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
Voor elke rij de getallen optellen met het hoogste aanpalende getal van de rij eronder.

Code:

[CENTER][color=red]3[/color]
[color=red]7[/color] 5
2 [color=red]4[/color] 6
8 5 [color=red]9[/color] 3[/CENTER]

Wat in deze driehoek dus is:
3+7+4+9 = 23
Er word 4 gebruikt op de 3de rij ipv 6 omdat 6 niet aanpalend is aan 7.

De code die ik heb geschreven lost de voorbeelddriehoek correct op maar geeft bij de opgavedriehoek niet de correcte oplossing.
Om te controleren of mijn code wel doet hetgeen ik wil ben ik zelf de driehoek even afgegaan.

Code:

[CENTER][color=red]75[/color]
[color=red]95[/color] 64
17 [color=red]47[/color] 82
18 35 [color=red]87[/color] 10
20 04 [color=red]82[/color] 47 65
19 01 23 [color=red]75[/color] 03 34
88 02 77 [color=red]73[/color] 07 63 67
99 65 04 [color=red]28[/color] 06 16 70 92
41 41 26 56 [color=red]83[/color] 40 80 70 33
41 48 72 33 [color=red]47[/color] 32 37 16 94 29
53 71 44 65 25 [color=red]43[/color] 91 52 97 51 14
70 11 33 28 77 [color=red]73[/color] 17 78 39 68 17 57
91 71 52 38 17 14 [color=red]91[/color] 43 58 50 27 29 48
63 66 04 68 89 53 [color=red]67[/color] 30 73 16 69 87 40 31
04 62 98 27 23 09 70 [color=red]98[/color] 73 93 38 53 60 04 23[/CENTER]

Waarna ik vond:
75+95+47+87+82+75+73+28+83+47+43+73+91+67+98 = 1064

(dezelfde som als die ik krijg met mijn code, maar die dus niet de juiste oplossing is)
Dat betekent dat ik de opgave verkeerd aan het interpreteren ben.
Kan er iemand even zeggen wat ik hier mis doe?

Ik vraag geen codevoorbeeld, enkel dat iemand mij kan uitleggen wat er fout is aan mijn redenering.

edit
Hmm, nevermind, dacht net aan iets.
Als er een 1 ergens vanboven staat zou ge de hele rij die achter die 1 hangt overslagen.

Volgens mijn redenering:

Code:

[center]
[color=red]5[/color]
1 [color=red]2[/color]
99 6 [color=red]7[/color]
99 10 [color=red]11[/color]
[/center]

correcte oplossing:

Code:

[center]
[color=red]5[/color]
[color=red]1[/color] 2
[color=red]99[/color] 6 7
[color=red]99[/color] 10 11
[/center]

204 > 25

killgore · 31 mei 2009

Ik heb het grootste deel al eens doorlopen. Eenmaal je de combinatie van wat wiskundig doordenken en het juiste algoritme mappen doorhebt kom je vrij snel aan de oplossing voor de meeste problemen

.

Als je deze beu bent kan je ook eens de vragen van ACM-ICPC wedstrijden zoals BAPC en NWERC oplossen. Daar zitten ook meestal enkele zeer leuke dingen tussen. Doorgaans van hoog, maar doenbaarder niveau (omdat die wedstrijden ook met een tijdslimiet zitten, itt project euler).

Krueger · 31 mei 2009

Ik heb er mij de laatste maanden eens opgesmeten, en ik vind wel dat er een redelijke niveau stijging is na de 100 moeilijkste vragen. Daarvoor kon je precies altijd met brute force makkelijk oplossen. Eenmaal daar voorbij moet je er enorm opletten dat je je algoritmes zeer performant maakt, en moet je eigenlijk toch ook soms het nodige opzoekingswerk doen.
Momenteel nr. 18 van België en rising

killgore · 2 jun 2009

tha_rippa1be zei:
Ik zit met een probleempje bij het interpreteren van de opgave van Problem 18
De opgave is als volgt:
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
Voor elke rij de getallen optellen met het hoogste aanpalende getal van de rij eronder.

Code:

[CENTER][color=red]3[/color] [color=red]7[/color] 5 2 [color=red]4[/color] 6 8 5 [color=red]9[/color] 3[/CENTER]

Wat in deze driehoek dus is:
3+7+4+9 = 23
Er word 4 gebruikt op de 3de rij ipv 6 omdat 6 niet aanpalend is aan 7.

De code die ik heb geschreven lost de voorbeelddriehoek correct op maar geeft bij de opgavedriehoek niet de correcte oplossing.
Om te controleren of mijn code wel doet hetgeen ik wil ben ik zelf de driehoek even afgegaan.

Code:

[CENTER][color=red]75[/color] [color=red]95[/color] 64 17 [color=red]47[/color] 82 18 35 [color=red]87[/color] 10 20 04 [color=red]82[/color] 47 65 19 01 23 [color=red]75[/color] 03 34 88 02 77 [color=red]73[/color] 07 63 67 99 65 04 [color=red]28[/color] 06 16 70 92 41 41 26 56 [color=red]83[/color] 40 80 70 33 41 48 72 33 [color=red]47[/color] 32 37 16 94 29 53 71 44 65 25 [color=red]43[/color] 91 52 97 51 14 70 11 33 28 77 [color=red]73[/color] 17 78 39 68 17 57 91 71 52 38 17 14 [color=red]91[/color] 43 58 50 27 29 48 63 66 04 68 89 53 [color=red]67[/color] 30 73 16 69 87 40 31 04 62 98 27 23 09 70 [color=red]98[/color] 73 93 38 53 60 04 23[/CENTER]

Waarna ik vond:
75+95+47+87+82+75+73+28+83+47+43+73+91+67+98 = 1064

(dezelfde som als die ik krijg met mijn code, maar die dus niet de juiste oplossing is)
Dat betekent dat ik de opgave verkeerd aan het interpreteren ben.
Kan er iemand even zeggen wat ik hier mis doe?

Ik vraag geen codevoorbeeld, enkel dat iemand mij kan uitleggen wat er fout is aan mijn redenering.

edit
Hmm, nevermind, dacht net aan iets.
Als er een 1 ergens vanboven staat zou ge de hele rij die achter die 1 hangt overslagen.

Volgens mijn redenering:

Code:

[center] [color=red]5[/color] 1 [color=red]2[/color] 99 6 [color=red]7[/color] 99 10 [color=red]11[/color] [/center]

correcte oplossing:

Code:

[center] [color=red]5[/color] [color=red]1[/color] 2 [color=red]99[/color] 6 7 [color=red]99[/color] 10 11 [/center]

204 > 25

die kan je eigenlijk extreem simpel oplossen met een lichte variant op dijkstra. Je maakt een nieuwe tree, begint met label vanboven, en elke rij zet je elk element op zijn waarde in de originele boom + het maximum van de elementen erboven.
Het maximum dat je dan vindt is dan de oplossing.

@Krueger: kben ook is herbegonnen in python, zit al aan bijna 40 vragen

.

Fraggie · 4 jun 2009

Ik heb er al een paar van bekeken, wel leuk bij momenten. De eerste keer dat ik een overflow van een int heb mee gemaakt :').. en ik maar zoeken..

killgore · 4 jun 2009

Fraggie zei:
Ik heb er al een paar van bekeken, wel leuk bij momenten. De eerste keer dat ik een overflow van een int heb mee gemaakt :').. en ik maar zoeken..

leve python

(tis dan ook wel een van de enige voordelen, op veel andere vlakken is een interpreted taal gewoon te traag

).

Krueger · 4 jun 2009

Fraggie zei:
Ik heb er al een paar van bekeken, wel leuk bij momenten. De eerste keer dat ik een overflow van een int heb mee gemaakt :').. en ik maar zoeken..

Het is niet voor niets dat ik voor project Euler de biginteger class heb gedownload voor C#

Messias. · 4 jun 2009

In Scala kan je die (ik veronderstel dat het gaat over die waar een faculteit aan te pas komt) wel leuk maken met implicit conversions en operator overloading.

PHP:

implicit def wrapInt(x: Int) = new IntWrapper(x)

class IntWrapper(x: Int) {
  def !() = Math.fac(x)  
}

object Math {
  def fac(n: Int): BigInt = {
    if (n == 0) 1
    else {
      def accumulate(acc: BigInt, x: Int): BigInt =
        if (x > n) acc else accumulate(acc * x, x + 1)
      accumulate(1, 1)
    }
  } 
}

Voor het berekenen van de faculteit kan je dan het uitroepteken in z'n wiskundige notatie gebruiken:

PHP:

scala> 10!  
res1: BigInt = 3628800

scala> Math.fac(10)
res2: BigInt = 3628800

Helaas is het niet meer dan een leuke gimmick, want operator precedence is vaak ambigue, en dan moet je haakjes toevoegen waardoor het compleet zijn nut voorbijstreeft.

Krueger · 5 jun 2009

Messias, ik mis een beetje het punt van je post. Wat probeer je juist aan te tonen?

Messias. · 5 jun 2009

Krueger zei:
Messias, ik mis een beetje het punt van je post. Wat probeer je juist aan te tonen?

Dat je via operator overloading faculteiten in Scala kan formuleren in hun wiskundige notatie (als in n!). Ik vond dat een leuke showcase van het dynamische karakter van Scala, en 't was iets waar ik gisteren toevallig opkwam in de context van Project Euler. Soit, niks meer dan een gimmick die ik met de wereld wou delen dus.

Ice · 12 jun 2009

Of je gebruikt een degelijke taal en doet simpelweg: 10 factorial "ctrl p" eh voila its done. ZZZZZZzzzzz

Archief - Project Euler

Jerre Muesli

Legacy Member

Tyfius

Legacy Member

JelleSampleThis

Legacy Member

Parnakra

Legacy Member

forloRn_

Legacy Member

Messias.

Legacy Member

tha_rippa1be

Legacy Member

killgore

Legacy Member

Krueger

Legacy Member

killgore

Legacy Member

Fraggie

Legacy Member

killgore

Legacy Member

Krueger

Legacy Member

Messias.

Legacy Member

Krueger

Legacy Member

Messias.

Legacy Member

Ice

Legacy Member