Anonymous user
Fraction reduction: Difference between revisions
+Racket
SqrtNegInf (talk | contribs) (Added Perl example) |
(+Racket) |
||
Line 950:
"10 minutes and 13s"
</pre>
=={{header|Racket}}==
Racket's generator is horribly slow, so I roll my own more efficient generator. Pretty much using continuation-passing style, but then using macro to make it appear that we are writing in the direct style.
<lang racket>#lang racket
(require racket/generator
syntax/parse/define)
(define-syntax-parser for**
[(_ [x:id {~datum <-} (e ...)] rst ...) #'(e ... (λ (x) (for** rst ...)))]
[(_ e ...) #'(begin e ...)])
(define (permutations xs n yield #:lower [lower #f])
(let loop ([xs xs] [n n] [acc '()] [lower lower])
(cond
[(= n 0) (yield (reverse acc))]
[else (for ([x (in-list xs)] #:when (or (not lower) (>= x (first lower))))
(loop (remove x xs)
(sub1 n)
(cons x acc)
(and lower (= x (first lower)) (rest lower))))])))
(define (list->number xs) (foldl (λ (e acc) (+ (* 10 acc) e)) 0 xs))
(define (calc n)
(define rng (range 1 10))
(in-generator
(for** [numer <- (permutations rng n)]
[denom <- (permutations rng n #:lower numer)]
(for* (#:when (not (equal? numer denom))
[crossed (in-list numer)]
#:when (member crossed denom)
[numer* (in-value (list->number (remove crossed numer)))]
[denom* (in-value (list->number (remove crossed denom)))]
[numer** (in-value (list->number numer))]
[denom** (in-value (list->number denom))]
#:when (= (* numer** denom*) (* numer* denom**)))
(yield (list numer** denom** numer* denom* crossed))))))
(define (enumerate n)
(for ([x (calc n)] [i (in-range 12)])
(apply printf "~a/~a = ~a/~a (~a crossed out)\n" x))
(newline))
(define (stats n)
(define digits (make-hash))
(for ([x (calc n)]) (hash-update! digits (last x) add1 0))
(printf "There are ~a ~a-digit fractions of which:\n" (for/sum ([(k v) (in-hash digits)]) v) n)
(for ([digit (in-list (sort (hash->list digits) < #:key car))])
(printf " The digit ~a was crossed out ~a times\n" (car digit) (cdr digit)))
(newline))
(define (main)
(enumerate 2)
(enumerate 3)
(enumerate 4)
(enumerate 5)
(stats 2)
(stats 3)
(stats 4)
(stats 5))
(main)</lang>
{{out}}
<pre>
16/64 = 1/4 (6 crossed out)
19/95 = 1/5 (9 crossed out)
26/65 = 2/5 (6 crossed out)
49/98 = 4/8 (9 crossed out)
132/231 = 12/21 (3 crossed out)
134/536 = 14/56 (3 crossed out)
134/938 = 14/98 (3 crossed out)
136/238 = 16/28 (3 crossed out)
138/345 = 18/45 (3 crossed out)
139/695 = 13/65 (9 crossed out)
143/341 = 13/31 (4 crossed out)
146/365 = 14/35 (6 crossed out)
149/298 = 14/28 (9 crossed out)
149/596 = 14/56 (9 crossed out)
149/894 = 14/84 (9 crossed out)
154/253 = 14/23 (5 crossed out)
1234/4936 = 124/496 (3 crossed out)
1239/6195 = 123/615 (9 crossed out)
1246/3649 = 126/369 (4 crossed out)
1249/2498 = 124/248 (9 crossed out)
1259/6295 = 125/625 (9 crossed out)
1279/6395 = 127/635 (9 crossed out)
1283/5132 = 128/512 (3 crossed out)
1297/2594 = 127/254 (9 crossed out)
1297/3891 = 127/381 (9 crossed out)
1298/2596 = 128/256 (9 crossed out)
1298/3894 = 128/384 (9 crossed out)
1298/5192 = 128/512 (9 crossed out)
12349/24698 = 1234/2468 (9 crossed out)
12356/67958 = 1236/6798 (5 crossed out)
12358/14362 = 1258/1462 (3 crossed out)
12358/15364 = 1258/1564 (3 crossed out)
12358/17368 = 1258/1768 (3 crossed out)
12358/19372 = 1258/1972 (3 crossed out)
12358/21376 = 1258/2176 (3 crossed out)
12358/25384 = 1258/2584 (3 crossed out)
12359/61795 = 1235/6175 (9 crossed out)
12364/32596 = 1364/3596 (2 crossed out)
12379/61895 = 1237/6185 (9 crossed out)
12386/32654 = 1386/3654 (2 crossed out)
There are 4 2-digit fractions of which:
The digit 6 was crossed out 2 times
The digit 9 was crossed out 2 times
There are 122 3-digit fractions of which:
The digit 3 was crossed out 9 times
The digit 4 was crossed out 1 times
The digit 5 was crossed out 6 times
The digit 6 was crossed out 15 times
The digit 7 was crossed out 16 times
The digit 8 was crossed out 15 times
The digit 9 was crossed out 60 times
There are 660 4-digit fractions of which:
The digit 1 was crossed out 14 times
The digit 2 was crossed out 25 times
The digit 3 was crossed out 92 times
The digit 4 was crossed out 14 times
The digit 5 was crossed out 29 times
The digit 6 was crossed out 63 times
The digit 7 was crossed out 16 times
The digit 8 was crossed out 17 times
The digit 9 was crossed out 390 times
There are 5087 5-digit fractions of which:
The digit 1 was crossed out 75 times
The digit 2 was crossed out 40 times
The digit 3 was crossed out 376 times
The digit 4 was crossed out 78 times
The digit 5 was crossed out 209 times
The digit 6 was crossed out 379 times
The digit 7 was crossed out 591 times
The digit 8 was crossed out 351 times
The digit 9 was crossed out 2988 times
</pre>
| |||