Mapping numbers to letters

Question

I had an interview question asking this:

text file has following lines>
            1: A C D
            4: A B
            5: D F
            7: A E
            9: B C  
*Every line has a unique integer followed by a colon and one or more letters. These letters are delimited spaces (one or more)>
                            #2 Write a short program in the language
of your choice that outputs a sorted list like
            A: 1 4 7
            B: 4 9
            C: 1 9
            D: 1 5
            E: 7
            F: 5

I'm not looking for someone to solve it, but I always get confused with problems like this. I'd like to do it in C# and was wondering should I store each line in a 2d array? What is the best way to handle this. After storing it how do I relist each line with letters rather then numbers?

Just looking for pointers here.

You will only grow if you keep trying until you find solution to this problem instead of asking others. Its good to get stuck and bang head against wall. Teaches you great deal of things including problem solving. — Muhammad Hasan Khan, Jun 23 '11 at 12:33

Martin Liversage · Answer 1 · 2011-06-23T12:42:13.333

You can solve the problem by creating a Lookup mapping letters to a collection of numbers. You can use the extension method ToLookup to create a Lookup.

Warning: Spoilers ahead

Using LINQ you can do it like this (breaks on invalid input):

var text = @"1: A C D
4: A B
5: D F
7: A E
9: B C";

var lookup = text
  .Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
  .Select(
    line => new {
      Number = Int32.Parse(line.Split(':').First()),
      Letters = line.Split(':').Skip(1).First().Split(
        new[] {' '}, StringSplitOptions.RemoveEmptyEntries
      )
    }
  )
  .SelectMany(x => x.Letters, (x, letter) => new { x.Number, Letter = letter })
  .OrderBy(x => x.Letter)
  .ToLookup(x => x.Letter, x => x.Number);

foreach (var item in lookup)
  Console.WriteLine(item.Key + ": " + String.Join(" ", item.ToArray()));

This is the nicest c# code i've seen in a while- very idiomatic like ruby - thanks ! — Dean Radcliffe, Jul 27 '11 at 13:59

sehe · Answer 2 · 2011-06-23T12:58:48.487

The thing that will help you solve this

IDictionary<char, IList<int> >

Yet Another Linq Masturbatory Implementation ("Look Ma! No loops!")

using System;
using System.IO;
using System.Linq;

public static class Program
{
    public static void Main(string[] args)
    {
        File.ReadAllLines("input.txt")
            .Select(line => 
            { 
                var split = line.Split(":".ToCharArray(), 2);
                return new { digit = split[0].Trim().Substring(0,1),
                     chars = split[1]
                        .Split(" \t".ToCharArray())
                        .Select(s=>s.Trim())
                        .Where(s => !String.IsNullOrEmpty(s))
                        .Select(s => s[0])
                    };
            })
            .SelectMany(p => p.chars.Select(ch => new { p.digit, ch }))
            .GroupBy(p => p.ch, p => p.digit)
            .ToList()
            .ForEach(g => Console.WriteLine("{0}: {1}", g.Key, string.Join(" ", g)));
    }
}

Of course you can replace GroupBy with ToLookup

score 1 · Answer 3 · answered Jun 23 '11 at 12:31

1

In case you are familiar with LINQ the below code can give you what you are looking for:

var result = File.ReadAllLines("inFile").SelectMany(line =>
                {
                    var ar = line.Split(" ".ToCharArray());
                    var num = int.Parse(ar[0].Split(":".ToCharArray())[0]);
                    return ar.Skip(1).Select(s => new Tuple<string, int>(s, num));
                }).GroupBy(t => t.Item1).OrderByDescending(g => g.Count())
                .Select(g => g.Key + ": " + g.Select(t => t.Item2.ToString()).Aggregate( (a,b) => a + " " + b));
            File.WriteAllLines("outFile", result);

answered Jun 23 '11 at 12:31

Ankur

33,367
2
46
72

1

It was only a matter of time till C# would degrade to the new Perl (but with Regex-challenged users). Q.E.D. – sehe Jun 23 '11 at 12:55
@sehe yes agree. Seems to be a challenge on writing obscure code – Felice Pollano Jun 23 '11 at 13:00
I wish people can come out of imperative programming world and see the Functional programming world – Ankur Jun 23 '11 at 15:50

score 1 · Answer 4 · answered Jun 23 '11 at 12:50

I know you said you didn't want full answers, but this kind of thing is fun. It looks like others have come up with similar solutions, but here's another way to represent it - in "one line" of code (but lots of brackets!) :)

