#!/usr/bin/perl -w

use v5.36;
use strict;

my @bots = sort { $b->[3] <=> $a->[3] } map { [ /(-?\d+)/g ] } <>;
# my @bots = map { [ /(-?\d+)/g ] } <>;

sub overlaps($bot1, $bot2) {
	abs($bot1->[0] - $bot2->[0])
	+ abs($bot1->[1] - $bot2->[1])
	+ abs($bot1->[2] - $bot2->[2]) <= $bot1->[3] + $bot2->[3];
}

my @best;

sub walk($subset) {
	our $loop;
	our $min_sub = @$subset if !defined $min_sub || @$subset < $min_sub;
	if (++$loop % 10000 == 0) {
		say "walk: best ", scalar @best,
			' min ', $min_sub;
		$min_sub = undef;
		die;
	}
	my $to_check = @bots - $subset->[-1];
	return if @$subset + $to_check < @best;
	CANDIDATE:
	for my $i ($subset->[-1] + 1 .. $#bots) {
		for my $j (@$subset) {
			next CANDIDATE if !overlaps($bots[$i], $bots[$j]);
		}
		walk([ @$subset, $i ]);
	}

	if (@best < @$subset) {
		@best = @$subset;
	}
}

# eval { say "walk($_)"; walk([$_]) } for 0 .. $#bots;
eval { walk([0]); };

@best = sort { $bots[$a]->[3] <=> $bots[$b]->[3] } @best;
say "Best subset has ", scalar @best, " members";
say "Smallest is ", join(',', @{ $bots[$best[0]] });

sub try_overlaps {
	for my $j (1 .. $#best) {
		last return undef
			if !overlaps($bots[$best[0]], $bots[$best[$j]]);
	}
	return 1;
}

my $shrink;
DIM:
while (1) {
	say "Trying diameter $bots[$best[0]]->[3]";
	if (try_overlaps) {
		last DIM if $bots[$best[0]]->[3] == 0;
		$shrink = int($bots[$best[0]]->[3]/4);
		$shrink = 1 if $shrink < 1;
		$bots[$best[0]]->[3] -= $shrink;
		next;
	}
	for my $dir ([-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]) {
		say "trying ", join(',', @$dir);
		for (0 .. 2) {
			$bots[$best[0]]->[$_] += $shrink*$dir->[$_];
		}
		next DIM if try_overlaps;
		say "failed";
		for (0 .. 2) {
			$bots[$best[0]]->[$_] -= $shrink*$dir->[$_];
		}
	}
	die "nothing matched. strange";
}
say "end: ", join(',', @{ $bots[$best[0]] });
say $bots[$best[0]]->[0]
	+ $bots[$best[0]]->[1]
	+ $bots[$best[0]]->[2];
	
