50184. 3-SAT

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

Task Description

We are going to simulate the 3-SAT problem. There are some lights and a sequence of locks. Each lock has three sensors triggered by the lights. If a lock has at least one sensor being triggered, it will be unlocked. Each sensor has a non-zero integer $k$ which means that the sensor is triggered by the $\vert k\vert $-th light. If $k$ is positive, the sensor will be triggered when the light is on; if $k$ is negative, the sensor will be triggered when the light is off. Please refer to the following figure.

figurefigure

First, please design an object for the locks. You can store any information you need in the object. We will use init function to initialize your structure. The int lockSeq[][3] is the sequence of locks with three sensors on each lock, and int n is the number of locks. init function will return a pointer of your object. Remember to use malloc() in your init function. Then, please write a function numUnlocked. Given the status of lights and the object of locks, you have to count the number of unlocked locks. Lights are stored in bool lights[] where 1 is on and 0 is off for the light. int m is the length of lights[]. Note that the status of the light 1 is stored in lights[0]. These are templates of the structure and function APIs in lock.h. You should implement the functions in the other file lock.c.

typedef struct locks {
  /* design yourself */
} Locks;
 
Locks* init(int lockSeq[][3], int n);
 
int numUnlocked(Locks *locks, bool lights[], int m);

You can use this main function (mainForNumUnlocked.c) to test your functions and structure:

#include <stdio.h>
#include <stdbool.h>
#include "lock.h"
 
#define SENSORNUM 3
 
int main() {
  int m, n;
  scanf("%d%d", &m, &n);
  bool lights[m];
  int lockSeq[n][SENSORNUM];
  for(int i = 0; i < m; i++) {
    int tmp;
    scanf("%d", &tmp);
    lights[i] = (tmp == 1);
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < SENSORNUM; j++) {
      scanf("%d", &lockSeq[i][j]);
    }
  }
  Locks *locks = init(lockSeq, n);
  printf("%d\n", numUnlocked(locks, lights, m));
  return 0;
}

Second, given a sequence of locks, you have to find out the status of lights which has the maximum number of unlocked locks. If there are different statuses having the same maximum number, you should choose the one with the lowest power consumption. The power consumption from the first to the $m$-th light is $1, 2, 4,..., 2^{m-1}$. You should implement this in your own main function, and you can use the functions provided by TAs.

Compile

gcc -std=c99 lock.c mainForNumUnlocked.c
gcc -std=c99 lock.c main.c

Note

For function testing, we will test your function using main function above. If you only want to check whether your lock.h and lock.c is correct, you still have to upload the main.c. You can use the following as your main.c.

int main() {}

For finding the status, we will only use your main.c. lock.c and lock.h we used were written by TA. That is, you can still use the functions and structure without implementing the them in lock.c and lock.h. To test your main.c only, you can upload the lock.h template above, and upload the following lock.c.

#include <stdbool.h>
#include "lock.h"
Locks* init(int lockSeq[][3], int n) {}
int numUnlocked(Locks *locks, bool lights[], int m) {}

Subtasks

  • 30 points: init and numUnlocked function testing
  • 70 points: finding the status of light to unlock most locks

Input Format

For function testing, the first line has $m$ and $n$. $m$ is the length of lights and $n$ is the number of locks. The following line has $m$ 0’s or 1’s representing the status of lights. Each of the following $n$ lines has three integers representing three sensors of a lock.

For finding the status of lights, the first line has $m$ and $n$. $m$ is the length of lights and $n$ is number of locks. Each of the following $n$ lines has three integers representing three sensors of a lock.

  • $1\leq m\leq 20$
  • $1\leq n\leq 100$

Output Format

For function testing, the output is an integer of the return value of function numUnlocked.

For finding the status of lights, the first line has $m$ characters (0 or 1) representing the status of lights. The second line is the number of unlocked locks of that status. The third line is the power consumption.

Sample Input 1 (function testing)

5 3
1 0 0 1 0
-1 2 4
-2 -5 1
-4 3 5

Sample Output 1

2

Sample Input 2 (function testing)

7 7
0 1 0 0 0 1 1
6 7 -5
4 7 -3
-6 -2 4
3 -1 5
2 -6 2
6 -1 -3
3 -2 5

Sample Output 2

5

Sample Input 3 (finding light status)

5 3
-1 2 4
-2 -5 1
-4 3 5

Sample Output 3

00000
3
0

Sample Input 4 (finding light status)

6 7
2 5 4
3 1 -1
3 2 6
4 5 3
1 6 -5
5 2 1
-2 1 6

Sample Output 4

111000
7
7

Discussion