var data = @"1: A C D
4: A B
5: D F
7: A E
9: B C";

Console.WriteLine(
    String.Join(
        Environment.NewLine,
        (from line in data.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)
         let lineParts = line.Split(new[] { ':', ' ' }, StringSplitOptions.RemoveEmptyEntries)
         from letter in lineParts.Skip(1)
         select new { Number = lineParts[0], Letter = letter })
        .ToLookup(l => l.Letter, l => l.Number)
        .OrderBy(l => l.Key)
        .Select(l => String.Format("{0}: {1}", l.Key, String.Join(" ", l)))));

Oh, and would I write code like that in production? Probably not, but it's fun in an exercise like this!

Felice Pollano · Accepted Answer · 2011-06-23T13:16:14.967

I will use a Dictionary<string,List<int>> I will read the input and add 1 into the list at keys A,C,D, A at keys A,B etc, so having the result is just a lookup by letter. So like this, in a non esoteric way:

 string inp = @"1: A C D
            4: A B
            5: D F
            7: A E
            9: B C";
            Dictionary<string, List<int>> res = new Dictionary<string, List<int>>();
            StringReader sr = new StringReader(inp);
            string line;
            while (null != (line = sr.ReadLine()))
            {
                if (!string.IsNullOrEmpty(line))
                {
                    string[] tokens = line.Split(": ".ToArray(),StringSplitOptions.RemoveEmptyEntries);
                    int idx = int.Parse(tokens[0]);
                    for (int i = 1; i < tokens.Length; ++i)
                    {
                        if (!res.ContainsKey(tokens[i]))
                            res[tokens[i]] = new List<int>();
                        res[tokens[i]].Add(int.Parse(tokens[0]));
                    }
                }
            }

res will contain the result of letter->list of numbers.

I can understand this if the text file started with the letters. However, the letters appear multiple times, how would you read the input to place A as a key given A might come up multiple times? — oJM86o, Jun 23 '11 at 12:53
@oJM86o each time you find a key already in the dictionary,, you take the list at that place and add the int to it. — Felice Pollano, Jun 23 '11 at 12:58
I don't think I understand that, how did your list start out with the keys being a string given the text file starts with numbers. The string / character appears multiple times on each row. Are you starting with a different dictionary and changing it later on? — oJM86o, Jun 23 '11 at 13:01

score 0 · Answer 6 · answered Jun 23 '11 at 12:24

0

String parsing using Split(":") and Split(" "). Then fill

Dictionary<int, List<string>>

and translate it into

Dictionary<string, List<int>>

answered Jun 23 '11 at 12:24

DiVan

381
2
6

score 0 · Answer 7 · edited May 23 '17 at 11:48

0

You could store the input in an IDictionary, and reverse it to produce your output.

Take a look at this question.

edited May 23 '17 at 11:48

Community

1
1

answered Jun 23 '11 at 12:26

Bruno Reis

37,201
11
119
156

score 0 · Answer 8 · answered Jun 23 '11 at 13:21

I see that multiple similar (loops) and not so similar (linq) solutions were already posted but since i've written this i thought i'd throw it in the mix.

static void Main(string[] args)
{
    var result = new SortedDictionary<char, List<int>>();
    var lines = System.IO.File.ReadAllLines(@"input.txt");
    foreach (var line in lines)
    {
        var split = line.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var lineNumber = Int32.Parse(split[0].Substring(0,1));
        foreach (var letter in split.Skip(1))
        {
            var key = letter[0];
            if (!result.ContainsKey(key))
            {
                result.Add(key, new List<int> { lineNumber });
            }
            else
            {
                result[key].Add(lineNumber);
            }
        }
    }
    foreach (var item in result)
    {
        Console.WriteLine(String.Format("{0}: {1}", item.Key, String.Join(" ", item.Value)));
    }
    Console.ReadKey();
}

score 0 · Answer 9 · answered Jun 23 '11 at 13:29

An important part of the interview process is asking about and verifying assumptions. Although your description states the file is structured as an integer followed by letters, the example you give shows the integers in increasing order. If that's the case, you can avoid all of the LINQ craziness and implement a much more efficient solution:

var results = new Dictionary<char, List<int>>();

foreach (var line in File.ReadAllLines(@"input.txt"))
{
    var split = line.Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries);
    var num = int.Parse(split[0].TrimEnd(':'));

    for (int i = 1; i < split.Length; i++)
    {
        char letter = split[i][0];
        if (!results.ContainsKey(letter))
            results[letter] = new List<int>();

        results[letter].Add(num);
    }
}

Mapping numbers to letters

9 Answers9