#!/usr/bin/perl -w
use strict;

my $string = '0000';  # Might as well start somewhere.
my %seen = ( $string => 1 );
my $seen = 1;

sub see {
    my $n = shift;
    $seen{$n}++;
    $seen++ if $seen{$n} == 1;
    return $seen{$n} == 1;
}

sub unsee {
    $seen{substr($string, -4)}--;
    $seen--;
    return substr($string, -1, 1, '');
}



my $last = '0';
while ($seen < 10000) {
    my $lastthree = substr($string, -3);
    my $sawnew = 0;
    for ($last..9) {
        if ( see($lastthree . $_) ) {
            $string .= $_;
            $last = 0;
            $sawnew++;
            last;
        }
    }

    if (! $sawnew) {
        do {
            $last = unsee();
        } until ($last != 9);
        $last += 1;
        next;
    }

    print "seen: $seen\n", "len : ", length $string, "\n";
}

print $string, "\n";