9 bits crammed in to 8 bits space...

[felixnielsen]

imagine a hollow cube.
every wall can have one of two states: open or closed. This would take
6 bits to represent.
Now, i allso neew to know whitch way i entered the room, this could be
representet with a integer from 0 to 5 = 3 bits.
As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
ofcourse have to do some creative thinking, it is however, not as hard
as it sounds, because the wall/door/direction in witch i entered the
room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
great deal lower than 255.
However, with this aproach one problem remains.
The walls/doors no longer have a fixes position in the bit field, fx.
if the direction from witch the room was entered is 5 and therefor
wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
doesnt need to be represented), if the direction ID is 4, the 5th
wall/door, will not be represented, it doesnt have to be. If the the
direction ID is 3 the 5th wall/door will be representet by the 7th bit,
ect.

This is all a bit confusing and im not quite sure i have explained it
good enough, however i have written a "class" that in my oppinion
should work, but dont(it compiles fine though, but the result is
wrong). maybe that could give some inspiration.

@code start
class Stack {
private:
std::vector<unsigned char> P_Stack;
unsigned char T_Stack;
public:
Stack() {
T_Stack = 0;
}
~Stack() {}
bool Put_Dir(int a) { // should work
T_Stack = (a >= 0 && a < 6) ? a : T_Stack;
}
void Put_Door(int a) { // should work
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
T_Stack |= (1 << a);
}
}
unsigned int Get_Dir() { //doesnt work
return (T_Stack & 7);
}
bool Get_Door(int a) { // seems to work, but missing door = 1
implementation is missing.
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
return (T_Stack & (1 << a));
}
}
bool Dead_End() { // probably doesnt work
if (T_Stack & (31 << 3)) {
return 1;
}
else {
return 0;
}
}
void Next() { // should work
P_Stack.push_back(T_Stack);
T_Stack = 0;
}
void Pop() { // should work
P_Stack.pop_back();
T_Stack = P_Stack.back();
}
};
class Grid {};
int main() {
Stack stack;
stack.Put_Dir(0);
stack.Put_Door(1);
stack.Put_Door(2);
stack.Put_Door(3);
stack.Put_Door(4);
stack.Put_Door(5);
std::cin.get();
// when i ask for direction the result should be 0.
// when i ask for door 0 the result should be 1, but this information
isnt stored in the bitfield.
// when i ask for door 1-5 the result in thiscase should allso be 1,
but only because i have set them, otherwise the should be 0;
}
@code end

Regards
Felix Zacariaz Bloutarski

 

[fandoras]

void Put_Door(int a) { // should work
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
T_Stack |= (1 << a);
}
}
unsigned int Get_Dir() { //doesnt work
return (T_Stack & 7);
}

bool Get_Door(int a) { // seems to work, but missing door = 1
implementation is missing.
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
return (T_Stack & (1 << a));
}
}

the "<<" ignores the 3 bits used for the "comming from direction"

 

[Tomás]

posted:

imagine a hollow cube.
every wall can have one of two states: open or closed. This would take
6 bits to represent.

Six sides, each of two possible states, so 6 bits.

I agree.

Now, i allso neew to know whitch way i entered the room, this could be
representet with a integer from 0 to 5 = 3 bits.

There are six possible combinations for which side you used to enter the
room.

A 3-Bit number has eight possible combinations.

You're wasting the last two of the combinations.

As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
ofcourse have to do some creative thinking, it is however, not as hard
as it sounds, because the wall/door/direction in witch i entered the
room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
great deal lower than 255.

Good thinking.

So let's say you entered the room through the side 2:

Bit 0: side 0 = closed
Bit 1: side 1 = open
Bit 2: side 3 = closed //We've omitted side 2
Bit 3: side 4 = open
Bit 4: side 5 = closed

Now we've three further bits to specify by which side we entered the room.
(ie. 0 to 5)


Makes sense.

room doesnt need a state
However, with this aproach one problem remains.
The walls/doors no longer have a fixes position in the bit field, fx.
if the direction from witch the room was entered is 5 and therefor
wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
doesnt need to be represented), if the direction ID is 4, the 5th
wall/door, will not be represented, it doesnt have to be. If the the
direction ID is 3 the 5th wall/door will be representet by the 7th bit,
ect.

Correct. The order has been disturbed.

Maybe that could give some inspiration.

Here's some code I just wrote. It's just to get you going; it may contain
errors and bugs as I wrote it quickly and sloppily.

