Looking for a specific post? Checkout the Blog Index.
Mar 1st, 2019 - written by Kimserey with .
Working with trees is an interesting task. Today we will look into the Basket of Apples problem, which can be solved using a tree structure. This deep dive will allow us to explore how we can reason around trees and understand concepts allowing us to vocalize ideas.
Consider the following Basket of Apples problem:
We have four apple baskets with exactly ten apple-slots per basket. With an iterative basket filling process, we start by placing apples in basket A, then once basket A is full, we move to basket B, then basket C, and so on until we either no longer have any apples, or the slots have all been filled, or we reached the limit of slots available.
In this example, limits of slots available are imposed on the amount of apples present between basket A and basket B, and between basket C and basket D. This link is also referred as limit node.
And lastly we want to be able to impose a limit on top of the limit nodes, which would act as a parent limit node for all child baskets.
In this example, we have
basket A and
basket B linked with
limit 2, and we have
basket C and
basket D linked with
Limit 2 and
limit 3 are themselves linked via
limit 1. Those limits introduce the following rules:
basket B(due to
basket D(due to
While each baskets have a dedicated slot amount, the limit linking baskets introduces an implicit slot amount. For example, on the subtree between
basket B, and
If ten apples are placed in
basket A, the implicit slot on
basket A and implicit limit imposed by
limit 2, from the point of view of
basket B, is zero.
limit 2, we are no longer able to accept apples in
basket B as
basket A used up to the limitation specified. In other word,
basket B has ten slots but has an implict slot value of zero.
In the previous example, we have seen that
basket B has an implicit slot value of zero, and conversely,
limit 2 has an implicit limit of zero from the point of view of
Point of view refers to the standpoint taken to calculate the implicit values of the graph. For example, in the previous subtree, the orange nodes were from the standpoint of
basket B standpoint,
limit 2 was zero as all the apples were in
basket A. But if we take the standpoint of
basket A, then
basket A slots is ten and
limit 2 implicit slots is ten.
This example demonstrates the existence of multiple perspectives for this particular graph. Each basket has its own perception of the graph, and depending on which basket standpoint we are looking at, the computation of the implicit limits will be different.
Taking a lesser trivial example, we place 5 apples in
From the point of view of
basket A, the implicit slots and limit remain ten.
But from the point of view of
basket B, the implicit slots have decreased to five due to the implicit limit which decreased to five as well.
Taking the concept of implicit slots and point of view, we can apply it to the whole graph, considering the initial with then apples in
basket A, the implicit limit on
basket C would be five:
The ten apples placed in
basket A have reduced the top parent
limit 1 from fifteen to five, resulting in the implicit
basket C slots being reduced to five (
limit 3 is bypassed as
limit 1 < limit 3).
The computation of a limit can be expressed from the point of view of a basket:
The implicit limit of a particular $limit$ from the point of view of $basket\,x$ is computed by taking its $limit$ and substracting the sum of its children baskets amount of $apples$.
limit 1, from the point of view of
basket C, the equation becomes:
From the point of view of
basket C, the limit imposed by
limit 1 is five.
Lastly the computation of the implicit slots on a basket can be represented as:
Continuing on the point of view of
basket C, we can substitute the variables:
If from here, we place five more apples in
basket C, by following those two formulas, we can quickly compute the implicit slots and limits from the point of view of
We can compute, from the point of view of
limit 3, and the implicit slots of
And we can see that the result of the computation is five as we expected.
Today we saw how we could solve through mathematical equations the Basket of Apples problem. We started by exploring different scenarios of the problem which we used as basis to test our logic. We then moved on to define the concept of implicit value and point of view which were necessary to discuss about the solution. Lastly we completed the post by extraction mathematical equations from the scenarios which if followed, yield the expect result. I hope you liked this post and I’ll see you on the next one!