$| = 1;

my @seen = ();

sub other {
	my $prev = shift;
	$seen[$prev] = 1;

	# try to subtract 1
	foreach my $p (0..length($prev)-1) {
		my $d = substr($prev, $p, 1);
		if ($d >= 1) {
			my $can = 0 + ( substr($prev, 0, $p) . ($d-1) . substr($prev, $p+1) );
			if (not $seen[$can]) {
				return $can;
			}
		}
	}

	# try to add 1
	foreach my $p (reverse 0..length($prev)-1) {
		my $d = substr($prev, $p, 1);
		if ($d<9) {
			my $can = substr($prev, 0, $p) . ($d+1) . substr($prev, $p+1);
			if (not $seen[$can]) {
			    return $can;
			}
		}
	}

	# append 10^k
	my $p = 1;
	while (1) {
		my $can = $p . $prev;
		if (not $seen[$can]) {
			return $can;
		}
		$p = $p . "0";
	}
}

my $a = 0;

foreach my $n (0..10_000) {
	print "$n $a\n";
	$a = other($a);
}