diff options
| -rwxr-xr-x | challenge-115/jo-37/perl/ch-1.pl | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/challenge-115/jo-37/perl/ch-1.pl b/challenge-115/jo-37/perl/ch-1.pl new file mode 100755 index 0000000000..7dbc6c160b --- /dev/null +++ b/challenge-115/jo-37/perl/ch-1.pl @@ -0,0 +1,249 @@ +#!/usr/bin/perl -s + +use v5.16; +use Test2::V0; +use Graph; +use List::Util 'first'; +use List::MoreUtils 'firstidx'; +use utf8; +use Unicode::Normalize; +use experimental qw(signatures postderef); + +our ($tests, $examples, $verbose); + +run_tests() if $tests || $examples; # does not return + +die <<EOS unless @ARGV; +usage: $0 [-examples] [-tests] [-verbose] [string ...] + +-examples + run the examples from the challenge + +-tests + run some tests + +-verbose + show a string circle if there is one + +string ... + try to chain given strings into a circle + +EOS + + +### Input and Output + +say 0 + !!has_string_circle(@ARGV); + + +### Implementation + +# Interpreting the task as follows: +# *Decide* if there is a single circle connecting all given strings. +# I.e. multiple disjoint cycles do not count nor a single cycle that +# does not contain all given strings. A *concrete* circle is not +# requested. +# +# With this interpretation, the task is equivalent to deciding if the +# multidigraph formed by the given strings is Eulerian, where each +# string represents a directed edge between the vertices identified by +# the string's first and last character. Particularly, there may be +# multiple (equally directed) edges between the same pair of vertices +# and there may be loops connecting a vertex to itself. + +# According to Euler-Hierholzer's Theorem (in its extension for +# multidigraphs), an Eulerian cycle exists if and only if the graph +# (ignoring isolated vertices) is strongly connected and every vertex +# has a degree of zero, where the degree is the difference between +# in-degree and out-degree. +# +# Note: This theorem is given in several places without quoting its +# origin and is sometimes attributed to "Good". For a proof and some +# discussion see below. +# +# References: +# https://en.wikipedia.org/wiki/Eulerian_path +# https://en.wikipedia.org/wiki/Directed_graph +# https://en.wikipedia.org/wiki/Multigraph +# Even more details in the corresponding German wiki pages. + +sub has_string_circle { + # Create a multidigraph from the strings. + my $g = Graph->new(multiedged => 1); + for (@_) { + # The core of a multidigraph: Map each edge to its source and + # target vertices. This construction ensures that there are no + # isolated vertices. + # Get the string's first and last character, even if there's + # only one. Convert to lowercase normalized form allowing + # case-insensitive chaining of extended grapheme clusters as + # first and last "characters". + my @e = map NFD(lc), /^(\X)/, /(\X)$/; + my $id = $g->add_edge_get_id(@e); + # Assign the string as an edge attribute if an actual string + # circle is requested. + $g->set_edge_attribute_by_id(@e, $id, str => $_) if $verbose; + } + + # The "Graph" package's method "is_strongly_connected" dies if + # applied to a multigraph. The corollary below offers a + # simple workaround: Checking the weak connectivity suffices and + # "is_weakly_connected" appears to work for multigraphs. + return unless $g->is_weakly_connected; + + # Check the degree of all vertices. + for my $v ($g->vertices) { + return if $g->vertex_degree($v); + } + + # Here the graph is Eulerian. + + # Construct and display a string circle if requested. + build_circle($g) if $verbose; + + return 1; +} + +# Implementation of Hierholzer's algorithm (see below for a +# justification): +# - Start with a random vertex v. +# - Build a cycle c starting from and ending in v. +# - Repeat: +# * Find a new vertex v1 in c that has an outgoing edge excluded +# from c. +# * If there is no such vertex, the cycle c is Eulerian. Stop. +# * Find a cycle c1 starting from and ending in v1, omitting all edges +# in c. +# * Join the cycle c1 with the existing cycle c. +sub build_circle ($g) { + my @circle; + # Pick a random start vertex. Loop while there is a vertex with an + # unselected outgoing edge. + for (my $v = ($g->vertices)[0]; + defined $v; + $v = first {$g->out_degree($_)} map $_->[0], @circle) { + # Find the vertex position in the (non-)existing circle. + my $vpos = @circle ? firstidx {$_->[0] eq $v} @circle : 0; + # Find a cycle through $v and join it with the circle. + splice @circle, $vpos, 0, @{extract_cycle($g, $v)}; + } + + do {local $, = ', '; say map qq{"$_->[1]"}, @circle}; +} + +# Find a cycle starting from and ending in $vertex and remove the +# selected edges on the way. +sub extract_cycle ($g, $vertex) { + my $v = $vertex; + my @cycle; + do { + # Select a random outgoing multi-edge. + my @e = ($g->edges_from($v))[0]->@*; + # Select a random edge from the multi-edge. + my $id = ($g->get_multiedge_ids(@e))[0]; + # Collect the edge's source vertex and the string. + push @cycle, [$e[0], $g->get_edge_attribute_by_id(@e, $id, 'str')]; + # Remove the selected edge from the graph. + $g->delete_edge_by_id(@e, $id); + # Advance to the target vertex. + $v = $e[1]; + } until ($v eq $vertex); + + \@cycle; +} + + +### Examples and tests + +sub run_tests { + + SKIP: { + skip "examples" unless $examples; + + is has_string_circle(qw(abc dea cd)), T(), 'example 1'; + is has_string_circle(qw(ade cbd fgh)), F(), 'example 2'; + } + + SKIP: { + skip "tests" unless $tests; + + is has_string_circle(qw(ab bc ca bd de eb)), T(), + 'has two cycles'; + is has_string_circle(qw(ab bc ca bc)), F(), 'remaining string'; + is has_string_circle(qw(ab ba cd dc)), F(), 'not connected'; + is has_string_circle(qw(ab bc ca ad de ed)), F(), + 'weakly connected, nonzero degree'; + is has_string_circle(qw(ab ba c)), F(), 'disconnected self loop'; + is has_string_circle(qw(ab bc ca bd de eb axb bxc cxa d 0a a0 0)), + T(), + 'the whole works: multi-edged, loops, single char, zero vertex'; + # This would fail for "yolk", "eyelet", "gust", "O-umlaut" :-) + is has_string_circle(qw(Eigelb Öse Bö), "O\x{308}"), T(), + 'mixed case unicode grapheme cluster'; + } + + done_testing; + exit; +} + +__END__ + +Theorem ("Good"?): + +For a multidigraph D the following two statements are equivalent: +(a) D is Eulerian +(b) The subgraph of D ignoring isolated vertices is strongly connected + and every vertex of D has a degree of zero. + +Note: a vertex solely connected to itself by loop edges has ingoing and +outgoing edges and thus is not isolated. + +Proof: + +(1): Show that (a) implies (b) + +As D has an Eulerian circle, each non-isolated vertex is visited in the +course of the circle and as this is a circle, every non-isolated vertex +is reachable from any other non-isolated vertex. Thus D without its +isolated vertices is strongly connected. + +A circle has no ending vertex, thus for every vertex in the circle +there is an outgoing edge for every incoming edge, which gives a degree +of zero for every vertex. (This holds for isolated vertices, too.) + +(2): Show that (b) implies (a) + +This is basicly the reasoning for Hierholzer's algorithm. + +Select any (non-isolated) vertex v in D and build an arbitrary walk w +starting in v. Because every vertex has a degree of zero this walk may +be augmented in every vertex it ends in and because the graph is finite +it must lead back to v. If there are no edges omitted by the +constructed walk, this walk is an Eulerian circle. Otherwise, from the +strong connectivity of D it follows, that there must be a vertex v1 in w +having an outgoing edge that is not part of w. Constructing a new walk +w1 starting in v1 taking the omitted outgoing edge and augmenting this +with omitted edges only will - following the same consideration - lead +back to v1. The newly constructed walk w1 thus has no common edge with +w an can be inserted into the existing walk at the vertex v1. + +Repeating the procedure for the extended walk leads to a sequence of +strictly growing walks, which must result in an Eulerian circle as the +graph is finite. + +Q.E.D. + + +Corollary: +"strongly connected" may be replaced with "weakly connected". + +Indeed: +In part (1) this is trivial as a strongly connected graph is weakly +connected, too. +In part (2) the existence of an *outgoing* edge from a vertex in w is a +consequence of the strong connectivity. Assuming a weakly connected +graph would ensure the existence of an incoming *or* outgoing edge only. +From the zero degree of each vertex it follows, that for an incoming +egde there must be a corresponding outgoing edge. +Thus we may presume a weakly connected graph and will always find a +strongly connected graph. |