Shlomi Fish avatar Shlomi Fish committed 07dcab7

More optimisations, but there's a bug.

It does not find the number 45 which can be used to construct it.

Comments (0)

Files changed (1)

project-euler/152/euler-152-take3.pl

 use warnings;
 
 use Math::BigInt (only => 'GMP', ':constant');
+use List::Util qw(sum);
+use List::MoreUtils qw(all);
 
 sub is_prime
 {
 @keys = @keys[grep { $ints[$_] % 4 == 0 } keys(@keys)];
 calc_stuff();
 
-print join("\n", @ints), "\n";
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 17 != 15 } keys(@keys)];
+calc_stuff();
+
+my $found = 1;
+MAIN_TRIM:
+while ($found)
+{
+    $found = 0;
+
+    if (@keys == 41)
+    {
+        # last MAIN_TRIM;
+    }
+
+    TRIM_STUFF:
+    for my $n ($MIN .. 1000)
+    {
+        print "N == $n ; NumKeys == ", scalar(@keys), "\n";
+
+        # mod is modulo
+        my %mods_hash;
+        foreach my $mod (grep { $_ } map { $_ % $n } @ints)
+        {
+            $mods_hash{"$mod"} ||= {count => 0, can_be_formed => 0,};
+            $mods_hash{"$mod"}{count}++;
+        }
+        my %agg_mods;
+
+        foreach my $mod (keys(%mods_hash))
+        {
+            foreach my $c (1 .. $mods_hash{$mod}{count})
+            {
+                my $agg_mod = (($mod*$c) % $n);
+                $agg_mods{$agg_mod} ||= {};
+                $agg_mods{$agg_mod}{$mod} = 1;
+            }
+        }
+        my $target_mod = $lcm % $n;
+
+        my @mods = sort { $a <=> $b } keys(%agg_mods);
+
+        if ((@mods == $n) || (@mods == $n-1) ||
+            ($n == 31 and @keys == 41) ||
+            ($n == 38 and @keys == 41) ||
+            (all { exists($agg_mods{$n-$_}) } @mods ) ||
+            (
+                (all { exists($agg_mods{$_}) } (1 .. 3))
+                    and
+                (all { $mods[$_+1] - $mods[$_] <= 3 } (0 .. $#mods-1))
+                    and
+                ($mods[-1] >= $n-3)
+            )
+                or
+            (@mods > 15)
+        )
+        {
+            next TRIM_STUFF;
+        }
+        my $count_not_found_yet = 0+scalar(keys(%mods_hash));
+        foreach my $combo (1 .. ((1 << @mods)-1))
+        {
+            my @indexes = grep { (($combo >> $_) & 0x1) } keys(@mods);
+            if (sum (@mods[@indexes]) % $n == $target_mod)
+            {
+                foreach my $agg_m (@mods[@indexes])
+                {
+                    foreach my $m (keys(%{$agg_mods{$agg_m}}))
+                    {
+                        if (! $mods_hash{"$m"}{can_be_formed})
+                        {
+                            if (not --$count_not_found_yet)
+                            {
+                                next TRIM_STUFF;
+                            }
+                        }
+                        $mods_hash{"$m"}{can_be_formed} = 1;
+                    }
+                }
+            }
+        }
+
+        my @not_included_mods =
+        (grep { ! $mods_hash{"$_"}{can_be_formed} } keys(%mods_hash));
+
+        if (@not_included_mods)
+        {
+            print "Found [@not_included_mods] for Modulo == $n!\n";
+            $found = 1;
+            my %not_mods = (map { $_.'' => 1 } (@not_included_mods));
+            @keys = @keys[
+                (grep { !exists($not_mods{($ints[$_] % $n).''}) } keys(@keys))
+            ];
+            last TRIM_STUFF;
+        }
+    }
+
+    if ($found)
+    {
+        calc_stuff();
+    }
+}
+
+print join("\n", map { "$keys[$_] => $ints[$_]" } keys(@keys)), "\n";
 
 print "TARGET ==\n$target\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.