CODEWITHSUNDEEP
phpmemorymemory-management
heron
heron

Reputation: 3679

PHP Strange issue with working code

There is a technique by which the list of (N+1) bit codes can be generated from (N)-bit codes.

  1. Take the list of N bit codes in the given order and call it List-N
  2. Reverse the above list (List-N), and name the new reflected list: Reflected-List-N
  3. Prefix each member of the original list (List-N) with 0 and call this new list 'A'
  4. Prefix each member of the new list (Reflected-List-N) with 1 and call this new list 'B'
  5. The list of codes with N+1 bits is the concatenation of Lists A and B.

A Demonstration of the above steps: Generating the list of 3-bit Mystery Codes from 2-Bit Mystery Codes

  1. 2-bit list of codes: 00, 01, 11, 10
  2. Reverse/Reflect the above list: 10, 11, 01, 00
  3. Prefix Old Entries with 0: 000, 001, 011, 010
  4. Prefix Reflected List with 1: 110, 111, 101, 100
  5. Concatenate the lists obtained in the last two steps: 000, 001, 011, 010, 110, 111, 101, 100

I found solution but when I enter 65 for example getting error

PHP Fatal error: Out of memory (allocated 538968064) (tried to allocate 20 bytes) in /home/pLR62k/prog.php on line 27

on Ideone http://goo.gl/WB3DKh

What Am I doing wrong?

<?php
function MysteryCodes($input){
    $initArr=array(0,1);
    if($input==1){
        return $initArr;
    }
    else {
        $list=array();
        $list[0]=$initArr;
        for ($i=1; $i<$input; $i++)
            {   
                $prevIndex=$i-1;
                $reflectedListN = array_reverse($list[$prevIndex]);
                $listA=prefixR($list[$prevIndex], '0');
                $listB=prefixR($reflectedListN, '1');
                $list[$i]=array_merge($listA, $listB);
            }
    }
    return array_slice($list[$input-1], -$input);
}



function prefixR($input, $prefix){
    $result=array();
    foreach($input as $value){
        $result[]=$prefix.$value;
    }
    return $result;
}

fscanf(STDIN, "%d", $inp);
if($inp>=1 && $inp<=65){
$result=MysteryCodes($inp);
$output="";
foreach($result as $key=>$value)
    $output.="$value\n";

fwrite(STDOUT, $output);
}

Upvotes: 2

Views: 401

Answers (3)

Eldho NewAge
Eldho NewAge

Reputation: 1333

What you did is almost correct, except "array_merge". This will utilize more memory .

Below code will work Like a Charm!!!!

    $length = 100;//input value

    if($length > 1) {
        $mysteryArray = ['0', '1'];
        for ($i=2; $i <= $length; $i++) {
            $reverseArray = array_reverse($mysteryArray);

            $tempArray = [];

            foreach ($mysteryArray as $key => $value) {
                $tempArray[] = '0' . $value;
            }

            foreach ($reverseArray as $key => $value) {
                $tempArray[] = '1' . $value;
            }

            if($i != $length) {
                $mysteryArray = array_slice($tempArray, 0, $i+$length);
            } else {
                $mysteryArray = array_slice($tempArray, -$length, $length);
            }

        }
        foreach ($mysteryArray as $key => $value) {
            echo $value . '<br>';
        }
    } else {
        echo '1';
    }

Upvotes: 0

Guilherme Blanco
Guilherme Blanco

Reputation: 1244

function prefixR(&$input, $prefix){

should already help with memory a lot, since arrays are copied instead of being passed by reference

Upvotes: 1

Carsten
Carsten

Reputation: 18446

You're using wayyyy too much memory. Creating an array which holds all elements is only going to work for small N.

You stated in your question that the "2-Bit Mystery Codes" are all four possible two-bit combinations. Your algorithm then becomes a method that generates all possible N bit combinations. For N=65, the number of combinations (and therefore, of elements you're trying to store) is

2^65 = 36893488147419103232 ≈ 3 * 10^19

That quite a lot. And it doesn't even count all the intermediate steps you're taking. Assuming no overhead, your list would take up about 30 Exabytes of memory. If you want to generate these numbers, you'll have to restrict yourself to smaller N or find another method of calculating them on the fly without saving them all.

Upvotes: 3

Related Questions