1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: assocs combinators kernel math math.order namespaces sequences project-euler.common ;
6 ! http://projecteuler.net/index.php?section=problems&id=151
11 ! A printing shop runs 16 batches (jobs) every week and each batch requires a
12 ! sheet of special colour-proofing paper of size A5.
14 ! Every Monday morning, the foreman opens a new envelope, containing a large
15 ! sheet of the special paper with size A1.
17 ! He proceeds to cut it in half, thus getting two sheets of size A2. Then he
18 ! cuts one of them in half to get two sheets of size A3 and so on until he
19 ! obtains the A5-size sheet needed for the first batch of the week.
21 ! All the unused sheets are placed back in the envelope.
23 ! At the beginning of each subsequent batch, he takes from the envelope one
24 ! sheet of paper at random. If it is of size A5, he uses it. If it is larger,
25 ! he repeats the 'cut-in-half' procedure until he has what he needs and any
26 ! remaining sheets are always placed back in the envelope.
28 ! Excluding the first and last batch of the week, find the expected number of
29 ! times (during each week) that the foreman finds a single sheet of paper in
32 ! Give your answer rounded to six decimal places using the format x.xxxxxx .
40 : (pick-sheet) ( seq i -- newseq )
52 : pick-sheet ( seq i -- res )
53 2dup swap nth dup zero? [
56 [ (pick-sheet) (euler151) ] dip *
59 : (euler151) ( x -- y )
62 { { 0 0 1 0 } [ { 0 0 0 1 } (euler151) 1+ ] }
63 { { 0 1 0 0 } [ { 0 0 1 1 } (euler151) 1+ ] }
64 { { 1 0 0 0 } [ { 0 1 1 1 } (euler151) 1+ ] }
65 [ [ dup length [ pick-sheet ] with map sum ] [ sum ] bi / ]
68 : euler151 ( -- answer )
71 { 1 1 1 1 } (euler151)
74 ! TODO: doesn't work currently, problem in area of 'with map' in (euler151)
76 ! [ euler151 ] 100 ave-time
77 ! ? ms run time - 100 trials