## DEV Community is a community of 756,027 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

dev.to staff

Posted on

# Daily Challenge #118 - Reversing a Process

Suppose we know the process (A) by which a string `s` has been coded to a string `r`.

The aim of the kata is to decode `r` to get back the original string s.

Explanation of the known process (A):

• data: a string `s` composed of lowercase letters from a to z and a positive integer `num`

• We know there is a correspondence between `abcde...uvwxyzand` `0, 1, 2 ..., 23, 24, 25` : `0 <-> a, 1 <-> b ...`

• If `c` is a character of `s` whose corresponding number is `x`, apply to x the function `f: x-> f(x) = num * x % 26` then find `ch` the corresponding character of `f(x)`

• Accumulate all these `ch` in a string `r`.

• Concatenate `num` and `r` and return the result.

Example:
`code("mer", 6015) -> "6015ekx"`
`m <-> 12, 12 * 6015 % 26 == 4, 4 <-> e`
`e <-> 4, 4 * 6015 % 26 == 10, 10 <-> k`
`r <-> 17, 17 * 6015 % 26 == 23, 23 <-> x`
`We get "ekx" hence "6015ekx"`

A string `s` has been coded to a string `r` by the above process (A). Write a function r -> decode(r) to get back s whenever it is possible.

Indeed it can happen that the decoding is impossible when positive integer `num` has not been correctly chosen. In that case return "Impossible to decode".

Example:

`decode("6015ekx") -> "mer"`
`decode("5057aan") -> "Impossible to decode"`

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (4)

Kiliman

TypeScript plus tests

``````export const code = (s: string, num: number): string => {
const map = (c: string) => c.charCodeAt(0) - 97
const unmap = (x: number) => String.fromCharCode(x + 97)
const f = (x: number) => (num * x) % 26

let r = ''
for (let i = 0; i < s.length; i++) {
const x = map(s[i])
const ch = unmap(f(x))
r += ch
}
return String(num) + r
}

// calculate modular inverse
// https://rosettacode.org/wiki/Modular_inverse#JavaScript
const modInverse = (a: number, b: number): number => {
a %= b
for (let x = 1; x < b; x++) {
if ((a * x) % b === 1) {
return x
}
}
return 1
}

export const decode = (r: string): string => {
const match = r.match(/^\d+/)
let num = -1
if (match) {
num = parseInt(match[0])
r = r.substring(match[0].length)
}
const a_ = modInverse(num, 26)
if (num === -1 || a_ === 1) {
return 'Impossible to decode'
}

const map = (c: string) => c.charCodeAt(0) - 97
const unmap = (x: number) => String.fromCharCode(x + 97)
const f = (x: number) => (a_ * x) % 26

let s = ''
for (let i = 0; i < r.length; i++) {
const x = map(r[i])
const ch = unmap(f(x))
s += ch
}

return s
}
``````

Test

``````import { code, decode } from '.'

describe('encode data', () => {
it('should return encoded data', () => {
expect(code('mer', 6015)).toBe('6015ekx')
expect(code('hello', 9317)).toBe('9317lkvvw')
expect(code('goodbye', 1234603)).toBe('1234603kggftoy')
})
})

describe('decode data', () => {
it('should return decoded data', () => {
expect(decode('6015ekx')).toBe('mer')
expect(decode('9317lkvvw')).toBe('hello')
expect(decode('1234603kggftoy')).toBe('goodbye')
})

it('should return "Impossible to decode" if unable to decode', () => {
expect(decode('5057aan')).toBe('Impossible to decode')
expect(decode('xxx5057aan')).toBe('Impossible to decode')
})
})
``````
Jon Bristow • Edited on

An overengineered arrow-kt solution where I never check explicitly for null.

Probably uglier than needed, but fun.

``````import arrow.core.Option
import arrow.core.getOption
import arrow.core.getOrElse
import arrow.core.toOption

const val errorMessage = "Impossible to decode"
const val asciiValOfA = 'a'.toInt()

const val alphabet = "abcdefghijklmnopqrstuvwxyz"

fun Char.decode(n: Int) = (((toInt() - asciiValOfA) * n) % 26 + asciiValOfA).toChar()

fun MatchResult.stringValueGroup(n: Int) = groups[n].toOption().map { it.value }
fun MatchResult.intValueGroup(n: Int) = groups[n].toOption().map { it.value.toInt() }

fun String.decode() =
"""(\d+)([a-z]+)""".toRegex()
.find(this).toOption()
.flatMap { mr ->
mr.stringValueGroup(2).flatMap { s ->
mr.intValueGroup(1).flatMap {
generateAlphaMap(it).flatMap { rmap ->
s.fold(Option.just(""), convertingStringFolder(it, rmap))
}
}
}
}.getOrElse { errorMessage }

private fun generateAlphaMap(num: Int) =
alphabet.map { c -> c.decode(num) to c }.toMap().let { alphamap ->
when (alphamap.size) {
26 -> Option.just(alphamap.map { (k, v) -> v to k }.toMap())
else -> Option.empty()
}
}

private fun convertingStringFolder(num: Int, rmap: Map<Char, Char>) = { acc: Option<String>, inputChar: Char ->
acc.flatMap { soFar ->
rmap.getOption(inputChar).map { c -> "\$soFar\${c.decode(num)}" }
}
}

fun main() {
println("6015ekx".decode())
println("5057aan".decode())
}
``````
Melvin Yeo

In python

``````import re

def decode(str):
# check whether input string is valid
if (first_digit := re.search(r"[a-zA-Z]", str)) is None:
return "Impossible to decode"
else:
# extract the integer and text from string
decode_num = int(str[0:first_digit.start()])
text = str[first_digit.start():]

result_str = ""

# loop through all characters to decode string
for char in text:
index = ord(char) - ord('a')
found = False
# loop through all alphabets to decode string
for num in range(0, 26):
if num * decode_num % 26 == index:
# if a character can be encoded in multiple alphabets, then it is impossible to decode
if found:
return "Impossible to decode"
else:
result_str += chr(ord('a') + num)
found = True