Shlomi Fish avatar Shlomi Fish committed 62a3655

Add the solution for Euler #109 (darts).

This is successful.

Comments (0)

Files changed (1)

project-euler/109/euler-109.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+
+=head1 DESCRIPTION
+
+In the game of darts a player throws three darts at a target board which is
+split into twenty equal sized sections numbered one to twenty.
+
+The score of a dart is determined by the number of the region that the dart
+lands in. A dart landing outside the red/green outer ring scores zero. The
+black and cream regions inside this ring represent single scores. However, the
+red/green outer ring and middle ring score double and treble scores
+respectively.
+
+At the centre of the board are two concentric circles called the bull region,
+    or bulls-eye. The outer bull is worth 25 points and the inner bull is a
+    double, worth 50 points.
+
+There are many variations of rules but in the most popular game the players
+will begin with a score 301 or 501 and the first player to reduce their running
+total to zero is a winner. However, it is normal to play a "doubles out"
+system, which means that the player must land a double (including the double
+    bulls-eye at the centre of the board) on their final dart to win; any other
+    dart that would reduce their running total to one or lower means the score
+    for that set of three darts is "bust".
+
+When a player is able to finish on their current score it is called a
+"checkout" and the highest checkout is 170: T20 T20 D25 (two treble 20s and
+    double bull).
+
+There are exactly eleven distinct ways to checkout on a score of 6:
+
+D3 	
+  	
+ 
+D1 	D2 	 S2 	D2 	 D2 	D1 	 S4 	D1 	 S1 	S1 	D2 S1 	T1 	D1 S1 	S3
+D1 D1 	D1 	D1 D1 	S2 	D1 S2 	S2 	D1
+
+Note that D1 D2 is considered different to D2 D1 as they finish on different
+doubles. However, the combination S1 T1 D1 is considered the same as T1 S1 D1.
+
+In addition we shall not include misses in considering combinations; for
+example, D3 is the same as 0 D3 and 0 0 D3.
+
+Incredibly there are 42336 distinct ways of checking out in total.
+
+How many distinct ways can a player checkout with a score less than 100?  
+
+=cut
+
+my %registry;
+my @score_lists;
+
+sub handle_final_doubles
+{
+    my ($results) = @_;
+
+    foreach my $double_result (1 .. 20, 25)
+    {
+        my $id = join(',', sort { $a cmp $b } map { join('*', @$_) } @$results)
+            . ";$double_result*2";
+
+        if (!exists($registry{$id}))
+        {
+            my $score = sum( map { $_->[0] * $_->[1] } @$results, [$double_result, 2]);
+            $registry{$id} = $score;
+            push @{$score_lists[$score]}, $id;
+        }
+    }
+}
+
+sub recurse
+{
+    my ($results) = @_;
+
+    my $depth = @$results;
+
+    handle_final_doubles($results);
+
+    if ($depth < 2)
+    {
+        foreach my $multiplier (1 .. 3)
+        {
+            foreach my $new_res (1 .. 20)
+            {
+                recurse([@$results, [$new_res, $multiplier]]);
+            }
+        }
+
+        foreach my $multiplier (1 .. 2)
+        {
+            recurse([@$results, [25, $multiplier]]);
+        }
+    }
+
+    return;
+}
+
+recurse([]);
+
+if (@{$score_lists[6]} != 11)
+{
+    die "Number of checkouts for 6 is not correct.";
+}
+
+print "Total = ", (sum (map { scalar(@{$_ || []}) } @score_lists[1 .. 99])), "\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.