(Best viewed on screens larger than a portrait phone)
Recap
In my last but one post I coded solutions to the task:
Implement a pseudo-encryption algorithm which given a string S and an integer N
concatenates all the odd-indexed characters of S with all the even-indexed
characters of S, this process should be repeated N times.
First implementation
My first implementation didn't use index variables to walk through strings, but instead used slicing and zip_longest:
from itertools import zip_longest
if not s or n <= 0:
return s
for _ in range(n):
s = s[1::2] + s[0::2]
return s
def decrypt(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = len(s) // 2
for _ in range(n):
s = ''.join(''.join(x)
for x in
zip_longest(s[l2:], s[:l2],
fillvalue=''))
return s
N modulo
In that same post I found that encryption repeats after some value found to be associated with
https://oeis.org/A002326 So if n is ls large, work will be reduced.
from functools import cache
@cache
def a002326(n: int) -> int:
"Least m > 0 such that 2n+1 divides 2^m-1"
n21 = 2 * n + 1
m, m2 = 1, 2
while (m2 - 1) % n21:
m, m2 = m+1, m2 * 2
return m
def encrypt2(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = len(s) // 2
for _ in range(n % a002326(l2)): # Modulo reduction on large n
s = s[1::2] + s[0::2]
return s
def decrypt2(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = len(s) // 2
for _ in range(n % a002326(l2)): # Modulo reduction on large n
s = ''.join(''.join(x)
for x in
zip_longest(s[l2:], s[:l2],
fillvalue=''))
return s
New Stuff
this marks the end of the previous posts precis.
Task generalisation #1: Reverse
Reverse the concatenation of the original.
The new task descripption:
New Task:
given a string S and an integer N concatenates all the EVEN-indexed
characters of S with all the ODD-indexed characters of S, this process
should be repeated N time. (Prevous was ODD-EVEN).
Examples:
encrypt('012345', 1) => '024135'
encrypt('012345', 2) => '043215'
encrypt('012345', 3) => '031425'
encrypt('0123456', 1) => '0246135'
encrypt('0123456', 2) => '0415263'
encrypt('0123456', 3) => '0123456'
Its code
def encrypt3(s: str, n: int) -> str:
if not s or n <= 0:
return s
for _ in range(n):
s = s[::2] + s[1::2]
return s
def decrypt3(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = (len(s) + 1) // 2 # Odd char now in first half for odd len(s)
for _ in range(n):
s = ''.join(''.join(x)
for x in
zip_longest(s[:l2], s[l2:],
fillvalue=''))
return s
N modulo for Reverse
I looked again for a value for n after which encryptions repeat and found a similar dependency on a002326 but with a subtle change in offset
def encrypt4(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = (l1:=len(s)) // 2
for _ in range(n % a002326((l1 - 1) // 2)):
s = s[::2] + s[1::2]
return s
def decrypt4(s: str, n: int) -> str:
if not s or n <= 0:
return s
l2 = ((l1:=len(s)) + 1) // 2 # Odd char now in first half for odd len(s)
for _ in range(n % a002326((l1 - 1) // 2)):
s = ''.join(''.join(x)
for x in
zip_longest(s[:l2], s[l2:],
fillvalue=''))
return s
Three groups
A task description like the first, that gave us encrypt1, but this time for three groups.
I am thinking about later generalisations and realise that after splitting into three, there could be 3! = 6 possible ways of concatenating groups, so call this encrypt_210 as 210 is the order used here:
New Task encrypt_210:
Given a string S and an integer N select chars at positions div 3
and concatenate all the remainder-2, then rem-1 then rem-0 ordered
groups of character. This process should be repeated N times to
form the encrpted string.
If N is 0 or the string is null return the input string.
Examples:
encrypt('012345', 0) => '012345'
encrypt('012345', 1) 03,14,25 => '251403'
encrypt('012345', 2) 24,50,13 => '135024'
Decode is encode!!
I realised that if you encode individual items to their output positions then the decode is always just the reverse mapping of encoded to starting state.
The above is easiest done by first encoding a list of integers then doing reverse indexing.
I decided to extend my knowledge of typing too. (Although I want to see if it helps with readability rather than running Mypy).
from typing import overload
@overload
def encrypt5(s: str, n: int) -> str: ... # normal
@overload
def encrypt5(s: list[int], n: int) -> list[int]: ... # internal, for decryption
def encrypt5(s, n) -> str:
if not s or n <= 0:
return s
for _ in range(n):
s = s[2::3] + s[1::3] + s[0::3]
return s
def decrypt5(s: str, n: int) -> str:
"""
In which I realise that for this _class_ of problem, decryption is reversing the encrpt
"""
base = list(range(len(s)))
enc = encrypt5(base, n)
if not enc:
return ''
return ''.join(s[enc.index(i)] for i in base)
Generalised groupings
I realized that these encodings might be described in terms of cards and dealings:
- You have a pack of S cards and dealt them into K piles, left to right, starting again at the leftmost pile when you last dealt at the rightmost until you dealt the last card.
- Number the piles, left-to-right from zero to K-1,
- You also have a permutation M of the integers 0 to K-1 and you concatenate the dealt piles in the order given in M to form the first reordering of S.
- Repeat the process N times to form the final ordering of S
The following picture is the first concatenation arrangement of M = 2, 1, 0:
My more formal definition of the generalised case:
Task Encrypt grouping chars by mod M, N times:
Given an input string S; Some order of the K integers 0..K-1 called
M, where K <= length_of(S); and an integer N > 0
First form groups:
Form group G[0] by concatenating every K'th item of S starting from index 0
Form group G[1] by concatenating every K'th item of S starting from index 1
...
Form group G[K-1] by concatenating every K'th item of S starting from index K-1
Group Concatenation:
Concatenate all the groups G in the order given M to form the partial result P
P(1) = concatenate_left_to_right(G[i] for i in M)
Repetition:
Substituting P for S, repeat the above process N times to form the final
encrypted string P(N)
Corner cases:
If S is empty or N is 0 then return S.
If M is empty return the empty version of sequence S (empty string).
Examples:
encrypt6('012345', [1, 0], 0) => '012345'
encrypt6('012345', [1, 0], 1) => '135024'
encrypt6('012345', [1, 0], 2) => '304152'
encrypt6('012345', [1, 0], 3) => '012345'
encrypt6('012345', [1, 0], 4) => '135024'
encrypt6('01234567', [2, 1, 0], 0) => '01234567'
encrypt6('01234567', [2, 1, 0], 1) => '25147036'
encrypt6('01234567', [2, 1, 0], 2) => '10576243'
encrypt6('01234567', [2, 1, 0], 3) => '52063174'
encrypt6('01234567', [2, 1, 0], 4) => '01234567'
Past encryptions in its terms
Note that:
encrypt(S, N), encrypt2(S, N) do encrypt6(S, [1, 0], N)
encrypt3(S, N), encrypt4(S, N) do encrypt6(S, [0, 1], N)
and
encrypt5(S, N), does encrypt6(S, [2, 1, 0], N)
Generalised Code
from typing import Sequence
def encrypt6(s: Sequence, # Supporting indexing and __add__
m: Sequence[int], # perm of ints 0..k-1, k <= len(s)
n: int
) -> Sequence:
if not s or n == 0:
return s
if not m:
return type(s)() # Empty sequence
assert n >= 0
assert (k:=len(m)) <= len(s)
assert set(range(k)) == set(m), \
f"List {m = } should contain a permutation of all the numbers 0..{k-1} inclusive."
s_type = type(s) #[0])
if issubclass(s_type, str):
for _ in range(n):
s = ''.join(s[offset::k] for offset in m)
else: # non-strings
empty_val = s_type()
for _ in range(n):
s = sum((s[offset::k] for offset in m),
start=empty_val)
return s
def decrypt6(s: Sequence, # Supporting indexing and __add__
m: Sequence[int], # perm of ints 0..k-1, k <= len(s)
n: int
) -> Sequence:
"By a reverse of the encoding"
# Where the encoding maps ordered items
base = list(range(len(s)))
enc = encrypt6(base, m, n)
if not enc:
return enc
# Return the revered mapping
s_type = type(s)
if issubclass(s_type, str):
return ''.join(s[enc.index(i)] for i in base)
else:
empty_val = s_type()
return sum((s[enc.index(i)] for i in base),
start=empty_val)
END BIT.
I have looked into the number sequences produced by encrypt6, but this is already a long post so I'll leave that 'till next time
No comments:
Post a Comment