CODEWITHSUNDEEP
pythoncbit-manipulation
f.rodrigues
f.rodrigues

Reputation: 3587

Bit manipulation giving wrong output

I'm trying to make a small bit of a sudoku solver which I have in Python using C.

I'm using the same tecnhinc I did in Python, but it yields a different result. Perhaps Python is cutting some edges I don't know.

First I take a 81 chars long string and convert it to a int[9][9], like so:

char puzzle[] = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";
int PUZZLE[9][9];

    for (int i = 0; i < 81; i++ ){
        int cur_char = puzzle[i];
        PUZZLE[row][column] = cur_char;
        column ++;
        if ((i+1)%9==0){
            column = 0;
            row ++;
        }

Then I do this bit manipulations to a int ROW[9]:

ROW[row] |= 1<<cur_char;

After going trought all the rows/columns, I can check if a number is in the row/column by doing:

if(ROW[i] & 1 << j) printf("ROW: %d has number: %d\n",i,j);

But even with a unfilled a unfilled grid, 9x9 with 0 in it. It give me this:

ROW: 0 has number: 1
ROW: 0 has number: 2
ROW: 0 has number: 3
ROW: 0 has number: 4
ROW: 0 has number: 6
ROW: 3 has number: 1
ROW: 3 has number: 3
ROW: 3 has number: 4
ROW: 3 has number: 5
ROW: 5 has number: 5
ROW: 5 has number: 6
ROW: 6 has number: 2
ROW: 6 has number: 6
ROW: 7 has number: 1
ROW: 7 has number: 7
ROW: 7 has number: 8
ROW: 7 has number: 9

Here's my C code:

#include <stdio.h>

int main(){
    char puzzle[] = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";

    int PUZZLE[9][9];

    char ROW[9];

    int row = 0;
    int column = 0;
    int i;

    for ( i = 0; i < 81; i++ ){
        int cur_char = puzzle[i];
        PUZZLE[row][column] = cur_char;
        ROW[row] |= 1 << cur_char;
        column ++;
        if ((i+1)%9==0){
            column = 0;
            row ++;
        }
    }

    int j;
    for ( i = 0; i < 9; i ++) {
        for ( j = 1; j < 10; j ++) {
            if(ROW[i] & 1 << j) printf("ROW: %d has number: %d\n",i,j);
        }
    }

    return 0;
}

Here's my Python code:

puzzle = "800000000003600000070090200050007000000045700000100030001000068008500010090000400"
PUZZLE = [[0]*9]*9
ROW = [0]*9
row = 0
column = 0
for i in xrange(81): # not the pythonic way, but the equivalent in C
    cur_char = int(puzzle[i])
    PUZZLE[row][column] = cur_char
    ROW[row] |= 1 << cur_char
    column += 1
    if (i+1)%9==0:
        row += 1
        column = 0

for i in xrange(9):
    for j in xrange(1,10):
        if ROW[i] & 1 << j:
            print "ROW: %d has number: %d"%(i,j)

My question is: Why the C code not giving the same result as the Python; although it's the same algorithm?

EDIT:

As pointed out, I'm now initialing char ROW[9] = {0,0,0,0,0,0,0,0,0}; and also removing the extra 48 from the cur_char int cur_char = puzzle[i] - 48;

C yields:

ROW: 0 has number: 7 #wrong
ROW: 0 has number: 8 #right
ROW: 0 has number: 9 #wrong
ROW: 1 has number: 2 #wrong
ROW: 1 has number: 5 #wrong
ROW: 2 has number: 1 #wrong
ROW: 2 has number: 6 #wrong
ROW: 3 has number: 4 #wrong
ROW: 3 has number: 6 #wrong
ROW: 4 has number: 3 #wrong
ROW: 4 has number: 4 #right
ROW: 4 has number: 6 #wrong
ROW: 5 has number: 2 #wrong
ROW: 6 has number: 5 #wrong
ROW: 6 has number: 7 #wrong
ROW: 6 has number: 8 #right
ROW: 6 has number: 9 #wrong
ROW: 7 has number: 4 #wrong
ROW: 7 has number: 7 #wrong
ROW: 7 has number: 8 #right
ROW: 7 has number: 9 #wrong
ROW: 8 has number: 3 #wrong

Python yields:

ROW: 0 has number: 8
ROW: 1 has number: 3
ROW: 1 has number: 6
ROW: 2 has number: 2
ROW: 2 has number: 7
ROW: 2 has number: 9
ROW: 3 has number: 5
ROW: 3 has number: 7
ROW: 4 has number: 4
ROW: 4 has number: 5
ROW: 4 has number: 7
ROW: 5 has number: 1
ROW: 5 has number: 3
ROW: 6 has number: 1
ROW: 6 has number: 6
ROW: 6 has number: 8
ROW: 7 has number: 1
ROW: 7 has number: 5
ROW: 7 has number: 8
ROW: 8 has number: 4
ROW: 8 has number: 9

As you can see, it yields few of the numbers right, but misses most, and adds some others too.

Upvotes: 0

Views: 106

Answers (2)

f.rodrigues
f.rodrigues

Reputation: 3587

Oh, manage to make it work: Thanks to Weather Vane and Dunes. It was two mistakes.

1) I wasn't initialing the ROW and 2) I was using a char array, instead of int.

This fixed both errors:

int ROW[9] = {0,0,0,0,0,0,0,0,0};

Result:

ROW 0 has numbers: 8
ROW 1 has numbers: 3, 6
ROW 2 has numbers: 2, 7, 9
ROW 3 has numbers: 5, 7
ROW 4 has numbers: 4, 5, 7
ROW 5 has numbers: 1, 3
ROW 6 has numbers: 1, 6, 8
ROW 7 has numbers: 1, 5, 8
ROW 8 has numbers: 4, 9

Upvotes: 0

Weather Vane
Weather Vane

Reputation: 34575

Looking at the line

ROW[row] |= 1 << cur_char;

I see two faults. First, ROW[] has not been initialised, so you are orring with uninitialised value. Secondly, the first char of the C string puzzle[] is '8' which is ascii 56. So shifting 1 << 56 makes no sense and is UB anyway, although I don't know how Python handles this.

Upvotes: 2

Related Questions