Issue
I am doing the following programming exercise: How many Wagons Are in the Train?. The statement is:
You are in a Train that is permanentely moving in a circle.The Train is looped: The head is connected with the tail and you can go from on to another directely.
Every Wagon has a light. The initial status of the lights is not known. You can switch it on or off if you wish.
Count the Number of Wagons!
You can move between wagons as you wish.
Contraints. After you count the Wagons, the lights in the train should be in the initial state. But at the end you dont need to be in the same Wagon where you started.
Use the implemented Train methods:
public boolean isLightOnInCurrentWagon()
public void switchLight()
public void goToNextWagon()
public void goToPreviousWagon()
Train notation "1 : 0 : 0" means that you have a train with three Wagon. The light is on in the first Wagon and off in the other two.
First I thought to keep three lists of Integers, original, switched and final. Original would store lights as they were at start. Switched would store original's complement (after switching each wagon's light). Final would have the lights as original (after switching back to the original state).
For example for train: 1:0:1
Original: {1,0,1}
Switched: {0,1,0}
Final: {1,0,1}
However the difficulty is, how we know where is the head / start of then train?
In addition I attempted some code for the base case, where the train has just one wagon:
import java.util.*;
public class Solution {
public int howManyWagons/*🚂❔🤔*/(Train train){
int haveWeEnded = 0, prev = 0, first = 0, next = 0;
if(train.isLightOnInCurrentWagon()){
first = 1;
}
System.out.println("first: "+first);
train.switchLight();
train.goToNextWagon();
if(train.isLightOnInCurrentWagon()){
next = 1;
}
System.out.println("next: "+next);
train.switchLight();
train.goToPreviousWagon();
if(first != next){
train.switchLight();
train.goToPreviousWagon();
if(train.isLightOnInCurrentWagon()){
prev = 1;
}
System.out.println("prev: "+prev);
train.switchLight();
}
return prev == next && first != prev && first != next ? 1 : 0;
}
}
Being the test cases (taken from the challenge):
import org.junit.jupiter.api.Test;
import java.util.Random;
import static org.junit.jupiter.api.Assertions.*;
class SolutionTest extends Train {
Solution sol = new Solution();
Random rand = new Random();
@Test
void howManyWagonsCornerCases() {
String repr;
Train train;
repr = "1";
train = Train.fromRepr(repr);
assertEquals(1, sol.howManyWagons(train), repr);
repr = "1 : 0 : 1 : 0 : 0";
train = Train.fromRepr(repr);
assertEquals(5, sol.howManyWagons(train), repr);
repr = "1 : 0 : 0";
train = Train.fromRepr(repr);
assertEquals(3, sol.howManyWagons(train), repr);
repr = "1 : 1 : 0 : 0 : 1 : 1";
train = Train.fromRepr(repr);
assertEquals(6, sol.howManyWagons(train), repr);
repr = "0 : 0 : 0 : 0 : 0";
train = Train.fromRepr(repr);
assertEquals(5, sol.howManyWagons(train), repr);
repr = "1 : 1 : 1 : 1 : 1";
train = Train.fromRepr(repr);
assertEquals(5, sol.howManyWagons(train), repr);
repr = "1 : 0 : 1 : 0 : 0 : 1 : 1 : 0 : 0";
train = Train.fromRepr(repr);
assertEquals(9, sol.howManyWagons(train), repr);
}
}
So when there is just one wagon, it does count it. However how could we make this general? Because of if we have 5 wagons (second test), as: "1 : 0 : 1 : 0 : 0", the code outputs:
first: 1
next: 0
prev: 0
Because of it detects the same patterns as if it were just one wagon, s then it returns 1 instead of 5.
Plus, I have read:
- Finding Length of Doubly Linked List
- Circular Linked List - Count Number of Nodes
- https://www.geeksforgeeks.org/count-nodes-circular-linked-list/
- Count number of nodes in a linked list that may be circular
How could we count the elements inside a doubly linked list (circular list), where we do not know the initial state nor where is head / tail‽
EDIT: Using @Chamika answer I tried to explain how is the thought process which creates the algorithm
import java.util.*;
public class Solution {
public int howManyWagons/*🚂❔🤔*/(Train train){
boolean end = false;
int count = 1;
while(!end){
//💡 We save the light of the initial wagon to be able to reset it later
boolean isFirstWagonLightOn = train.isLightOnInCurrentWagon();
//🕳️ We turn off the light of the initial wagon, to mark ⛳ where we started this iteration
if(train.isLightOnInCurrentWagon()){
train.switchLight();
}
goForward(train,count);
//If the light is on 🔆, we know we are not in the initial wagon, we go to the initial wagon and count it
if(train.isLightOnInCurrentWagon()){
goBack(train,count);
count++;
//When the light is off 🕳️, we may have go back to the initial position
}else{
//We switch the light 🔲,go back
train.switchLight();
goBack(train,count);
//If after going back the wagon light is on 🔆, it means we stand inside the end wagon
if(train.isLightOnInCurrentWagon()){
end=true;
}else{
//If light is off 🕳️, we have not been in the end position yet
goForward(train,count);
train.switchLight();
goBack(train,count);
count++;
}
}
//Reset end position light
if(isFirstWagonLightOn != train.isLightOnInCurrentWagon()){
train.switchLight();
}
}
return count;
}
public static void goForward(Train train,int count){
while(count > 0){
train.goToNextWagon();
count--;
}
}
public static void goBack(Train train,int count){
while(count > 0){
train.goToPreviousWagon();
count--;
}
}
}
Solution
Ole V.V. has provided an excellent solution for this problem and I implemented that algorithm in Java:
public int howManyWagons(Train train){
boolean end = false;
int count = 1;
while(!end){
//save the state of the first wagon
boolean isFirstWgonLightOn = train.isLightOnInCurrentWagon();
//light off in the first wagon
if(train.isLightOnInCurrentWagon()){
train.switchLight();
}
//go n forward
goFoward(train,count);
if(train.isLightOnInCurrentWagon()){
goBack(train,count);
count++;
}else{
train.switchLight();
goBack(train,count);
if(train.isLightOnInCurrentWagon()){
end=true;
}else{
//we need to reset the ligt state
goFoward(train,count);
train.switchLight();
goBack(train,count);
count++;
}
}
//we need to reset to the initial state
if(isFirstWgonLightOn != train.isLightOnInCurrentWagon()){
train.switchLight();
}
}
return count;
}
Answered By - Chamika
0 comments:
Post a Comment
Note: Only a member of this blog may post a comment.