2021/day12.pl


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

use strict;
use warnings;
my %edges;
while (<>) {
	/(\w+)-(\w+)/;
	$edges{$1} //= [];
	$edges{$2} //= [];
	push @{$edges{$1}}, $2;
	push @{$edges{$2}}, $1;
}
my $paths = 0;
my @queue = (['start']);
while (@queue) {
	my @path = @{pop @queue};
	my %visited = map { $_ => 1 } @path;
	for (@{$edges{$path[0]}}) {
		if ($_ eq 'end') {
			$paths++;
		} elsif (/[a-z]/ && $visited{$_}) {
			next;
		} else {
			my @next = ($_, @path);
			push @queue, \@next;
		}
	}
}
print "$paths\n";
$paths = 0;
@queue = (['start']);
while (@queue) {
	my @path = @{pop @queue};
	my (%visited, $twice);
	for (@path) {
		$twice = 1 if $visited{$_}++ && /[a-z]/;
	}
	for (@{$edges{$path[0]}}) {
		next if $_ eq 'start';
		if ($_ eq 'end') {
			$paths++;
		} elsif (/[a-z]/ && $visited{$_} && $twice) {
			next;
		} else {
			my @next = ($_, @path);
			push @queue, \@next;
		}
	}
}
print "$paths\n";