Skip to content

Instantly share code, notes, and snippets.

@cairdcoinheringaahing

cairdcoinheringaahing/draft.md

Last active December 27, 2020 15:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cairdcoinheringaahing/310fae9b895cfb9bcbf71c388792a2c9 to your computer and use it in GitHub Desktop.
Save cairdcoinheringaahing/310fae9b895cfb9bcbf71c388792a2c9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
draft.md

Input

A string S of length between 2 and 30. The characters are taken from the 95 printable ASCII characters, byte values 32 (0x20) to 126 (0x7E) ( to ~)

Output

Your code must compute and output all strings within Levenshtein distance 2 of S. You can have duplicates as long as you also have all the different strings, and the output may be in any order.

Scoring

I will generate a set of 30 strings of random lengths between 2 and 30, each consisting of a random selection of ASCII characters. Each answer will be tested on the same set of strings, and your score is the total runtime over all 30, when run on my computer (spec details below). This means you need to give me simple and complete instructions on how to compile and run your code in Linux.

Example

Take the input string obenquillo. Using my test code the first output string is 8benquifllo and the last is o^be9quillo. There are 1871366 different strings in the output.

My PC

I have an AMD Ryzen 5 3400G running Ubuntu 20.04.

Winning

The lowest time for the test set as specified above wins

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment