Matching a generated string of random letters to an input

Question

I made a program in Python and wanted it to be faster, so I wrote it on C# because it's compiled. To my surprise, the Python program is much faster. I guess there is something wrong with my C# code, but it is pretty simple and straightforward, so I don't know. They are structured about the same way.

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;

//This program generates a string of random lowercase letters and matches it to the user's input
//It does this until it gets a match
//It also displays the closest guess so far and the time it took to guess

namespace Monkey
{
    class Program
    {
        static string userinput()
        {
            //Takes user input, makes sure it is all lowercase letters, returns string
            string input;

            while(true)
            {
                input = Console.ReadLine();

                if (Regex.IsMatch(input, @"^[a-z]+$"))
                {
                    return input;
                }
            }
        }

        static string generate(int len)
        {
            //generates string of random letters, returns the random string
            Random rnd = new Random();
            string alpha = "abcdefghijklmnopqrstuvwxyz";
            int letterInt;
            StringBuilder sb = new StringBuilder();


            for (int i = 0; i < len; i++)
            {
                letterInt = rnd.Next(26);
                sb.Append(alpha[letterInt]);
            }

            return sb.ToString();
        }

        static int count(int len, string s, string g)
        {
            //returns number of letters that match user input
            int same = 0;

            for (int i = 0; i < len; i++)
            {
                if(g[i] == s[i])
                {
                    same++;
                }
            }

            return same;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("They say if you lock a monkey in a room with a typewriter and enough time,");
            Console.WriteLine("the monkey would eventually type a work of Shakespeare.");
            Console.WriteLine("Let's see how well C# does...");
            Console.WriteLine("Enter a word");
            Console.WriteLine("(3 letters or less is recommended)");
            string solution = userinput();

            int size = solution.Length;
            bool success = false;
            string guess = null;
            int correct;
            int best = 0;
            Stopwatch watch = Stopwatch.StartNew();

            while (!success)
            {
                guess = generate(size);
                correct = count(size, solution, guess);

                if (correct == size)
                {
                    success = true;
                }

                else if (correct > best)
                {
                    Console.Write("The best guess so far is: ");
                    Console.WriteLine(guess);
                    best = correct;
                }
            }

            watch.Stop();
            TimeSpan ts = watch.Elapsed;
            Console.WriteLine("Success!");
            Console.Write("It took " + ts.TotalSeconds + " seconds for the sharp C to type ");
            Console.WriteLine("\"" + guess + "\"");

            Console.ReadLine();
        }
    }
}

Python:

import random
import time
#This program generates a string of random letters and matches it with the user's string
#It does this until it's guess is the same as the user's string
#It also displays closest guess so far and time it took to guess


def generate():
    # generate random letter for each char of string
    for c in range(size):
        guess[c] = random.choice(alpha)


def count():
    # count how many letters match
    same = 0
    for c in range(size):
        if guess[c] == solution[c]:
            same += 1
    return same


print("They say if you lock a monkey in a room with a typewriter and enough time,")
print("the monkey would eventually type a poem by Shakespeare")
print("Let's see how well a python does...'")

user = ""
badinput = True
while badinput:
    # Make sure user only inputs letters
    user = input("Enter a word\n(5 letters or less is recommended)\n")
    if user.isalpha():
        badinput = False

solution = list(user.lower())
size = len(solution)
guess = [""] * size
alpha = list("abcdefghijklmnopqrstuvwxyz")
random.seed()
success = False
best = 0    # largest number of correct letters so far
start = time.time()    # start timer

while not success:
    # if number of correct letters = length of word
    generate()
    correct = count()
    if correct == size:
        success = True
    elif correct > best:
        print("The best guess so far is: ", end="")
        print("".join(guess))
        best = correct

finish = time.time()    # stop timer
speed = finish - start

print("Success!")
print("It took " + str(speed) + " seconds for the python to type ", end="")
print("\"" + "".join(guess) + "\"")
input()

Answer 1

I don't know python so I'll focus on the c# code.

