The weekly challenge 382 - Task 1: Hamiltonian Cycle

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-382/#TASK1
 3 #
 4 # Task 1: Hamiltonian Cycle
 5 # =========================
 6 #
 7 # You are given a target number.
 8 #
 9 # Write a script to arrange all the whole numbers from 1 up to the given target
10 # number into a circle so that every pair of side-by-side numbers adds up to a
11 # perfect square. Please make sure, the last number and the first must also add
12 # up to a square.
13 #
14 ## Example 1
15 ##
16 ## Input: $n = 32
17 ## Output: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18,
18 ## 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15
19 ##
20 ## 1  + 8  = 9
21 ## 8  + 28 = 36
22 ## 28 + 21 = 49
23 ## 21 + 4  = 25
24 ## 4  + 32 = 36
25 ## 32 + 17 = 49
26 ## 17 + 19 = 36
27 ## 19 + 30 = 49
28 ##
29 ## so on, all the way through the sequence.
30 #
31 ## Example 2
32 ##
33 ## Input: $n = 15
34 ## Output: ()
35 ##
36 ## No valid circular list of numbers exists.
37 #
38 ## Example 3
39 ##
40 ## Input: $n = 34
41 ## Output: 1, 8, 28, 21, 4, 32, 17, 19, 6, 30, 34, 15, 10, 26, 23, 2, 14, 22,
42 ## 27, 9, 16, 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3
43 #
44 ############################################################
45 ##
46 ## discussion
47 ##
48 ############################################################
49 #
50 # We recursively try to find a hamiltonian cycle:
51 # - We pick the "1" at the beginning as the current last element
52 # - from all remaining numbers in the 1..$n list, we pick each one
53 # - if adding it to the last element creates a square, we recursively check
54 #   if we can turn it into a hamiltonian cycle, with the new last element
55 # - if we have a hamiltonian cycle, we are done, otherwise backtrack and
56 #   check for other potential solutions until we run out of possibilities
57 
58 use v5.36;
59 
60 hamiltonian_cycle(32);
61 hamiltonian_cycle(15);
62 hamiltonian_cycle(34);
63 
64 sub hamiltonian_cycle($n) {
65     say "Input $n";
66     my @numbers = (1..$n);
67     say join(", ", @numbers);
68     my @seq = ();
69     push @seq, shift @numbers;
70     my @found = find_hamiltonian_cycle(0, $seq[0], @numbers);
71     push @seq, @found;
72     return say "Output: (" . join(", ", @seq) . ")" if @found;
73     say "Output: ()";
74 }
75 
76 sub find_hamiltonian_cycle($indent, $last, @rest) {
77     if(scalar(@rest) == 1) {
78         return @rest if is_square($last + $rest[0]) && is_square($rest[0] + 1);
79         return ();
80     }
81     foreach my $i (0..$#rest) {
82         next unless is_square($last + $rest[$i]);
83         my @found = find_hamiltonian_cycle($indent + 1, $rest[$i], @rest[0..$i-1, $i+1..$#rest]);
84         next unless @found;
85         next unless is_square($found[$#found] + 1);
86         return ($rest[$i], @found);
87     }
88     return ();
89 }
90 
91 sub is_square($n) {
92     my $root = sqrt($n);
93     return $root == int($root);
94 }
95