The weekly challenge 354 - Task 2: Shift Grid

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-354/#TASK2
  3 #
  4 # Task 2: Shift Grid
  5 # ==================
  6 #
  7 # You are given m x n matrix and an integer, $k > 0.
  8 #
  9 # Write a script to shift the given matrix $k times.
 10 #
 11 # Each shift follow the rules:
 12 #
 13 # Rule 1:
 14 # Element at grid[i][j] moves to grid[i][j + 1]
 15 # This means every element moves one step to the right within its row.
 16 #
 17 # Rule 2:
 18 # Element at grid[i][n - 1] moves to grid[i + 1][0]
 19 # This handles the last column: elements in the last column of row i wrap to the first column of the next row (i+1).
 20 #
 21 # Rule 3:
 22 # Element at grid[m - 1][n - 1] moves to grid[0][0]
 23 # This is the bottom-right corner: it wraps to the top-left corner.
 24 #
 25 ## Example 1
 26 ##
 27 ## Input: @matrix = ([1, 2, 3],
 28 ##                   [4, 5, 6],
 29 ##                   [7, 8, 9],)
 30 ##        $k = 1
 31 ## Output: ([9, 1, 2],
 32 ##          [3, 4, 5],
 33 ##          [6, 7, 8],)
 34 ##
 35 ## Rule 1: grid[i][j] -> grid[i][j+1] for j < n-1.
 36 ##
 37 ## We take elements from the original grid at (i, j) and put them into new_grid[i][j+1].
 38 ##
 39 ## From original:
 40 ##
 41 ## (0,0): 1 -> new_grid[0][1] = 1
 42 ## (0,1): 2 -> new_grid[0][2] = 2
 43 ## (1,0): 4 -> new_grid[1][1] = 4
 44 ## (1,1): 5 -> new_grid[1][2] = 5
 45 ## (2,0): 7 -> new_grid[2][1] = 7
 46 ## (2,1): 8 -> new_grid[2][2] = 8
 47 ##
 48 ## New grid looks after Rule 1:
 49 ##
 50 ## ([?, 1, 2],
 51 ##  [?, 4, 5],
 52 ##  [?, 7, 8],)
 53 ##
 54 ## Rule 2: grid[i][n-1] -> grid[i+1][0] for i < m-1.
 55 ##
 56 ## Elements from original last column (except last row) go to next row's first column.
 57 ##
 58 ## From original:
 59 ##
 60 ## (0,2): 3 -> new_grid[1][0] = 3
 61 ## (1,2): 6 -> new_grid[2][0] = 6
 62 ##
 63 ## Now new grid after Rules 1 + 2:
 64 ##
 65 ## ([?, 1, 2],
 66 ##  [3, 4, 5],
 67 ##  [6, 7, 8],)
 68 ##
 69 ## Rule 3: grid[m-1][n-1] -> grid[0][0].
 70 ##
 71 ## Original (2,2): 9 -> new_grid[0][0] = 9.
 72 ##
 73 ## Now new_grid is complete:
 74 ##
 75 ## ([9, 1, 2],
 76 ##  [3, 4, 5],
 77 ##  [6, 7, 8],)
 78 #
 79 ## Example 2
 80 ##
 81 ## Input: @matrix = ([10, 20],
 82 ##                   [30, 40],)
 83 ##                 $k = 1
 84 ## Output: ([40, 10],
 85 ##          [20, 30],)
 86 ##
 87 ## Rule 1 (move right in same row if not last column):
 88 ##
 89 ## (0,0): 10 -> new[0][1] = 10
 90 ## (1,0): 30 -> new[1][1] = 30
 91 ##
 92 ## After Rule 1:
 93 ##
 94 ## ([?, 10],
 95 ##  [?, 30],)
 96 ##
 97 ## Rule 2 (last col -> next row’s first col, except last row):
 98 ##
 99 ## (0,1): 20 -> new[1][0] = 20
