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.
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");
}
?>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.
1 Like
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])
}“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:
- Time out, no answer (wrong logic, stack overflow, not enough memory, runtime error, etc)
- Time out, correct answers (running several minutes or hours and finally it is able to return correct answers)
- 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.
2 Likes
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…
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.
1 Like
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);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.
1 Like
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
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.
1 Like
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… 
PS:
WHAT WILL I LEARN?
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%...
4 Likes
[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:
- 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.
- 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. - 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.
1 Like
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.
5 Likes
hello, if I have a starting position 11111 is 11101 a valid move?
Yes it is valid
thanks for the reply.
Hello, i’m lock on the last case with 25 bulbs.
I write my code in python and it work well with 22 bulbs.
But I have a time-out with the last case( i try my programme in my own computer and I find the solution in 30secondes)
Some People have find a solution in python ?
import sys
import math
def Resolv(Src,Obj):
global Mvt
#The Start And Goal is equal then Stop The Programme
if Src==Obj:
return
#Juste The Last Bulb Is Differente, Add 1 Move And Stop The Programme
elif Src[0:-1]==Obj[0:-1] :
Mvt+=1
return
#Several bulb was Differente, So Find A Cossing Point And Resolve For The 2 new Start And Goal
else:
for i in range (len(Src)):
if Src[i]!=Obj[i]:
break
i+=1
Mvt+=1
Cross_Point=("1").ljust(len(Src[i:]),'0')
Resolv(Src[i:],Cross_Point)
Resolv(Cross_Point ,Obj[i:])
s = input()
t = input()
Mvt=0
Resolv(s,t)
print(Mvt)
This Is my Code, if someone find a new improvement it will be great 
I solved it by brute force without recursion. C#.
I have a question about the rules. When can you switch the (N-1)-th bulb? Is it when the N-th is on or when the N-th is off, (or both)?