50012. Block Mover with Bit Operations

Problem Description

Write a block moving program. A block is a k by k square in a 8 by 8 grid. The grid has 8 rows (from 0 to 7, top to bottom) and eight columns (from 0 to 7, left to right). A 2 by 2 block with its upper left corner located at row 3 and column 2 is like this.

We can represent a block with an unsigned long long integer, which has 64 bits, therefore the block above can be represented as a binary number like this. As a result, we can use fast bit operations, e.g., bitwise and/or and shifting, to implement the following operations (including the initialization of the grid). If you do not use bit operatios, it is very likely that your program will receive TLEs.

lowbit                                                   highbit
0         1         2         3         4         5         6
0123456789012345678901234567890123456789012345678901234567890123
0000000000000000000000000011000000110000000000000000000000000000

NOTE: Here the left-top digit on the 8 by 8 grid is the lowest bit of the integer.

Now given a block as an unsigned 64 bit integer, you need to implement the following functions.

void printBlock(unsigned long long int *block);
Print a block as indicated above.
void initialize(unsigned long long int *block, int row, int column, int size);
This function will initialize the block so that the left upper corner is located at (row, column), and with size. For example, we can use initialize(&block, 3, 2, 2) to get the block in the previous example.
int moveLeft(unsigned long long int *block);
This function will move the block left by one column. For example, if we call moveLeft(&block) then the block will look like this.
```
00000000
00000000
00000000
01100000
01100000
00000000
00000000
00000000
```
int moveRight(unsigned long long int *block); This function will move the block right by one column. For example, if we call moveRight(&block) then the block will look like this.
```
00000000
00000000
00000000
00011000
00011000
00000000
00000000
00000000
```
int moveUp(unsigned long long int *block); This function will move the block up by one row. For example, if we call moveUp(&block) then the block will look like this.
```
00000000
00000000
00110000
00110000
00000000
00000000
00000000
00000000
```
int moveDown(unsigned long long int *block);
This function will move the block down by one row. For example, if we call moveDown(&block) then the block will look like this.
```
00000000
00000000
00000000
00000000
00110000
00110000
00000000
00000000
```

Some moves may be invalid. For example, if the block is on row 0 then it cannot be moved up, and if is at column 0 then it cannot be moved left. A move function should return 1 if the move is valid, and 0 if the move is invalid. If the move is invalid, the value of the block should NOT be changed.

Source codes

main.c

download main.c

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 #include <stdio.h>
#include "blockmover.h"
 
int main() {
    unsigned long long int num;
    char operation;
    int ret;
 
    scanf("%llu", &num);
 
    while (1) {
        ret = 1;
 
        scanf("%c", &operation);
 
        if (operation == 'p') {
            printBlock(&num);
            break;
        } else if (operation == 'u')
            ret = moveUp(&num);
        else if (operation == 'd')
            ret = moveDown(&num);
        else if (operation == 'l')
            ret = moveLeft(&num);
        else if (operation == 'r')
            ret = moveRight(&num);
        else if (operation == 'i') {
            int row, column, size;
            scanf("%d %d %d", &row, &column, &size);
            initialize(&num, row, column, size);
        }
 
        if (ret == 0)
            printf("Invalid move!\n");
    }
 
    return 0;
}

blockmover.h

download blockmover.h

1
2
3
4
5
6 void printBlock(unsigned long long int *block);
void initialize(unsigned long long int *block, int row, int column, int size);
int moveLeft(unsigned long long int *block);
int moveRight(unsigned long long int *block);
int moveUp(unsigned long long int *block);
int moveDown(unsigned long long int *block);

blockmover.c

Here is the template code.

download blockmover.c

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 #include <stdio.h>                                                                              
 
// You can write your own functions here. 
 
void printBlock(unsigned long long int *block) {
    // your implementation here
}
 
void initialize(unsigned long long int *block, int row, int column, int size) {
    // your implementation here
}
 
int moveLeft(unsigned long long int *block) {
    // your implementation here    
    return 0; // You may change this return value.
}
 
int moveRight(unsigned long long int *block) {
    // your implementation here    
    return 0; // You may change this return value.
}
 
int moveUp(unsigned long long int *block) {
    // your implementation here    
    return 0; // You may change this return value.
}
 
int moveDown(unsigned long long int *block) {
    // your implementation here    
    return 0; // You may change this return value.
}

Technical Specification and Constraints

20pt. Implement printBlock.
15pt. Implement printBlock, moveLeft, and moveRight. All moves are valid.
20pt. Implement printBlock, and all four move functions. All moves are valid.
30pt. Implement all four move and initialize functions. All moves are valid.
15pt. Implement all four move and initialize functions. Some moves may be invalid.

Except illegal moves, all other inputs are valid.

Sample Inputs and Outputs

In input files, the first line is the initial value of block. The following lines are actions. 'l' means moving left, 'u' means moving up, and so on. 'i' means initialization. The three arguments of 'i' command mean row, column and size. 'p' prints the current block. Once 'p' is called, the program ends.

Sample Input 1

123628217696256
l
u
p

Sample Output 1

Sample Input 2

0
i 4 0 4
l
r
p

Sample Output 2

Invalid move!
00000000
00000000
00000000
00000000
01111000
01111000
01111000
01111000

Hint

To initialize a 2 by 2 block we need to build the following pattern.

If we write it in binary it will become the following.

0000000000000000000000000000000000000000000000000000001100000011

To get this pattern we simply take them or of the following.

0000000000000000000000000000000000000000000000000000000000000011
0000000000000000000000000000000000000000000000000000001100000000

Then we can use moveUp and moveLeft to move the block into the correct position.

To detect the cases that we cannot move a block we need to detect whether the block is at row 0 or 7, or column 0, and 7, so we need the following four patterns.

It is easy to construct the first and second pattern, which is simply 255. In order to construct the fourth pattern, we consider its binary form.

0000000100000001000000010000000100000001000000010000000100000001

It is easy to see that it can be constructed by taking an "or" on the following.

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000100000000
0000000000000000000000000000000000000000000000010000000000000000
0000000000000000000000000000000000000001000000000000000000000000
0000000000000000000000000000000100000000000000000000000000000000
0000000000000000000000010000000000000000000000000000000000000000
0000000000000001000000000000000000000000000000000000000000000000
0000000100000000000000000000000000000000000000000000000000000000