8
\$\begingroup\$

I applied for a job as a C#/.NET Junior Developer, and had a test to do::

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file?

I'm looking for some constructive comments on how I could have done it better.

using System;
using System.Collections.Generic;
using System.Configuration;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace Name.Data.RetrieveNames
{
    public class Names
    {
        public string Name  { get; set; }
    }

    public static class RetrieveListOfNames
    {
        public static IEnumerable<Names> LstOfNames()
        {
            //**********************************
            //
            //File location is stored in app.config file,
            //this allows for ease in case the file needs
            //to be moved somewhere else.
            //So 1st check that it exists
            //
            //**********************************
            var fileExists = File.Exists(ConfigurationManager.AppSettings["LocationOfNamesFile"]);
            //**********************************
            //
            //If file does not exist, throw file not found exception, as no point in continuing
            //
            //**********************************
            if (!fileExists) throw new FileNotFoundException("FileNotFound Check AppSettings Location");
            //**********************************
            //Set buffer size, on huge file this can help with performance
            //
            //**********************************
            const int bufferSize = 1024;
            //**********************************
            //
            //Here we create the list and open the file and read all the names
            //
            //**********************************
            var data = new List<Names>();
            using (var fileStream = File.OpenRead(ConfigurationManager.AppSettings["LocationOfNamesFile"]))

            using (var streamReader = new StreamReader(fileStream, Encoding.UTF8, true, bufferSize))
            {

                string line;
                while ((line = streamReader.ReadLine()) != null)
                { 
                    //Split the string on the comma
                    string[] namesArray = Regex.Split(line, ",");
                    //Sort the names a-z
                    Array.Sort(namesArray);
                    //Loop over all names and add to list
                    data.AddRange(namesArray.Select(names => new Names
                    { 
                        Name    = names.ToLower()
                    }));
                }
               }
            //Finally return the names
            return data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using Name.Data.RetrieveNames;

namespace Name.UI
{
    class Program
    {
        //********************************************************************
        //Names scores
        //Problem 22
        //Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. 
        //Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
        //For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. 
        //So, COLIN would obtain a score of 938 × 53 = 49714.
        //What is the total of all the name scores in the file?
        //
        //********************************************************************

        static void Main(string[] args)
        {
            try
            {
            //********************************************************************
            //List of names returned from text file
            //********************************************************************
            var data = RetrieveListOfNames.LstOfNames().ToList();
            //********************************************************************
            //My own interest to see how long it takes to run code
            Stopwatch timer = new Stopwatch();
            //********************************************************************
            //Create list to hold the values
            //********************************************************************
                List<string> sumOffAllNames     = new List<string>();

            timer.Start();
            //********************************************************************
            //Loop over names replacing a-z with numbers 1-26, make all letters lowercase
            //********************************************************************
                List<string> listOfNames = data.Select(v => Regex.Replace(v.Name.Trim('"').ToLower(), "a", "1,")
                                                                                          .Replace("b", "2,")
                                                                                          .Replace("c", "3,")
                                                                                          .Replace("d", "4,")
                                                                                          .Replace("e", "5,")
                                                                                          .Replace("f", "6,")
                                                                                          .Replace("g", "7,")
                                                                                          .Replace("h", "8,")
                                                                                          .Replace("i", "9,")
                                                                                          .Replace("j", "10,")
                                                                                          .Replace("k", "11,")
                                                                                          .Replace("l", "12,")
                                                                                          .Replace("m", "13,")
                                                                                          .Replace("n", "14,")
                                                                                          .Replace("o", "15,")
                                                                                          .Replace("p", "16,")
                                                                                          .Replace("q", "17,")
                                                                                          .Replace("r", "18,")
                                                                                          .Replace("s", "19,")
                                                                                          .Replace("t", "20,")
                                                                                          .Replace("u", "21,")
                                                                                          .Replace("v", "22,")
                                                                                          .Replace("w", "23,")
                                                                                          .Replace("x", "24,")
                                                                                          .Replace("y", "25,")
                                                                                          .Replace("z", "26,") + 0).ToList(); 
                //********************************************************************
            //Variable for name row
            int nameId = 1;
            //********************************************************************
            //Loop over all rows returned from above foreach loop and add up each value to get total for name
            //Then times that by position in table
            //As all names are in alphabetical order, the variable nameId will increment by 1 on every loop
            //So I can use that to muliple total name value
            //********************************************************************
            foreach (var s in listOfNames)
            {
                var sumArray        = string.Join("", s.ToArray());
                var sumOfName      = (sumArray.Split(',').Sum(x => int.Parse(x)) * nameId++).ToString();
                sumOffAllNames.Add(sumOfName);
                //Console.WriteLine(nameNumber);
            }
            //********************************************************************
            //Turn list sumOffAllNames into string
            //Then add all values up to get total
            //********************************************************************
            string characterArray   = string.Join(",", sumOffAllNames.ToArray());
            int number              = characterArray.Split(',').Sum(x => int.Parse(x));
            timer.Stop();

            //********************************************************************
            //OK done display total and number of names and time to run code
            Console.WriteLine("Total is {0} from {1} names, time taken {2} seconds", number.ToString("##,000"), data.Count.ToString("##,000"), ((float)timer.ElapsedTicks)/Stopwatch.Frequency); 
            Console.Read();
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Console.Read();
            }
        }
    }
}
\$\endgroup\$
6
10
\$\begingroup\$
  • Use File.ReadLines to read from your file. This makes everything a lot simpler and avoids having to work with stream readers and buffers. You will just get back every line, so you don’t have too much about things.
  • Regex.Split(line, ",") – Don’t use Regex.Split here but just String.Split: line.Split(',')
  • List<string> sumOffAllNames – This shouldn’t be a list of strings for two reasons: A sum is a single value, and more importantly, it is a number.
  • Don’t use Regex.Replace but just use String.Replace for simple static replacements.
  • Regex.Replace(…).Replace(…) actually uses two different replace methods: First it uses Regex.Replace, which returns a string, and then you use String.Replace.
  • For the character to number conversions, use a dictionary that just looks up the values for each character. Or use arithmetics to calculate the value based on the character value.
  • You shouldn’t need to use int.Parse for this situation ever. If instead of replacing characters by number strings you just collect the numbers directly, then you can just sum them later without having to parse them (you actually parse them multiple times making this worse).

Finally, you are looping over the list of names three times in total: Once over the file to collect the names; and then once over the list of names to create sumOfAllNames. Since you collect the sum for each name separately in that list, you need to again loop over that list (which has the same length as you have names) to get the actual sum.

You can actually do this all much easier. All you need to do is get the names, sort them, and then iterate the sorted names collection once and sum the values directly.

// read the lines from the file
File.ReadLines(fileName)
    // if there are multiple names per line, extract all of them
    .SelectMany(line => line.Split(','))

    // sort by the name
    .OrderBy(name => name)

    // now for each name, we also get the index and use that to calculate the score
    .Select((name, index) => {
        // convert to lower
        name = name.ToLower();

        // convert each character to an int, and subtract 96
        // (since the character 'a' has the value 97);
        // finally get the sum
        int score = name.AsEnumerable().Select(character => character - 96).Sum();

        // multiplicate by the index, add 1 because the index starts at 0
        score *= index + 1;

        // return the score
        return score;
    })
    // finally, calculate the sum of all scores
    .Sum();

For the future, if you need a more complicated lookup that does not work using character arithmetics, use a dictionary:

Dictionary<char, int> scoreLookup = new Dictionary<char, int>() {
    { 'a', 1 }, { 'b', 2 }, { 'c', 3 }, { 'd', 4 }, { 'e', 5 }, { 'f', 6 }, { 'g', 7 },
    { 'h', 8 }, { 'i', 9 }, { 'j', 10 }, { 'k', 11 }, { 'l', 12 }, { 'm', 13 }, { 'n', 14 },
    { 'o', 15 }, { 'p', 16 }, { 'q', 17 }, { 'r', 18 }, { 's', 19 }, { 't', 20 },
    { 'u', 21 }, { 'v', 22 }, { 'w', 23 }, { 'x', 24 }, { 'y', 25 }, { 'z', 26 } };

// then to convert the string
name.ToLower().Select((character, index) => scoreLookup[character] * (index + 1)).Sum();
\$\endgroup\$
9
  • \$\begingroup\$ Hi Poke, thanks wish I knew that before I wrote the code, that's why I'm applying for Junior developer :) \$\endgroup\$ Aug 3 '15 at 10:26
  • 1
    \$\begingroup\$ @poke be sure to use a case insensitive IEqualityComparer when looking up with the dictionary or, include all the upper case keys too. \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 10:39
  • 1
    \$\begingroup\$ @Jodrell Yeah but we get lots of other problems too if we leave the set of those 26 letters. So I am assuming that this is an implicit restriction of the original problem. Otherwise we would need answers to questions like “what is the alphabetical position of umlauts” etc ;) \$\endgroup\$
    – poke
    Aug 3 '15 at 11:03
  • 2
    \$\begingroup\$ I would really prefer to wrap the "ToLower" and "-96" into a named sub-function, (e.g. getCharacterScore(char c)), just because it's a dirty little implementation detail which will break on edge cases. \$\endgroup\$
    – deworde
    Aug 3 '15 at 11:52
  • 1
    \$\begingroup\$ One disadvantage that might earn you some brownie points with ReadLines() - not so important at 46k - is that if you increase the size of the read file much more, you're going to end up having to read the entire file in at once which might be detrimental to just loading the file into the program bits at a time (which is what a stream does). Again, for 46k - not important. 46 megabytes? definitely important \$\endgroup\$
    – Dan
    Aug 3 '15 at 13:44
7
\$\begingroup\$

i want to discuss the

List<string> listOfNames =
                data.Select(
                    v =>
                    Regex.Replace(v.Name.Trim('"').ToLower(), "a", "1,")
                         .Replace("b", "2,")
                         .Replace("c", "3,")
                         .Replace("d", "4,");

code.

The first thing is that my formatting is better, because it is not that wide. the second is that you did not need that much replaces. you could work in bytes. here is a little code example.

string testString = "AThisIsMyName";

var lowerTestString = testString.ToLower();

foreach (char character in lowerTestString)
{
    // if a small 'a' is 97 substract 96 to get 1
    // 'b' - 'a' <=> 'b' - 96 <=> 98 - 96 <=> 2
    var byteRepresentation = (byte)character;
    int numberOfChar = byteRepresentation - 96;
    // ...
}

i convert every character to its byte representation. then i can subtract the offset(which is a = 97 minus 1) and i get the number. this is much less to code and if you wrap it into an function it has a very good readability. Your's has a good readability too, but it is not that short.

Refereed to Comments:
Oh, i have seen that Jodrell answered to nearly the same. if you combine our solution i think you have the ultimate :)

As Vogel612 wrote in a comment you could calculate the number with even better readability with this line of code: character.ToLower().ToInt32() - 'a'.ToInt32() + 1; Then you do not need to convert the character into its byte equivalent and substract the constant 96.

What do you think about my suggestion? Would be nice to have a discussion

\$\endgroup\$
11
  • \$\begingroup\$ Hi Jens I never knew that a = 97 etc, that is something new I have learned today. \$\endgroup\$ Aug 3 '15 at 10:32
  • 1
    \$\begingroup\$ @GeorgePhillipson yeah. that's something i learned in a c lession. check this image out: upload.wikimedia.org/wikipedia/commons/thumb/1/1b/… As you can see. it is the ascii table. \$\endgroup\$
    – Jens
    Aug 3 '15 at 10:44
  • 1
    \$\begingroup\$ I think you need range checking or a special case for names that include say an apostrophe ('\'') like an Irish name. These could otherwise result in negative values. \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 11:04
  • 2
    \$\begingroup\$ @GeorgePhillipson, 'a' does indeed have a decimal value of 97. You can use this to avoid writing lots of code. Whilst this mapping is unlikely to change, it is still an implementation detail that others will need to know to understand your code. If you use this you should comment accordingly so other developers understand, or learn. \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 11:12
  • 1
    \$\begingroup\$ I would really prefer to wrap "int numberOfChar = byteRepresentation - 96;" into its own function, getNumberFromChar(), just because it's a dirty little implementation detail which will break on edge cases such as other languages; being able to encapsulate that complexity has value. \$\endgroup\$
    – deworde
    Aug 3 '15 at 11:50
2
\$\begingroup\$

Apart from the optimizations others have mentioned with reading files and sorting, your code needs restructuring. You have 2 classes that contain only 1 property each! If that is all that is needed, then there is no need to encapsulate those properties into classes. However, I think you could use some Object Oriented principles and create a meaningful class that encapsulates the data, and the methods that act on the data.

Public class NameScore
{
  Public IEnumerable<String> TheNames()

  Private void SortNames()
  {
    //Alphabetically Sorts TheNames
  }

  Public int GetScore(string name)
  {
    //Returns the name score
  }

  Private bool GetNamesFromFile(string fileName)
  {
    //Populates TheNames with names read from file, returns false if file does not exist
  }

  Public bool PopulateAndSort(string filename)
  {
    if (GetNamesFromFile(filename))
    {
      SortNames();
      return true;
    }
    return false
}

class Program
{
  static void Main(string[] args)
  {
    NameScore data = new NameScore();
    int totalScore = 0;

    if(data.PopulateAndSort(ConfigurationManager.AppSettings["LocationOfNamesFile"])
    {
      for each(String name in data.TheNames)
      {
        totalScore += data.GetScore(name);
      }
    }

    Console.WriteLine("Total score is {0}", totalScore);
  }
}

This is just a quick stub, so there are ways to improve it and/or do it differently. As others have said, scores could be calculated at the same time as populating the data in order to reduce the amount of times the entire list is iterated. But if I were the interviewer, I would be more concerned with the class structures than the overall performance of your original code.

\$\endgroup\$
0
\$\begingroup\$

After thinking about the task four hours i decided to code my own solution. I'd like to share it with you.

Test File:

At first i have created this file with the help of this website:

Jeanetta,Sharri,Hilaria,Shanelle,Dominica,
Leota,Rochelle,
Myrta,Donnell,
Wei,Charleen,Nicky,
Delbert,Felicidad,Lupita,Wallace,
Tiffiny,Leroy,
Vertie,Emily,
Jung,Ulysses,
Miranda,Felicia,
Susannah,Rosalinda,Jalisa,
Alexa,Natalie,Geri,
Patria,Vennie,
Olivia,
Pilar,
Lacey,Katheryn,
Britta,Mario,Malena,Sherrill,Kimber,Elyse,
Robyn,Shena,Ida,Mana,Keenan,
Craig,Lanelle,Kimbery

Code:

This is my Person class: It holds the Position in the Sort, the Sum of the Chars, it's Name and the value calculated from the Position * the Sum of the Chars

class Person
{
    private int position;

    private int sumOfChars;

    public string Name { get; set; }

    // Calculates Value every time Position or SumOfChars is set
    public int Position
    {
        get
        {
            return this.position;
        }
        set
        {
            this.position = value;
            this.CalculateValue();
        }
    }

    public int SumOfChars
    {
        get
        {
            return this.sumOfChars;
        }
        set
        {
            this.sumOfChars = value;
            this.CalculateValue();
        }
    }

    public int Value { get; private set; }

    public void CalculateValue()
    {
        this.Value = this.Position * this.SumOfChars;
    }

    public static int CharToNumber(char character)
    {
        // character is a "ToLower" character
        return (byte)character - (byte)'a' + 1;
    }
}

and this is my execution / main method. I have only splitted the execution from the main because of the StopWatch. You used StopWatch.ElapsedTicks / StopWatch.Frequency. As you can see StopWatch.ElapsedMilliseconds is better (readable).

Moreover you can see the alternative reading of an file. File.ReadAllText() or File.ReadAllLines() are methods which are nice to know.

Many things are like in your solution or in the answers here but a bit more optimized. you should also add the File.Exist() to my solution because it is a very nice idea and good programming style!

static void Main(string[] args)
{
    Stopwatch sw = Stopwatch.StartNew();

    Execution();

    sw.Stop();
    Console.WriteLine("Took {0} Seconds for execution", (sw.ElapsedMilliseconds / 1000.0).ToString("N3"));
    Console.WriteLine("Press a key for termination");
    Console.ReadKey();
}

private static void Execution()
{
    // Extract the Names out of the File
    // Steps:
    // 1)   Get all lines out of the File
    // After this the Document is represented in 1 string
    // 2)   Split the string into the name with ',' parameter
    // 3)   Order it
    // 4)   Convert all the name to lower
    // 5)   "Convert" the linq expression into a List -- feels for me better to work with
    List<string> names =
        File.ReadAllText(@"C:\Users\jenshor\Desktop\Names.txt")
            .Replace("\r", "")
            .Replace("\n", "")
            .Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries)
            .OrderBy(x => x)
            .Select(x => x.ToLower())
            .ToList();

    // Calculate the Value of each Name
    var resultList = new List<Person>();

    // Use List as an Array
    for (int index = 0; index != names.Count; index++)
    {
        // I calculate Position as index + 1
        // because otherwise the first person always has 0 as Value
        var person = new Person()
        {
            Name = names[index],
            Position = index + 1,
            SumOfChars = names[index].Sum(x => Person.CharToNumber(x))
        };
        resultList.Add(person);
    }

    // Calculate the total number for all numbers
    int totalScore = resultList.Sum(x => x.Value);

    // That's it!
    Console.WriteLine("Total is {0} from {1} names", totalScore, resultList.Count);
}

The Output:

Total is 87191 from 50 names
Took 0,005 Seconds for execution

There is a ',' for the decimal seperator because my operating system language is german. if you want to change this you need a culture info:

yourDouble.ToString(new CultureInfo("en-US"));

Results
The results my method comuptes is correct. i tested it on this website.

Recommendation:

I may recommend you the visual studio tool ReSharper. It cost a bit of money (no for me because i am a student), but it is very very good. the code you have read is coded by me but optimized by ReSharper. I am not that good LINQ programmer the code looks like. It was ReSharper. It helps you to format code and write things like LINQ. Maybe you want to take a look at it :)

\$\endgroup\$
8
  • \$\begingroup\$ use StopWatch.StartNew msdn.microsoft.com/en-us/library/bb46x3x1(v=vs.110).aspx \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 12:16
  • \$\begingroup\$ @Jodrell yeah - nice idea. i will change that. For all that are reading this: the code was: Stopwatch sw = new Stopwatch(); sw.Start(); \$\endgroup\$
    – Jens
    Aug 3 '15 at 12:18
  • \$\begingroup\$ If you use StringSplitOptions.RemoveEmptyEntries, like in my answer, you can avoid the need for the Replaces. \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 12:21
  • \$\begingroup\$ If you make your char to value function handle both upper and lower case, you can avoid the extra iteration for ToLower. \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 12:23
  • \$\begingroup\$ if you use the other overload of Select you can avoid the ToList and associated memory allocation. msdn.microsoft.com/en-us/library/vstudio/… \$\endgroup\$
    – Jodrell
    Aug 3 '15 at 12:26
0
\$\begingroup\$

Here's a way to do it in one line of Linq code:

int score = System.IO.File.ReadAllLines(ConfigurationManager.AppSettings["LocationOfNamesFile"])
    .SelectMany(s => s.Split(','))
    .OrderBy(b => b)
    .Select((s, i) => new { 
        Index = i + 1, 
        Score = s.Sum(ch => (int)(char.ToUpper(ch) - 'A' + 1)) })
    .Sum(s => s.Index * s.Score);

This will throw an exception if the file doesn't exist, but your original code does this as well.

\$\endgroup\$
0
\$\begingroup\$

I've taken the liberty of preparing an answer specific to the problem, as stated on Project Euler.

There is a working example of my code here.

using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        var fileName = ConfigurationManager.AppSettings["LocationOfNamesFile"];
        var result = File.ReadAllText(fileName)
            .Split(',')
            .OrderBy(name => name)
            .Select((name, i) => (name.Where(c => c != '"').Sum(c => c & 0x1F) * ++i))
            .Sum();

        Console.WriteLine("Answer: {0},", result);
    }
}

for what its worth, this would also work with lower case characters from the alphabet.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.