From: Jan "Yenya" Kasprzak <kas@fi.muni.cz>
Date: Sun, 12 Dec 2021 05:27:34 +0000 (+0100)
Subject: Day 12: graph walking. Quite interesting.
X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc2021.git;a=commitdiff_plain;h=fa8ceebea72c6630d8ac9a5a05abbb8793716755

Day 12: graph walking. Quite interesting.
---

diff --git a/23.pl b/23.pl
new file mode 100755
index 0000000..1cb99a6
--- /dev/null
+++ b/23.pl
@@ -0,0 +1,38 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+my %g;
+while (<>) {
+	chomp;
+	my ($n1, $n2) = split /-/;
+	$g{$n1}->{$n2} = 1;
+	$g{$n2}->{$n1} = 1;
+}
+
+my @paths;
+my %subpaths;
+
+sub walk {
+	my (@path) = @_;
+	my $here = $path[-1];
+	my %visited = map { $_ => 1 } grep { /[a-z]/ } @path;
+
+	for my $node (keys %{ $g{$here} }) {
+		next if $visited{$node};
+		if ($node eq 'end') {
+			push @paths, [ @path, $node ];
+			say join('-', @{ $paths[-1] });
+		} else {
+			my $p = join('-', @path, $node);
+			next if $subpaths{$p}++;
+			walk(@path, $node);
+		}
+	}
+}
+
+walk('start');
+
+say scalar @paths;
+		
+
diff --git a/24.pl b/24.pl
new file mode 100755
index 0000000..de622d8
--- /dev/null
+++ b/24.pl
@@ -0,0 +1,41 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+my %g;
+while (<>) {
+	chomp;
+	my ($n1, $n2) = split /-/;
+	$g{$n1}->{$n2} = 1;
+	$g{$n2}->{$n1} = 1;
+}
+
+my @paths;
+my %subpaths;
+
+sub walk {
+	my (@path) = @_;
+	my $here = $path[-1];
+	my %visited;
+	$visited{$_}++ for grep { /[a-z]/ } @path;
+	my $two = grep { $_ == 2 } values %visited;
+
+	for my $node (keys %{ $g{$here} }) {
+		next if $visited{$node}
+			&& ($two || $node eq 'start' || $node eq 'end');
+		my $p = join('-', @path, $node);
+		next if $subpaths{$p}++;
+		if ($node eq 'end') {
+			push @paths, [ @path, $node ];
+			say join('-', @path, $node);
+		} else {
+			walk(@path, $node);
+		}
+	}
+}
+
+walk('start');
+
+say scalar @paths;
+		
+