[Community Puzzle] Light Bulbs


#1

https://www.codingame.com/training/medium/light-bulbs

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @cg123,@selenae and @Deltaspace.
If you have any issues, feel free to ping them.


#2

ok, I run out of memory on last 2 test cases. I’m sure there are other ways to do it, but I was hoping this would be considered valid:

<?php
function gen($s,$m,$d=0) {
    global $saved;
    global $t;
    if ($s==$t) return min($m,$d);
    $saved[bindec($s)]=1;
    if ($d>$m)  return $m;
    $cs=strlen($s);
    for ($i=0;$i<$cs-1;$i++)
        if (substr($s,$i+1)==("1".str_repeat("0",$cs-($i+2)))) {
            $ts=$s;
            $ts[$i]=($ts[$i]=='0'?'1':'0');
            if (!isset($saved[bindec($ts)]))
                $m=min($m,gen($ts,$m,$d+1));
        }
    $ts=$s;
    $ts[$cs-1]=($ts[$cs-1]=='0'?'1':'0');
    if (!isset($saved[bindec($ts)]))
        $m=min($m,gen($ts,$m,$d+1));
    return $m;
}

$start=trim(fgets(STDIN)); //  stream_get_line(STDIN, 255 + 1, "\n");
$t=trim(fgets(STDIN)); //  = stream_get_line(STDIN, 255 + 1, "\n");
error_log("$start -> $t");

if (strlen($start)==1)
    echo("1\n");
else {
    $saved=[];
    echo(gen($start,INF)."\n");
}
?>

#3

Time out because you are killing memory in your recursive function.

A basic rule is not to declare any new variable in a recursive function. Data are sent to the function by parameters, or stored in global variables to let the function to read it. Processed data are sent out by return or to write to global variables declared outside the function.


#4

hello there, i got the same problem in javascript, lost after N=11,
i follow the remark of @java_coffee_cup, about variable declaration
i m sure i m loosing something but take too much time on it.
if someone see it, a litte advice would be very nice

applyRules  = (entry, last, deep) => {
    if(entry.join('') != expected) {
        // rule 1
        entry1 = [...entry]
        matcher = entry1.join('').match(/[0-1]10*$/)
        if(matcher) {
            entry1[matcher.index] = entry1[matcher.index] ? 0 : 1
            if(entry1[matcher.index] != last[matcher.index]) 
                applyRules(entry1, entry, deep + 1)
        }
        // rule 2
        entry2 = [...entry]
        entry2[length] = entry2[length] ? 0 : 1
        if(entry2[length]  != last[length] ) {
            applyRules(entry2, entry, deep + 1)
        }
         
    } else founds.push([entry, deep])
}

#5

“Cannot pass some test cases” is not descriptive enough. Run your code locally and test with all test cases.
You should determine what kind of situation you are in:

  1. Time out, no answer (wrong logic, stack overflow, not enough memory, runtime error, etc)
  2. Time out, correct answers (running several minutes or hours and finally it is able to return correct answers)
  3. Wrong Answer (no matter it is fast enough or time out).

Finding out what problem you have, and then figure out the cause of problem, sometimes will lead to a solution.


#6

RangeError: Maximum call stack size exceeded at Answer.js. on line 8
same problem locally,

i guess my recursive is too expensive, i get a deep to 7200 / 22561 (expected) before it crashes

and even with putting variable outside the recursive function, i only get some hundreds more…


#7
recur
  if solution not found
    if rule1_suitable
      apply_rule1
      recur
    if rule2_suitable
      apply_rule2
      recur
  else write_solution_to_global

Does the above design reflect your recursive function?

Add a few comment outputs. Trace the steps manually by using a small input. You may discover the program is doing unnecessary steps.


#8

this pseudo code is closed to mine…
I translate from javascript to PHP and get the N=16 working now with deep = 585002
the last two tests still failed, I m getting frustrated… lost really too much time on this medium…

<?php

$start    = stream_get_line(STDIN, 30 + 1, "\n");
$expected = stream_get_line(STDIN, 30 + 1, "\n");

function apply($entry, $expected, $last = '', $deep = 0) {

    if($entry != $expected) {
        preg_match("/[0-1]10*$/", $entry, $matcher, PREG_OFFSET_CAPTURE);
        if(isset($matcher[0])) {
            $entry1 = $entry;
            $entry1[$matcher[0][1]] = $entry[$matcher[0][1]] ? 0 : 1;
            if($entry1 != $last) apply($entry1, $expected, $entry, $deep + 1);
        }
        $entry1 = $entry;
        $l = strlen($entry1) - 1;
        $entry1[$l] = $entry[$l] ? 0 : 1;
        if($entry1 != $last) apply($entry1, $expected, $entry, $deep + 1);
    } else echo($deep);
}

