#! /usr/bin/perl
#
# This script creates a graph in which we ignore the stray numbers that don't
# have any other numbers pointing to them. Instead we represent these in the
# relative sizes of circles in the graph.
# So the area of each circle corresponds to how many other numbers resolve there
# in one iteration of the kaprekar procedure.
#
# try using 'dot' on the file output by this script.
#
use strict;
use warnings;
use subs qw(kRoutine gotoNext getDiameter adjustedSizes generateDotFile);


my $digits = $ARGV[0] || 4;
my ($lower,$upper) = ("0" x $digits,"9" x $digits);     # e.g. (0000,9999)

my @converged;          # numbers which are "attractors"
my %nodes;              # $number => ($points_to, $num_nodes_that_point_here)


for my $n ("$lower".."$upper"){
    if ($nodes{$n}) {next}      # stored this already, and no need to increment

    my $nn = gotoNext($n);      # $n point to $nn

    if ($nodes{$nn}) {          # if we've found this value previously, 
        $nodes{$nn}[1]++;       # then just increment the counter, or else...
    } else {
        my $nnn = gotoNext ($nn);   # If we've never pointed here before...
        
        if ($nn eq $nnn) {push @converged, $nn}   # (number is an attractor)
                                    
        $nodes{$nn} = [ $nnn, 1 ];  # make a new entry showing only one
    }                               # number pointing to $nn so far
} 


## Analyze our data  bit: we want the smallest area circle to be height 1,
## adjust the others accordingly.
my $lowest_a = $upper;    #  initialize to 9999...


for (keys %nodes){
    my $n = $nodes{$_}[1];
    if ($n < $lowest_a) {$lowest_a = $n}
}

generateDotFile();


    #-------------------------------------#

sub gotoNext {
    my $n = shift;
    my @sort_nums = sort {$b cmp $a} split (//,$n);
    
    my $new_num = (join('',@sort_nums)) - 
                  (join('', reverse @sort_nums));
    
    while (length $new_num < $digits) 
        {$new_num = ("0" . "$new_num")}             #pad with leading zeros
    
    #return ( sprintf("%0${digits}d", $new_num) );  #pad with leading zeros
    return $new_num;
}



## Print to screen the dot file, line by line. Experiment sub generateDotFile {
   my $graph_name = "kaprekar_$digits";
    
        print  "digraph $graph_name {\n";
        print       "\tnode [shape = doublecircle,color=red3,fontcolor=red,fixedsize=true,margin=0]; @converged;\n";
        print       "\tnode [shape = circle,style=filled,fillcolor=gray94,fontcolor=grey,margin=0,fixedsize=true];\n";
        print       "\tgraph [overlap=false,splines=true,outputorder=nodesfirst];\n";
        #print       "\tranksep=2;\n";                           #experiment w/ value
        #print       "\tratio=auto;\n";

    for my $n (keys %nodes){
      my @sizes = adjustedSizes( $nodes{$n}[1] );
    
        print       "\t$n [height=$sizes[0],fontsize=$sizes[1]];\n";
        print       "\t$n -> $nodes{$n}[0] [penwidth=$sizes[0],arrowsize=$sizes[0]];\n";
    }
        print  "}\n";
    
}

sub getDiameter {
    my $area = shift;
    my $diameter = 2*sqrt($area / 3.14);
}

## Scale our circles and keep the same fontsize to circleheight ratio:
sub adjustedSizes {
    my $height = getDiameter(shift);
    
    $height = sprintf("%.1f", 
                ($height / $lowest_a));  # smallest circle should have height ~1
    my $fontsize = sprintf("%.1f", 
                    ($height * 12));    # for circle size 1, font should be 12
    
    return ($height,$fontsize);
}