Java - Altered Fibonacci Rabbits - Java Heap Space Error

Question

Here is the situation - Fibonacci developed his recursive sequence f(n) = f(n-1) + f(n-2) by studying a pair of rabbits that reproduce every month and have another pair of rabbits that will reproduce the next month. I am altering the situation so that they do not reproduce after the first month, but after the second month instead. The numbers in my output are correct. However, my problem is that after 45 months, for some reason I am getting a Java Heap Space error. I have tried using a long and a double instead but to no avail. Please let me know what you think. Code:

import java.util.*;
import java.io.*;
import java.lang.System.*;

public class Rabbits {
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new File("rabbits.dat"));
        int numSets = Integer.parseInt(in.nextLine().trim());
        for(int curSet = 0; curSet<numSets; curSet++){
            ArrayList<Integer> population = new ArrayList<>();
            population.add(0);
            int months = Integer.parseInt(in.nextLine().trim());
            for(int i = 0; i < months; i++){
                int matured = 0;
                for(int pos = 0; pos<population.size(); pos++){
                    population.set(pos, population.get(pos)+1);
                    if(population.get(pos)>=3){
                        matured++;
                    }
                }
                for(int n = 0; n<matured; n++){
                    population.add(0);
                }
            }
            System.out.println("Months: " + months + " Population: " + population.size());
        }
    }

}

with input:

28
1
2
3
4
5
6
7
8
9
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100

and output:

--------------------Configuration: <Default>--------------------
Months: 1 Population: 1
Months: 2 Population: 1
Months: 3 Population: 2
Months: 4 Population: 3
Months: 5 Population: 4
Months: 6 Population: 6
Months: 7 Population: 9
Months: 8 Population: 13
Months: 9 Population: 19
Months: 10 Population: 28
Months: 15 Population: 189
Months: 20 Population: 1278
Months: 25 Population: 8641
Months: 30 Population: 58425
Months: 35 Population: 395033
Months: 40 Population: 2670964
Months: 45 Population: 18059374
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2245)
    at java.util.Arrays.copyOf(Arrays.java:2219)
    at java.util.ArrayList.grow(ArrayList.java:213)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:187)
    at java.util.ArrayList.add(ArrayList.java:411)
    at Rabbits.main(Rabbits.java:22)

Process completed.

Answer 1

Unfortunately, the current way you are doing this won't work. You are keeping an Integer for each rabbit. Since the number of rabbits increases rapidly, their won't be a way to hold every rabbit in an array.

Since you only need to know the ages of the rabbits, you can keep variables which represent the number of rabbits at a certain age. As each month passes, all rabbits increase in age and new rabbits are born at age 0.

This way you can keep track of the number of matured rabbits, as well as how many rabbits are in each age group.

The final population would simply be the sum of all the rabbits at different age groups.

Scanner in = new Scanner(new File("src/q22565464/rabbits.dat"));
int numSets = Integer.parseInt(in.nextLine().trim());

for(int curSet = 0; curSet<numSets; curSet++){
   int months = Integer.parseInt(in.nextLine().trim());
   // Could be converted to an array, left for clarity's sake
   long matured = 0;
   long age2 = 0;
   long age1 = 0;
   long age0 = 1;

   for(int i = 0; i < months; i++){
    // the ages of the rabbits increase with each month
       matured += age2;
       age2 = age1;
       age1 = age0;
       age0 = matured;
   }
   System.out.println("Months: " + months + " Population: " + (matured+age2+age1+age0));
}
in.close();