Count the number of railway wagons

[Shantanu Kumar]

Suppose there are some unknown number of railway wagons interconnected with each other so that you can move from one wagon to another without getting off. There is a bulb and corresponding switch in every room which you can turn on or off when inside the room.The problem is to count the total number of railway wagons given that you start from the inside of some wagon and go around as many times as you want but remain inside the train.You can't see whether a light is on or off in some other wagon from inside of another wagon.

 

[Yike Lu]

Is this a simple doubly linked list or a circularly linked one?

You break the connection between two trains, then count how many trains it takes to go from one end to the other.

 

[Barny]

Are the lights initially on or off?

 

[Daniel Duffy]

Send two guys, one to the front and one the the end of the train. Let them ring you (using the train's intercom) when they have arrived. Add individual results up.

For best results, start in the middle carriage, it possible.

What-if the light bulb is not working?

 

[rnick]

let 2 lights off at the starting point. then you can create a series of on and off lights (for extra security) or just on lights until you reach the starting point. it works in a circular or non circular trains.

 

[Daniel Duffy]

why do you need lights?

 

[Yike Lu]

Haha, I think the original question is probably more along the lines of...

You have a circularly linked list with node values randomly set to 1 or 0. You can set the node values to 1 or 0, you cannot change the pointers. How do you determine the length of the list?

 

[Drew Norton]

Go around once and turn every light off, then go around again and count the number of lights you turn on.


Edit: Hmm, guess you would never know if you had gone all the way around. Number of cars could be so high that you couldn't be sure you had reached them all.

 

[Shantanu Kumar]

I don't know the correct answer myself but i guess Yike answered it correctly.As a mathematical puzzle i think its unsolvable.

What-if the light bulb is not working?

You can call the electrician to fix the bulb without any further assistance.

 

[Yike Lu]

Thinking about it, the singularly linked case is rather difficult - you would never know if you were changing a light that you had already affected.

The doubly linked case is a bit simpler - you go one forward from where you started, observe its state, go one backward from where you started and flip the switch, and return to one forward and verify that its state is unchanged. Keep going until you find that flipping the switch in the backward node actually changes the value in the forward node.

 

[Yike Lu]

I don't know the correct answer myself but i guess Yike answered it correctly.As a mathematical puzzle i think its unsolvable.

It's interesting, I find the change of problem domain from physical to CS was quite a significant step for me to be able to put forth my original solution.

When I thought of trains, the link-breaking operation seemed very expensive so I didn't think of doing it. On the other hand, when I thought in CS terms, a simple pointer operation seems very cheap so it was natural to use it.

I often finding myself creating "engineering" solutions from the original physical statement of brainteasers in the opposite way - the physical domain suggests some non-mathematical trick.

The irritating thing about brain teasers is that it's never clear which domain you are expected to operate in, as there are examples of both, and it depends heavily on the interviewer as to whether or not he accepts an alternate (but valid) solution.

 

[Drew Norton]

Remove the light bulb in the starting car and proceed until you find the car with no light bulb.