distance from root search of tree fails

Question!

The tree is as follows:

       (1,1)
       /   \
    (2,1)  (1,2)
    / \      / \
 (3,1)(2,3) (3,2)(1,3) 
      and onward

The root is (1,1), all values in the tree are tuples.

Where (x,y) is an element of the tree:
The leftChild will be (x+y,y)
The rightChild will be (x,x+y)

I am building a function that finds the distance from the root (1,1). I cannot build the tree from scratch as it will be too time consuming.

I have found that 1 distance from the tuple being searched for we must subtract the the max with the min. We can work backward.

     1      2
(3,2)->(1,2)->(1,1)
(3,2)->(3-2,2) = (1,2)->(1,2-1) = (1,1)
given this is always true:
if x > y:
   newtuple = (x-y,y)
   distance += 1
else if y > x:
   newtuple = (x,y-x)
   distance += 1

Yet because possible test cases can go up to even x = 10^50, this is even too slow.

So I have found a formally to find the amount of subtractions of x with y or vice versa to make a x > y change to y < x and vice versa until (x,y) = (1,1).

So X - Y(a certain amount of times, say z) will make x less than y... X - Y*z = y find z via algebra... z = (Y-X)/(-Y)

This is my code so far:

from decimal import Decimal
import math

def answer(M,F):
    M = int(M)
    F = int(F)
    i = 0
    while True:
        if M == 1 and F == 1:
            return str(i)
        if M > F:
            x = math.ceil((F-M)/(-F))
            M -= F*x
        elif F > M:
            x = math.ceil((M-F)/(-M))
            F -= M*x
        else:
            if F == M and F != 1:
                return "impossible"
        i += x
        if M < 1 or F < 1:
            return "impossible"

    return str(i)

And it's not passing some unknown test cases, yet passes all the test cases I can think of. What test cases could I be failing? Where is my code wrong?

p.s. used Decimal module, just removed from code to make more readible.



Answers

Floor division allows for no loss, but maybe -1 in error which I consider for the code below.

def answer(M,F):
    M = int(M)
    F = int(F)
    i = 0
    while True:
        if M == 1 and F == 1:
            return str(i)
        if M > F:
            x = F-M
            x = x//(-F)
            if F < M-(F*x):
                x += 1
            M -= F*x
        elif F > M:
            x = M-F
            x = x//(-M)
            if M < F-(M*x):
                x += 1
            F -= M*x
        else:
            if F == M and F != 1:
                return "impossible"
        i += x
        if M < 1 or F < 1:
            return "impossible"

    return str(i)


Try this:

for (unsigned int row = 0; row < 3; ++row)
{
    for (unsigned int column = 0; column < 3; ++column)
    {
        inFile >> image[row][column];
    }
}

Since your values are separated by "white space", which is spaces, tabs or newlines, this should work regardless of whether all values are on one line or many.

Edit 1: A safer alternative
The above assumes there is always 9 values and they are all valid integers. If something goes awry, the above won't work. The following is a more robust method.

unsigned int row = 0;
unsigned int column = 0;
bool all_values_read = false;
int value = 0;
while ((inFile >> value) && !all_values_read)
{
  image[row][column] = value;
  ++column;
  if (column >= 3)
  {
      column = 0;
      ++row;
      if (row >= 3)
      {
         all_values_read = true;
      }
  }
}


Yes, you can roll a whole lot of software into a single Docker image (GitLab does this, with one image that includes Postgres and everything else), but generalhenry is right - that's not the typical way to use Docker.

As you say, Cassandra and Kafka are dependencies for your Scala app, they're not part of the app, so they don't all belong in the same image.

Having to orchestrate many containers with Docker Compose adds an extra admin layer, but it gives you much more flexibility:

  • your containers can have different lifespans, so when you have a new version of your app to deploy, you only need to run a new app container, you can leave the dependencies running;
  • you can use the same app image in any environment, using different configurations for your dependencies - e.g. in dev you can run a basic Kafka container and in prod have it clustered on many nodes, your app container is the same;
  • your dependencies can be used by other apps too - so multiple consumers can run in different containers and all work with the same Kafka and Cassandra containers;
  • plus all the scalability, logging etc. already mentioned.


This video can help you solving your question :)
By: admin