50013. Bingo

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

Problem Description

Write a program to play bingo. The bingo is played on 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). For example, this is a bingo board.

00100100
00000100
11000100
01111111
00110100
01000100
01000100
00000100

A bingo board can be easily represented as a 64 bit unsigned long long integer. For example, the bingo board above can easily represented as the following binary number.

highbit                                                   lowbit
   6         5         4         3         2         1         0
3210987654321098765432109876543210987654321098765432109876543210
0010010000000100110001000111111100110100010001000100010000000100

Now given a bingo board, please determine if you have a bingo. A board has a bingo if any of the following conditions is true.

  1. The bingo board has all 1's in a row.
  2. The bingo board has all 1's in a column.
  3. The bingo board has all 1's in either diagonal.

You need to implement the following functions to determine if a given board has a bingo. The return value should be 0 if the board does not have a bingo. It should return 1 if the first condition is satisfied, 2 the second condition, 3 the third condition. If multiple conditions are satisfied, you should return the smallest one.

1
int bingo(const unsigned long long int *board, int *rowColumn);

Also you need to set the rowColumn variable as the smallest row and column index if you have a bingo. If you have the third condition, you should set rowColumn to 0 for the diagonal from (0, 0) to (7, 7), and 1 for the diagonal from (0, 7) to (7, 0). Note that (0, 0) is the upper left corner of the board. If you have both, then set rowColumn to 0.

Subtasks

  • 10pt. The board has exactly 8 1's, and all of them are in row 7.
  • 10pt. The board has exactly 8 1's, and all of them are in the same row, which could be row 5, 6, or 7.
  • 20pt. You only need to check the first bingo condition.
  • 10pt. The board has exactly 8 1's, and all of them are in the same column, which could be column 5, 6, or 7. Note that solving this subtask does not guarantee that your solution can solve the first three subcases. However, this subtask will help you solve the task in identifying the second condition.
  • 35pt. You only need to check the first and the second bingo conditions.
  • 15pt. You need to check all bingo conditions.

Source codes

main.c

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include "bingo.h"
int main(void)
{
    unsigned long long int board;
    int res = 0, rowColumn = 0;
    scanf("%llu", &board);
    res = bingo(&board, &rowColumn);
    if(res == 0) printf("no\n");
    else printf("%d %d\n", res, rowColumn);
    return 0;
}

bingo.h

int bingo(const unsigned long long int *board, int *rowColumn);

Sample Inputs and Outputs

Sample Board 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Input 1

16711680

Sample Output 1

1 5

Sample Board 2

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0

Sample Input 2

254

Sample Output 2

no

Hint

For detecting the first and the second bingo conditions we need to detect whether one rwo or column are full of 1's. For example, we need to following four patterns to detect row 0 and 7, and column 0 and 7.

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 construc the fourth pattern, we consider its binary form.

0000000100000001000000010000000100000001000000010000000100000001

It is easy to see that it can be construicted 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