100 ##
101 ## After Rule 2:
102 ##
103 ## ([?,  10],
104 ##  [20, 30],)
105 ##
106 ## Rule 3 (bottom-right to top-left):
107 ##
108 ## (1,1): 40 -> new[0][0] = 40
109 ##
110 ## After Rule 3:
111 ##
112 ## ([40, 10],
113 ##  [20, 30],)
114 #
115 #
116 ## Example 3
117 ##
118 ## Input: @matrix = ([1, 2],
119 ##                   [3, 4],
120 ##                   [5, 6],)
121 ##        $k = 1
122 ## Output: ([6, 1],
123 ##          [2, 3],
124 ##          [4, 5],)
125 ##
126 ## Rule 1:
127 ## (0,0): 1 -> new[0][1] = 1
128 ## (1,0): 3 -> new[1][1] = 3
129 ## (2,0): 5 -> new[2][1] = 5
130 ##
131 ## After Rule 1:
132 ## ( [?, 1],
133 ##   [?, 3],
134 ##   [?, 5],)
135 ##
136 ## Rule 2:
137 ## (0,1): 2 -> new[1][0] = 2
138 ## (1,1): 4 -> new[2][0] = 4
139 ##
140 ## After Rule 2:
141 ## ([?, 1],
142 ##  [2, 3],
143 ##  [4, 5],)
144 ##
145 ##  Rule 3:
146 ##  (2,1): 6 -> new[0][0] = 6
147 ##
148 ##  After Rule 3:
149 ##  ([6, 1],
150 ##   [2, 3],
151 ##   [4, 5],)
152 #
153 #
154 ## Example 4
155 ##
156 ## Input: @matrix = ([1, 2, 3],
157 ##                   [4, 5, 6],)
158 ##        $k = 5
159 ## Output: ([2, 3, 4],
160 ##          [5, 6, 1],)
161 ##
162 ## Shift 1
163 ##
164 ## Rule 1
165 ## 1 -> (0,1)
166 ## 2 -> (0,2)
167 ## 4 -> (1,1)
168 ## 5 -> (1,2)
169 ##
170 ## Rule 2
171 ## 3 -> (1,0) (last column of row 0)
172 ##
173 ## Rule 3
174 ## 6 -> (0,0) (bottom-right corner)
175 ##
176 ## Result
177 ## [6, 1, 2]
178 ## [3, 4, 5]
179 ##
180 ## ----------------------------
181 ##
182 ## Shift 2
183 ##
184 ## Starting from the previous matrix:
185 ##
186 ## [6, 1, 2]
187 ## [3, 4, 5]
188 ##
189 ## Rule 1
190 ## 6 -> (0,1)
191 ## 1 -> (0,2)
192 ## 3 -> (1,1)
193 ## 4 -> (1,2)
194 ##
195 ## Rule 2
196 ## 2 -> (1,0)
197 ##
198 ## Rule 3
199 ## 5 -> (0,0)
200 ##
201 ## Result
202 ## [5, 6, 1]
203 ## [2, 3, 4]
204 ##
205 ## ----------------------------
206 ##
207 ## Shift 3
208 ##
209 ## [5, 6, 1]
210 ## [2, 3, 4]
211 ##
212 ## Rule 2: 1 -> (1,0)
213 ## Rule 3: 4 -> (0,0)
214 ##
215 ## Others follow Rule 1
216 ##
217 ## Result
218 ## [4, 5, 6]
219 ## [1, 2, 3]
220 ##
221 ## ----------------------------
222 ##
223 ## Shift 4
224 ##
225 ## [4, 5, 6]
226 ## [1, 2, 3]
227 ##
228 ## Result
229 ## [3, 4, 5]
230 ## [6, 1, 2]
231 ##
232 ## ----------------------------
233 ##
234 ## Shift 5
235 ## [3, 4, 5]
236 ## [6, 1, 2]
237 ##
238 ## Result
239 ## [2, 3, 4]
240 ## [5, 6, 1]
241 ##
242 ## Final Output (after k = 5 shifts)
243 ## ([2, 3, 4],
244 ##  [5, 6, 1])
245 #
246 #
247 ## Example 5
248 ##
249 ## Input: @matrix = ([1, 2, 3, 4])
250 ##        $k = 1
251 ## Output: ([4, 1, 2, 3])
252 ##
253 ## Rule 1:
254 ## (0,0): 1 -> new[0][1] = 1
255 ## (0,1): 2 -> new[0][2] = 2
256 ## (0,2): 3 -> new[0][3] = 3
257 ##
258 ## After Rule 1:
259 ## ([?, 1, 2, 3])
260 ##
261 ## Rule 2:
262 ## (0,3): 4 -> new[1][0] ??
263 ##
264 ## Wait — but i=0, n-1=3, next row i+1=1 doesn’t exist (m=1).
265 ## So this is actually a special case where Rule 2 should not apply.
266 ## because m=1, so (0,3) goes by Rule 3 actually.
267 ##
268 ## The rules say:
269 ## grid[i][j]     -> grid[i][j+1] for j < n-1.
270 ## grid[i][n-1]   -> grid[i+1][0] for i < m-1.
271 ## grid[m-1][n-1] -> grid[0][0].
272 ##
273 ## For m = 1:
274 ## Elements (0,0),(0,1),(0,2) follow Rule 1 -> (0,1),(0,2),(0,3).
275 ## Element (0,3) is (m-1, n-1), so follows Rule 3 -> (0,0).
276 ##
277 ## Actually, that means after Rule 1:
278 ## We put 1,2,3 in positions 1,2,3, leaving position 0 empty.
279 ## Then Rule 3 puts 4 in position 0.
280 ##
281 ## So final directly:
282 ## [4, 1, 2, 3]
283 #
284 ############################################################
285 ##
286 ## discussion
287 ##
288 ############################################################
289 #
290 # The rules are a complicated way to bascially say "move every
291 # element in the matrix to the right, just handing over the overflow
292 # into the next line unless it's the last line in which case the
293 # overflow goes into the first line". So this whole operation
294 # turns into something pretty straight forward: k times, we just
295 # do this simple operation of moving the last element of the last
296 # array in the matrix to the beginning of the first one, and then
297 # for all array starting in the first and ending in the
298 # second to last one, we just move the last element to the beginning
299 # of the next array.
300 
301 use v5.36;
302 
303 shift_grid([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 1);
304 shift_grid([[10, 20], [30, 40]], 1);
305 shift_grid([[1, 2], [3, 4], [5, 6]], 1);
306 shift_grid([[1, 2, 3], [4, 5, 6]], 5);
307 shift_grid([[1, 2, 3, 4]], 1);
308 
309 sub shift_grid($matrix, $k) {
310     say "Input: \@matrix = [";
311     foreach my $array (@$matrix) {
312         say "            [" . join(", ", @$array) . "],";
313     }
314     say "       ], \$k = $k";
315     foreach my $count (1..$k) {
316         my $last = scalar(@$matrix) - 1;
317         my $elem = pop(@{$matrix->[$last]});
318         unshift @{$matrix->[0]}, $elem;
319         foreach my $line (0..$last-1) {
320             $elem = pop(@{$matrix->[$line]});
321             unshift @{$matrix->[$line+1]}, $elem;
322         }
323     }
324     say "Output: [";
325     foreach my $array (@$matrix) {
326         say "         [" . join(", ", @$array) . "],";
327     }
328     say "        ]";
329 }