#!/usr/bin/perl -w

use v5.16;
use strict;


=comment

    Magic Missile costs 53 mana. It instantly does 4 damage.
    Drain costs 73 mana. It instantly does 2 damage and heals you for 2 hit points.
    Shield costs 113 mana. It starts an effect that lasts for 6 turns. While it is active, your armor is increased by 7.
    Poison costs 173 mana. It starts an effect that lasts for 6 turns. At the start of each turn while it is active, it deals the boss 3 damage.
    Recharge costs 229 mana. It starts an effect that lasts for 5 turns. At the start of each turn while it is active, it gives you 101 new mana.

You start with 50 hit points and 500 mana points. The boss's actual stats are in your puzzle input. What is the least amount of mana you can spend and still win the fight? (Do not include mana recharge effects as "spending" negative mana.)

Boss: Hit Points: 71
Damage: 10

=cut

use Array::Heap;
my @q;
if (1) {
	push @q, [ 0, {
		turn       => 0,
		player_hp  => 50,
		mana       => 500,
		boss_hp    => 71,
		damage     => 10,
		spells     => [],
	} ];
} else {
	push @q, [ 0, {
		turn       => 0,
		player_hp  => 10,
		mana       => 250,
		boss_hp    => 14,
		damage     => 8,
		spells     => [],
	} ];
}

my %effects = map { $_ => 1 } qw(shield poison recharge);

sub spell {
	my ($name, $reqd, $entry, $action) = @_;
	my ($spent, $state, @spells) = @$entry;
	my %ns = %$state;
	$ns{turn}++;
	return if $ns{mana} < $reqd;
	$ns{mana} -= $reqd;
	$spent += $reqd;
	$ns{spells} = [ @{ $state->{spells} }, $name ];
	if ($effects{$name}) {
		return if $ns{$name};
		$ns{$name} = $name eq 'recharge' ? 5 : 6;
	} else {
		$action->(\%ns) if $action;
		if ($ns{boss_hp} <= 0) {
			say "won after spending $spent:_", join(',', @{ $ns{spells} });
			exit 0;
		}
	}
	push_heap @q, [ $spent, \%ns, ];
}

sub do_timer {
	my ($name, $entry, $action) = @_;
	my ($spent, $state) = @$entry;
	if ($state->{$name}) {
		# say "timer $name: $state->{$name}";
		$action->($entry);
		$state->{$name}--;
		if ($state->{boss_hp} <= 0) {
			say "won after spedning $spent: ", join(',', @{ $state->{spells} });
			exit 0;
		}
	}
}

sub do_timers {
	my ($entry) = @_;
	do_timer('shield', $entry, sub { });
	do_timer('poison', $entry, sub { $_[0]->[1]->{boss_hp} -= 3; });
	do_timer('recharge', $entry, sub { $_[0]->[1]->{mana} += 101; });
}

while (@q) {
	my $entry = pop_heap @q;
	my ($spent, $state) = @$entry;

	do_timers($entry);
	if ($state->{turn} & 1) { # boss
		$state->{turn}++;
		my $damage = $state->{damage};
		$damage -= 7 if $state->{shield};
		$damage = 1 if $damage < 1;
		$state->{player_hp} -= $damage;
		say "boss turn $state->{turn} player_hp $state->{player_hp} mana $state->{mana} boss_hp $state->{boss_hp} spent $spent ", join(',', @{ $state->{spells} }), " shield $state->{shield}";
		if ($state->{player_hp} <= 0) { # boss wins
			next;
		}
		push_heap @q, [$spent, $state ];
		next;
	}
	# Player
	spell('magic_missile', 53, $entry, sub {
		$_[0]->{boss_hp} -= 4;
	});
	spell('drain', 73, $entry, sub {
		$_[0]->{boss_hp} -= 2;
		$_[0]->{player_hp} += 2;
	});
	spell('shield', 113, $entry);
	spell('poison', 173, $entry);
	spell('recharge', 229, $entry);
}

