diff options
| -rw-r--r-- | challenge-057/adam-russell/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-057/adam-russell/inverted.dot | 25 | ||||
| -rw-r--r-- | challenge-057/adam-russell/inverted.png | bin | 0 -> 20139 bytes | |||
| -rw-r--r-- | challenge-057/adam-russell/original.dot | 25 | ||||
| -rw-r--r-- | challenge-057/adam-russell/original.png | bin | 0 -> 20432 bytes | |||
| -rw-r--r-- | challenge-057/adam-russell/perl/ch-1.pl | 108 |
6 files changed, 159 insertions, 0 deletions
diff --git a/challenge-057/adam-russell/blog.txt b/challenge-057/adam-russell/blog.txt new file mode 100644 index 0000000000..66690ce931 --- /dev/null +++ b/challenge-057/adam-russell/blog.txt @@ -0,0 +1 @@ +https://adamcrussell.livejournal.com/15872.html diff --git a/challenge-057/adam-russell/inverted.dot b/challenge-057/adam-russell/inverted.dot new file mode 100644 index 0000000000..e919f6c9f7 --- /dev/null +++ b/challenge-057/adam-russell/inverted.dot @@ -0,0 +1,25 @@ +digraph GRAPH_0 { + + // Generated by Graph::Easy 0.76 at Sun Apr 26 16:18:51 2020 + + edge [ arrowhead=open ]; + graph [ rankdir=LR ]; + node [ + fillcolor=white, + fontsize=11, + shape=box, + style=filled ]; + + 43 -> 49 [ color="#000000", fontcolor="#000000", label=left ] + 43 -> 31 [ color="#000000", fontcolor="#000000", label=right ] + 19 -> 17 [ color="#000000", fontcolor="#000000", label=right ] + 19 -> 43 [ color="#000000", fontcolor="#000000", label=left ] + 11 -> 19 [ color="#000000", fontcolor="#000000", label=left ] + 11 -> 6 [ color="#000000", fontcolor="#000000", label=right ] + 6 -> 4 [ color="#000000", fontcolor="#000000", label=right ] + 6 -> 8 [ color="#000000", fontcolor="#000000", label=left ] + 8 -> 10 [ color="#000000", fontcolor="#000000", label=left ] + 4 -> 5 [ color="#000000", fontcolor="#000000", label=left ] + +} + diff --git a/challenge-057/adam-russell/inverted.png b/challenge-057/adam-russell/inverted.png Binary files differnew file mode 100644 index 0000000000..e7b6808bdc --- /dev/null +++ b/challenge-057/adam-russell/inverted.png diff --git a/challenge-057/adam-russell/original.dot b/challenge-057/adam-russell/original.dot new file mode 100644 index 0000000000..a93f049a73 --- /dev/null +++ b/challenge-057/adam-russell/original.dot @@ -0,0 +1,25 @@ +digraph GRAPH_0 { + + // Generated by Graph::Easy 0.76 at Sun Apr 26 16:00:04 2020 + + edge [ arrowhead=open ]; + graph [ rankdir=LR ]; + node [ + fillcolor=white, + fontsize=11, + shape=box, + style=filled ]; + + 4 -> 5 [ color="#000000", fontcolor="#000000", label=right ] + 19 -> 17 [ color="#000000", fontcolor="#000000", label=left ] + 19 -> 43 [ color="#000000", fontcolor="#000000", label=right ] + 11 -> 6 [ color="#000000", fontcolor="#000000", label=left ] + 11 -> 19 [ color="#000000", fontcolor="#000000", label=right ] + 6 -> 8 [ color="#000000", fontcolor="#000000", label=right ] + 6 -> 4 [ color="#000000", fontcolor="#000000", label=left ] + 43 -> 49 [ color="#000000", fontcolor="#000000", label=right ] + 43 -> 31 [ color="#000000", fontcolor="#000000", label=left ] + 8 -> 10 [ color="#000000", fontcolor="#000000", label=right ] + +} + diff --git a/challenge-057/adam-russell/original.png b/challenge-057/adam-russell/original.png Binary files differnew file mode 100644 index 0000000000..69d486e32e --- /dev/null +++ b/challenge-057/adam-russell/original.png diff --git a/challenge-057/adam-russell/perl/ch-1.pl b/challenge-057/adam-russell/perl/ch-1.pl new file mode 100644 index 0000000000..dc6ac607bb --- /dev/null +++ b/challenge-057/adam-russell/perl/ch-1.pl @@ -0,0 +1,108 @@ +use strict; +use warnings; +## +# Write a script to invert a binary tree. +## +use Graph; +use boolean; +use Graph::Reader::Dot; +use Graph::Easy::Parser; + +sub insert{ + my($graph, $root, $next) = @_; + if(!$graph->vertices()){ + $graph->add_vertex($next); + $graph->set_edge_attribute($next, "left", "left", true); + $graph->set_edge_attribute($next, "right", "right", true); + return $next; + } + if($root > $next){ + if($graph->has_edge_attribute($root, "left", "left")){ + $graph->delete_edge_attributes($root, "left"); + $graph->set_edge_attribute($root, $next, "left", true); + $graph->set_edge_attribute($next, "left", "left", true); + $graph->set_edge_attribute($next, "right", "right", true); + } + my @successors = $graph->successors($root); + for my $s (@successors){ + if($graph->has_edge_attribute($root, $s, "left")){ + insert($graph, $s, $next); + } + } + } + if($root < $next){ + if($graph->has_edge_attribute($root, "right", "right")){ + $graph->delete_edge_attributes($root, "right"); + $graph->set_edge_attribute($root, $next, "right", true); + $graph->set_edge_attribute($next, "left", "left", true); + $graph->set_edge_attribute($next, "right", "right", true); + } + my @successors = $graph->successors($root); + for my $s (@successors){ + if($graph->has_edge_attribute($root, $s, "right")){ + insert($graph, $s, $next); + } + } + } +} + + +sub invert{ + my($graph, $root) = @_; + my @successors = $graph->successors($root); + for my $s (@successors){ + if($graph->has_edge_attribute($root, $s, "right")){ + $graph->delete_edge_attribute($root, $s, "right"); + $graph->delete_edge($root, $s); + $graph->set_edge_attribute($root, $s, "left", true); + invert($graph, $s); + } + elsif($graph->has_edge_attribute($root, $s, "left")){ + $graph->delete_edge_attribute($root, $s, "left"); + $graph->delete_edge($root, $s); + $graph->set_edge_attribute($root, $s, "right", true); + invert($graph, $s); + } + } +} + +sub display{ + my($graph) = @_; + my @edges = $graph->edges(); + my @lines; + for my $n (@edges){ + my ($u, $v) = @{$n}; + if($graph->get_edge_attribute($u, $v, "left")){ + push @lines, "[ $u ] -- left --> [ $v ]"; + } + if($graph->get_edge_attribute($u, $v, "right")){ + push @lines, "[ $u ] -- right --> [ $v ]"; + } + } + my $parser = new Graph::Easy::Parser(); + my $graph_viz = $parser->from_text(join("", @lines)); + print $graph_viz->as_ascii(); + #print $graph_viz->as_graphviz(); +} + +MAIN:{ + my $graph = new Graph(multivertexed => true); + my @a = (11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31); + my $root; + for my $a (@a){ + if(!$root){ + $root = insert($graph, $root, $a) + } + else{ + insert($graph, $root, $a) + } + } + while($graph->has_vertex("left") && $graph->has_vertex("right")){ + $graph->delete_vertices("left", "right"); + } + print "Original\n\n"; + display($graph); + invert($graph, $root); + print "\n\nInverted\n\n"; + display($graph); +} |
