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

@eternalthinker-Kvsi5Y • Oct 21, 2024

Oct 21, 2024

953

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!

Like 0 Replies 9

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

PraveenKumar Purushothaman

@praveenkumar-66Ze92 • Dec 21, 2011

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

@eternalthinker-Kvsi5Y • 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 😀
0
PraveenKumar Purushothaman

@praveenkumar-66Ze92 • 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... 😀
0

PraveenKumar Purushothaman

@praveenkumar-66Ze92 • 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?

PraveenKumar Purushothaman

@praveenkumar-66Ze92 • 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! 😀

eternalthinker

@eternalthinker-Kvsi5Y • 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 😀
0
PraveenKumar Purushothaman

@praveenkumar-66Ze92 • 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?
0
eternalthinker

@eternalthinker-Kvsi5Y • Dec 23, 2011

@Praveen

I was updating it now! Check it again.
0
PraveenKumar Purushothaman

@praveenkumar-66Ze92 • Dec 23, 2011

eternalthinker
@Praveen

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