I was solving this problem:
Given a tetrahedron with vertices A, B, C and D. An ant is standing at vertex D. The ant won't sit idle. It will keep on moving from one vertex to another along some edge of the tetrahedron. Your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps.
So for input 2 Output : 3
I was able to solve this comfortably using recursion the following way. But it seems not very efficient for a large input, say, 15 because of its time complexity.
This can be solved through dynamic programming but I don't see any scope of memoization in my current approach. Maybe I need to change the approach. So appreciate any help.
I would like to solve it using recursion + memoization
var count = 0;
function recursion(n, arr=['d']){
if(n <=1) return 0;
if(arr.length === n+1 && arr[arr.length-1] ==='d'){
console.log(arr.join(" -> "))
count++;
return;
}
if(arr.length > n+1) return;
for(let el of ['a', 'b', 'c', 'd']){
if(arr[arr.length-1] != el){
recursion(n, [...arr, el]);
}
}
}
recursion(3)
console.log(count);You can indeed use memoization here.
First let's analyse the recurrence relationships.
Define:
𝑆𝑛 to be the number of paths of length 𝑛 to go from a vertex to itself.
𝐷𝑛 to be the number of paths of length 𝑛 to go from one vertex to a chosen different one. It doesn't matter which destination vertex we choose, since the tetrahedron is completely symmetric.
Now the recurrence relationships:
To get the number of paths of length 𝑛 to the original vertex (𝑆𝑛), you can choose a neighbor from three neighbors and then count the number of (shorter) paths from there back to the start vertex, which is given by 𝐷. So:
𝑆𝑛 = 3𝐷𝑛−1
To get the number of paths of length 𝑛 to a different vertex (𝐷𝑛), you can either choose that neighbor and count the number of (1 step shorter) paths from there to itself, or you can choose one of the other two neighbors and count the number of (1 step shorter) paths from there to the target vertex. So:
𝐷𝑛 = 𝑆𝑛−1 + 2𝐷𝑛−1
The latter equation can be expanded by substitution to this recurrence relationship:
𝐷𝑛 = 3𝐷𝑛−2 + 2𝐷𝑛−1
As we reference 𝑛−2, we need to have at least two base cases:
As we have a nice recurrence relationship for 𝐷, we could first implement a function that returns the number of paths from one vertex to another one. And then use the first relation to translate the original query (for the number of paths to the same vertex) into that problem:
// Memoize the number of paths from one vertex to a different one
const memo = new Map().set(0, 0).set(1, 1);
function numPathsToOther(size) {
let result = memo.get(size);
if (result === undefined) {
result = 3*numPathsToOther(size-2) + 2*numPathsToOther(size-1);
memo.set(size, result);
}
return result;
}
function numPathsToSelf(size) {
return size ? 3 * numPathsToOther(size - 1) : 1;
}
// Demo runs for the first few path-sizes:
for (let i = 0; i <= 10; i++) {
console.log(i, numPathsToSelf(i));
console.log((3*0^i-(-4)^i)/4)
}Let's say we label the four vertices as 𝑎, 𝑏, 𝑐, and 𝑑 as you did, and that 𝑛 is 3. We want to know the number of paths of size 𝑛 that start and end in vertex 𝑎.
There are three ways to start that path: 𝑎→𝑏, 𝑎→𝑐 or 𝑎→𝑑. Let's take 𝑎→𝑏. Now we need to know how many paths there are of size 2 that start in 𝑏 and end in 𝑎.
Here, let's stop for a minute. You can get to the realisation that there is nothing special about 𝑎 and 𝑏. They are just neighbors, but here it comes: any two vertices in a tetrahedron are neighbors, and relate to each other in the same way as 𝑎 to 𝑏. So we can generalise this case as "the number of paths from one vertex to another"!
For the case where the size of such path needs to be 2, there are only two possible paths from 𝑏 that end in 𝑎: either we go via 𝑐, or we go via 𝑑.
Now we go back to the initial situation. We said that paths of size 3 from 𝑎 back to 𝑎 could pass first via 𝑏, and now we know that from 𝑏 there are two possibilities. But we could also have gone from 𝑎 to 𝑐, or from 𝑎 to 𝑑. And as the tetrahedron is completely symmetric we can immediately conclude that also those two alternatives each represent 2 paths. So in total we have found 3x2=6 paths.
This little analysis shows that it is useful to know what the number of paths are from some vertex to another vertex.
The recurrence relationship has a solution. oeis.org provides it:
Number of closed walks of length n along the edges of a tetrahedron based at a vertex.
FORMULA a(n) = (3^n + (-1)^n*3)/4.
for (let i = 0; i <= 10; i++) {
console.log(i, (3**i + (-1)**i*3)/4)
}