PHP Strange issue with working code

Question

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

Take the list of N bit codes in the given order and call it List-N
Reverse the above list (List-N), and name the new reflected list: Reflected-List-N
Prefix each member of the original list (List-N) with 0 and call this new list 'A'
Prefix each member of the new list (Reflected-List-N) with 1 and call this new list 'B'
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

2-bit list of codes: 00, 01, 11, 10
Reverse/Reflect the above list: 10, 11, 01, 00
Prefix Old Entries with 0: 000, 001, 011, 010
Prefix Reflected List with 1: 110, 111, 101, 100
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://ideone.com/HHRBoG

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);
}

Avoid using array_merge by using same array for both reverse array and real array. — Eldho NewAge
– Eldho NewAge, Commented Nov 20, 2017 at 14:31

Carsten · Accepted Answer · 2014-06-02 07:39:48Z

3

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.

answered Jun 2, 2014 at 7:39

Carsten

18.5k4 gold badges51 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Guilherme Blanco · Accepted Answer · 2015-11-24 22:16:22Z

1

function prefixR(&$input, $prefix){

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

answered Nov 24, 2015 at 22:16

Guilherme Blanco

1,2448 silver badges8 bronze badges

Comments

Eldho NewAge · Accepted Answer · 2017-11-20 14:29:26Z

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';
    }

Collectives™ on Stack Overflow

PHP Strange issue with working code

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related