The weekly challenge 308 - Task 2: Decode XOR

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-308/#TASK2
 3 #
 4 # Task 2: Decode XOR
 5 # ==================
 6 #
 7 # You are given an encoded array and an initial integer.
 8 #
 9 # Write a script to find the original array that produced the given encoded
10 # array. It was encoded such that encoded[i] = orig[i] XOR orig[i + 1].
11 #
12 ## Example 1
13 ##
14 ## Input: @encoded = (1, 2, 3), $initial = 1
15 ## Output: (1, 0, 2, 1)
16 ##
17 ## Encoded array created like below, if the original array was (1, 0, 2, 1)
18 ## $encoded[0] = (1 xor 0) = 1
19 ## $encoded[1] = (0 xor 2) = 2
20 ## $encoded[2] = (2 xor 1) = 3
21 #
22 ## Example 2
23 ##
24 ## Input: @encoded = (6, 2, 7, 3), $initial = 4
25 ## Output: (4, 2, 0, 7, 4)
26 #
27 ############################################################
28 ##
29 ## discussion
30 ##
31 ############################################################
32 #
33 # Let's have a look at bitwise xor:
34 # a xor b = c
35 # 0     0 = 0
36 # 1     0 = 1
37 # 0     1 = 1
38 # 1     1 = 0
39 # We can see: a xor b = c <=> a = b xor c
40 # In other words, we can calculate the next numer in the orig array by
41 # calculating the last found element in the orig array and the corresponding
42 # element in the encoded array. Since the first element of orig is given,
43 # the solution is well-defined.
44 
45 use v5.36;
46 
47 decode_xor(1, (1, 2, 3));
48 decode_xor(4, (6, 2, 7, 3));
49 
50 sub decode_xor {
51    my ($initial, @encoded) = @_;
52    print "Input: (" . join(", ", @encoded) . "), $initial\n";
53    my @result = ($initial);
54    foreach my $elem (@encoded) {
55       my $last = $result[$#result];
56       my $r = $last ^ $elem;
57       push @result, $r;
58    }
59    print "Output: (" . join(", ", @result) . ")\n";
60 }