-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathQuestions-parta.txt
96 lines (64 loc) · 12.4 KB
/
Questions-parta.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
Question 1) What is printed in the console for:
— console.log(visPseudoku(genPseudoku([1,3,4,2],7)));
- console.log(visPseudoku(genPseudoku([4,1,3,2],10)));
Answer:
- console.log(visPseudoku(genPseudoku([1,3,4,2],7)));
-----------------
| | | 4 | |
-----------------
| 4 | | | 3 |
-----------------
| 3 | 4 | 2 | |
-----------------
| | 1 | 3 | 4 |
-----------------
console.log(visPseudoku(genPseudoku([1,3,4,2],7))) prints to the console a pseudoku puzzle in a string, generated by cyclic permutations of the [1,3,4,2] array (row) as rows of a 4x4 2D array (4x4 matrix) and with 7 (n) blank entries at random positions. It satisfies all Pseudoku conditions - every row, every column and every 2-bg-2 block include all integers 1-4.
The genPseudoku(row,n) function, where row is [1,3,4,2] and n is 7, calls genArray(row), permArray(arr) and delEntries(arr,n).
genArray(row) generates a 2D array from the "row" array [1,3,4,2] by copying (slicing) the "row" array 4 times - in this case [[1,3,4,2],[1,3,4,2],[3,4,2,1],[2,1,3,4]].
The generated 2D array is feeded into permArray(arr), which calls perm(arr,a,b,c) within a three-level nested for loop with i, j and k (generated by the for loop) as arguments corresponding to parameters a, b and c respectively. This generates combinations for cyclic permutation of rows 1 to 3 (i, j and k) by 1 to 4 elements each.
perm(arr,a,b,c), where arr is the 2D array (output of genArray(row)) and a, b and c are the number of elements (i, j and k) for cyclic permutation in rows 1, 2 and 3 respectively, calls cyclicPerm(arr,row,n) within a for loop.
cyclicPerm(arr,row,n), where arr is the 2D array, row is the row to be cyclically permutated and n is the number of elements for cyclic permutation, generates a single combination of cyclically permutated rows 1-3. Arguments of cyclicPerm(arr,row,n) within perm(arr,a,b,c) are arr - the 2D array, i - the row number generated by the for loop to include all rows from 1 to the end of the array, i.e. 1 to 3, and n[i - 1], where n is an array holding the number of elements for cyclic permutation in each row i sequentially. For each combination of i, j and k generated by the nested three-level for-loop in permArray(arr) and feeded into perm(arr,i,j,k), cyclicPerm(arr,row,n) runs three times. It traverses the array in row "row" in a for loop, removes the last element "n" times and adds the removed returned elements to the beginning of the row sequentially. The result is a cyclically permutated row by n elements, which is then returned by the function. In this case, the generated values for i, j and k in permArray(arr) are 2, 3 and 1 respectively. perm(arr,2,3,1) creates a new n array and stores values 2, 3, 1 as n[0], n[1] and n[3], i.e. [2,3,1]. It then runs cyclicPerm(arr,row,n) three times. The first time, cyclicPerm(arr,row,n) accepts as inputs the 2D array [[1,3,4,2],[1,3,4,2],[1,3,4,2],[1,3,4,2]] as arr, 1 as row and 2 as n, and returns the 2D array [[1,3,4,2],[4,2,1,3],[1,3,4,2],[1,3,4,2]], in which row 1 is cyclically permutated by 2 elements from [1,3,4,2] to [4,2,1,3]. The second time, it accepts the array [[1,3,4,2],[4,2,1,3],[1,3,4,2],[1,3,4,2]] as arr, 2 as row and 3 as n, and returns [[1,3,4,2],[4,2,1,3],[3,4,2,1],[1,3,4,2]], in which row 2 is cyclically permutated by 3 elements from [1,3,4,2] to [3,4,2,1]. And finally, the third time, cyclicPerm(arr,row,n) accepts as inputs the array [[1,3,4,2],[4,2,1,3],[3,4,2,1],[1,3,4,2]], 3 as row and 1 as n, and returns [[1,3,4,2],[4,2,1,3],[3,4,2,1],[2,1,3,4]] as output, in which row 3 is cyclically permutated by 1 element from [1,3,4,2] to [2,1,3,4].
perm(arr,i,j,k) then returns the cyclically permutated 2D array to permArray(arr) for testing. For each returned cyclically permutated combination by perm(arr,i,j,k), permArray(arr) calls colCheck(arrnew) and squCheck(arrnew) to test whether it satisfies conditions 2 and 3 for the Pseudoku, i.e. set membership of all integers 1-4 in each column (condition 2) and every block (2-by-2 sub-grid) (condition 3).
colCheck(arr), where arr is the returned by perm(arr,i,j,k) 2D array, calls singleColCheck(arr,column) for each column in a for loop, where arr is the returned by perm(arr,i,j,k) combination to be tested and column is the column number generated by the for loop - 0-3. colCheck(arr) counts rows passing singleColCheck(arr, column) and if the count matches the column number of the 2D array, colCheck(arr) returns true.
squCheck(arr) determines the square root of the length of the array, which corresponds to the number of entries per row and per column that split the 2D array into squares of equal length and height. The function calls singleBlockCheck(arr,x1,y1,x2,y2), where arr is the 2D array accepted by squCheck(arr) as input, x1 and y1 are the row and column numbers corresponding to the top left position of a single square and x2 and y2 are the row and column numbers corresponding to the bottom right position of the square. A two level nested for loop generates incremental values for calculating x1, y1, x2 and y2 values for each square to be feeded into singleBlockCheck(arr,x1,y1,x2,y2). It traverses all squares in the 2D array with i as a row of squares, i.e. 0 - 1 for a pseudoku (2 rows of squares), and j as a suqare index within the row of squares, i.e. 0 - 1 (2 squares per row of squares). x1 is generated by multiplying the index of the row of squares i by the number of entries per row of a square squCount (x1 = i*squCount). y1 is generated by multiplying the suqare index within the row of squares j by squCount (y1 = j*squCount). x2 is generated by adding squCount - 1 (-1 to count x1 as well) to x1 and y2 - by adding squCount - 1 (-1 to count y1 as well) to y1. In a pseudoku, x1 is then row 0 * 2 = 0 or 1 * 2 = 2, y1 is column 0 * 2 = 0 or 1 * 2 = 2, x2 is row 0 + 2 - 1 = 1 or 2 + 2 - 1 = 3 and y2 is column 0 + 2 - 1 = 1 or 2 + 2 - 1 = 3.
If singleBlockCheck(arr,x1,y1,x2,y2) returns true, count increments by 1. The total number of squares in the pseudoku is calculated by multiplying the number of squares per row by the number of squares per column and assigned to variable numSqu. numSqu is then compared to the number of squares passing singleBlockCheck(arr,x1,y1,x2,y2), stored in count. If the numbers match, squCheck(arr) returns true.
If a combination matches both conditions tested by colCheck(arr) and squCheck(arr), it is returned by permArray(arr) - in this case a matching combination is [[1,3,4,2],[4,2,1,3],[2,1,3,4],[3,4,2,1]].
The matching combination is then feeded into delEntries(arr,n), where arr is the returned by permArray(arr) 2D array and n is the number blank entries (" ") required.
delEntries(arr,n) calls entriesToDel(size,n), where size is the length of the 2D array returned by permArray(arr) and n is the number of elements to be randomly selected - in this case 7. entriesToDel(size,n) returns a 2D array of element positions in the format [[row, column],[row, column],...], repeating [row, column] n times - in this case [[0,0],[0,1],[0,3],[1,1],[1,2],[2,3],[3,0]]. The returned positions are then replaced with the string " " by delEntries(arr,n) in a for loop. In this case, delEntries(arr,n) returns the following 2D array: [[" "," ",4," "],[4," "," ",3],[3,4,2," "],[" ",1,3,4]], which is then returned by genPseudoku([1,3,4,2],7) for further processing by the visPseudoku(arr). visPseudoku(arr) accepts the returned 2D array as input and converts it to a string for output. It contains a nested for loop, which adds a row of dashes "-" ("-" + (4*"-" per element)) to the beginning of each row 0-3 as well as to the end of row 3, a new line "\n" to the beginning of rows 0-3 following the dashes, a vertical line "|" before elements 0-3 and after element 3 of each row, and a single space " " on both sides of each element. The string is then printed to the console by console.log(msg) as shown above, where msg is the string output of visPseudoku(genPseudoku([1,3,4,2],7)).
- console.log(visPseudoku(genPseudoku([4,1,3,2],10)));
-----------------
| | 1 | | |
-----------------
| 3 | | 4 | |
-----------------
| | 3 | | 4 |
-----------------
| | | | 3 |
-----------------
console.log(visPseudoku(genPseudoku([4,1,3,2],10))) prints to the console a pseudoku puzzle in a string, generated by cyclic permutations of the [4,1,3,2] array (row) as rows of a 4x4 2D array (4x4 matrix) with 10 (n) blank entries at random positions, which satisfies all Pseudoku conditions - every row, every column and every 2-bg-2 block include all integers 1-4.
genPseudoku(row,n), visPseudoku(arr) and console.log(obj1), function as described above for console.log(visPseudoku(genPseudoku([1,3,4,2],7))), but in this case genPseudoku(row,n) accepts as inputs [4,1,3,2] as row and 10 as n. genArray(row) generates the 2D array [[4,1,3,2],[4,1,3,2],[4,1,3,2],[4,1,3,2]] from [4,1,3,2]. The generated values for i, j and k in permArray(arr) are the same - 2, 3 and 1 respectively. perm(arr,2,3,1) creates a new n array and stores values 2, 3, 1 as n[0], n[1] and n[3], i.e. [2,3,1].
The first time, cyclicPerm(arr,row,n) accepts as inputs the 2D array [[4,1,3,2],[4,1,3,2],[4,1,3,2],[4,1,3,2]] as arr, 1 as row and 2 as n, and returns the 2D array [[4,1,3,2],[3,2,4,1],[4,1,3,2],[4,1,3,2]], in which row 1 is cyclically permutated by 2 elements from [4,1,3,2] to [3,2,4,1]. The second time, it accepts the array [[4,1,3,2],[3,2,4,1],[4,1,3,2],[4,1,3,2]] as arr, 2 as row and 3 as n, and returns [[4,1,3,2],[3,2,4,1],[1,3,2,4],[4,1,3,2]], in which row 2 is cyclically permutated by 3 elements from [4,1,3,2] to [1,3,2,4]. And finally, the third time, cyclicPerm(arr,row,n) accepts as inputs the array [[4,1,3,2],[3,2,4,1],[1,3,2,4],[4,1,3,2]], 3 as row and 1 as n, and returns [[4,1,3,2],[3,2,4,1],[1,3,2,4],[2,4,1,3]] as output, in which row 3 is cyclically permutated by 1 element from [4,1,3,2] to [2,4,1,3]. The combination [[4,1,3,2],[3,2,4,1],[1,3,2,4],[2,4,1,3]] passes both colCheck(arr) and squCheck(arr) and is returned by the permArray(arr). The returned 2D array is then feeded into delEntries(arr,n) as arr, where n is 10. delEntries(arr,n) calls entriesToDel(size,n) to generate 10 entries at randomly positions for deletion. The returned array by entriesToDel(size,n) is now [[0,0],[0,2],[0,3],[1,1],[1,3],[2,0],[2,2],[3,0],[3,1],[3,2]]. The returned positions are replaced with the string " " to generate the 2D array [[" ",1," "," "],[3," ",4," "],[" ",3," ",4],[" "," "," ",3]], which is then returned by genPseudoku(row,n), accepted as input by visPseudoku(arr), converted to a string and returned as output. It is then printed to the console by console.log(msg) as shown above, where msg is the output of visPseudoku(genPseudoku([4,1,3,2],10)).
Question 2) Give one example of a Pseudoku puzzle that cannot be produced by genPseudoku(row,n) and give a simple explanation why. (hint: think of a puzzle with one or two empty spaces)
Answer:
-----------------
| 1 | 2 | 3 | 4 |
-----------------
| 3 | | 1 | 2 |
-----------------
| 2 | 1 | 4 | 3 |
-----------------
| 4 | 3 | | 1 |
-----------------
The Pseudoku puzzle above cannot be generated by genPseudoku(row,n) with inputs the array [1,2,3,4] as "row" and 2 as "n" blank elements, because rows 2 and 3 cannot be generated by cyclicPerm(arr,row,n). Cyclic permutation of [1,2,3,4] by 1 element would return [4,1,2,3], by 2 elements - [3,4,1,2], by 3 elements - [2,3,4,1] and by 4 elements - [1,2,3,4], none of which matches [2,1,4,3] or [4,3,2,1].
Question 3) What one extra algorithmic component could you add to the approach of genPseudoku(row,n) to produce a puzzle that genPseudoku(row,n) cannot currently produce?
Answer:
To produce the puzzle from question 2, rows 0-3 from the 2D array have to be reveresed in a for loop prior to cyclic permutation. This can be achieved with the addition of an inner for loop to permArray(arr) to traverse the arr array starting from row 2, where row index is l, and assign arr[l], where l is index 2-3, to its reverse (arr[l].reverse()) prior to cyclic permutation with perm(arr,i,j,k). With the addition of the suggested extra algorithmic component genPseudoku([1,2,3,4],0) outputs [[1,2,3,4],[3,4,1,2],[2,1,4,3],[4,3,2,1]], genPseudoku([1,2,3,4],2) outputs [[1,2,3,4],[3," ",1,2],[2,1,4,3],[4,3," ",1]] and visPseudoku(genPseudoku([1,2,3,4],2)) outputs the string printed to the console in question 2 (if the output of entriesToDel(size,n) is [[1,1],[3,2]]):
-----------------
| 1 | 2 | 3 | 4 |
-----------------
| 3 | | 1 | 2 |
-----------------
| 2 | 1 | 4 | 3 |
-----------------
| 4 | 3 | | 1 |
-----------------