• Your program is coded upside down. One would expect void Main at the top, with the more specialized code below.
• Method names in C# are expected to consistently follow PascalCasing convention. Only your Main method does that, and if you were to adopt a camelCasing convention, userinput would be better off called userInput.
• It doesn't feel right that the Count method doesn't infer the number of iterations from the length of the string(s) it's given, and doesn't do anything to verify whether the index is legal, which at first glance seems like asking for an IndexOutOfRangeException.

Performance-wise, I think you'll need to factor out the randomness from your tests for any benchmarking to mean anything.

Using StringBuilder was a good call.

Answer 2

If you want performance, don't create objects in the inner loop:

    static string generate(int len)
    {
        Random rnd = new Random();                    // creating a new object
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        int letterInt;
        StringBuilder sb = new StringBuilder();      // creating a new object
        ....

    }

create them once and reuse them

Answer 3

To answer the question of why your c# code is so slow.

It's this line. According to a profiler ~90% of the execution time is being taken up by recreating the Random object. You'll notice your python code only uses the random rather than recreates it.

Random rnd = new Random();

if you change the generate method to:

    static Random rnd = new Random();

    static string generate(int len)
    {
        //generates string of random letters, returns the random string
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        int letterInt;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }

These changes will show similar perf for both languages.

Answer 4

In your python code you use a character array as your guess. In your C# code you build a StringBuffer instead. Try using a char[] instead.

Since you are on Code Review - I'll also give some thoughts about your code:

Naming Conventions - C# method naming is PascalCase, and python function naming in snake_case, so - UserInput() and user_input(): respectively.

Meaningful names - generate and count do not convey well the meaning of the code in them GenerateRandomString and CountSimilarLetters is better. Same goes for alpha, len, g, s, etc.

Answer 5

I'd look at compiling your regex and having it as a class-level member for optimal reuse. Also lift the random number generator out the same way, as it's never good practice to continually regenerate it.

old code:

    static string userinput()
    {
        //Takes user input, makes sure it is all lowercase letters, returns string
        string input;

        while(true)
        {
            input = Console.ReadLine();

            if (Regex.IsMatch(input, @"^[a-z]+$"))
            {
                return input;
            }
        }
    }

    private static string generate(int len)
    {
        // generates string of random letters, returns the random string
        Random rnd = new Random();
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        int letterInt;

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }

new code:

    private static readonly Regex regex = new Regex(@"^[a-z]+$", RegexOptions.Compiled);
    private static readonly Random rnd = new Random();

    static string userinput()
    {
        //Takes user input, makes sure it is all lowercase letters, returns string
        string input;

        while(true)
        {
            input = Console.ReadLine();

            if (regex.IsMatch(input))
            {
                return input;
            }
        }
    }

    private static string generate(int len)
    {
        // generates string of random letters, returns the random string
        const string alpha = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        int letterInt;

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }

Answer 6

Here's a late commentary on your Python program.

---

I know no C#. To be honest, though, I'm truly surprised that the C# isn't faster, because what you have written is not how to implement a fast variant in Python.

In Python, you'll want to use Numpy if things are getting slow. In fact, you'll want something like:

"""
This program generates a string of random letters and matches it with the user's string.
It does this until its guess is the same as the user's string.
It also displays closest guess so far and time it took to guess.
"""

import numpy
import time
from string import ascii_lowercase

# Everything is ASCII, which is what the "c" means.
letters = numpy.array(list(ascii_lowercase), dtype="c")