apply($start, $expected);

#9

Your code do not have a mechanism to stop processing when a solution is found.

According to the pseudo code logic,
in recur,
if rule1_suitable
then apply rule1,
then go into recur,
then found solution (very lucky),
then it will come back to the first recur
and continue testing is rule2 is suitable.

If you go deep into 1000 recur levels and found solution, it goes back 1000 level and in each level continue doing the remaining testing.

Writing comment outputs at each step. It will reveal the actual flow.


#10

yes… this is what i was doing in the first code i post in js, but here i do not get even one good answer for N=21 or more… thx for your answer


#11

You need better flow control measures.

if...then.
  action1
else
  action2

so that action1 and action2 will not be doing in a sequence.

Recursion is often harder to debug and implement well. However, most recursive functions can be written as loops. In your case, rewriting the function into a for- or while-loop is straight forward.


#12

This puzzle was quite hard for me, harder than many ‘hard’ ones…
My solution timeouted at big N and when I was out of ideas on how to make it faster in PHP, the last validator still timeouted. But it seems I was so close to the threshold, that after several resubmits (without any change) I passed… Maybe the PHP opcache makes source parsing unnecessary the second time, or the runtime machine had less background work to do… :slight_smile:

PS:

WHAT WILL I LEARN?

:bulb::bulb::bulb::bulb::bulb:

LOL…

What I really DID learn, is a paraphrase from the known joke:
- "How many Codingamers are needed to change a lightbulb?"
- Two! Because the success rate of the Light Bulb CG community puzzle is ~50%...
:slight_smile:


#13

[JS]

For me it was quite hard. I got stuck at finding working algorithm, then I desperate until i found how to code it fast enought. My approach was have current “number” in array(x[i]=y vs some string concate operations and stuff) of char and compare it to final number in const string. I would like some comments:

  1. Binary numbers 110, 1100, 11000,… are 6, 12, 24, but i think that this fact is usseless. I dont see how should I use advatage of that.
  2. I tried rewrite my re-cursed code to stack machine, but after check its duration (in JS for example console.time()) I found out that its slower?? It didnt work for me. Also i tried optimalize everything other, one thing that i am aware of, but i see it nearly everywhere is construct like this:for(let i = 0; i < array.length - 1; i++){} this is bad because every loop is array.lenght process once again, much more efficient is declare and used only constant: len = array.length - 1;, but after some ideas (check for other tips in internet), it didnt work as well for me.
  3. At last, last thing that I was missing in my approach was line which had huge impact on result:
    let matcher = x.join('').match(/[0-1]10*$/); . These buildin functions were for my code too heavy, too cumbersome. I tried write my implementation of them, its quite easy but powefull. (Write 1 for-loop over element of array and chceck if for i ==1 and i+1==1, then return i is satisfy enough).

Thanks for this puzzle @java_coffee_cup, i almost lost all my hair, but it worth it.


#14

Guys, @TBali, @JakubFaktorialDvorak and others, thanks your intense interest and effort on this puzzle. Thanks even more for your interesting feedbacks too. I laughed while reading.

I admit this puzzle is harder than the average “Medium”. I was struggling whether to put it to “Hard” or to “Medium” while publishing. Finally it became the “very-hard-medium” puzzle because of some reasons below.

In my project folder for this puzzle there are 4 versions of solution and 1 random puzzle generator.
Three of the solutions are using different algorithms of simulations. The last one solution is a “super-tricky” short-cut method I am not going to explain it here.

The difficulty of the puzzle is mainly determined by N, the length of the string. Combination of the start-stop conditions is a secondary factor.

I ran the generator hundred of times to create puzzles, and for each puzzle I solved it by different versions of my solutions. The purpose was to verify my solutions are really correct. The even more important purpose was to find out the limit of N before time-out when different “normal” approaches and algorithms are used.

Finally I set N to be max at 25. At this level my average (without too much odd-looking optimization) solution in java (famous for its slowness) can marginally pass all test cases and validators. When server is busy it can time-out, but most of the time it can pass. When a similarly slow language is used, it should still be able to pass with some effort in optimization.

Had the constraint been set higher and solvable only by math-intensive and extremely abstract approaches, it would have been put in “Hard”.

I found that sometimes it is difficult to set a tag for a puzzle. Having such tags sometimes could reveal the solution too much. Sometimes it could constraint coders’ focus on a “normal” approach but reduce their creativity in inventing or discovering alternative approaches.

To help codingame obtaining higher public exposure (get higher hit rate and ranking in google search by having more different URLs), I choose not to leave the tag empty. So come the eye-catching and neutral tag. Do you like it? LOL.


#15

hello, if I have a starting position 11111 is 11101 a valid move?


#16

Yes it is valid


#17

thanks for the reply.