class PresenceInRoom
{
private:

char data; //Stores our data

struct SixBools
{
bool side_status[6];
};


bool GetBit(unsigned i)
{
return i && ( 1U << (i - 1) );
}

SixBools GetSixBools()
{
//First we determine which side we came in through

unsigned side_came_in = 0;

if GetBit( 5 ) side_came_in += 4;
if GetBit( 6 ) side_came_in += 2;
if GetBit( 7 ) side_came_in += 1;

//Now we have our side

SixBools six_bools;

six_bools[side_came_in] = false;

{
unsigned bit = 0;

for (unsigned side = 0; side < 6; ++side, ++bit)
{
if (side == side_came_in)
{
--bit;
continue;
}

six_bools[side] = GetBit( bit );
}
}

}
};

-Tomás

 

[felixnielsen]

Tomás skrev:

posted:

imagine a hollow cube.
every wall can have one of two states: open or closed. This would take
6 bits to represent.

Six sides, each of two possible states, so 6 bits.

I agree.

Now, i allso neew to know whitch way i entered the room, this could be
representet with a integer from 0 to 5 = 3 bits.

There are six possible combinations for which side you used to enter the
room.

A 3-Bit number has eight possible combinations.

You're wasting the last two of the combinations.

As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
ofcourse have to do some creative thinking, it is however, not as hard
as it sounds, because the wall/door/direction in witch i entered the
room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
great deal lower than 255.

Good thinking.

So let's say you entered the room through the side 2:

Bit 0: side 0 = closed
Bit 1: side 1 = open
Bit 2: side 3 = closed //We've omitted side 2
Bit 3: side 4 = open
Bit 4: side 5 = closed

Now we've three further bits to specify by which side we entered the room.
(ie. 0 to 5)


Makes sense.

room doesnt need a state
However, with this aproach one problem remains.
The walls/doors no longer have a fixes position in the bit field, fx.
if the direction from witch the room was entered is 5 and therefor
wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
doesnt need to be represented), if the direction ID is 4, the 5th
wall/door, will not be represented, it doesnt have to be. If the the
direction ID is 3 the 5th wall/door will be representet by the 7th bit,
ect.

Correct. The order has been disturbed.

Maybe that could give some inspiration.

Here's some code I just wrote. It's just to get you going; it may contain
errors and bugs as I wrote it quickly and sloppily.

class PresenceInRoom
{
private:

char data; //Stores our data

struct SixBools
{
bool side_status[6];
};


bool GetBit(unsigned i)
{
return i && ( 1U << (i - 1) );
}

SixBools GetSixBools()
{
//First we determine which side we came in through

unsigned side_came_in = 0;

if GetBit( 5 ) side_came_in += 4;
if GetBit( 6 ) side_came_in += 2;
if GetBit( 7 ) side_came_in += 1;

//Now we have our side

SixBools six_bools;

six_bools[side_came_in] = false;

{
unsigned bit = 0;

for (unsigned side = 0; side < 6; ++side, ++bit)
{
if (side == side_came_in)
{
--bit;
continue;
}

six_bools[side] = GetBit( bit );
}
}

}
};

-Tomás

looks nice, thank you wery much.
Im sry i havent got time to take a look at it right now,m but im on my
way to a party.
Regard

 

[felixnielsen]

Tomás skrev:

posted:


Six sides, each of two possible states, so 6 bits.

I agree.


There are six possible combinations for which side you used to enter the
room.

A 3-Bit number has eight possible combinations.

You're wasting the last two of the combinations.




Good thinking.

So let's say you entered the room through the side 2:

Bit 0: side 0 = closed
Bit 1: side 1 = open
Bit 2: side 3 = closed //We've omitted side 2
Bit 3: side 4 = open
Bit 4: side 5 = closed

Now we've three further bits to specify by which side we entered the room.
(ie. 0 to 5)


Makes sense.


Correct. The order has been disturbed.



Here's some code I just wrote. It's just to get you going; it may contain
errors and bugs as I wrote it quickly and sloppily.

Some bugs indeed needed solving, however, its was nothing seriously.

class PresenceInRoom
{
private:

char data; //Stores our data

struct SixBools
{
bool side_status[6];
};


bool GetBit(unsigned i)
{
return i && ( 1U << (i - 1) );
}

SixBools GetSixBools()
{
//First we determine which side we came in through

unsigned side_came_in = 0;

if GetBit( 5 ) side_came_in += 4;
if GetBit( 6 ) side_came_in += 2;
if GetBit( 7 ) side_came_in += 1;

//Now we have our side

SixBools six_bools;

six_bools[side_came_in] = false;

{
unsigned bit = 0;

for (unsigned side = 0; side < 6; ++side, ++bit)
{
if (side == side_came_in)
{
--bit;
continue;
}

six_bools[side] = GetBit( bit );
}
}

}
};

Still, i dont quite understand how this is suposed to work

Regards