You can switch 0011 into 0001, or 0001 into 0011, by Rule 1.
Thank you!
Here is the background info for anyone who are stuck in solving this puzzle, or for further research in this topic…
I studied and created this Light Bulb puzzle while I was trying to solve a Chinese “Nine Rings puzzle”.
(Chinese Nine Linked Rings Puzzle - ChinesePuzzles.org)
Do you see the similarity between the linked rings and the rules of the light bulb array?
There are research papers and mathematical analysis on this topic. It can be your next research topic if you could discover something new.
4 Likes
Hi, it’s helpful. I change someplace of your code. I found that you calculate the same situation too many times while lead to the time-out.
i used your code and cached some results, than it is fast enough to pass all tests.
ltable = {}
def resolv(Src, Obj):
# The Start And Goal is equal then Stop The Programme
if Src == Obj:
return 0
# Juste The Last Bulb Is Differente, Add 1 Move And Stop The Programme
elif Src[0:-1] == Obj[0:-1]:
return 1
# Several bulb was Differente, So Find A Cossing Point And Resolve For The 2 new Start And Goal
else:
key = Src+'_'+Obj
if (len(Src) <= 8):
d = ltable.get(key, -1)
if d > 0:
return d
for i in range(len(Src)):
if Src[i] != Obj[i]:
break
i += 1
Cross_Point = ("1").ljust(len(Src[i:]), '0')
d = 1 + resolv(Src[i:], Cross_Point) + resolv(Cross_Point, Obj[i:])
if (len(Src) <= 8):
ltable[key] = d
return domg anyone learned digital circuit??? I found out that this is exactly Gary Code, and u just need to transfer it to binary then to decimal, minus, boom!
I saw several solutions splitting the string and solving for substrings but I’m not sure why it works. Looks to me like any substring that doesn’t contain the last bit should be getting wrong results.
It also is related to the Towers of Hanoi puzzle. I fiddled around on scratch paper for a while, trying to avoid something that was O(2^(length of s)) before just writing out the full 4-bit sequence and recognizing the pattern. There’s a nice O(length of s) solution.
Uh, “Gray”; not “Gary”. And yeah, that’s it. (Actually, it’s one particular binary Gray code, called the “reflected binary code”, but that’s the one that Frank Gray actually used in 1947.)
Hello, the test N=5 shows that we need 21 switches to get from 11111 to 00000. However, the following path has 18 switches. What am I doing wrong?
11111
11110
11010
11011
11001
11000
01000
01001
01011
01010
01100
00100
00101
00111
00110
00010
00011
00001
00000
Never mind, just saw my error.
I must say, java_coffee_cup’s February 2020 message about a ‘“super-tricky” short-cut method’ was amazingly helpful. This is probably my shortest CodinGame solution ever, with 9 lines of code (C#), ignoring the default code, declarations and curly braces.
@Husiski
I just did the (Hard) Hanoi puzzle in C and I see what you mean about O(2^n)
After completing Hanoi and seeing the other submissions, I noticed that most coders didn’t see the pattern and instead simulated the moves from [1 … n]… which is a shame : /
So I came to the forums looking for any discussion on the Hanoi (there’s no “discussion” link on the puzzle page) but all I found was this thread. Oh well.
Perhaps I should look at “Light Bulbs” next : ))))
Indeed this puzzle is related to the ToH problem.
If you see a pattern in ToH as a short-cut, it may be applicable to this puzzle too.
If this problem seems too hard for medium, that could be mitigated by suggesting that people learn about Gray codes Gray code - Wikipedia.
The algorithm for converting from a Gray code to an ordinal integer is trivial and completes in O(N) time, where N is the number of bits.
The problem statement makes it a bit more interesting because the rules of transformation do not allow for the Gray code Wraparound case, which would be one additional rule:
- Light bulb 1 can be turned on or off if all other light bulbs are off.