Python Advanced Modular Arithmetic Algorithm

Question

I have this program:

#!/usr/bin/python3
def bounce(modulo: int, here: int, add: int) -> int:
    # additive version
    # modulo = 2n > 0, 0 <= here < n, add is any integer
    # cycle {
    #   {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
    #    0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
    #   {0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...,
    #    0, 1, 2, 3, ..., n - 1, n - 2, n - 3, ...},
    #   ...
    # }
    tmp = abs(here + add) % (2 * modulo)
    if tmp <= modulo:
        tmp *= -1
        tmp -= 1
    tmp %= modulo
    return tmp


m = abs(int(input('Modulus: '))) + 1
i = abs(int(input('Iterate: '))) + 1

h: int = 0
m2: int = 3 * m

for x in range(1, 1 + i):
    print(h, end = ('\n' if x % m2 == 0 else ', '))
    h = bounce(m, h, 1)

input('Done.')

For some reason, niether the bounce() function or its testing code is working. I don't know why. For example, if I enter 6 for the modulus and 4 for the iteration variable i, the program should print 5 lines of 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0. Instead, I'd be seeing 2 lines of 6, 0, 6, 0, .... The answer is likely simple. I've just bashed my brains against this bounce() function so many times that I can't see it. The signage of the add parameter is tripping me up.

Answer 1

You probably do not need to generate the entire sequence, following is an implementation of a closed form that calculates and returns the index in a sequence of a given size you wish to iterate over in a go-and-back cycle fashion:

You can start at any point in time, including the past (negative time), and obtain where in the sequence (index) you are, without the need to iterate or build the entire sequence.

def bounce_back_and_forth(size: int, start_t: int=0)->int:
    """returns the index position in a sequence at time t=t, when the index starts
    at position zero at time t=0, and walks the list from end to end, and and bounces
    back and forth.
    returns the index for all t in Z

    @param size: int, the size of the sequence to iterate over
    @param start_t: int, the starting indice (usually time), zero by default
    :return: the index in the sequence corresponding to the start_t provided

    closed form, no iteration necessary --> O(1) time & space complexity

       size=5                     size=5                    size=5
       start at t=0               start at t=6              start at t=-1 and decreases
     0 [0, _, _, _, _]         6 [_, _, 2, _, _]        -1 [_, _, _, _, 4]
     1 [_, 1, _, _, _]         7 [_, 1, _, _, _]        -2 [_, _, _, 3, _]
     2 [_, _, 2, _, _]         8 [0, _, _, _, _]        -3 [_, _, 2, _, _]
     3 [_, _, _, 3, _]         9 [_, 1, _, _, _]        -4 [_, 1, _, _, _]
     4 [_, _, _, _, 4]        10 [_, _, 2, _, _]        -5 [0, _, _, _, _]
     5 [_, _, _, 3, _]        11 [_, _, _, 3, _]        -6 [_, 1, _, _, _]
     6 [_, _, 2, _, _]        12 [_, _, _, _, 4]        -7 [_, _, 2, _, _]
     7 [_, 1, _, _, _]        13 [_, _, _, 3, _]        -8 [_, _, _, 3, _]
     8 [0, _, _, _, _]        14 [_, _, 2, _, _]        -9 [_, _, _, _, 4]
     9 [_, 1, _, _, _]        15 [_, 1, _, _, _]       -10 [_, _, _, 3, _]
    10 [_, _, 2, _, _]        16 [0, _, _, _, _]       -11 [_, _, 2, _, _]
    """

    go_and_back = size * 2 - 2

    if start_t < 0:
        start_t = size - abs(start_t) % go_and_back

    tdx_at_start_t = start_t % go_and_back
    if tdx_at_start_t >= size:
        tdx_at_start_t = go_and_back - tdx_at_start_t

    return tdx_at_start_t


if __name__ == '__main__':

    # tests
    res = [0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1]
    for idx in range(18):
        actual, expected = bounce_back_and_forth(5, start_t=idx), res[idx]
        assert actual == expected

    stride = 0
    for _ in range(5):
        mod = 8  # the size of the sequence to iterate over
        start = 0
        stride += 1
        print(f'size: {mod}, stride: {stride} -> ', end='')
        for tdx in range(start, 20, stride):  # <-- get indices for 20 time steps ahead
            print(bounce_back_and_forth(mod, tdx), end=' ')
        print()

output:

size: 8, step: 1 -> 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0 1 2 3 4 5 
size: 8, step: 2 -> 0 2 4 6 6 4 2 0 2 4 
size: 8, step: 3 -> 0 3 6 5 2 1 4 
size: 8, step: 4 -> 0 4 6 2 2 
size: 8, step: 5 -> 0 5 4 1 

tests:

class TestBounceBackAndForth(unittest.TestCase):

    def test_size5_t0(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=0), 0)

    def test_size5_t3(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=3), 3)

    def test_size5_t4(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=4), 4)

    def test_size5_t5(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=5), 3)

    def test_size5_t6(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=6), 2)

    def test_size5_t7(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=7), 1)

    def test_size5_t8(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=8), 0)

    def test_size5_t9(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=9), 1)

    def test_size5_t10(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=10), 2)

    def test_size5_t11(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=11), 3)

    def test_size2_t0(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=0), 0)

    def test_size2_t1(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=1), 1)

    def test_size2_t2(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=2), 0)

    def test_size2_t3(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=3), 1)

    def test_size2_t4(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=4), 0)

    def test_size15_t7(self):
        self.assertEqual(bounce_back_and_forth(size=15, start_t=7), 7)

    def test_size15_t8(self):
        self.assertEqual(bounce_back_and_forth(size=15, start_t=97), 13)

    # --- Negative Indices ------------
    def test_size5_t_m1(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-1), 4)

    def test_size5_t_m2(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-2), 3)

    def test_size5_t_m3(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-3), 2)

    def test_size5_t_m4(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-4), 1)

    def test_size5_t_m5(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-5), 0)

    def test_size5_t_m6(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-6), 1)

    def test_size5_t_m7(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-7), 2)

    def test_size5_t_m8(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-8), 3)

    def test_size5_t_m9(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-9), 4)

    def test_size5_t_m10(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-10), 3)

    def test_size5_t_m11(self):
        self.assertEqual(bounce_back_and_forth(size=5, start_t=-11), 2)

    def test_size2_t_m1(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=-1), 1)

    def test_size2_t_m2(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=-2), 0)

    def test_size2_t_m3(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=-3), 1)

    def test_size2_t_m4(self):
        self.assertEqual(bounce_back_and_forth(size=2, start_t=-4), 0)

    def test_size15_t_m7(self):
        self.assertEqual(bounce_back_and_forth(size=15, start_t=-7), 8)

    def test_size15_t_m8(self):
        self.assertEqual(bounce_back_and_forth(size=15, start_t=-8), 7)

    def test_size15_t_m97(self):
        self.assertEqual(bounce_back_and_forth(size=15, start_t=-97), 2)


if __name__ == '__main__':
    unittest.main()