Here is my assignment:
There is a colony of 8 cells arranged in a straight line where each day every cell competes with its adjacent cells(neighbour). Each day, for each cell, if its neighbours are both active or both inactive, the cell becomes inactive the next day,. otherwise itbecomes active the next day.
Assumptions: The two cells on the ends have single adjacent cell, so the other adjacent cell can be assumsed to be always inactive. Even after updating the cell state. consider its pervious state for updating the state of other cells. Update the cell informationof allcells simultaneously.
Write a fuction cellCompete which takes takes one 8 element array of integers cells representing the current state of 8 cells and one integer days representing te number of days to simulate. An integer value of 1 represents an active cell and value of 0 represents an inactive cell.
Program:
int* cellCompete(int* cells,int days) { //write your code here } //function signature ends Test Case 1: INPUT: [1,0,0,0,0,1,0,0],1 EXPECTED RETURN VALUE: [0,1,0,0,1,0,1,0] Test Case 2: INPUT: [1,1,1,0,1,1,1,1,],2 EXPECTED RETURN VALUE: [0,0,0,0,0,1,1,0]
This is the problem statement given above for the problem. The code which I have written for this problem is given below. But the output is coming same as the input.
#include<iostream>
using namespace std;
// signature function to solve the problem
int *cells(int *cells,int days)
{ int previous=0; for(int i=0;i<days;i++) { if(i==0) { if(cells[i+1]==0) { previous=cells[i]; cells[i]=0; } else { cells[i]=0; } if(i==days-1) { if(cells[days-2]==0) { previous=cells[days-1]; cells[days-1]=0; } else { cells[days-1]=1; } } if(previous==cells[i+1]) { previous=cells[i]; cells[i]=0; } else { previous=cells[i]; cells[i]=1; } } }
return cells;
}
int main()
{ int array[]={1,0,0,0,0,1,0,0}; int *result=cells(array,8); for(int i=0;i<8;i++) cout<<result[i];
}I am not able to get the error and I think my logic is wrong. Can we apply dynamic programming here If we can then how?
224 Answers
private List<Integer> finalStates = new ArrayList<>();
public static void main(String[] args) { // int arr[] = { 1, 0, 0, 0, 0, 1, 0, 0 }; // int days = 1; EightHousePuzzle eightHousePuzzle = new EightHousePuzzle(); int arr[] = { 1, 1, 1, 0, 1, 1, 1, 1 }; int days = 2; eightHousePuzzle.cellCompete(arr, days);
}
public List<Integer> cellCompete(int[] states, int days) { List<Integer> currentCellStates = Arrays.stream(states).boxed().collect(Collectors.toList()); return getCellStateAfterNDays(currentCellStates, days);
}
private List<Integer> getCellStateAfterNDays(List<Integer> currentCellStates, int days) { List<Integer> changedCellStates = new ArrayList<>(); int stateUnoccupied = 0; if (days != 0) { for (int i1 = 0; i1 < currentCellStates.size(); i1++) { if (i1 == 0) { changedCellStates.add(calculateCellState(stateUnoccupied, currentCellStates.get(i1 + 1))); } else if (i1 == 7) { changedCellStates.add(calculateCellState(currentCellStates.get(i1 - 1), stateUnoccupied)); } else { changedCellStates .add(calculateCellState(currentCellStates.get(i1 - 1), currentCellStates.get(i1 + 1))); } } if (days == 1) { System.out.println("days ==1 hit"); finalStates = new ArrayList<>(changedCellStates); return finalStates; } days = days - 1; System.out.println("Starting recurssion"); getCellStateAfterNDays(changedCellStates, days); } return finalStates;
}
private int calculateCellState(int previousLeft, int previousRight) { if ((previousLeft == 0 && previousRight == 0) || (previousLeft == 1 && previousRight == 1)) { // the state gets now changed to 0 return 0; } // the state gets now changed to 0 return 1;
}Here is my solution in Java:
public class Colony
{ public static int[] cellCompete(int[] cells, int days) { int oldCell[]=new int[cells.length]; for (Integer i = 0; i < cells.length ; i++ ){ oldCell[i] = cells[i]; } for (Integer k = 0; k < days ; k++ ){ for (Integer j = 1; j < oldCell.length - 1 ; j++ ){ if ((oldCell[j-1] == 1 && oldCell[j+1] == 1) || (oldCell[j-1] == 0 && oldCell[j+1] == 0)){ cells[j] = 0; } else{ cells[j] = 1; } } if (oldCell[1] == 0){ cells[0] = 0; } else{ cells[0] = 1; } if (oldCell[6] == 0){ cells[7] = 0; } else{ cells[7] = 1; } for (Integer i = 0; i < cells.length ; i++ ){ oldCell[i] = cells[i]; } } return cells; }
}Your program does not distinguish between the number of days to simulate and the number of cells.
#include <bits/stdc++.h>
using namespace std;
int* cellCompete(int* cells,int days)
{ for(int j=0; j<days; j++) { int copy_cells[10]; for(int i=1; i<9; i++) copy_cells[i]=cells[i-1]; copy_cells[0]=0;copy_cells[9]=0; for(int i=0; i<8; i++) cells[i]=copy_cells[i]==copy_cells[i+2]?0:1; } return cells;
}
int main()
{ int arr[8]={1,1,1,0,1,1,1,1}; int arr2[8]={1,0,0,0,0,1,0,0}; cellCompete(arr2,1); for(int i=0; i<8; i++) { cout<<arr2[i]<<" "; }
}Here's some sweet little python code:
def cell(arr, days): new = arr[:] #get a copy of the array n = len(arr) if n == 1: print [0] #when only 1 node, return [0] for _ in range(days): new[0] = arr[1] #determine the edge nodes first new[n - 1] = arr[n - 2] for i in range(1, n-1): new[i] = 1 - (arr[i-1] == arr[i+1]) #logic for the rest nodes arr = new[:] #update the list for the next day return new
arr = [1, 1, 1, 0, 1, 1, 1, 1]
days = 2
print cell(arr, days)You can easily do this in Javascript with few lines of code
let cells = [1,1,1,0,1,1,1,1];
let numOfDays = 2;
let changeState = (cellarr)=> cellarr.map((cur, idx, arr)=> (arr[idx-1] ||0) + (arr[idx+1] || 0)===1?1:0);
let newCells =cells;
for (let i = 0 ; i <numOfDays; i++) newCells = changeState(newCells);
console.log(newCells);This is a C# version of a possible answer. I really struggled with this for a while for some reason! I also incorporated some of Janardan's stuff above as it helped spur me in the right direction. (cheers!)
The tricky part of the question was dealing with the fact that you had to persist the state of the cell to figure out the next cell competition which I had originally tried with a second array which was messy.
Note: I chose to use the Array.Copy method as I believe it is slightly more efficient and a lot more readable than copying arrays with a for loop when reading through.
Hopefully this helps someone out in the future!
public int[] cellCompete(int[] cell, int day) { //First create an array with an extra 2 cells (these represent the empty cells on either end) int[] inputArray = new int[cell.Length + 2]; //Copy the cell array into the new input array leaving the value of the first and last indexes as zero (empty cells) Array.Copy(cell, 0, inputArray, 1, cell.Length); //This is cool I stole this from the guy above! (cheers mate), this decrements the day count while checking that we are still above zero. while (day-- > 0) { int oldCellValue = 0; //In this section we loop through the array starting at the first real cell and going to the last real cell //(we are not including the empty cells at the ends which are always inactive/0) for (int i = 1; i < inputArray.Length - 1; i++) { //if the cells below and above our current index are the same == then the target cell will be inactive/0 //otherwise if they are different then the target cell will be set to active/1 //NOTE: before we change the index value to active/inactive state we are saving the cells oldvalue to a variable so that //we can use that to do the next "cell competition" comparison (this fulfills the requirement to update the values at the same time) if (oldCellValue == inputArray[i + 1]) { oldCellValue = inputArray[i]; inputArray[i] = 0; } else { oldCellValue = inputArray[i]; inputArray[i] = 1; } } } //Finally we create a new output array that doesn't include the empty cells on each end //copy the input array to the output array and Bob's yer uncle ;)...(comments are lies) int[] outputArray = new int[cell.Length]; Array.Copy(inputArray, 1, outputArray, 0, outputArray.Length); return outputArray; }With C#
public static int[] cellCompete(int[] states, int days) { if (days == 0) return states; int leftValue = 0; int rigthValue = 0; for (int i = 0; i < states.Length; i++) { if (i == states.Length - 1) rigthValue = 0; else rigthValue = states[i + 1]; if (leftValue == rigthValue){ leftValue = states[i]; states[i] = 0; } else{ leftValue = states[i]; states[i] = 1; } } cellCompete(states, days - 1); return states; }Here is my solution in c++ using bitwise operators :
#include <iostream>
using namespace std;
void cellCompete( int *arr, int days )
{ int num = 0; for( int i = 0; i < 8; i++ ) { num = ( num << 1 ) | arr[i]; } for( int i = 0; i < days; i++ ) { num = num << 1; num = ( ( ( num << 1 ) ^ ( num >> 1 ) ) >> 1 ) & 0xFF; } for( int i = 0; i < 8; i++ ) { arr[i] = ( num >> 7 - i ) & 0x01; }
}
int main()
{ int arr[8] = { 1, 0, 0, 0, 0, 1, 0, 0}; cellCompete( arr, 1 ); for(int i = 0; i < 8; i++) { cout << arr[i] << " "; }
}I think some of the answers above could be more readable (in addition to being more efficient). Use an additional array and alternate updates between them depending on the number of days. You can return the most recently updated array, which will always be the correct one. Like this:
function cellCompete(states, days) { const newStates = []; let originalStates = true; while (days--) { changeStates( originalStates ? states : newStates, originalStates ? newStates : states, states.length ); originalStates = !originalStates; } return originalStates ? states : newStates; } function changeStates(states, newStates, len) { newStates[0] = !states[1] ? 0 : 1; newStates[len-1] = !states[len-2] ? 0 : 1; for (let i = 1; i < len - 1; i++) { newStates[i] = states[i-1] === states[i+1] ? 0 : 1; } }#include <stdio.h>
int main() { int days,ind,arr[8],outer; for(ind=0;ind<8;scanf("%d ",&arr[ind]),ind++); //Reading the array scanf("%d",&days); int dupArr[8]; for(outer=0;outer<days;outer++){ //Number of days to simulate for(ind=0;ind<8;ind++){ //Traverse the whole array //cells on the ends have single adjacent cell, so the other adjacent cell can be assumsed to be always inactive if(ind==0){ if(arr[ind+1]==0) dupArr[ind]=0; else dupArr[ind]=1; } else if(ind==7){ if(arr[ind-1]==0) dupArr[ind]=0; else dupArr[ind]=1; } else{ if((arr[ind-1]==0&&arr[ind+1]==0) || (arr[ind-1]==1&&arr[ind+1]==1)){// if its neighbours are both active or both inactive, the cell becomes inactive the next day dupArr[ind]=0; } else //otherwise it becomes active the next day dupArr[ind]=1; } } for(ind=0;ind<8;ind++){ arr[ind]=dupArr[ind]; //Copying the altered array to original array, so that we can alter it n number of times. } } for(ind=0;ind<8;ind++) printf("%d ",arr[ind]);//Displaying output return 0;
}Here is my code which i had created some months ago,
- You want to create two different arrays, because altering same array element will gives you different results.
func competeCell(cell []uint, days uint) []uint{ n := len(cell) temp := make([]uint, n) for i :=0; i < n; i ++ { temp[i] = cell[i] } for days > 0 { temp[0] = 0 ^ cell[1] temp[n-1] = 0 ^ cell[n-2] for i := 1; i < n-2 +1; i++ { temp[i] = cell[i-1] ^ cell[i +1] } for i:=0; i < n; i++ { cell[i] = temp[i] } days -= 1 } return cell
}Using c++
#include <list>
#include <iterator>
#include <vector>
using namespace std;
vector<int> cellCompete(int* states, int days)
{ vector<int> result1; int size=8; int list[size]; int counter=1; int i=0; int temp; for(int i=0;i<days;i++)//computes upto days { vector<int> result; if(states[counter]==0) { temp=0; list[i]=temp; //states[i]=0; result.push_back(temp); } else { temp=1; list[i]=temp; result.push_back(temp); } for(int j=1;j<size;j++) { if(j==size) { if(states[j-1]==0) { temp=0; list[j]=temp; //states[i]=1; result.push_back(temp); } else { temp=1; list[i]=temp; //states[i]=1; result.push_back(temp); } } else if(states[j-1]==states[j+1]) { temp=0; list[j]=temp; //states[i]=1; result.push_back(temp); } else { temp=1; list[j]=temp; //states[i]=1; result.push_back(temp); } } result1=result; for(int i=0;i<size;i++) { states[i]=list[i]; } } return result1;
}Java solution
This is solution is Java, which will work any number of Cells and any number of days .
public class Solution
{ public List<Integer> cellCompete(int[] states, int days) { List<Integer> inputList = new ArrayList<Integer>(); List<Integer> finalList = new ArrayList<Integer>(); // Covert integer array as list for (int i :states) { inputList.add(i); } // for loop for finding status after number of days. for(int i=1; i<= days; i++) { if(i==1) { finalList = nextDayStatus(inputList); } else { finalList = nextDayStatus(finalList); } } return finalList; } // find out status of next day, get return as list public List<Integer> nextDayStatus(List<Integer> input) { List<Integer> output = new ArrayList<Integer>(); input.add(0,0); input.add(0); for(int i=0; i < input.size()-2; i++) { if (input.get(i) == input.get(i+2)) { output.add(0); } else { output.add(1); } } return output; }
}I know this has been answered, but I gave it a go in Java and am pretty sure it will work for any size states array along with number of days:
public class CellCompete { public static List<Integer> cellCompete(int[] states, int days) { List<Integer> resultList = new ArrayList<>(); int active = 1, inactive = 0; int dayCount = 1; // Execute for the given number of days while (days > 0) { int[] temp = new int[states.length]; System.out.print("Day " + dayCount + ": "); // Iterate through the states array for (int i = 0; i < states.length; i++) { // Logic for first end cell if (i == 0) { temp[i] = states[i + 1] == active ? active : inactive; resultList.add(temp[i]); System.out.print(temp[i] + ", "); } // Logic for last end cell if (i == states.length - 1) { temp[i] = states[i - 1] == active ? active : inactive; resultList.add(temp[i]); System.out.println(temp[i]); } // Logic for the in between cells if (i > 0 && i < states.length - 1) { if ((states[i - 1] == active && states[i + 1] == active) || (states[i - 1] == inactive && states[i + 1] == inactive)) { temp[i] = inactive; } else { temp[i] = active; } resultList.add(temp[i]); System.out.print(temp[i] + ", "); } } dayCount++; days--; // Reset the states array with the temp array states = temp; } return resultList; } public static void main(String[] args) { int[] states = {1, 1, 0, 1, 0, 1, 0, 0}; int days = 5; // Total of 40 System.out.println(cellCompete(states, days) ); }
}Where did the people who wanted optimized solutions go?
def Solution(states, days): for i in range(days): for j in range(len(states)): if (j == 0): states[i] = states[1] elif (j == len(states)-1): states[i] = states[-2] else: states[i] = abs(states[i-1] - states[i+1]) return statesBy definition, all the cells, including non-existent ones, are in fact booleans:
var cellUpdate = (cells, days) => {
let result = [];
// update states
for(let i = 0; i < cells.length; i++) result.push((!Boolean(cells[i-1]) === !Boolean(cells[i+1])) ? 0 : 1) ;
// repeat for each day
if (days > 1) result = cellUpdate(result, days - 1);
return result;Here is the best python Solution
value=input()
n=int(input())
lst=[]
for i in value: if "1"in i: lst.append(1) elif "0" in i: lst.append(0)
for _ in range(n): store = [] for i in range(8): if i==0: store.append(lst[i+1]) elif i==7: store.append(lst[i-1]) elif lst[i-1]==lst[i+1]: store.append(0) else: store.append(1) lst=store
print(store)Scala solution:
def cellDayCompete(cells: Seq[Int]): Seq[Int] = { val addEdges = 0 +: cells :+ 0 (addEdges.dropRight(2) zip addEdges.drop(2)).map { case (left, right) => (left - right).abs }
}
def cellCompete(cells: Seq[Int], days: Int): Seq[Int] = { if (days == 0) { cells } else { cellCompete(cellDayCompete(cells), days - 1) }
}A code run with the example above can be found at Scastie
Just answered this question today and here was my solution in python3
def cellCompete(states, days):
for i in range(0, days): #this is where we will hold all the flipped states newStates = [] ''' Algo: if neigbors are the same, append 0 to newStates if they are different append 1 to newStates ''' for currState in range(len(states)): #left and right ptr's left = currState - 1 right = currState + 1 #if at beginning of states, left is automatically inactive if left < 0: if states[right] == 1: newStates.append(1) else: newStates.append(0) #if at end of states, right is automatically inactive elif right > 7: #we know there is always only 8 elems in the states list if states[left] == 1: newStates.append(1) else newStates.append(0) #check to see if neighbors are same or different elif states[left] != states[right]: newStates.append(1) else: newStates.append(0) #Set the states equal to the new flipped states and have it loop N times to get final output. states = newStates
return statesdef cellCompete(states, days): d = 0 l = len(states) while d < days: new_states = [0] * l for i in range(l): if i == 0 and states[i+1] == 0 or i == l - 1 and states[i-1] == 0: new_states[i] = 0 elif i == 0 and states[i+1] == 1 or i == l - 1 and states[i-1] == 1: new_states[i] = 1 elif states[i+1] == states[i-1]: new_states[i] = 0 else: new_states[i] = 1 states = new_states d = d + 1 return states static int[] CellCompete(int[] states, int days) { int e = states.Length; int[] newStates = new int[(e+2)]; newStates[0] = 0; newStates[e+1] = 0; Array.Copy(states, 0, newStates, 1, e); for (int d = 0; d < days; d++) { states = Enumerable.Range(1, e).Select(x => newStates[x - 1] ^ newStates[x + 1]).ToArray(); newStates[0] = 0; newStates[e + 1] = 0; Array.Copy(states, 0, newStates, 1, e); } return states; }//Here is a working solution for this problem in C#
public class HousesinSeq
{ private string _result; public string Result { get { return _result; } } public void HousesActivation(string houses, int noOfDays) { string[] housesArr = houses.Split(' '); string[] resultArr = new string[housesArr.Length]; for (int i = 0; i < noOfDays; i++) { for (int j = 0; j < housesArr.Length; j++) { if (j == 0) { if (housesArr[j + 1] == "0") { resultArr[j] = "0"; } else { resultArr[j] = "1"; } } else if (j == housesArr.Length - 1) { if (housesArr[j - 1] == "0") { resultArr[j] = "0"; } else { resultArr[j] = "1"; } } else { if (housesArr[j + 1] == housesArr[j - 1]) { resultArr[j] = "0"; } else { resultArr[j] = "1"; } } } resultArr.CopyTo(housesArr, 0); } foreach (var item in resultArr) { //Console.Write($"{item} "); _result += item + " "; } _result = _result.Trim(); }
}public class Colony { public static int[] cellCompete(int[] cell, int day) { int[] ar = new int[10]; for(int i=1; i<9; i++) { ar[i] = cell[i-1]; } while(day-- >0) { int temp = 0; for(int i=1; i<9; i++) { if(Math.abs(temp-ar[i+1])==1) { temp = ar[i]; ar[i] = 1; } else { temp = ar[i]; ar[i] = 0; } } } return ar; } public static void main(String[] args) { int[] cell = {1,0,1,1,0,1,0,1}; int day = 1; cell = cellCompete(cell, day); for(int i=1; i<9; i++) { System.out.print(cell[i]+" "); } }
}
