2014-11-26 #projecteuler #racketlang
L'énoncé sur projecteuler.net
If you can't explain it simply, you don't understand it well enough.
—Albert Einstein
J'ai passé pas mal de temps sur ce problème 60, au point où je me dis que si j'arrive à l'expliquer (même mal) ça sera bien pour ma compréhension.
Voici l'énoncé :
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
Ce qui vient à la lecture :
- On dit que 2 premiers sont liés si leurs concatenations droite/gauche donnent aussi des premiers. Traduction:
(define (concat a b)
(string->number (string-append (number->string a)
(number->string b))))
(define (linked? p1 p2)
(and (prime? (concat p1 p2))
(prime? (concat p2 p1))))- Il faudra à un moment où à un autre tester chaque premier avec tous les autres pour voir lesquels sont liés : O(N^2)
- Il faudra fixer une limite de nombres premiers sur lequels travailler (j'ai pris <10k)
- On va pas pouvoir bruteforcer trop bêtement…
- Il "suffit" ensuite de trouver tous les quintuplets de nombres premiers qui sont tous liés entre eux (chacun lié aux 5 autres).
C'est ce dernier point qui est intéressant, en tout cas algorithmiquement.
Voici ma première implémentation en Racket qui trouve le résultat : commit 0dcca1d
En gros,
- Générer la liste de tous les nombres premiers avec leurs premiers associés "concatenables"
- Filtrer cette liste comme il suit :
- Garder uniquement les nombres qui ont au moins 5 connexions (jusque là, c'est logique)
- Garder uniquement les nombres dont les connexions ont au moins 5 connexions entre elles
- Énumérer les quintuplets possibles à partir de la liste réduite (dans cette première version je m'arrête à la première occurence)
Traduction du 2ème point :
(define (graph-filter g)
(let loop ((cur-g (cdr g)) (cur (car g)) (res '()))
(if (empty? cur-g)
res
(let* ((cur-ct (point-connected-to cur))
(cur-v (point-value cur))
(at-least-5
(filter (lambda(p)
(>= (length
(filter (lambda(pp) (member pp cur-ct))
(point-connected-to (graph-get g p))))
5))
cur-ct)))
(if (>= (length at-least-5) 5)
(loop (cdr cur-g) (car cur-g) (cons (cons cur-v cur-ct) res))
(loop (cdr cur-g) (car cur-g) res))))))Cela me donne une liste de nombres dont certains sont potentiellement tous connectés. Ce que je cherche c'est 5 points qui sont tous interconnectés :
(define (euler60)
(define g (mk-graph))
(define candidats (reverse (graph-filter g)))
; for*/first instead of for*/list : assume it's the first found (lucky it is)
(for*/first ((p (in-list candidats))
(lp (in-range (length p)))
(p1 (in-range lp))
(p2 (in-range (add1 p1) lp))
(p3 (in-range (add1 p2) lp))
(p4 (in-range (add1 p3) lp))
(p5 (in-range (add1 p4) lp))
#:when (< p1 p2 p3 p4 p5)
(perm (in-value (list (list-ref p p1)
(list-ref p p2)
(list-ref p p3)
(list-ref p p4)
(list-ref p p5))))
#:when (all-connected? g perm))
perm))J'arrive au résultat mais ce n'est pas satisfaisant pour plusieurs raisons :
- solution pas élégante
- ~80 secondes à s'éxécuter sur i5-2520M @ 2.50GHz, raisonnable mais c'est supérieur à la 1-min rule du projecteuler
- ne retourne que le premier quintuplet et s'arrête. Devrait retourner la somme minimum d'une liste de quintuplés possibles. C'est un pur hasard si le premier est le bon.
Pour analyser où mon temps CPU est utilisé, j'invoque profile-thunk du module profile.
(require profile)
(profile-thunk euler60)Ce qui donne :
Profiling results
-----------------
Total cpu time observed: 80076ms (out of 80200ms)
Number of samples taken: 1592 (once every 50ms)
============================================================================
Caller
Idx Total Self Name+src Local%
ms(pct) ms(pct) Callee
============================================================================
[1] 80076(100.0%) 0(0.0%) ??? ...acket/collects/racket/private/misc.rkt:87:7
profile-thunk14 [2] 100.0%
----------------------------------------------------------------------------
??? [1] 100.0%
[2] 80076(100.0%) 0(0.0%) profile-thunk14 ...t/pkgs/profile-lib/main.rkt:9:0
run [3] 100.0%
----------------------------------------------------------------------------
profile-thunk14 [2] 100.0%
[3] 80076(100.0%) 0(0.0%) run ...share/racket/pkgs/profile-lib/main.rkt:31:2
euler60 [4] 100.0%
----------------------------------------------------------------------------
run [3] 100.0%
[4] 80076(100.0%) 0(0.0%) euler60 ...dim/Dropbox/Projects/euler/60.rkt:146:0
for-loop [5] 91.0%
loop [6] 6.9%
loop [7] 2.1%
----------------------------------------------------------------------------
euler60 [4] 12.6%
for-loop [5] 87.4%
[5] 72852(91.0%) 1464(1.8%) for-loop ...im/Dropbox/Projects/euler/60.rkt:150:2
for-loop [5] 87.4%
for-loop [8] 12.2%
----------------------------------------------------------------------------
euler60 [4] 100.0%
[6] 5515(6.9%) 0(0.0%) loop ...fridim/Dropbox/Projects/euler/60.rkt:104:2
pairs [9] 87.1%
loop [11] 12.0%
graph-complete [12] 0.9%
----------------------------------------------------------------------------
euler60 [4] 100.0%
[7] 1709(2.1%) 0(0.0%) loop ...fridim/Dropbox/Projects/euler/60.rkt:120:2
loop [18] 58.9%
filter [10] 41.1%
----------------------------------------------------------------------------
for-loop [5] 48.0%
for-loop [8] 52.0%
[8] 71388(89.2%) 11108(13.9%) for-loop ...im/Dropbox/Projects/euler/60.rkt:137:2
for-loop [8] 52.0%
graph-get [16] 42.2%
----------------------------------------------------------------------------
loop [6] 100.0%
[9] 4804(6.0%) 308(0.4%) pairs ...fridim/Dropbox/Projects/euler/60.rkt:42:0
for-loop [13] 93.6%
----------------------------------------------------------------------------
??? [14] 13.3%
loop [7] 86.7%
[10] 753(0.9%) 150(0.2%) filter ...t/collects/racket/private/list.rkt:256:2
??? [14] 86.7%
----------------------------------------------------------------------------
loop [6] 100.0%
[11] 662(0.8%) 0(0.0%) loop .../fridim/Dropbox/Projects/euler/60.rkt:78:2
graph-add [15] 100.0%
----------------------------------------------------------------------------
loop [6] 100.0%
[12] 50(0.1%) 0(0.0%) graph-complete ...opbox/Projects/euler/60.rkt:75:0
graph-add [15] 100.0%
----------------------------------------------------------------------------
pairs [9] 100.0%
[13] 4495(5.6%) 162(0.2%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:43:2
linked? [17] 86.3%
prime? [21] 10.1%
----------------------------------------------------------------------------
filter [10] 41.1%
loop [18] 58.9%
[14] 1709(2.1%) 0(0.0%) ??? ...fridim/Dropbox/Projects/euler/60.rkt:126:24
loop [18] 76.6%
graph-get [16] 14.6%
filter [10] 8.8%
----------------------------------------------------------------------------
graph-complete [12] 7.0%
loop [11] 93.0%
[15] 712(0.9%) 302(0.4%) graph-add ...im/Dropbox/Projects/euler/60.rkt:62:0
loop [19] 29.5%
graph-get [16] 14.1%
loop [20] 14.1%
----------------------------------------------------------------------------
graph-add [15] 0.2%
??? [14] 0.4%
for-loop [8] 99.4%
[16] 60630(75.7%) 60630(75.7%) graph-get ...im/Dropbox/Projects/euler/60.rkt:48:0
----------------------------------------------------------------------------
for-loop [13] 100.0%
[17] 3880(4.8%) 558(0.7%) linked? ...idim/Dropbox/Projects/euler/60.rkt:33:0
prime? [21] 85.6%
----------------------------------------------------------------------------
loop [7] 40.3%
??? [14] 59.7%
[18] 1559(1.9%) 1309(1.6%) loop ...ket/collects/racket/private/list.rkt:264:4
??? [14] 40.3%
----------------------------------------------------------------------------
graph-add [15] 100.0%
[19] 210(0.3%) 210(0.3%) loop ...hare/racket/collects/racket/list.rkt:443:2
----------------------------------------------------------------------------
graph-add [15] 15.0%
loop [20] 85.0%
[20] 100(0.1%) 100(0.1%) loop ...are/racket/collects/racket/list.rkt:331:34
loop [20] 85.0%
----------------------------------------------------------------------------
for-loop [13] 12.0%
linked? [17] 88.0%
[21] 3776(4.7%) 153(0.2%) prime? ...te/number-theory/number-theory.rkt:205:4
loop [22] 68.1%
prime-strong-pseudo/explanation [23] 27.9%
----------------------------------------------------------------------------
prime? [21] 100.0%
[22] 2571(3.2%) 2009(2.5%) loop (unknown source)
loop [24] 19.8%
prime-strong-pseudo-single? [25] 2.0%
----------------------------------------------------------------------------
prime? [21] 100.0%
[23] 1052(1.3%) 650(0.8%) prime-strong-pseudo/explanation (unknown source)
loop [24] 38.2%
----------------------------------------------------------------------------
prime-strong-pseudo/explanation [23] 44.0%
loop [22] 56.0%
[24] 912(1.1%) 0(0.0%) loop ...vate/number-theory/number-theory.rkt:151:8
loop [26] 100.0%
----------------------------------------------------------------------------
loop [22] 100.0%
[25] 52(0.1%) 0(0.0%) prime-strong-pseudo-single? (unknown source)
random-integer [27] 100.0%
----------------------------------------------------------------------------
loop [24] 13.8%
loop [26] 86.2%
[26] 912(1.1%) 912(1.1%) loop ...r-theory/modular-arithmetic-base.rkt:53:11
loop [26] 86.2%
----------------------------------------------------------------------------
prime-strong-pseudo-single? [25] 100.0%
[27] 52(0.1%) 52(0.1%) random-integer (unknown source)
----------------------------------------------------------------------------
75.7% du temps passé dans graph-get ! J'étais parti sur une liste mais il va falloir utiliser une structure plus adaptée. Par exemple un hash qui a un accès en O(log N) contrairement à ma liste qui a un accès en O(N):
Immutable hash tables actually provide O(log N) access and update. Since N is limited by the address space so that log N is limited to less than 30 or 62 (depending on the platform), log N can be treated reasonably as a constant.
Juste en remplaçant la liste par un hash (commit a878195b8d), on passe à 13 secondes :
Profiling results
-----------------
Total cpu time observed: 13262ms (out of 13307ms)
Number of samples taken: 263 (once every 50ms)
(Hiding functions with self<1.0% and local<2.0%: 1 of 26 hidden)
===========================================================================
Caller
Idx Total Self Name+src Local%
ms(pct) ms(pct) Callee
===========================================================================
[1] 13262(100.0%) 0(0.0%) ??? ...acket/collects/racket/private/misc.rkt:87:7
profile-thunk14 [2] 100.0%
---------------------------------------------------------------------------
??? [1] 100.0%
[2] 13262(100.0%) 0(0.0%) profile-thunk14 ...t/pkgs/profile-lib/main.rkt:9:0
run [3] 100.0%
---------------------------------------------------------------------------
profile-thunk14 [2] 100.0%
[3] 13262(100.0%) 0(0.0%) run ...share/racket/pkgs/profile-lib/main.rkt:31:2
euler60 [4] 100.0%
---------------------------------------------------------------------------
run [3] 100.0%
[4] 13262(100.0%) 0(0.0%) euler60 ...dim/Dropbox/Projects/euler/60.rkt:115:0
for-loop [5] 58.5%
loop [6] 34.3%
graph-filter [7] 7.2%
---------------------------------------------------------------------------
euler60 [4] 12.9%
for-loop [5] 87.1%
[5] 7760(58.5%) 1411(10.6%) for-loop ...im/Dropbox/Projects/euler/60.rkt:119:2
for-loop [5] 87.1%
for-loop [8] 10.2%
---------------------------------------------------------------------------
euler60 [4] 100.0%
[6] 4545(34.3%) 52(0.4%) loop .../fridim/Dropbox/Projects/euler/60.rkt:77:2
pairs [9] 96.6%
loop [11] 1.1%
graph-complete [12] 1.1%
---------------------------------------------------------------------------
euler60 [4] 100.0%
[7] 957(7.2%) 0(0.0%) graph-filter ...Dropbox/Projects/euler/60.rkt:91:0
for-loop [10] 100.0%
---------------------------------------------------------------------------
for-loop [5] 40.2%
for-loop [8] 59.8%
[8] 6350(47.9%) 6350(47.9%) for-loop ...im/Dropbox/Projects/euler/60.rkt:106:2
for-loop [8] 59.8%
---------------------------------------------------------------------------
loop [6] 100.0%
[9] 4392(33.1%) 454(3.4%) pairs ...fridim/Dropbox/Projects/euler/60.rkt:42:0
for-loop [13] 89.7%
---------------------------------------------------------------------------
graph-filter [7] 33.3%
for-loop [10] 66.7%
[10] 957(7.2%) 0(0.0%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:93:2
for-loop [10] 66.7%
loop [14] 26.3%
filter [15] 7.0%
---------------------------------------------------------------------------
loop [6] 100.0%
[11] 52(0.4%) 0(0.0%) loop .../fridim/Dropbox/Projects/euler/60.rkt:68:2
graph-add [16] 100.0%
---------------------------------------------------------------------------
loop [6] 100.0%
[12] 50(0.4%) 0(0.0%) graph-complete ...opbox/Projects/euler/60.rkt:65:0
graph-add [16] 100.0%
---------------------------------------------------------------------------
pairs [9] 100.0%
[13] 3938(29.7%) 50(0.4%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:43:2
linked? [17] 81.8%
prime? [19] 15.4%
---------------------------------------------------------------------------
??? [18] 49.8%
for-loop [10] 50.2%
[14] 906(6.8%) 752(5.7%) loop ...ket/collects/racket/private/list.rkt:264:4
??? [18] 50.2%
---------------------------------------------------------------------------
??? [18] 43.2%
for-loop [10] 56.8%
[15] 355(2.7%) 154(1.2%) filter ...t/collects/racket/private/list.rkt:256:2
??? [18] 56.8%
---------------------------------------------------------------------------
graph-complete [12] 49.3%
loop [11] 50.7%
[16] 102(0.8%) 102(0.8%) graph-add ...im/Dropbox/Projects/euler/60.rkt:55:0
---------------------------------------------------------------------------
for-loop [13] 100.0%
[17] 3224(24.3%) 308(2.3%) linked? ...idim/Dropbox/Projects/euler/60.rkt:33:0
prime? [19] 88.9%
---------------------------------------------------------------------------
filter [15] 21.1%
loop [14] 78.9%
[18] 957(7.2%) 52(0.4%) ??? .../fridim/Dropbox/Projects/euler/60.rkt:96:44
loop [14] 78.6%
filter [15] 16.0%
---------------------------------------------------------------------------
for-loop [13] 17.4%
linked? [17] 82.6%
[19] 3470(26.2%) 505(3.8%) prime? ...te/number-theory/number-theory.rkt:205:4
loop [20] 63.7%
prime-strong-pseudo/explanation [21] 21.8%
---------------------------------------------------------------------------
prime? [19] 100.0%
[20] 2209(16.7%) 1156(8.7%) loop (unknown source)
loop [22] 43.2%
prime-strong-pseudo-single? [23] 4.5%
---------------------------------------------------------------------------
prime? [19] 100.0%
[21] 756(5.7%) 405(3.1%) prime-strong-pseudo/explanation (unknown source)
loop [22] 46.5%
---------------------------------------------------------------------------
prime-strong-pseudo/explanation [21] 26.9%
loop [20] 73.1%
[22] 1305(9.8%) 100(0.8%) loop ...vate/number-theory/number-theory.rkt:151:8
loop [24] 92.3%
---------------------------------------------------------------------------
loop [20] 100.0%
[23] 100(0.8%) 50(0.4%) prime-strong-pseudo-single? (unknown source)
random-integer [25] 50.0%
---------------------------------------------------------------------------
loop [22] 22.4%
loop [24] 77.6%
[24] 1205(9.1%) 1205(9.1%) loop ...r-theory/modular-arithmetic-base.rkt:53:11
loop [24] 77.6%
---------------------------------------------------------------------------
prime-strong-pseudo-single? [23] 100.0%
[25] 50(0.4%) 50(0.4%) random-integer (unknown source)
---------------------------------------------------------------------------
Maintenant c'est 47.9% du temps passé dans la procédure all-connected?. Le souci est que dans ma boucle :
(for*/first ((p (in-list candidats))
(lp (in-range (length p)))
(p1 (in-range lp))
(p2 (in-range (add1 p1) lp))
(p3 (in-range (add1 p2) lp))
(p4 (in-range (add1 p3) lp))
(p5 (in-range (add1 p4) lp))Je teste tous les quintuplets à chaque fois. En fait il faudrait prendre p1, voir s'il est connecté à p2, sinon prendre un autre p2, et ainsi de suite. En fait il faudrait même plutôt faire l'intersection des connexions de p1 (on les a déjà calculées à ce niveau là) avec p. Prendre p2 dans cet ensemble puis faire l'intersection avec les connexions de p2, et ainsi de suite, jusqu'à trouver une intersection d'intersection d'intersection ... (x5) qui soit un quintuplet.
Le type set
Il y a un type dans Racket qui semble être parfait pour ce que je veut faire : le set (ensemble au sens mathématique). Il y a même une procédure set-intersect. Pour chaque nombre premier p, cette procédure va nous permettre de trouver directement les intersections entre:
- l'ensemble des connexions de p
- l'ensemble des connexions de 5 des connexions de p
Voir commit 415363e5aa
En remplaçant list par set, et en utilisant set-intersect on passe à 5 secondes au lieu des 13 et on a enfin la liste complète des possibilités (avec l'ensemble de départ de 1100 nombres premiers). La version précédente pouvait mouliner des heures sans jamais donner de deuxième quintuplet possible.
Profiling results
-----------------
Total cpu time observed: 5358ms (out of 5380ms)
Number of samples taken: 106 (once every 51ms)
==========================================================================
Caller
Idx Total Self Name+src Local%
ms(pct) ms(pct) Callee
==========================================================================
[1] 5358(100.0%) 0(0.0%) ??? ...acket/collects/racket/private/misc.rkt:87:7
profile-thunk14 [2] 100.0%
--------------------------------------------------------------------------
??? [1] 100.0%
[2] 5358(100.0%) 0(0.0%) profile-thunk14 ...t/pkgs/profile-lib/main.rkt:9:0
run [3] 100.0%
--------------------------------------------------------------------------
profile-thunk14 [2] 100.0%
[3] 5358(100.0%) 0(0.0%) run ...share/racket/pkgs/profile-lib/main.rkt:31:2
euler60 [4] 100.0%
--------------------------------------------------------------------------
run [3] 100.0%
[4] 5358(100.0%) 0(0.0%) euler60 ...idim/Dropbox/Projects/euler/60.rkt:84:0
loop [5] 83.1%
for-loop [6] 16.9%
--------------------------------------------------------------------------
euler60 [4] 100.0%
[5] 4452(83.1%) 0(0.0%) loop .../fridim/Dropbox/Projects/euler/60.rkt:75:2
pairs [7] 98.9%
for-loop [9] 1.1%
--------------------------------------------------------------------------
euler60 [4] 18.5%
for-loop [6] 81.5%
[6] 906(16.9%) 250(4.7%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:87:4
for-loop [6] 81.5%
custom-set-intersect [8] 13.7%
--------------------------------------------------------------------------
loop [5] 100.0%
[7] 4402(82.2%) 200(3.7%) pairs ...fridim/Dropbox/Projects/euler/60.rkt:43:0
for-loop [10] 95.5%
--------------------------------------------------------------------------
for-loop [6] 100.0%
[8] 656(12.2%) 102(1.9%) custom-set-intersect ...rivate/set-types.rkt:186:0
for-loop [11] 76.9%
for-loop [12] 7.6%
--------------------------------------------------------------------------
loop [5] 100.0%
[9] 50(0.9%) 0(0.0%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:69:2
graph-add [13] 100.0%
--------------------------------------------------------------------------
pairs [7] 100.0%
[10] 4202(78.4%) 52(1.0%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:44:2
linked? [14] 92.8%
prime? [16] 5.9%
--------------------------------------------------------------------------
custom-set-intersect [8] 100.0%
[11] 504(9.4%) 504(9.4%) for-loop ...cts/racket/private/set-types.rkt:198:3
--------------------------------------------------------------------------
custom-set-intersect [8] 100.0%
[12] 50(0.9%) 50(0.9%) for-loop ...cts/racket/private/set-types.rkt:142:2
--------------------------------------------------------------------------
for-loop [9] 100.0%
[13] 50(0.9%) 0(0.0%) graph-add ...im/Dropbox/Projects/euler/60.rkt:56:0
custom-set-union [15] 100.0%
--------------------------------------------------------------------------
for-loop [10] 100.0%
[14] 3900(72.8%) 520(9.7%) linked? ...idim/Dropbox/Projects/euler/60.rkt:34:0
prime? [16] 86.7%
--------------------------------------------------------------------------
graph-add [13] 100.0%
[15] 50(0.9%) 0(0.0%) custom-set-union ...et/private/set-types.rkt:158:0
for-loop [17] 100.0%
--------------------------------------------------------------------------
for-loop [10] 6.9%
linked? [14] 93.1%
[16] 3630(67.7%) 253(4.7%) prime? ...te/number-theory/number-theory.rkt:205:4
loop [18] 72.3%
prime-strong-pseudo/explanation [19] 20.7%
--------------------------------------------------------------------------
custom-set-union [15] 100.0%
[17] 50(0.9%) 0(0.0%) for-loop ...cts/racket/private/set-types.rkt:164:3
for-loop [20] 100.0%
--------------------------------------------------------------------------
prime? [16] 100.0%
[18] 2626(49.0%) 1774(33.1%) loop (unknown source)
loop [21] 30.5%
prime-strong-pseudo-single? [22] 1.9%
--------------------------------------------------------------------------
prime? [16] 100.0%
[19] 752(14.0%) 602(11.2%) prime-strong-pseudo/explanation (unknown source)
loop [21] 13.3%
prime-strong-pseudo-single? [22] 6.7%
--------------------------------------------------------------------------
for-loop [17] 100.0%
[20] 50(0.9%) 50(0.9%) for-loop ...cts/racket/private/set-types.rkt:168:5
--------------------------------------------------------------------------
prime-strong-pseudo/explanation [19] 11.1%
loop [18] 88.9%
[21] 902(16.8%) 0(0.0%) loop ...vate/number-theory/number-theory.rkt:151:8
loop [23] 100.0%
--------------------------------------------------------------------------
prime-strong-pseudo/explanation [19] 50.0%
loop [18] 50.0%
[22] 100(1.9%) 100(1.9%) prime-strong-pseudo-single? (unknown source)
--------------------------------------------------------------------------
loop [21] 20.2%
loop [23] 79.8%
[23] 902(16.8%) 902(16.8%) loop ...r-theory/modular-arithmetic-base.rkt:53:11
loop [23] 79.8%
--------------------------------------------------------------------------
Bon là, c'est gagné. Le temps de calcul se trouve maintenant principalement à la génération des candidats possibles:
pairs [7] 100.0%
[10] 4202(78.4%) 52(1.0%) for-loop ...dim/Dropbox/Projects/euler/60.rkt:44:2
linked? [14] 92.8%
prime? [16] 5.9%
On doit certainement pouvoir creuser encore pour gagner des cycles, mais je vais m'arrêter là :)
Pour résumer :
- temps de calcul : 80 secs > 13 secs > 5 secs
- le module
profilepour savoir ce qu'il se passe. Il est même possible d'afficher le rendu texte pendant l'éxécution toutes les N secondes pour comprendre où ça patine:
(require profile profile/render-text)
(profile-thunk euler60 #:periodic-renderer (list 60 render))- Les procédures que j'aurais pu implémenter :
next-primesavec l'algo de Sieveprime?avec quelque chose comme
(define (prime? n) (and (not (= (modulo n 2) 0)) (for/and ([i (in-range 3 (add1 (sqrt n)) 2)]) (not (= 0 (modulo n i))))))
set-intersectmais le code se comprend plutôt bien :
(define (list-intersect s . sets) (for ([s2 (in-list sets)] [i (in-naturals 1)]) (unless (list? s2) (apply raise-argument-error 'set-intersect "list?" i s sets))) (for/fold ([s1 '()]) ([x (in-list s)] #:when (for/and ([s2 (in-list sets)]) (member x s2))) (list-add s1 x)))
Wow, Tu veux un cookie (fait maison) ?