Perl logo (Thanks to The weekly challenge 361 - Task 2: Find Celebrity
1 #!/usr/bin/env perl 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-361/#TASK2 3 # 4 # Task 2: Find Celebrity 5 # ====================== 6 # 7 # You are given a binary matrix (m x n). 8 # 9 # Write a script to find the celebrity, return -1 when none found. 10 # 11 ### A celebrity is someone, everyone knows and knows nobody. 12 # 13 # 14 ## Example 1 15 ## 16 ## Input: @party = ( 17 ## [0, 0, 0, 0, 1, 0], # 0 knows 4 18 ## [0, 0, 0, 0, 1, 0], # 1 knows 4 19 ## [0, 0, 0, 0, 1, 0], # 2 knows 4 20 ## [0, 0, 0, 0, 1, 0], # 3 knows 4 21 ## [0, 0, 0, 0, 0, 0], # 4 knows NOBODY 22 ## [0, 0, 0, 0, 1, 0], # 5 knows 4 23 ## ); 24 ## Output: 4 25 # 26 # 27 ## Example 2 28 ## 29 ## Input: @party = ( 30 ## [0, 1, 0, 0], # 0 knows 1 31 ## [0, 0, 1, 0], # 1 knows 2 32 ## [0, 0, 0, 1], # 2 knows 3 33 ## [1, 0, 0, 0] # 3 knows 0 34 ## ); 35 ## Output: -1 36 # 37 # 38 ## Example 3 39 ## 40 ## Input: @party = ( 41 ## [0, 0, 0, 0, 0], # 0 knows NOBODY 42 ## [1, 0, 0, 0, 0], # 1 knows 0 43 ## [1, 0, 0, 0, 0], # 2 knows 0 44 ## [1, 0, 0, 0, 0], # 3 knows 0 45 ## [1, 0, 0, 0, 0] # 4 knows 0 46 ## ); 47 ## Output: 0 48 # 49 # 50 ## Example 4 51 ## 52 ## Input: @party = ( 53 ## [0, 1, 0, 1, 0, 1], # 0 knows 1, 3, 5 54 ## [1, 0, 1, 1, 0, 0], # 1 knows 0, 2, 3 55 ## [0, 0, 0, 1, 1, 0], # 2 knows 3, 4 56 ## [0, 0, 0, 0, 0, 0], # 3 knows NOBODY 57 ## [0, 1, 0, 1, 0, 0], # 4 knows 1, 3 58 ## [1, 0, 1, 1, 0, 0] # 5 knows 0, 2, 3 59 ## ); 60 ## Output: 3 61 # 62 # 63 ## Example 5 64 ## 65 ## Input: @party = ( 66 ## [0, 1, 1, 0], # 0 knows 1 and 2 67 ## [1, 0, 1, 0], # 1 knows 0 and 2 68 ## [0, 0, 0, 0], # 2 knows NOBODY 69 ## [0, 0, 0, 0] # 3 knows NOBODY 70 ## ); 71 ## Output: -1 72 # 73 # 74 ## Example 6 75 ## 76 ## Input: @party = ( 77 ## [0, 0, 1, 1], # 0 knows 2 and 3 78 ## [1, 0, 0, 0], # 1 knows 0 79 ## [1, 1, 0, 1], # 2 knows 0, 1 and 3 80 ## [1, 1, 0, 0] # 3 knows 0 and 1 81 ## ); 82 ## Output: -1 83 # 84 ############################################################ 85 ## 86 ## discussion 87 ## 88 ############################################################ 89 # 90 # Since the matrix has information on each person in respect to each 91 # other, the mxn matrix is actually a mxm matrix. So we can use the 92 # number of rows and columns interchangibly, so we'll do that. 93 # Now we prefill an array @known_by_all with all ones, and later 94 # turn each value to 0 if we see one person not knowing this one. 95 # So in the end we know which people are known by all. 96 # We also count how many people everyone knows. If that number is 0, 97 # we remember that person in the array @knows_none. 98 # In the end, if multiple people or nobody at all knows none, we can 99 # return -1. If exactly one person knows none, we return that persons 100 # index if everybody knows this one. Otherwise, we couldn't find 101 # any celebrity and return -1 again. 102 103 use v5.36; 104 105 find_celebrity( 106 [0, 0, 0, 0, 1, 0], # 0 knows 4 107 [0, 0, 0, 0, 1, 0], # 1 knows 4 108 [0, 0, 0, 0, 1, 0], # 2 knows 4 109 [0, 0, 0, 0, 1, 0], # 3 knows 4 110 [0, 0, 0, 0, 0, 0], # 4 knows N 111 [0, 0, 0, 0, 1, 0], # 5 knows 4 112 ); 113 find_celebrity( 114 [0, 1, 0, 0], # 0 knows 1 115 [0, 0, 1, 0], # 1 knows 2 116 [0, 0, 0, 1], # 2 knows 3 117 [1, 0, 0, 0] # 3 knows 0 118 ); 119 find_celebrity( 120 [0, 0, 0, 0, 0], # 0 knows NOBODY 121 [1, 0, 0, 0, 0], # 1 knows 0 122 [1, 0, 0, 0, 0], # 2 knows 0 123 [1, 0, 0, 0, 0], # 3 knows 0 124 [1, 0, 0, 0, 0] # 4 knows 0 125 ); 126 find_celebrity( 127 [0, 1, 0, 1, 0, 1], # 0 knows 1, 3, 5 128 [1, 0, 1, 1, 0, 0], # 1 knows 0, 2, 3 129 [0, 0, 0, 1, 1, 0], # 2 knows 3, 4 130 [0, 0, 0, 0, 0, 0], # 3 knows NOBODY 131 [0, 1, 0, 1, 0, 0], # 4 knows 1, 3 132 [1, 0, 1, 1, 0, 0] # 5 knows 0, 2, 3 133 ); 134 find_celebrity( 135 [0, 1, 1, 0], # 0 knows 1 and 2 136 [1, 0, 1, 0], # 1 knows 0 and 2 137 [0, 0, 0, 0], # 2 knows NOBODY 138 [0, 0, 0, 0] # 3 knows NOBODY 139 ); 140 find_celebrity( 141 [0, 0, 1, 1], # 0 knows 2 and 3 142 [1, 0, 0, 0], # 1 knows 0 143 [1, 1, 0, 1], # 2 knows 0, 1 and 3 144 [1, 1, 0, 0] # 3 knows 0 and 1 145 ); 146 147 sub find_celebrity(@party) { 148 my @known_by_all = (); 149 my @knows_none; 150 foreach my $i (0..$#party) { 151 push @known_by_all, 1; 152 } 153 foreach my $who (0..$#party) { 154 my $knows_how_many = 0; 155 foreach my $whom (0..$#party) { 156 $knows_how_many += $party[$who]->[$whom]; 157 $known_by_all[$whom] = 0 unless $party[$who]->[$whom] or $who == $whom; 158 } 159 push @knows_none, $who unless $knows_how_many; 160 } 161 return say "Output: -1" unless scalar(@knows_none) == 1; 162 return say "Output: $knows_none[0]" if $known_by_all[$knows_none[0]]; 163 return say "Output: -1"; 164 }