Sally wants all apples!

Computer Science Level 3

Sally loves apples, thus, she has an apple garden in her backyard, where she has grown $25$ apples in the shape of a square of side $5$ . She is standing in the center of the garden, i.e. $3^{\text{rd}}$ row and $3^{\text{rd}}$ column. Now, she wants to move through the garden eating apple in every square, and she won't move into square without any apple. How many ways are there in which she can eat all the $25$ apples?

Example:

If it were a $3\times 3$ garden, and Sally would have started from center, i.e. ( $2,2)$ there would be $8$ solutions as follows

$1.\ (2,2),(3,2),(3,3),(2,3),(1,3),(1,2),(1,1),(2,1),(3,1)$ $2.\ (2,2),(3,2),(3,1),(2,1),(1,1),(1,2),(1,3),(2,3),(3,3)$ $3.\ (2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2),(1,3)$ $4.\ (2,2),(2,3),(1,3),(1,2),(1,1),(2,1),(3,1),(3,2),(3,3)$ $5.\ (2,2),(1,2),(1,3),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1)$ $6.\ (2,2),(1,2),(1,1),(2,1),(3,1),(3,2),(3,3),(2,3),(1,3)$ $7.\ (2,2),(2,1),(1,1),(3,2),(3,3),(2,3),(1,3),(1,2),(1,1)$ $8.\ (2,2),(2,1),(1,1),(1,2),(1,3),(2,3),(3,3),(3,2),(3,1)$

The answer is 456.

3 solutions

Arulx Z
Sep 16, 2015

I used recursion to solve the problem. The code might look a bit scary so here's the working -

For simplicity, consider this array. Each individual members of the array are called cell (for no special reason) -

1,  2,  3,  4,  5,
6,  7,  8,  9,  10,
11, 12, 13, 14, 15,
16, 17, 18, 19, 20,
21, 22, 23, 24, 25

The method neighbours takes an cell as input and returns the neighbors of that cell. If you add 5 to a cell, you will get the cell to the bottom of the original cell. If you add -5, then you get the top cell. For 1 and -1, it's right and left respectively.

In the method recursion , I look for neighbors of a cell. Let say array $N$ has neighbours of any cell $x$ . First I look at neighbors of $N$ then neighbours of neighbours of $N$ and then neighbours of neighbours of neighbours of $N$ and so on. When the recursion method is called exactly 25 times by and cell, then I count that cell because that cell satisfies the condition. This way, I count the number of ways.

Java code:

import java.util.ArrayList;
import java.util.List;

class brilliant {
    private static int count = 0;
    private static int matrix[][] = new int[5][5];

    public static void main (String args[]){
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                matrix[i][j] = 0;
        matrix[2][2] = 1;
        recursion(matrix, 13, 0);
        System.out.println(count);
    }

    private static void recursion(int mx[][], int cell, int step){
        if (step < 24){
            for(int x : neighbours(cell, matrix)){
                int coords[] = ntc(x);
                mx[coords[1]][coords[0]] = 1;
                recursion(mx, x, step + 1);
                mx[coords[1]][coords[0]] = 0;
            }
        } else
            count += 1;
    }

    private static List<Integer> neighbours(int n, int mx[][]){
        List<Integer> list = new ArrayList<>();

        if (n - 5 >= 1 && (Math.floor((n - 1) / 5) == (Math.floor((n - 5 - 1) / 5) + 1))){ //top one
            int coords[] = ntc(n - 5);
            if(mx[coords[1]][coords[0]] == 0)
                list.add(n - 5);
        }
        for(int i : new int[]{-1, 1}){  //middle 2
            if (n + i >= 1 && n + i <= 25 && Math.floor((n - 1) / 5) == Math.floor((n + i - 1) / 5)){
                int coords[] = ntc(n + i);
                if(mx[coords[1]][coords[0]] == 0)
                    list.add(n + i);
            }
        }
        if (n + 5 <= 25 && Math.floor((n - 1) / 5) == Math.floor((n + 5 - 1) / 5) - 1){ //bottom one
            int coords[] = ntc(n + 5);
            if(mx[coords[1]][coords[0]] == 0)
                    list.add(n + 5);
        }
        return list;
    }

    private static int[] ntc(int n){ //convert numerical index to coordinates. Index is 1 and [0, 0].
        int y = (int) Math.floor((n - 1) / 5);
        return new int[]{(int) (n - 5 * y - 1), (int) y}; //x, y. x, y = [0, 0] at top left
    }
}

Time taken is about 0.09 secs.

Moderator note:

Great job on the timing. It would be helpful to other users to illustrate your algorithm at work on a smaller grid for several starting positions.

0.09 seconds is quite nice for this!

Pranjal Jain - 5 years, 9 months ago

Thanks! Earlier I was assuming that Sally can pass through diagonals too but I fixed it after reading the example.

Arulx Z - 5 years, 9 months ago

The DFS I wrote is 0.003 seconds. Although it says sys time is 0.000 but I don't know what to make of that.

Jorge Fernández - 5 years, 8 months ago

@Jorge Fernández – Basic functionality of code is same though. The difference is possibly due to C++.

Arulx Z - 5 years, 7 months ago

Abdelhamid Saadi
Sep 15, 2015

My solution in python 3.4:

garden = {}
voisins = {}
ariane = []
nbpaths = 0
taille = 0
def initgarden(n):
    for i in range(1, n+1):
        for j in range(1, n+1):
            garden[(i,j)] = True
    for i in range(1, n+1):
        for j in range(1, n+1):
            voisins[(i,j)] = [x for x in [(i+1, j), (i-1,j), (i,j+1), (i, j-1)] if x in garden]

def godeep(x, n):
    global nbpaths, taille
    if n == taille*taille : nbpaths += 1 
    garden[x] = False
    ariane.append(x)
    for y in voisins[x]:
        if garden[y]:
            godeep(y, n + 1)
    x = ariane.pop()
    garden[x] = True

def solve(n):
    "Sally wants all apples!"
    global taille
    initgarden(n)
    taille = n
    godeep((n//2 + 1 , n//2 + 1), 1)
    return nbpaths

print(solve(5))

Jorge Fernández
Sep 9, 2015

We can solve this using Depth First Search. Here is the C++ code I wrote:

#include <cstdio>
int grid[5][5];
int a,b,k,r;
void find(int x,int y){
  grid[x][y]=1;
  k++;
  if(k==25){
    r++;
  }
  if(x-1>=0 && grid[x-1][y]==0){
    find(x-1,y);
  }
  if(x+1<5 && grid[x+1][y]==0){
    find(x+1,y);
  }
  if(y-1>=0 && grid[x][y-1]==0){
    find(x,y-1);
  }
  if(y+1<5 && grid[x][y+1]==0){
    find(x,y+1);
  }
  grid[x][y]=0;
  k--;
}
int main(){
  int m,n;
  find(2,2);
  printf("%d\n",r);
}

I can't help but notice the declaration of unused variables. Why'd you do that?

Agnishom Chattopadhyay - 5 years, 9 months ago

When I wrote it it solved for a more general case and then I manually substituted the values of the variables into the code, so those variables disappeared from the body.

Jorge Fernández - 5 years, 8 months ago

Sally wants all apples!

The answer is 456.

3 solutions

Moderator note:

1 pending report

Vote up reports you agree with