Can you find an efficient solution to this bit manipulation problem?

eternalthinker
Member • Dec 20, 2011

Can you find an efficient solution to this bit manipulation problem?
The problem at hand is to map a number pair to a binary map:

For a length of 5,

Map (1,5) to 01110
Map (1,4) to 01100
Map (2,4) to 00100

and so on.

You can use any binary operators and the binary representations of given number limits (obviously).

I am trying to find an optimum solution with minimal looping and more intelligent use of binary operations. Can you try?!

Update: more explanation

For a length of 5, consider a row like this:

- * - -*

(_ is empty space and * is occupied space)
Now, for the above row, the indices of occupied spaces are:

(2,5)

Suppose we're representing
- the empty spaces between *'s by 1's
- all the rest by 0's (Note that 0's in the right side matter!)
Thus: _ * _ _ * maps to (2,5) maps to 00110

_ * * _ _ maps to (2,3) maps to 00000

I think that's clear now!
Replies

Howdy guest!

Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.

Replies

PraveenKumar Purushothaman

Member • Dec 21, 2011

What is the language you are trying to implement? Coz, in PHP it is very easy! 😀

Are you sure? This action cannot be undone.
Cancel
eternalthinker

Member • Dec 22, 2011

@Praveen
Bit operations shouldn't be very different throughout languages, I suppose.
Or does PHP have any special operators which makes the solution easier?

In any case, do share your solution 😀

Are you sure? This action cannot be undone.
Cancel
PraveenKumar Purushothaman

Member • Dec 22, 2011

eternalthinker
@Praveen
Bit operations shouldn't be very different throughout languages, I suppose.
Or does PHP have any special operators which makes the solution easier?

In any case, do share your solution 😀
PHP has associative array technique, which makes declaration of 2D Arrays / Maps easier... 😀

Are you sure? This action cannot be undone.
Cancel

PraveenKumar Purushothaman

Member • Dec 22, 2011

For eg., consider this program:


<?php
    $n = 5;
    $a = array();
    for($i = 0; $i < $n; $i++)
        for($j = 0; $j < $n; $j++)
            $a[$i][$j] = decbin($i + $j);
    var_dump($a);
?>

The output is

array(5) {
  [0]=>
  array(5) {
    [0]=>
    string(1) "0"
    [1]=>
    string(1) "1"
    [2]=>
    string(2) "10"
    [3]=>
    string(2) "11"
    [4]=>
    string(3) "100"
  }
  [1]=>
  array(5) {
    [0]=>
    string(1) "1"
    [1]=>
    string(2) "10"
    [2]=>
    string(2) "11"
    [3]=>
    string(3) "100"
    [4]=>
    string(3) "101"
  }
  [2]=>
  array(5) {
    [0]=>
    string(2) "10"
    [1]=>
    string(2) "11"
    [2]=>
    string(3) "100"
    [3]=>
    string(3) "101"
    [4]=>
    string(3) "110"
  }
  [3]=>
  array(5) {
    [0]=>
    string(2) "11"
    [1]=>
    string(3) "100"
    [2]=>
    string(3) "101"
    [3]=>
    string(3) "110"
    [4]=>
    string(3) "111"
  }
  [4]=>
  array(5) {
    [0]=>
    string(3) "100"
    [1]=>
    string(3) "101"
    [2]=>
    string(3) "110"
    [3]=>
    string(3) "111"
    [4]=>
    string(4) "1000"
  }
}

And, for this code:


<?php
    $n = 5;
    $a = array();
    for($i = 0; $i < $n; $i++)
        for($j = 0; $j < $n; $j++)
            $a[$i][$j] = decbin($i + $j);
    for($i = 0; $i < $n; $i++)
    {
        for($j = 0; $j < $n; $j++)
            echo $a[$i][$j] . "\t";
        echo "\n";
    }
?>

The output is

0       1       10      11      100
1       10      11      100     101
10      11      100     101     110
11      100     101     110     111
100     101     110     111     1000

Did I understand your problem rightly?

Are you sure? This action cannot be undone.

Cancel

PraveenKumar Purushothaman

Member • Dec 22, 2011

@ET: Finally you can arrive the same solution of yours in this way:


<?php
    $n = 5;
    $a = array();
    for($i = 0; $i < $n; $i++)
        for($j = 0; $j < $n; $j++)
            $a[$i][$j] = decbin($i + $j);
    for($i = 0; $i < $n; $i++)
        for($j = 0; $j < $n; $j++)
            echo "Map ($i, $j) is {$a[$i][$j]}\n";
?>

And the output for the same is:

Map (0, 0) is 0
Map (0, 1) is 1
Map (0, 2) is 10
Map (0, 3) is 11
Map (0, 4) is 100
Map (1, 0) is 1
Map (1, 1) is 10
Map (1, 2) is 11
Map (1, 3) is 100
Map (1, 4) is 101
Map (2, 0) is 10
Map (2, 1) is 11
Map (2, 2) is 100
Map (2, 3) is 101
Map (2, 4) is 110
Map (3, 0) is 11
Map (3, 1) is 100
Map (3, 2) is 101
Map (3, 3) is 110
Map (3, 4) is 111
Map (4, 0) is 100
Map (4, 1) is 101
Map (4, 2) is 110
Map (4, 3) is 111
Map (4, 4) is 1000

This one is identical to what you asked! 😀

Are you sure? This action cannot be undone.

Cancel

eternalthinker

Member • Dec 23, 2011

@Praveen
I like the idea of storing all the patterns in an array once, and only referring to it subsequently.

Anyhow, did you check the bit patterns in the question? There is a particular logic in how they are arranged.
I think I should've been more clear in the question!

Please see the updated question 😀

Are you sure? This action cannot be undone.
Cancel
PraveenKumar Purushothaman

Member • Dec 23, 2011

eternalthinker
@Praveen
I like the idea of storing all the patterns in an array once, and only referring to it subsequently.

Anyhow, did you check the bit patterns in the question? There is a particular logic in how they are arranged.
I think I should've been more clear in the question!

Please see the updated question 😀
I couldn't see the update buddy. Say once more na?

Are you sure? This action cannot be undone.
Cancel
eternalthinker

Member • Dec 23, 2011

@Praveen

I was updating it now! Check it again.

Are you sure? This action cannot be undone.
Cancel
PraveenKumar Purushothaman

Member • Dec 23, 2011

eternalthinker
@Praveen

I was updating it now! Check it again.
Okay, got it... Gimme some time... Will do something.. 😁

Are you sure? This action cannot be undone.
Cancel