Touch recursion question

[myst]

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:

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:

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

{false, true, false, false, true, false

and then if you press the switch in location 4 you get

{false, true, false, true, false, true

and that is the wanted form of light bulbs.

However,

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!

[m00nchile]

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.

[JosAH]

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

[JosAH]

I decided to cook something up: the following program shows that there are only two disjunct paths. Here's the 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

[xcallmejudasx]

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)

[JosAH]

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

[Norm]

System.out.printf("%4d", vertex[i][j]);

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

[JosAH]

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

[myst]

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??

[JosAH]

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

[myst]

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.

[Norm]

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?

[JosAH]

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

[Norm]

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?

[JosAH]

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

[Norm]

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?

[JosAH]

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

[Norm]

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?

[JosAH]

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