#!/usr/bin/env perl

# xd3archival.pl - find smallest xdelta3 permutation
# ed <irc.rizon.net>, MIT-licensed, 2019-02-18, v0.1
# https://ocv.me/dev/

use strict;
use warnings;

use Storable qw(dclone);

my %isotab;
my %efftab;

sub lv1 {
	my $spent0, %have0, %maptab0, $depth = $_;
	
	if ($depth == 5)
		print(%maptab0);
	
	die "2deep4me" unless $depth < 100;
	
	my @best;
	foreach $f1 (keys %have0) {
		foreach $f2 (keys %isotab) {
			if (exists $have0{$f2})
				next;

			# sic: $ even though they're hashes
			my $have = dclone(\%have0);
			my $maptab = dclone(\%maptab0);

			my $spent = $spent0 + $efftab{$f1}{$f2};
			$have{$f2} = 1;
			if (!exists @maptab{$f1})
				@maptab{$f1} = ($f2)
			else
				push @maptab{$f1}, $f2;

			my $complete = 1;
			foreach $fn (keys %isotab) {
				if (!exists %have{$fn}) {
					$complete = 0;
					break;
				}
			}

			if ($complete == 0)
				$spent, %have, %maptab = lv1(
					$spent, %have, %maptab, $depth+1);
			
			if (@best == 0 || $best[0] > $spent)
				@best = ($spent, %have, %maptab);

			break  # hack
		}
	}
	return @best;
}

my $fn_eff = 'xd3archival.efficiency';
my $fn_iso = 'xd3archival.isolist';

open(my $fh, '<:encoding(UTF-8)', $fn_eff)
	or die('could not open '.$fn_eff);

while (my $ln = <$fh>) {
	chomp $ln;
	my @la = split(/ /, $ln);
	$efftab{$la[1]}{$la[2]} = int($la[0]);
	$efftab{$la[2]}{$la[1]} = int($la[0]);
}
close($fh);

open(my $fh, '<:encoding(UTF-8)', $fn_iso)
	or die('could not open '.$fn_iso);

while (my $ln = <$fh>) {
	chomp $ln;
	my @aln = split(/ /, $ln);
	$isotab{$aln[1]} = int($aln[0]);
}
close($fh);

my @best;
foreach $fn (keys %isotab) {
	print 'trying with base iso '.$fn.'\n';
	my $spent, %have, %maptab = lv1(
		$isotab{$fn}, ($fn=>1), (), 0);
	
	print '-- '.$spent.'\n';
	if (@best == 0 || $best[0] > $spent)
		@best = ($spent, $fn, %maptab);
	
	break;  # hack
}

print '\nbest = '.$best[0].' bytes; '.$best[1].'\n';

my @seen = ($best[1]);
my %left = %best[2];
while (%left != 0) {
	my $found = 1;
	foreach $k (@seen) {
		if (exists @left{$k}) {
			$found = 0;
			foreach $v (@left{$k}) {
				push @seen, $v;
				print $efftab{$k}{$v}.' spent;  '.$k.'  >>  '.$v.'\n';
			}
			delete @left[$k];
			break;
		}
	}
	if ($found == 1)
		break;
}

foreach $k (keys %left) {
	foreach $v (@left{$k}) {
		print 'UNLINKED:  '.$efftab{$k}{$v}.' spent;  '.$k.'  >>  '.$v.'\n';
	}
}

