Results 1 to 19 of 19
  1. #1
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default 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)
    which receives two boolean arrays equal in length. The first array is the original form of the light bulbs and the second array is the wanted form of the light bulbs.
    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};
    returns true since if you press the switch in location 1 (starting from zero, so 1 is the second light bulb...) you get
    Java Code:
    {false, true, false, false, true, false
    and then if you press the switch in location 4 you get
    Java Code:
    {false, true, false, true, false, true
    and that is the wanted form of light bulbs.

    However,
    Java Code:
    boolean[] original = {true, false, true, false, true };
    boolean[] wanted = { false, false, true, false, true };
    returns false since it is impossible to get from the original form to the wanted form.

    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; 06-07-2010 at 02:35 PM.

  2. #2
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    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.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    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

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    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();
    	}
    }
    kind regards,

    Jos

  5. #5
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    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.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by xcallmejudasx View Post
    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)
    Permutations have nothing to do with this and Dijkstra is about shortest paths which is also not an issue here. See my code for an example.

    kind regards,

    Jos

  7. #7
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,513
    Rep Power
    25

    Default

    System.out.printf("%4d", vertex[i][j]);
    Would the output be easier to understand if in hex?
    System.out.printf("%4x", vertex[i][j]);

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Norm View Post
    Would the output be easier to understand if in hex?
    System.out.printf("%4x", vertex[i][j]);
    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

  9. #9
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    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.length-1] = 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; 06-08-2010 at 11:38 AM.

  10. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by myst View Post
    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.length-1] = 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??
    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,

    Jos
    Last edited by JosAH; 06-08-2010 at 11:57 AM.

  11. #11
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    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.
    Sorry, I thought it was to be assumed. 8 light bulbs is only an example. The two arrays's lengths are chosen by the user.
    he could choose:
    original - (true)
    wanted - (false)
    which returns true...

    original - (true, true)
    wanted - (false, false)
    which returns true

    original - (true-1,...,true-n)
    wanted - (false-1,...,true-n)

    But the idea i guess is to make the program work for n amount of switches.

  12. #12
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,513
    Rep Power
    25

    Default

    there are only two disjunct paths
    If the answer is 2, what is the question?
    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);
    Why is mark incremented?


    How does your posted code relate to the OPs question?
    Last edited by Norm; 06-08-2010 at 05:04 PM.

  13. #13
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Norm View Post
    If the answer is 2, what is the question?
    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?
    paths is an array that contains a path number or set number; if for two vertices the path numbers are equal those two vertices can be constructed given one, and using those switches.

    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

  14. #14
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,513
    Rep Power
    25

    Default

    disjunct sets of configurations
    Thanks for the response. However, its been ages since I studied this stuff.
    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?

  15. #15
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Norm View Post
    Thanks for the response. However, its been ages since I studied this stuff.
    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?
    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

  16. #16
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,513
    Rep Power
    25

    Default

    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?

  17. #17
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Norm View Post
    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?
    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

  18. #18
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,513
    Rep Power
    25

    Default

    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?

  19. #19
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Norm View Post
    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
    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?
    I don't know; my little program doesn't give a constructive solution, i.e. it simply finds the number of disjoint subsets. I gave it some thoughts and figured out that 0x0a^0x1b == 0x11, so bulb 0 and 4 have to change from on to off or vice versa. switches 0,1, 2, 3 and 4 are applicable ... since the order of the switches doesn't matter a solution either has to start with a 0 or a 1. I haven't figured out the recursive steps yet and the bounding rules ...

    kind regards,

    Jos

Similar Threads

  1. how do i do recursion.....
    By sonny in forum New To Java
    Replies: 4
    Last Post: 03-17-2010, 05:15 PM
  2. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  3. How could Swing support multi-touch?
    By pianyao in forum AWT / Swing
    Replies: 2
    Last Post: 08-18-2009, 10:06 AM
  4. Recursion
    By jachandru in forum New To Java
    Replies: 1
    Last Post: 01-24-2009, 12:52 PM
  5. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 08:03 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •