Year 2015

[aoc.git] / 2015 / 38.pl

diff --git a/2015/38.pl b/2015/38.pl
new file mode 100755 (executable)
index 0000000..1a30e5f
--- /dev/null
+++ b/2015/38.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use strict;
+
+my %rules;
+while (<>) {
+       chomp;
+       last if /^$/;
+       my ($src, $dst) = /(\w+) => (\w+)/;
+       # push @rules, [$src, $dst];
+       push @{ $rules{$src} }, [ split(/(?=[A-Z])/, $dst) ];
+}
+
+chomp (my $mol = <>);
+my @mol = split(/(?=[A-Z])/, $mol);
+
+$; = ',';
+my $added = 1;
+while ($added) {
+       $added = 0;
+       for my $elem (keys %rules) {
+               for my $rule (@{ $rules{$elem} }) {
+                       my $first = $
+my @q = ([ ['e'], \@mol, 0 ]);
+
+my %seen;
+
+while (@q) {
+       my $entry = shift @q;
+       my ($stack, $mol, $steps) = @$entry;
+
+       if (!@$stack && !@$mol) {
+               say $steps;
+               last;
+       }
+       if (!@$stack || !@$mol) {
+               next;
+       }
+       say "apply $steps: @$stack => @$mol";
+
+       if ($stack->[0] eq $mol->[0]) {
+               say "reduce $stack->[0]";
+               my @nstack = @$stack;
+               shift @nstack;
+               my @nmol = @$mol;
+               shift @nmol;
+               unshift @q, [ \@nstack, \@nmol, $steps ];
+       }
+       for my $rule (@{ $rules{$stack->[0]} }) {
+               my @nstack = @$stack;
+               shift @nstack;
+               unshift @nstack, @$rule;
+               my $key = join(' ', @nstack, '=', @$mol);
+               next if $seen{$key}++;
+               say "push $stack->[0] => @$rule";
+               push @q, [ \@nstack, [ @$mol ], $steps+1 ];
+       }
+}