Emergency task#
I face this task while solving the Yandex “algorithms trainings part one” course on home work for first lesson.
Problem condition#
An ambulance crew went on a call to a segregated neighbourhood. Unfortunately, when the dispatcher received the call, he only had time to write down the house address and the number of flat \(K_1\), and then the connection was cut off. However, he remembered that at the same house address some time ago an ambulance had travelled to flat \(K_2\), which is located in entrance \(P_2\) on floor \(N_2\). It is known that there are \(M\) floors in the house and the number of flats on each landing is the same. Write a programme that calculates the number of staircase \(P_1\) and the number of floor \(N_1\) of flat \(K_1\).
Input format \(K_1\), \(M\), \(K_2\), \(P_2\), \(N_2\) one after the other. All positive.
The programme returns \(N_1\) and \(P_1\).
If there are multiple options for a result, you must return \(0\).
If the numbers passed are wrong, you must return -1 -1.
Theoretical ideas#
Basic#
The task was quite difficult (I wasn’t the only one). Therefore, I will describe some theoretical calculations that will help in solving it.
Sometimes I use preudographic schemes for clarity, where each row is a staircase, [n] is an apartment with the number \(n\), the symbol | separates different staircases. So 2 stored buildings with 2 staircases and 2 flats on the floor will look like this:
[3][4] | [7][8]
[1][2] | [5][6]
\(M*(P_2-1)\) - number of stairwells on all previous staircases.
The number of stairwells in flat 2, including all the staircases of the previous staircases, which we will call \(T_2\), can be calculated as follows:
But there are special cases associated with this number, we have only mentioned them here, they will be discovered more precisely in the following subsections:
\(T_2 = 1\) - means that flat with known parameters is located on the ground floor of the first entrance;
\(T_2 > K_2\) - means that a flat with the given parameters can’t exist.
Let \(G\) be the number of dwellings on a stairwell - actually it’s a crusical number for our task.
Let’s express a pair of quantities with this number:
\(T_2*G\) - number of the last flat on the same staircase as flat 2 (it could actually be flat 2);
\((T_2-1)*G\) - number of the last flat on the previous staircase as flat 2.
So \(G\) is the integer that must satisfy the following conditions:
Now let us solve the inequalities with respect to \(G\):
So \(G\) can take all integers between \(G_{min}=\lceil K_2/T_2 \rceil\) and \(G_{max}=\lceil K_2/(T_2 - 1) \rceil - 1\), including both.
But there are some cases where we need to consider the values entered:
\(G_{min}=G_{max}\) - the best option - we have only one possible \(G\) and as a result of only one possible and guaranteed solution;
\(G_{min} < G_{max}\) means that there are several possible numbers of flats on a stairwell. But actually that doesn’t mean we can’t unambiguously define \(P_1\) or \(N_1\) or even both of them. Read more in one of the next following subsections;
\(T_2 = 1\) makes \(G_{max}\) is underfined. The algebra here just follows the logic of life (as always, really). \(T_2-1=0\), which makes the denominator in \(G_{max}\) equal to zero. And just think - if flat 2 is on the first staircase, you won’t understand how many flats are on the staircase, because there can be any number of flats on the same staircase behind \(K_2\). But you have to remember that if \(K_1<K_2\) we don’t need to find \(G_{max}\) - \(K_1\) is on the first staircase as well as \(K_2\);
\(G_{min} > G_{max}\) - means that apartment number \(K_2\) on stariwell \(T_2\) can’t exist. Read more in one of the following subsections;
Now suppose we have chosen some value for \(G\). We can calculate solutions for this G using formulas:
\(T_2 = 1\)#
It means that the apartment with known parameters is on the first floor of the first staircase. The main challenge here is that we can’t determine \(G\), because it can be any number of flats behind flats with known parameters in the same staircase.
Consider the example with parameters \(M=3, K_2=5, P_2=1, N_2=1\) - different \(K_1\) can lead to different special cases, so it’s set for each case.
\(K_1 = 3 \Rightarrow K_2 > K_1\) there are no way for second flat to be any where except first floor of first staircase, so the answer have to be \(P_1=1, N_1=1\);
\(K_1 = 6\) we cannot define \(G\), but we can be sure that it is not less than \(K_2\), since there are at least \(K_2\) apartments on the first floor, it guarantees that there are not more than \(K_2M\) apartments in the first staircase, so if \(K_1 \leq K_2M\) it guarantees that the apartment we are interested in is in the first staircase, but we still cannot define the floor of the apartment we are interested in so the answer should be \(P_1=1, N_1=0\);
\(K_1 = 50 \Rightarrow K_1 > K_2M\) we can’t define anything so the answer have to be \(P_1=0, N_1=0\).
\(T_2 > K_2\)#
Consider case \(K_1=11\), \(M=10\), \(K_2=2\), \(P_2=3\), \(N_2=3\).
\(T_2 = 10*2 + 3 = 23\)
And what have we got? A 2nd flat on the 23rd stairwell? No sense! There must be at least one flat on each stairwell, which can be written formally as \(T_2 > K_2\).
So if the condition \(T_2 > K_2\) isn’t complete, we have to return -1, -1.
\(G_{min} < G_{max}\)#
Probably the easiest case I foud: \(M=3, K_2 = 4, P_2 = 1, N_2 = 2\).
In these conditions there are two possible option for number of flats on the straiwell.
If \(G=2\), apartment with number \(K_2=4\) can be the second apartment on the second staircase. As in the pseudographic scheme below:
[5][6] | [11][12] | [17][18]
[3][4] | [ 9][10] | [15][16]
[1][2] | [ 7][ 8] | [13][14]
But even if \(G=3\), such an apartment still exists as the first apartment of the second stairwell:
[7][8][9] | [16][17][18] | [25][26][27]
[4][5][6] | [13][14][15] | [22][23][24]
[1][2][3] | [10][11][12] | [19][20][21]
Using different values of G, we can calculate \(P_1\) in \(N_1\) using formulas \((1), (2), (3)\), assuming there are \(G\) apartments on the stairwell.
So from this point everything depends on \(K_1\) - in some cases the problem can be solved unambiguously, in others there may be some uncertainty.
Option1 - one solution. Suppose \(K_1=2\) in case both cases \(N_1=1, P_1=1\).
Option2 - uncertain floor. Suppose \(K_1=6\) in case \(G = 2 \rightarrow N_1 = 3\), but in case \(G=3\rightarrow N_1 = 2\), but the number of stairs in both cases take the same number \(P_1 = 1\). So the answer must be \(P_1=1\), \(N_1=0\).
Option3 - uncertain both. Suppose \(K_1=9\) in case \(G=2 \rightarrow N_1=2, P_1=2\), but in case \(G=3 \rightarrow N_1=1, P_1=3\). So both \(N1\) and \(P_1\) take different values in different cases. So the answer must be \(P_1=0\), \(N_1=0\).
Option4 - uncertain staircase. Suppose \(K_1=15\), in case \(G=2 \rightarrow P_1=2\) but in case \(G_2=3 \rightarrow P_1=3\) but the floor can only be determined one way \(N_1 = 2\). So the final answer must be \(P_1=0\) , \(N_1=2\).
So the best solution I have found so far is to try all possible values of \(G\) and see what values of \(N_1\) and \(P_1\) we get.
\(G_{min} > G_{max}\)#
Some combinations for \(K_2\), \(N_2\), \(P_2\) are impossible - some flats can’t exist on some stairwells. For example flat with number \(K_2 = 6\) can’t exist on stairwell with number \(T_2 = 4\). The simpliest example here is \(M=10\), \(K_2=6\), \(N_2=4\), \(P_2=1\).
Suppose \(G=1\) then we will have schema:
[6]
[5]
[4]
[3]
[2]
[1]
So apartment six is on the sixth floor, which is more than the specified \(N_2=4\).
Ok let’s try \(G=2\). Schema is below:
[5][6]
[3][4]
[1][2]
So here is a flat with known parameters on the 3rd floor, which is less than the given \(N_2=4\). And increasing \(G\) will only make things worse.
There are no options for \(G\) that satisfy the given conditions.
Solution description#
Finally let’s describe final solution.
\(M < N_2\) means that the second apartment is on a higher floor than the one in the house under consideration - so we have to return (-1, -1) in this case. I’m not sure about this point, maybe it’s always \(G_{max} < G_{min}\) in case \(M < N_2\) - it has to be proved or rejected;
Compute \(T_2 = M*(P_2-1)+N_2\);
If \(T_2 > K_2\) we have to return (-1, -1);
If \(T_2=1\):
If \(K_1 \leq K_2\) return (1, 1);
If \(K_1 > K_2\) and \(K_1 \leq K_2M\) return (1, 0);
If \(K_1 > K_2M\) return (-1, -1);
Compute \(G_{min}=\lceil K_2/T_2 \rceil\) and \(G_{max}=\lceil K_2/(T_2 - 1) \rceil - 1\);
If \(G_{min} < G_{max}\);
We need to try all options for \(G = \overline{G_{min}, G_{max}}\) and compute follwoing numbers:
\(T_1 = \lceil K_1/G \rceil\);
\(P_1=\lceil T_1/M \rceil\);
\(N_1 = T_1 - (P_1-1)M\);
If for each \(G\) we got same values of \(P_1\) and \(N_1\) - return them;
If for different \(G\) there are different \(P_1\) or \(N_1\) or both, we have to retrun 0 for the corresponding value;
If \(G_{min} \geq G_{max}\) return (-1, -1).
Python implementation#
The program from the following cell describes the python implementation of the task. The input to the program is \(K_1, M, K_2, P_2, N_2\) in one line, separated by spaces. The output of the programme is \(P_1\), \(N_1\) separated by a space.
%%writefile emergency_task_files/solution.py
from math import ceil
def get_P_N(K, G, M):
'''
Calculate the number of stairs (P) and the floor (N)
of the flat using information about it's number (K)
number of flats on the stairwell (G) and number
of floors in the building.
Paramters
---------
G : int
number of flats on the stairwell'
flatno : int
number of the flat;
M : int
numver of flats in the house;
Returns
---------
P : int
staircase number for
the apartment in question;
M : int
floor number of the flat.
'''
# The number of stairwells,
# including all the staircases
# of the previous staircases
T = ceil(K/G)
P = ceil(T/M)
N = T - (P-1)*M
return P, N
def potential_transformation(curr, pot):
'''
Transformate potential value to real value.
If current value isn't defined we need to replace
it with potential value.
If there is current value and it differs from
potential value we have uncertainty that means
that we need to replace current value with 0.
Parameters
----------
curr : int
current value;
pot : int
potential value;
Returns
----------
out : int
new current value.
'''
if curr is None:
return pot
elif curr!=pot:
return 0
return curr
def sol(K1, M, K2, P2, N2):
# if second flat is higher
# than possible
if N2 > M:
return (-1, -1)
# The number of stairwells in flat 2,
# including all the staircases of the
# previous staircases
T2 = M*(P2 - 1) + N2
# one more impossible case
if T2 > K2:
return (-1, -1)
P1 = None
N1 = None
if T2 > 1:
G_min = ceil(K2/T2)
# In the description I wrote
# formula G_max = ceil(K2/(T2-1))-1
# but in the Python3 implementation it's
# easier to use such formula - because
# the `range` function, which doesn't include the
# last value.
G_max = ceil(K2/(T2-1))
# Here is greater or equal because if
# we didn't subtract one from G_max
if G_min >= G_max:
return -1, -1
for G in range(G_min, G_max):
# Calculate such values of P and N
# that satisfy K1, G and M
# but are not yet potential values
pot_P1, pot_N1 = get_P_N(K1, G, M)
# if P1 is not defined yet we fill it
# with new value
P1 = potential_transformation(P1, pot_P1)
N1 = potential_transformation(N1, pot_N1)
# The following cases are checked
# when T2 = 1
elif K1 <= K2:
# This case is used when
# the second flat is on the first floor
# of the first staircase and
# and the first flat has a lower number.
# All the above guarantees that
# the first flat is on the first floor of the
# of the first staircase.
P1=1;N1=1
elif K1 < M*K2:
# This case is used when
# the second flat is on the first floor
# of the first staircase and
# the first flat has a greater number.
# But not great enought to be in the other
# staircase - so we can't define floor of
# the flat but staircase sertainly 1.
P1=1;N1=0
else:
# This case is used when
# the second flat is on the first floor
# of the first staircase and
# the first flat has a greater number.
# We can't define how many flats there are
# above the second flat on the same
# staircase, so the parameters of the
# first flat cannot be defined.
P1=0;N1=0
if M==1 and N1==0:
# If we have decided in a previous step that
# that number of floor is underdefined. If there is
# only one floor in the building, we can be
# be sure that the first apartment is on the first floor.
N1 = 1
return P1, N1
if __name__ == "__main__":
print(" ".join(map(str,
sol(*map(int, input().split(" ")))
)))
Overwriting emergency_task_files/solution.py
Here is some unittests for program in the previous cell:
%%writefile emergency_task_files/test.py
import unittest
from solution import sol, potential_transformation
class Test(unittest.TestCase):
def test_sol(self):
'''
Testing main function of the solution
'''
cases = [
# just basic case
({'K1': 89, 'M': 20, 'K2': 41, 'P2': 1, 'N2': 11}, (2, 3)),
# the known flat on the first cell
# but there's only one floor so it's safe
# you can go ahead and
({'K1': 11, 'M': 1, 'K2': 1, 'P2': 1, 'N2': 1}, (0, 1)),
# the known flat in the second entrance
# of a one-storey building
({'K1': 11, 'M': 1, 'K2': 3, 'P2': 2, 'N2': 1}, (6, 1)),
# T2 > K2
({'K1': 3, 'M': 2, 'K2': 2, 'P2': 2, 'N2': 1}, (-1, -1)),
# we can't define G because there can be any
# number of flats befind any flat on the first
# stairwell of the first staircase and K1>K2
({'K1': 11, 'M': 2, 'K2': 1, 'P2': 1, 'N2': 1}, (0, 0)),
# we can't define G because there can be any
# number of flats behind any flat on the first
# staircase, but K1<K2 which guarantees that the second
# apartment is on the first staircase
({'K1': 3, 'M': 3, 'K2': 5, 'P2': 1, 'N2': 1}, (1, 1)),
# we can't define G and number of stairswells, but number
# of the dwelling in question is not large enough
# to be in the next staircase
({'K1': 10, 'M': 3, 'K2': 5, 'P2': 1, 'N2': 1}, (1, 0)),
# G_min < G_max
({'K1': 15, 'M': 10, 'K2': 31, 'P2': 4, 'N2': 20}, (-1, -1)),
# the following group of cases checking
# belongs to pattern when G_min > G_max
# one solution
({'K1': 2, 'M': 3, 'K2': 4, 'P2': 1, 'N2': 2}, (1, 1)),
# several cases for N
({'K1': 6, 'M': 3, 'K2': 4, 'P2': 1, 'N2': 2}, (1, 0)),
# this is specific subcase for several N
# there is G_max - G_min = 3 so there are
# several iterations of the solution-finding loop
# and K1 selected in such way to make algo try to
# replace 0 with potential value
({'K1': 14, 'M': 3, 'K2': 18, 'P2': 1, 'N2': 3}, (1, 0)),
# several cases for both
({'K1': 9, 'M': 3, 'K2': 4, 'P2': 1, 'N2': 2}, (0, 0)),
# several cases for P
({'K1': 15, 'M': 3, 'K2': 4, 'P2': 1, 'N2': 2}, (0, 2)),
# N2>M flat is higher than maximum floor
({'K1': 11, 'M': 1, 'K2': 5, 'P2': 1, 'N2': 2}, (-1, -1)),
# G_min > G_max
({'K1': 13, 'M': 2, 'K2': 6, 'P2': 2, 'N2': 2}, (-1, -1))
]
for k, c in cases:
self.assertEqual(sol(**k), c, msg=str(k))
def test_potential_transformation(self):
'''
Tests for funtion `potential_transformation`.
I caught a bug in this function.
'''
cases = [
# a case where ambiguity of judgement
# has already been established
# and funtion have to return zero again
({"curr":0, "pot": 10}, 0),
# if we trying to replace curr with
# the same value we have ot leave same value
({"curr":10, "pot":10}, 10),
# if curr isn't defined yet we have
# to set it with potential value
({"curr":None, "pot":10}, 10),
# if curr was set and we found
# another potential value - return
# marker of ambiguity
({"curr":10, "pot":9}, 0)
]
for arg, ret in cases:
self.assertEqual(potential_transformation(**arg), ret, msg=str(arg))
Overwriting emergency_task_files/test.py
Ok now let’s try to run gotten unitests.
%%bash
cd emergency_task_files
python3 -m unittest test
..
----------------------------------------------------------------------
Ran 2 tests in 0.000s
OK