recursion help ??

SUNIL GUTTA

13y2.3kJava

Hi everyone

I am stuck i donno were to start how to deal .. please look at the below requirement doc

Write a recursive method that counts the number of creatures on a grid. An creature is defined as a contiguous collection of 1's (connected horizontally and vertically).

Input

Max dimensions of the array

Distribution of organisms on the array

Output

The number of creatures and the layout of the grid showing the locations of the creatures.

Requirements checklist:

q Documented source code (include any assumptions you make)

Input File (in.txt)

The format of the input file is as follows: First line is the dimensions of the grid.. Then the grid containing 1s for the creatures and 0s for the spaces. The file terminates by 0 0.

5 5

0 0 0 0 0

0 1 1 1 0

0 0 0 0 0

5 5

0 0 0 0 1

0 1 1 1 0

1 0 0 0 0

0 0 0 0 0

0 0

Output File (out.txt)

Experiment # 1

Number of Creatures: 1

0 0 0 0 0

0 1 1 1 0

0 0 0 0 0

Experiment #2

Number of Creatures: 3

0 0 0 0 1

0 2 2 2 0

3 0 0 0 0

0 0 0 0 0

Cheers & best wishes

Thank you

6 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes13y ago
Accepted answer
Try this:

// Creatures.java

import java.io.*;

class Cell
{
public int value;
public int creature;
ArrayList connections = new ArrayList();
}

public class Creatures
{
public static void main(String[] args) throws IOException
{
FileInputStream in = new FileInputStream("in.txt");
BufferedReader br = new BufferedReader(new InputStreamReader(in));
PrintWriter pw = new PrintWriter("out.txt");
String line;
String[] split;
int x, y, experiment = 1;

try
{
while(true)
{
line = br.readLine();
split = line.split(" ");
x = Integer.parseInt(split[0]);
y = Integer.parseInt(split[1]); // corrected
if(x == 0 && y == 0) return; // end of file
int[][] values = new int[x][y];
br.readLine(); // skip empty line
for(int i = 0; i < x; i++)
{
line = br.readLine();
split = line.split(" ");
for(int j = 0; j < y; j++) values[i][j] = Integer.parseInt(split[j]);
br.readLine(); // skip empty line
}
findCreatures(x, y, values, experiment, pw);
experiment++;
}
}
catch(IOException e)
{
System.out.println(e);
return;
}
finally
{
br.close();
in.close();
pw.close();
}
}

static void findCreatures(int x, int y, int[][] values, int experiment, PrintWriter pw)
{
// create a 2D array of Cells corresponding to values array

Cell[][] cells = new Cell[x][y];

for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
cells[i][j] = new Cell();
cells[i][j].value = values[i][j];
}
}

// get all connected cells

for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{

if (i > 0 && cells[i - 1][j].value == 1)
{
cells[i][j].connections.add(cells[i - 1][j]);
}

if (i < x - 1 && cells[i + 1][j].value == 1)
{
cells[i][j].connections.add(cells[i + 1][j]);
}

if (j > 0 && cells[i][j - 1].value == 1)
{
cells[i][j].connections.add(cells[i][j - 1]);
}

if (j < y - 1 && cells[i][j + 1].value == 1)
{
cells[i][j].connections.add(cells[i][j + 1]);
}
}
}

int creature = 1;

for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
if (cells[i][j].value == 1 && cells[i][j].creature == 0)
{
cells[i][j].creature = creature;
addConnections(cells[i][j], creature);
creature++;
}
}
}

// print results to file

pw.println("Experiment#" + experiment);
pw.println();
pw.println("Number of Creatures: " + (creature - 1));
pw.println();

for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
pw.print(cells[i][j].creature + " ");
}
pw.println();
pw.println();
}

pw.println();
}

static void addConnections(Cell cell, int creature)
{
int size = cell.connections.size();
if( size == 0) return;
for(int i = 0; i < size; i++)
{
Cell connected = cell.connections.get(i);
if (connected.creature == 0)
{
connected.creature = creature;
addConnections(connected, creature); // recursive call
}
}
}
}
Vulpes13y ago
I suspect the problem lies with the file rather than the code.

To do anything like this you need to know exactly how the text file is laid out.

The code assumes that there will be a blank line between each pair of lines in the file as this is what there appeared to be in your opening post. If there isn't a blank line or there's more than one, then the code won't work properly.

So I'd check the file. If in fact there are no blank lines, then it's easy to adjust the code for that: just remove the 2 lines which are commented - skip empty line.
SUNIL GUTTA13y ago
Hi friend

well sometimes i hate these un-usual exceptions .. . . everything is fine .. build successful .

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 at Creatures.main(Creatures.java:53) Java Result: 1 BUILD SUCCESSFUL (total time: 0 seconds) // this is ar Creatures class

Any for loop above is doing infinate itirations or array limit overflowed ? .. i don't think so .. code looks perfect ?

any ideas for this exception ..
Vulpes13y ago
Well, I have two classes Cell and Creatures (public) in a single source file, Creatures.java.

But, if you are using the online compiler, you'll need to remove the 'public' from Creatures as we discussed in another thread.

You also need the input file, in.txt, which on my machine is in the same folder as the executable. Hopefully, you''l be able to upload this file or type it online with ideone.

However, I've just noticed that there's a missing 'import' in the code I posted (must have been a copy and paste error on my part). The imports should be :

import java.util.*;
import java.io.*;
SUNIL GUTTA13y ago
Hi

Well tried to check the code .. i can say for sure you given good code .. but there are lapses in me to understand things ,, so please help me further sorry for re-insisting

I tried your code ..
there is compiling error don't know how ..
how many classes in ur code ?
and how can I test it ? please explain in brief details details .. thanks

it also tells me " no main class found" :(
Vulpes13y ago
Just noticed a mistake in the code in that this line:

y = Integer.parseInt(split[0]);

should, of course, be:

y = Integer.parseInt(split[1]);

I've corrected it above though it made no difference to the results as x and y were the same :)