The weekly challenge 324 - Task 2: Total XOR

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-324/#TASK2
 3 #
 4 # Task 2: Total XOR
 5 # =================
 6 #
 7 # You are given an array of integers.
 8 #
 9 # Write a script to return the sum of total XOR for every subset of given
10 # array.
11 #
12 ## Example 1
13 ##
14 ## Input: @ints = (1, 3)
15 ## Output: 6
16 ##
17 ## Subset [1],    total XOR = 1
18 ## Subset [3],    total XOR = 3
19 ## Subset [1, 3], total XOR => 1 XOR 3 => 2
20 ##
21 ## Sum of total XOR => 1 + 3 + 2 => 6
22 #
23 #
24 ## Example 2
25 ##
26 ## Input: @ints = (5, 1, 6)
27 ## Output: 28
28 ##
29 ## Subset [5],       total XOR = 5
30 ## Subset [1],       total XOR = 1
31 ## Subset [6],       total XOR = 6
32 ## Subset [5, 1],    total XOR => 5 XOR 1 => 4
33 ## Subset [5, 6],    total XOR => 5 XOR 6 => 3
34 ## Subset [1, 6],    total XOR => 1 XOR 6 => 7
35 ## Subset [5, 1, 6], total XOR => 5 XOR 1 XOR 6 => 2
36 ##
37 ## Sum of total XOR => 5 + 1 + 6 + 4 + 3 + 7 + 2 => 28
38 #
39 #
40 ## Example 3
41 ##
42 ## Input: @ints = (3, 4, 5, 6, 7, 8)
43 ## Output: 480
44 #
45 ############################################################
46 ##
47 ## discussion
48 ##
49 ############################################################
50 #
51 # First, we make sure that we have a set of unique elements,
52 # eliminating duplicates using List::Util's uniq().
53 # Then we create all possible subsets using Algorithm::Combinatorics'
54 # subsets() - we use the iterator interface so we don't eat
55 # unnecessary memory.
56 # For each subset, we then calculate the xor of this subset. For
57 # that, we start with 0, then we xor each element of the array to
58 # the current value until there are no more elements. Then we add
59 # that result to our current total value.
60 #
61 
62 use v5.36;
63 use List::Util qw( uniq );
64 use Algorithm::Combinatorics qw( subsets );
65 
66 total_xor(1, 3);
67 total_xor(5, 1, 6);
68 total_xor(3, 4, 5, 6, 7, 8);
69 
70 sub total_xor( @ints ) {
71     say "Input: (" . join(", ", @ints) . ")";
72     my @set = uniq @ints;
73     my $iter = subsets( \@ints );
74     my $result = 0;
75     while ( my $set = $iter->next ) {
76         my $tmp = 0;
77         foreach my $elem (@$set) {
78             $tmp = $tmp ^ $elem;
79         }
80         $result += $tmp;
81     }
82     say "Output: $result";
83 }
84