Shlomi Fish avatar Shlomi Fish committed 7f76ccb

Fix a few bugs in Euler #148.

Comments (0)

Files changed (2)

project-euler/148/Test.bash

 #!/bin/bash
-n=49
+n=98
 diff -u <(head -$n dump.txt | perl -lanE 'print $., ": ", y/Y/Y/') \
-    <(seq 1 "$n" | (while read i ; do echo "$i: $(perl calc-num-Y-in-row.pl "$i")" ; done))
+    <(perl calc-num-Y-in-row.pl $(seq 1 "$n"))
 

project-euler/148/calc-num-Y-in-row.pl

     my $n_proto = shift;
     my $n = $n_proto - 1;
 
+    my $recurse;
+
+    my $n_from_digits;
+
+    $n_from_digits = sub {
+        my $aref = shift;
+
+        if (! @$aref)
+        {
+            return 0;
+        }
+        return $aref->[0] + $BASE * $n_from_digits->([ @$aref[1 .. $#$aref] ]);
+    };
+
+    $recurse = sub {
+        my ($digits_aref) = @_;
+
+        my @digits = @$digits_aref;
+
+        if (@digits <= 1)
+        {
+            return 0;
+        }
+        elsif (@digits == 2)
+        {
+            return ($BASE-1-$digits[0]->{d}) * $digits[1]->{d};
+        }
+        elsif (@digits == 3)
+        {
+            my $big_Y_num = ($digits[-1]->{power}-1-$digits[-2]->{total_mod});
+            my $big_Y_total = $big_Y_num * $digits[-1]->{d};
+            # my $remaining_n = $digits[-1]->{total_mod} - $big_Y_total;
+
+            return $big_Y_total + ($digits[-1]->{d}+1) * $recurse->([@digits[0 .. $#digits-1]]);
+        }
+        else
+        {
+            die "Cannot handle.";
+        }
+    };
+
     my @digits;
 
     my $digit_n = $n->copy();
+    my $power = 1;
+    my $total_mod = 0;
     while ($digit_n)
     {
-        push @digits, $digit_n % $BASE;
+        my $digit = ($digit_n % $BASE);
+        $total_mod = $total_mod + $digit * $power;
+        push @digits, { d => $digit, power => $power, total_mod => $total_mod };
         $digit_n /= $BASE;
+        $power *= $BASE;
     }
 
-    if (@digits <= 1)
-    {
-        return 0;
-    }
-    elsif (@digits == 2)
-    {
-        return ($BASE-1-$digits[0]) * $digits[1];
-    }
-    else
-    {
-        die "Cannot handle.";
-    }
+    return $recurse->([@digits]);
 }
 
-my $n = shift(@ARGV);
-
-print calc_num_Y_in_row_n($n), "\n";
+foreach my $n (@ARGV)
+{
+    print "${n}: ", calc_num_Y_in_row_n($n), "\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.