Avatar of ogv

ogv's solution

to Crypto Square in the Go Track

Published at Feb 14 2020 · 2 comments
Instructions
Test suite
Solution

Implement the classic method for composing secret messages called a square code.

Given an English text, output the encoded version of that text.

First, the input is normalized: the spaces and punctuation are removed from the English text and the message is downcased.

Then, the normalized characters are broken into rows. These rows can be regarded as forming a rectangle when printed with intervening newlines.

For example, the sentence

"If man was meant to stay on the ground, god would have given us roots."

is normalized to:

"ifmanwasmeanttostayonthegroundgodwouldhavegivenusroots"

The plaintext should be organized in to a rectangle. The size of the rectangle (r x c) should be decided by the length of the message, such that c >= r and c - r <= 1, where c is the number of columns and r is the number of rows.

Our normalized text is 54 characters long, dictating a rectangle with c = 8 and r = 7:

"ifmanwas"
"meanttos"
"tayonthe"
"groundgo"
"dwouldha"
"vegivenu"
"sroots  "

The coded message is obtained by reading down the columns going left to right.

The message above is coded as:

"imtgdvsfearwermayoogoanouuiontnnlvtwttddesaohghnsseoau"

Output the encoded text in chunks that fill perfect rectangles (r X c), with c chunks of r length, separated by spaces. For phrases that are n characters short of the perfect rectangle, pad each of the last n chunks with a single trailing space.

"imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn  sseoau "

Notice that were we to stack these, we could visually decode the ciphertext back in to the original message:

"imtgdvs"
"fearwer"
"mayoogo"
"anouuio"
"ntnnlvt"
"wttddes"
"aohghn "
"sseoau "

Coding the solution

Look for a stub file having the name crypto_square.go and place your solution code in that file.

Running the tests

To run the tests run the command go test from within the exercise directory.

If the test suite contains benchmarks, you can run these with the --bench and --benchmem flags:

go test -v --bench . --benchmem

Keep in mind that each reviewer will run benchmarks on a different machine, with different specs, so the results from these benchmark tests may vary.

Further information

For more detailed information about the Go track, including how to get help if you're having trouble, please visit the exercism.io Go language page.

Source

J Dalbey's Programming Practice problems http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

crypto_square_test.go

package cryptosquare

import "testing"

var tests = []struct {
	pt string // plain text
	ct string // cipher text
}{
	{
		"s#$%^&plunk",
		"su pn lk",
	},
	{
		"1, 2, 3 GO!",
		"1g 2o 3 ",
	},
	{
		"1234",
		"13 24",
	},
	{
		"123456789",
		"147 258 369",
	},
	{
		"123456789abc",
		"159 26a 37b 48c",
	},
	{
		"Never vex thine heart with idle woes",
		"neewl exhie vtetw ehaho ririe vntds",
	},
	{
		"ZOMG! ZOMBIES!!!",
		"zzi ooe mms gb ",
	},
	{
		"Time is an illusion. Lunchtime doubly so.",
		"tasney inicds miohoo elntu  illib  suuml ",
	},
	{
		"We all know interspecies romance is weird.",
		"wneiaw eorene awssci liprer lneoid ktcms ",
	},
	{
		"Madness, and then illumination.",
		"msemo aanin dnin  ndla  etlt  shui ",
	},
	{
		"Vampires are people too!",
		"vrel aepe mset paoo irpo",
	},
	{
		"",
		"",
	},
	{
		"1",
		"1",
	},
	{
		"12",
		"1 2",
	},
	{
		"12 3",
		"13 2 ",
	},
	{
		"12345678",
		"147 258 36 ",
	},
	{
		"123456789a",
		"159 26a 37  48 ",
	},
	{
		"If man was meant to stay on the ground god would have given us roots",
		"imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn  sseoau ",
	},
	{
		"Have a nice day. Feed the dog & chill out!",
		"hifei acedl veeol eddgo aatcu nyhht",
	},
}

func TestEncode(t *testing.T) {
	for _, test := range tests {
		if ct := Encode(test.pt); ct != test.ct {
			t.Fatalf(`Encode(%q):
got  %q
want %q`, test.pt, ct, test.ct)
		}
	}
}

func BenchmarkEncode(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, test := range tests {
			Encode(test.pt)
		}
	}
}
package cryptosquare

import (
	"math"
	"strings"
	"unicode"
)

// Encode composes a secret message using a square code:
// it removes spaces and punctuation from the input,
// changes the text to lower case,
// it puts the result in a rows x columns rectangle,
// with columns - rows <= 1, by row,
// then outputs the encoded text in chunks that fill perfect rectangles
// (rows X columns of the original text),
// having "columns" chunks of "rows" length, with one or more spaces BETWEEN them.
// For phrases that are n characters short of the perfect rectangle,
// it pads each of the last n chunks with a single TRAILING space.
func Encode(s string) string {
	cryptBuffer := strings.Builder{}

	s = strings.Map(onlyDigitsLettersToLowercase, s)
	asRunes := []rune(s)
	rows, columns := widthLength(len(asRunes))

	for c := 0; c < columns; c++ {
		if c >= 1 {
			cryptBuffer.WriteRune(' ')
		}

		for r := 0; r < rows; r++ {
			value := ' '
			position := r*columns + c
			if position < len(asRunes) {
				value = asRunes[position]
			}
			cryptBuffer.WriteRune(value)
		}
	}

	return cryptBuffer.String()
}

// onlyDigitsLettersToLowercase returns
// - the lowercase version for a Unicode letter;
// - the provided rune for a digit;
// - a negative value for anything else.
func onlyDigitsLettersToLowercase(r rune) rune {
	if unicode.IsLetter(r) || unicode.IsDigit(r) {
		return unicode.ToLower(r)
	}

	return -1
}

// widthLength returns the int sides of the smallest rectangle
// with an area of at least n, that's as close as possible to a square.
// The first return value is the width, and the second is the length.
// That is, it returns ints w, l such that :
// w * l >= n
// 0 <= l - w <= 1 (l is larger than w by at most 1)
// w and l are the smallest such int values
// It only provides correct results for positive inputs.
func widthLength(n int) (int, int) {
	if n < 0 {
		return -1, -1
	}

	sqrt := math.Sqrt(float64(n))
	return int(math.Round(sqrt)), int(math.Ceil(sqrt))
}

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of ogv
ogv
Solution Author
commented 101 days ago

Made the program about 3 times faster using bytes.Buffer instead of a string for building the encrypted text.

Avatar of ogv
ogv
Solution Author
commented 87 days ago

Slight time and space reductions by using strings.Builder instead of bytes.Buffer.

ogv's Reflection

It was not trivial to correctly determine the width and length of the rectangle to put the text in.