def brute_force(solution):
    """
    BRRUUUUTTTEEE FFOOORRRCCCEEEE!!!!

    Repeatedly guess at a solution until it matches.
    """

    # Convert to char array
    solution = numpy.array(list(solution.casefold()), dtype="c")

    best = 0
    while True:
        # Do loads of guesses (100000) at once
        guesses = numpy.random.choice(letters, (100000, len(solution)))

        # Check all of the characters for equality, and count the number
        # of correct for each row
        corrects = (guesses == solution).sum(axis=1)

        # Gets the highest-so-far at each point
        maximums = numpy.maximum.accumulate(corrects)

        # Gets how much the maximum increased
        changes = numpy.diff(maximums)

        # Indexes of the increases
        # numpy.where returns a tuple of one element, so unpack it
        [when_increased] = numpy.where(changes > 0)
        # Need to increase by one, because these are indexes into
        # the differences whilst we want indexes into the final array
        # for the *increased* (not increasing) elements
        when_increased += 1

        for index in when_increased:
            guess = guesses[index]
            correct = corrects[index]

            if correct > best:
                yield str(guess, encoding="ascii")
                best = correct

            if correct == len(solution):
                return


print("They say if you lock a monkey in a room with a typewriter and enough time,")
print("the monkey would eventually type a poem by Shakespeare")
print("Let's see how well a python does...'")

while True:
    print("Enter a word")
    print("(5 letters or less is recommended)")
    user_input = input()

    # Make sure user only inputs letters
    if user_input.isalpha():
        break

start = time.time()

for solution in brute_force(user_input):
    print("The best guess so far is: ", solution)

elapsed_time = time.time() - start

print("Success!")
print("It took ", elapsed_time, " seconds for the python to type ", repr(solution))

It might look more intimidating but there are only ~30 lines of logic there, most of which are trivial.

The basic idea is to make loads of random choices in bulk:

guesses = numpy.random.choice(letters, (100000, len(solution)))

which is fast. This makes a 100000xN matrix, eg. for N=3:

h s l
w t x
a m e
i x t
  ⋮

Then you can calculate the number correct for each row by comparing each row to the solution (guesses == solution) giving a bool array, and you can sum each row (.sum(axis=1)) to get the number correct.

The extra parts from there (numpy.diff) serve to pretend we did this sequentially, although we did not. It's not relevant in most real-world circumstances, where one can just print the best answer from that bunch.

Overall this is much faster than the original (>10x), and most of the time is spent in numpy.random.choice, implying it's not possible to meaningfully speed up further without replacing the high-quality random numbers that Numpy generates.

So don't go thinking that Python is slow because it's interpreted and dynamic. It's perfectly possible to have a high-quality implementation run fast with these kinds of programs.

---

Since this is Code Review, I'll also point out some things that you should be improving on:

• Docstrings, not comments.

  Write

  """
  This program generates a string of random letters and matches it with the user's string.
  It does this until its guess is the same as the user's string.
  It also displays closest guess so far and time it took to guess.
  """
  

  instead of

  # This program generates a string of random letters and matches it with the user's string.
  # It does this until its guess is the same as the user's string.
  # It also displays closest guess so far and time it took to guess.
  

  This might sound meaninglessly fussy, but it helps introspection.

• Reduce your usage of globals. Functions should (almost) never share state; it should be passed between them. Trust me on this. It means that you can reuse them and move them around without worrying about dependencies, for one. It also allows local changes to stay local.

• Try and clump IO in one place. If you look at my variant, all the printing is localized and the logic is separated. This modularizes the program, so you can move things around and mess with logic without having "things" in your way all of the time.

• random.seed() with no value given is pointless here. It should only be used after random.seed(some_value) to remove the seed.

• This code:

  done = False
  while not done:
      if ...:
          done = True
  

  is much better written

  while True:
      if ...:
          break
  

  Some people disagree. They are wrong.

• Things like

  for c in range(size):
      guess[c] = random.choice(alpha)
  

  where you're visiting each item in turn, are much better written without indexes, like:

  guess[:] = [random.choice(alpha) for _ in range(size)]
  

  although this really should be

  def generate(size):
      """Generate random letter for each character of string."""
      return [random.choice(alpha) for _ in range(size)]
  

  if you use my prior advice.

  The same goes for count, which can be

  sum(g==s for g, s in zip(guess, solution))
  

• Don't meaninglessly preallocate values, like guess = [""] * size. It just hides bugs.

  If you ever find you need to do that, you're probably not following my advice about not using globals.