Commits

Shlomi Fish committed 91f8aca

Add the solution.

Comments (0)

Files changed (2)

project-euler/121/121-planning.txt

 
 The state machine is:
 
-S1 -> S1 - 2/3
+S1 -> S1 = 2/3
 
-S1 -> S2 - 1/3
+S1 -> S2 = 1/3
 
-S2 -> S1 - 0
+S2 -> S1 = 0
 
-S2 -> S2 - 1/1
+S2 -> S2 = 1/1
 
 The output is:
 
 Out[S1] = B -> 1/2
 Out[S1] = R -> 1/2
 Out[S2] = B -> 0
-Out[S3] = R -> 1/1
+Out[S2] = R -> 1/1
 
+1 Turn:
+-------
+
+1/2 : N[B] = 0
+1/2 : N[B] = 1
+
+2 Turns:
+--------
+
+For the second turn,
+

project-euler/121/euler-121.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+=head1 DESCRIPTION
+
+A bag contains one red disc and one blue disc. In a game of chance a player
+takes a disc at random and its colour is noted. After each turn the disc is
+returned to the bag, an extra red disc is added, and another disc is taken at
+random.
+
+The player pays £1 to play and wins if they have taken more blue discs than red
+discs at the end of the game.
+
+If the game is played for four turns, the probability of a player winning is
+exactly 11/120, and so the maximum prize fund the banker should allocate for
+winning in this game would be £10 before they would expect to incur a loss.
+Note that any payout will be a whole number of pounds and also includes the
+original £1 paid to play the game, so in the example given the player actually
+wins £9.
+
+Find the maximum prize fund that should be allocated to a single game in which
+fifteen turns are played.
+
+=cut
+
+use Math::BigRat;
+
+my $num_turns = shift(@ARGV);
+
+my @B_nums_probs = (1);
+
+foreach my $turn_idx (1 .. $num_turns)
+{
+    my $this_B_prob = Math::BigRat->new('1/'.($turn_idx+1));
+
+    push @B_nums_probs, (0);
+
+    my @new_B_probs = map { 
+        my $i = $_; 
+        $B_nums_probs[$i] * (1-$this_B_prob) + 
+            (($i == 0) ? 0 : ($B_nums_probs[$i-1] * $this_B_prob))
+        } (0 .. $turn_idx);
+
+    @B_nums_probs = @new_B_probs;
+}
+
+my $s = Math::BigRat->new('0');
+
+foreach my $idx ( int($num_turns/2)+1 .. $num_turns)
+{
+    $s += $B_nums_probs[$idx];
+}
+
+print "S = $s\n";
+print "Int[1/S] = ", int(1/$s), "\n";
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.