#!/usr/bin/perl -wW

$reversesubstitute = "0213";

$ndigits = $ARGV[0];
$radix = $ARGV[1];
if (defined $ARGV[2])
{ $reversesubstitute = $ARGV[2]; }
$rotationstep = 1;
if (defined $ARGV[3])
{ $rotationstep = $ARGV[3]; }

unless (defined $radix)
{
	print STDERR "Usage: $0 <ndigits> <radix> [<reverse-substitutions>] "
		. "[rotation-step]\n";
	exit 1;
}

for ($i = 0; $i < $radix; $i++)
{
	$symbol = substr $reversesubstitute, $i, 1;
	if ($symbol >= $radix)
	{
		die("reverse substitute has invalid value for $i (" . $symbol
			. ")\n");
	}
}

# generate all possible codes

$code = "";
for ($pos = 0; $pos < $ndigits; $pos++)
{ $code .= "0"; }

$firstcode = $code;

@codes = ();
$generated = 0;

for (;;)
{
	$generated++;
	push @codes, $code;
	# increment code
	for ($pos = $ndigits; --$pos >= 0; )
	{
		$symbol = substr $code, $pos, 1;
		#print "pos is $pos, symbol is $symbol\n";
		$symbol++;
		#print "symbol is $symbol\n";
		if ($symbol < $radix)
		{
			#print "increment\n";
			substr $code, $pos, 1, $symbol;
			last;
		}
		else
		{
			#print "reset and carry\n";
			substr $code, $pos, 1, "0";
		}
	}
	#print $code . "\n";
	if ($code == $firstcode)
	{ last; }
}
print "generated $generated codes\n";
for ($i = 0; $i < $generated; $i++)
{
	print "code $i is \"" . $codes[$i] . "\"\n";
}
print "removing rotational duplicates\n";
$kept = 0;
@keeping = ();
for ($i = 0; $i < $generated; $i++)
{
	$unique = 1;
	$code = $codes[$i];
	#print "i is $i, code is $code\n";
	for ($j = 0; $j < $i; $j++)
	{
		$checkcode = $codes[$j];
		#print "checkcode $j is $checkcode\n";
		for($p = 0; $p < $ndigits; $p += $rotationstep)
		{
			my $rotated = rotate ($checkcode, $p);
			if ($rotated eq $code)
			{
				$unique = 0;
				#print "not unique\n";
			}
		}
	}
	if ($unique == 1)
	{
		#print "keeping $code\n";
		push @keeping, $code;
		$kept++;
	}
}
print "kept $kept codes\n";
for ($i = 0; $i < $kept; $i++)
{
	print "code $i is \"" . $keeping[$i] . "\"\n";
}

print "removing mirrored rotational duplicates\n";
@codes = @keeping;
@keeping = ();
$generated = $kept;
$kept = 0;

for ($i = 0; $i < $generated; $i++)
{
	$unique = 1;
	$code = $codes[$i];
	#print "i is $i, code is $code\n";
	for ($j = 0; $j < $i; $j++)
	{
		$checkcode = $codes[$j];
		#print "checkcode $j is $checkcode\n";
		# compute reverse of checkcode
		my $reversed = "";
		for ($p = 0; $p < $ndigits; $p++)
		{
			my $symbol = substr $checkcode, $p, 1;
			$symbol = substr $reversesubstitute, $symbol, 1;
			$reversed = $symbol . $reversed;
		}
		#print "reversed is $reversed\n";
		for ($r = 0; $r < $ndigits; $r += $rotationstep)
		{
			my $rotated = rotate ($reversed, $r);
			#print "$reversed rotated is $rotated\n";
			if ($rotated eq $code)
			{
				$unique = 0;
				#print "not unique\n";
			}
		}
	}
	if ($unique == 1)
	{
		#print "keeping $code\n";
		push @keeping, $code;
		$kept++;
	}
}
print "kept $kept codes\n";
for ($i = 0; $i < $kept; $i++)
{
	print "code $i is \"" . $keeping[$i] . "\"\n";
}

print "reversing direction replaced";
$sep = " ";
for ($i = 0; $i < $radix; $i++)
{
	print $sep . "$i -> " . substr $reversesubstitute, $i, 1;
	$sep = ", ";
}
print "\n";

sub rotate
{
	my $code = shift;
	my $rotation = shift;

	my $left = substr $code, 0, $rotation;
	my $right = substr $code, $rotation, $ndigits;
	my $rotated = $right . $left;
	#print "code is $code, pos is $p, left is $left, right is $right, rotated is $rotated\n";
	return $rotated;
}
