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"

Task:

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 [e-mail] with your suggestions!

Comments

[Kiliman]

TypeScript plus tests

github.com/kiliman/dev-to-daily-ch...

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]

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

        if not found:
            return "Impossible to decode"

    return result_str


print(decode("6015ekx"))
print(decode("5057aan"))