Results 1 to 19 of 19
Thread: Touch recursion question
 06072010, 12:00 PM #1Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
Tough recursion question
You have a row of light bulbs. 0 represents them turned off, 1 represents them turned on. There is a switch next to each light bulb. Each time you press the switch it changes the status (on or off) of that light bulb and the two light bulbs on either side of it.
For example: 0011001 If you press the 4th light bulb it changes to this 0000101
(if you press either the first or last light bulb, it changes that light bulb and the one after or behind it...)
The task is to write a recursive static method:
Java Code:public static boolean bulbs(boolean[] original, boolean[] wanted)
The method returns true if it possible to get from the original form to the wanted form by any order of pressing the switches. Otherwise, it returns false.
For example:
Java Code:boolean[] original = {true, false, true, false, true, false}; boolean[] wanted = {false, true, false, true, false, true};
Java Code:{false, true, false, false, true, false
Java Code:{false, true, false, true, false, true
However,
Java Code:boolean[] original = {true, false, true, false, true }; boolean[] wanted = { false, false, true, false, true };
Does anybody have an idea for an algorithm even???
(This seems like a typical recursion question though. Does anybody know a website which explains famous recursion scenarios? I'd like to read them to prepare for my finals.)
Thanks!Last edited by myst; 06072010 at 02:35 PM.
 06072010, 02:36 PM #2Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
I'd recommend starting with a simple algorithm that simply checks all the possibilities, ie. calculate all the possible permutations and check if they correspond to the wanted array. When you're done with the simple algorithm, check when you can eliminate certain possibilities to speed up the algorithm.
Ever seen a dog chase its tail? Now that's an infinite loop.
 06072010, 03:06 PM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
This a simple path finding problem. When you have n bulbs construct 2^n vertices representing the position (on/off) of the bulbs. If you have eight bulbs you have 256 vertices. Each vertex has eight edges to other nodes representing a switch toggled, e.g. node 00000000 has an edge to node 00000011 if the rightmost switch is toggled.
This makes an undirected graph. The problem of two (different) bulb configurations is equivalent to finding a path between the corresponding nodes. If there is a path the bulb configurations can be 'constructed' by toggling the corresponding switches, otherwise there is no sequence of switches that can do the job.
kind regards,
Jos
 06072010, 03:43 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
I decided to cook something up: the following program shows that there are only two disjunct paths. Here's the code:
Java Code:public class Bulbs { private static int[] SWITCH = { 0xc0, 0xe0, 0x70, 0x38, 0x1c, 0x0e, 0x07, 0x03 }; private int[][] vertex= new int[256][8]; private int[] paths= new int[256]; Bulbs() { initialize(); } private void initialize() { buildGraph(); } private void findPath(int i, int mark) { if (paths[i] == mark) return; paths[i]= mark; for (int j= 0; j < SWITCH.length; j++) findPath(vertex[i][j], mark); } private void find() { int mark= 0; for (int i= 0; i < vertex.length; i++) if (paths[i] == 0) findPath(i, ++mark); System.out.println("paths: "+mark); for (int r= 0; r < 256; r+= 16) { for (int c= 0; c < 16; c++) System.out.print(paths[r+c]+" "); System.out.println(); } System.out.println(); for (int i= 0; i < 256; i++) { System.out.printf("%3d:", i); for (int j= 0; j < SWITCH.length; j++) System.out.printf("%4d", vertex[i][j]); System.out.println(); } } private void buildGraph() { for (int i= 0; i < vertex.length; i++) for (int j= 0; j < SWITCH.length; j++) vertex[i][j]= i^SWITCH[j]; } public static void main(String[] args) { Bulbs bulbs= new Bulbs(); bulbs.find(); } }
Jos
 06072010, 04:57 PM #5
Pathfinding algorithms....Djikstras is the one that comes to mind at first. If I remember it's fairly easy to implement however it's used for finding the shortest path so it may not give you all possibilities.
You should also look up Truth tables. They excel at this type of thing. (Showing all possible permutations, not navigating them)Liberty has never come from the government.
Liberty has always come from the subjects of government.
The history of liberty is the history of resistance.
The history of liberty is a history of the limitation of governmental power, not the increase of it.
 06072010, 05:01 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
 06072010, 11:24 PM #7System.out.printf("%4d", vertex[i][j]);
System.out.printf("%4x", vertex[i][j]);
 06082010, 07:42 AM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
Sure, be my guest ;) you're free to do with the code what you want. Maybe a binary representation would even be better. What surprised me a bit is that only two paths are formed in that 256 node graph. (play with those SWITCH values to see different results).
kind regards,
Jos
 06082010, 11:32 AM #9Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
The only issue I have is that I don't know how many light bulbs there are. The user chooses how the number of light bulbs. There could be 1,000,000 light bulbs in both arrays. How can I write a program for that??
Is the way to solve it like this: Check if a[0] through a[a.length1] = b[0] through b[b.length] and that is the base case. And if a single cell is different than I switch that cell's value and check again from the beginning? The only problem is that it is possible that there is no solution. How will I know when to stop checking for 1,000,000 light bulbs??Last edited by myst; 06082010 at 11:38 AM.
 06082010, 11:55 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
You should have mentioned those numbers in your OP; your example showed just eight lightbulbs; for 1,000,000 bulbs the algorithm I gave you cannot be used (it doesn't scale to such huge dimensions). Your attempt doesn't work at all because you're searching with the 'lights off', i.e. you don't know where you are in the search space and you don't know where you're going to.
I suspect that your big problem can be partitioned, e.g. changing the leftmost lightbulbs doesn't change the rightmost bulb configuration; that should be a key to reducing the size of your problem.
kind regards,
JosLast edited by JosAH; 06082010 at 11:57 AM.
 06082010, 12:24 PM #11Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
You should have mentioned those numbers in your OP; your example showed just eight lightbulbs; for 1,000,000 bulbs the algorithm I gave you cannot be used (it doesn't scale to such huge dimensions). Your attempt doesn't work at all because you're searching with the 'lights off', i.e. you don't know where you are in the search space and you don't know where you're going to.
I suspect that your big problem can be partitioned, e.g. changing the leftmost lightbulbs doesn't change the rightmost bulb configuration; that should be a key to reducing the size of your problem.
he could choose:
original  (true)
wanted  (false)
which returns true...
original  (true, true)
wanted  (false, false)
which returns true
original  (true1,...,truen)
wanted  (false1,...,truen)
But the idea i guess is to make the program work for n amount of switches.
 06082010, 04:55 PM #12there are only two disjunct paths
I am unable to understand what your code does. (Some comments would help.)
For example the first time the code looks at paths[], paths[] has not been set to any value (ie its still zero).if (paths[i] == 0)
findPath(i, ++mark);
How does your posted code relate to the OPs question?Last edited by Norm; 06082010 at 05:04 PM.
 06082010, 05:16 PM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
The question I answered is: how many disjunct subsets exist given those 256 vertices and those 8x256 edges?
I am unable to understand what your code does. (Some comments would help.)
For example the first time the code looks at paths[], paths[] has not been set to any value (ie its still zero).
Why is mark incremented?
How does your posted code relate to the OPs question?
It partly answered the OP's question: which configurations can be constructed using those switches. The answer (given eight bulbs) is: there are only two disjunct sets of configurations. Each configuration in a set can be constructed out of the other.
kind regards,
Jos
 06082010, 05:25 PM #14disjunct sets of configurations
Could you explain in practical terms what you mean?
For example given one setting of bulbs and one target setting, how many ways are there to change the initial setting to the target setting?
 06082010, 05:50 PM #15
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
Given three bulbs there is only one set; as you can see (after scribbling those switch configurations on paper) all eight configurations can be constructed given configuration 000. For eight bulbs there are two of those sets.
Let those switches S_i be 0x03, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0 and 0xc0 for eight switches, then configuration C2 can be constructed out of configuration C1 as follows: C1^sum(a_i*S_i) where a_i is 0 (switch i not used) or 1 (switch i used). You only have to use a switch at most once because C_j^S_i^S_i == C_j. That 'sum' notation is the 'exclusive or sum'.
kind regards,
Jos
 06082010, 05:55 PM #16
Thanks again. Sorry, my theoretical days are gone. I'll have to get some background before I can understand what you are saying.
I wrote a program using the brute force method. I used bytes as you did to define 8 bulbs.
With a starting setting of x0A and a target of x1b the code did 150 toggles and found a solution at a depth of 71. So far my code can only find the one solution. Can there be more than one solution?
 06082010, 06:15 PM #17
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
Not really: think of it, when you toggle a switch an even number of times you could've left that switch alone (not toggle it at all). Also the order in which you toggle your switches doesn't matter either, e.g. 000 > 011 > 101 is the same as 000 > 110 > 101 for a three switch setup. Mathematically speaking: the xor operation is commutative and it annihilates itself.
kind regards,
Jos
 06082010, 06:37 PM #18
For the example you gave, start at 000 and end at 101 there are two paths of two steps each:
Path one: flip switch 2 then switch 0; for second: flip switch 0 then switch 2
For the case: starting setting of x0A and a target of x1b
How many paths and how many steps in each?
 06082010, 06:48 PM #19
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
Don't you consider 02 and 20 the same steps? They both arrive at the same configuration ...
For the case: starting setting of x0A and a target of x1b
How many paths and how many steps in each?
kind regards,
Jos
Similar Threads

how do i do recursion.....
By sonny in forum New To JavaReplies: 4Last Post: 03172010, 06:15 PM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
How could Swing support multitouch?
By pianyao in forum AWT / SwingReplies: 2Last Post: 08182009, 10:06 AM 
Recursion
By jachandru in forum New To JavaReplies: 1Last Post: 01242009, 01:52 PM 
Recursion help
By rjg_2186 in forum New To JavaReplies: 1Last Post: 01022009, 09:03 AM
Bookmarks