50012. Block Mover with Bit Operations

I'm a slow walker, but I never walk backwards.

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.

00000000
00000000
00000000
00110000
00110000
00000000
00000000
00000000

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

00000000
00000000
00011100
00011100
00011100
00000000
00000000
00000000

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.

00000000
00000000
00000000
00000000
00000000
00000000
00000011
00000011

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.

11111111
00000000
00000000
00000000
00000000
00000000
00000000
00000000
 
00000000
00000000
00000000
00000000
00000000
00000000
00000000
11111111
 
10000000
10000000
10000000
10000000
10000000
10000000
10000000
10000000
 
00000001
00000001
00000001
00000001
00000001
00000001
00000001
00000001

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

It is easy then to construct the third pattern from this.

Discussion