The weekly challenge 391 - Task 2: Arrange Box

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-391/#TASK2
 3 #
 4 # Task 2: Arrange Box
 5 # ===================
 6 #
 7 # You are given an array of box dimensions.
 8 #
 9 # Write a script to determine the maximum number of these boxes that can fit
10 # inside each other in a single stack. For a box to fit inside another, it must
11 # be smaller in both dimensions.
12 #
13 ## Example 1
14 ##
15 ## Input: @boxes = ([1, 3], [3, 5], [6, 8], [2, 4])
16 ## Output: 4
17 ##
18 ## Sort by width ascending: ([1, 3], [2, 4], [3, 5], [6, 8])
19 ## Extract heights: [3, 4, 5, 8]
20 ## [1, 3] -> [2, 4] -> [3, 5] -> [6, 8]
21 #
22 ## Example 2
23 ##
24 ## Input: @boxes = ([4, 5], [4, 6], [6, 7], [2, 3], [4, 3])
25 ## Output: 3
26 ##
27 ## Sort by width ascending: ([2, 3], [4, 6], [4, 5], [4, 3], [6, 7])
28 ## Extract heights: (3, 6, 5, 3, 7)
29 ## [2, 3] -> [4, 5] -> [6, 7]
30 #
31 ## Example 3
32 ##
33 ## Input: @boxes = ([5, 5], [5, 5], [5, 5])
34 ## Output: 1
35 ##
36 ## Sort by width ascending: ([5, 5], [5, 5], [5, 5])
37 ## Extract heights: (5, 5, 5)
38 ## [5, 5]
39 #
40 ## Example 4
41 ##
42 ## Input: @boxes = ([2, 100], [3, 200], [4, 300], [5, 50], [5, 400])
43 ## Output: 4
44 ##
45 ## Sort by width ascending: ([2, 100], [3, 200], [4, 300], [5, 400], [5, 50])
46 ## Extract heights: (100, 200, 300, 400, 50)
47 ## [2, 100] -> [3, 200] -> [4, 300] -> [5, 400]
48 #
49 ## Example 5
50 ##
51 ## Input: @boxes = ([10, 20], [15, 10], [20, 30], [12, 18], [16, 25])
52 ## Output: 3
53 ##
54 ## Sort by width ascending: ([10, 20], [12, 18], [15, 10], [16, 25], [20, 30])
55 ## Extract heights: (20, 18, 10, 25, 30)
56 ## [15, 10] -> [16, 25] -> [20, 30]
57 #
58 ############################################################
59 ##
60 ## discussion
61 ##
62 ############################################################
63 #
64 # After sorting, we check for the longest chain:
65 # 1. Given a current element and a rest array, we recursively find the length
66 #    of the next possible combination (1 + length of recursive call of the rest)
67 # 2. When we call the function with an empty rest, we return 0 (which should
68 #    actually be 1, as we didn't count the current head yet)
69 # 3. Since we counted 1 less than we need, we add it in the end
70 
71 use v5.36;
72 
73 sub arrange_box(@boxes) {
74     say "Input: (" . join(", ", map { "[$_->[0], $_->[1]]" } @boxes) . ")";
75     my @sorted = sort { $a->[0] <=> $b->[0] or $b->[1] <=> $a->[1] } @boxes;
76     say "Output: " . ( 1 + find_longest(undef, @sorted) );
77 }
78 
79 sub find_longest($current, @rest) {
80     my $longest = 0;
81     foreach my $i (0..$#rest) {
82         if(defined($current)) {
83             if($current->[0] < $rest[$i]->[0] and $current->[1] < $rest[$i]->[1] ) {
84                 my $current = 1 + find_longest($rest[$i], @rest[$i+1..$#rest]);
85                 $longest = $current if $current > $longest;
86             }
87         } else {
88             my $current = find_longest($rest[$i], @rest[$i+1..$#rest]);
89             $longest = $current if $current > $longest;
90         }
91     }
92     return $longest;
93 }
94 
95 arrange_box([1, 3], [3, 5], [6, 8], [2, 4]);
96 arrange_box([4, 5], [4, 6], [6, 7], [2, 3], [4, 3]);
97 arrange_box([5, 5], [5, 5], [5, 5]);
98 arrange_box([2, 100], [3, 200], [4, 300], [5, 50], [5, 400]);
99 arrange_box([10, 20], [15, 10], [20, 30], [12, 18], [16, 25]);