Comma Quibbling

Comma Quibbling

Rate This

[UPDATE: Holy goodness. Apparently this was a more popular pasttime than I anticipated. There's like a hundred solutions in there. Who knew there were that many ways to stick commas in a string? It will take me some time to go through them all, so don't be surprised if it's a couple of weeks until I get them all sorted out.]

Comma The point of Monday’s post about comma-separated lists was not so much about the actual problem; it’s a rather trivial problem. Rather, I wanted to make two points. First, stating the actual problem rather than a much harder and more general version of the problem is likely to get you a realistic solution to your actual problem much faster. And second, reworking the statement of the problem into an equivalent but structurally different statement is a great way to see solutions that you might have otherwise missed.

But whenever I make a post illustrating such points with a specific example, lots of people pipe up with their ideas for how to solve the specific example. Which is awesome; I encourage this behaviour.

So in that spirit, here’s a slightly harder version of the string concatenation problem, just for the fun of it. Write me a function that takes a non-null IEnumerable<string> and returns a string with the following characteristics:

(1) If the sequence is empty then the resulting string is "{}".
(2) If the sequence is a single item "ABC" then the resulting string is "{ABC}".
(3) If the sequence is the two item sequence "ABC", "DEF" then the resulting string is "{ABC and DEF}".
(4) If the sequence has more than two items, say, "ABC", "DEF", "G", "H" then the resulting string is "{ABC, DEF, G and H}". (Note: no Oxford comma!)

I think you get the idea. You can post your solution in the comments or use the link on the blog page to email your solution to me.

The strings in the sequence can be assumed to be non-null but can otherwise be any string value, including empty strings or strings containing commas, braces and "and".

There’s no size limit on the sequence; it could be tiny, it could be thousands of strings. But it will be finite.

All you get are the methods of IEnumerable<string>; if you want to make that thing into a list or an array, you’re going to need to do that explicitly rather than casting it and hoping for the best.

I am particularly interested in solutions which make the semantics of the code very clear to the code maintainer.

Of course, C# is most interesting to me, but if there are neat ways to express this in other languages, I’d love to see them too.

If there are any particularly amusing or interesting implementations I’ll dissect them on the blog in a future episode, probably in a week or so. I’m not going to have time to do a detailed analysis of every one.

And… go!

  • using System;
    using System.Collections.Generic;
    public class CommaQuibbling
    {
      static string Extend(string concat, string separator, string value)
      {
        if ( value == null)
          return concat;
        if ( concat.Length > 1)
          return concat + separator + value;
        return concat + value;
      }
      static string Concat(IEnumerable<string> strings)
      {
        var concat = "{";
        var iter = strings.GetEnumerator();
        string lastItem = null;
        while (iter.MoveNext())
        {
          concat = Extend(concat, ", ", lastItem);
          lastItem = iter.Current;
        }
        concat = Extend(concat," and ", lastItem);
        return concat + "}";
      }
      static void TestConcat(IEnumerable<string> strings, string expected)
      {
        var value = Concat(strings);
        WL("{0} == {1} => {2}", expected, value, expected == value);
      }
      public static void Main()
      { 
        TestConcat(new string[]{}, "{}");
        TestConcat(new []{"ABC"}, "{ABC}");
        TestConcat(new []{"ABC", "DEF"}, "{ABC and DEF}");
        TestConcat(new []{"ABC", "DEF", "G", "H"}, "{ABC, DEF, G and H}");
        Console.ReadLine();
      }
      static void WL(object text, params object[] args)
      {
        Console.WriteLine(text.ToString(), args);
      }
    }

  • Here is my single pass solution

           public string MakeNonOxfordList(IEnumerable<string> values)

           {

               IEnumerator<string> enumerator = values.GetEnumerator();

               string current = "";

               StringBuilder output = new StringBuilder();

               while(enumerator.MoveNext())

               {

                   if(output.Length>0)

                   {

                       output.Append(", ");

                   }

                   output.Append(current);

                   current = enumerator.Current;

               }

               if(output.Length==0)

               {

                   output.Append(current);

               }

               else

               {

                    output.Append(" AND " + current);

               }

               return "{" + output + "}";

           }

  • I went after two different options - one for utmost clarity and one for performance. I'd use the performant one if I was exposing this method as a public because I have no idea of what's being enumerated.

    However, I suspect that in some cases the internal unsafe implementation of string.Join will beat the StringBuilder, making the "clarity" approach faster than the "performant" approach. If I read the source right for string.Join, it will only ever do a single allocation, while StringBuilder will do a normal growth behavior as you add to it.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    namespace StringGame
    {
       class Program
       {
           private static string GetPrettyJoinClear(IEnumerable<string> theStrings)
           {
               List<string> list = theStrings.ToList();
               switch (list.Count())
               {
                   case 0:
                       return "{}";
                   case 1:
                       return "{" + list[0] + "}";
                   case 2:
                       return "{" + list[0] + " and " + list[1] + "}";
                   default:
                       // Faster for some cases
                       list[0] = "{" + list[0];
                       list[list.Count - 2] = string.Join(" and ", new string[] { list[list.Count - 2], list[list.Count - 1] + "}" });
                       return string.Join(", ", list.Take(list.Count - 1).ToArray());
                       // Clearer for all cases
                       //return 
                       //    "{" + 
                       //    string.Join(", ", list.Take(list.Count - 1).ToArray()) + 
                       //    " and " + 
                       //    list[list.Count - 1] + 
                       //    "}";
               }
           }

           private static string GetPrettyJoinOnePass(IEnumerable<string> theStrings)
           {
               StringBuilder sb = new StringBuilder();
               sb.Append("{");
               IEnumerator<string> ie = theStrings.GetEnumerator();
               bool isFirst = true;
               bool isSecond = true;
               string oneAgo = string.Empty;
               string twoAgo = string.Empty;
               foreach (string current in theStrings)
               {
                   if (isFirst)
                   {
                       oneAgo = current;
                       isFirst = false;
                       continue;
                   }
                   if (isSecond)
                   {
                       twoAgo = oneAgo;
                       oneAgo = current;
                       isSecond = false;
                       continue;
                   }
                   sb.Append(twoAgo);
                   sb.Append(", ");
                   twoAgo = oneAgo;
                   oneAgo = current;
               }
               if (!isFirst)
               {
                   if (!isSecond)
                   {
                       sb.Append(twoAgo);
                       sb.Append(" and ");
                   }
                   sb.Append(oneAgo);
               }
               sb.Append("}");
               return sb.ToString();
           }

           static void Main(string[] args)
           {
               string[] testArray26 = new string[] { 
                   "a", "b", "c", "d", "e", 
                   "f", "g", "h", "i", "j", 
                   "k", "l", "m", "n", "o", 
                   "p", "q", "r", "s", "t", 
                   "u", "v", "w", "x", "y", "z" };
               string[] testArray3 = new string[] { "A", "B", "C" };
               string [] testArray2 = new string[] { "A", "B"};
               string [] testArray1 = new string[] { "A" };
               string[] testArray0 = new string[] { };
               RunTest(testArray0);
               RunTest(testArray1);
               RunTest(testArray2);
               RunTest(testArray3);
               RunTest(testArray26);
               Console.ReadLine();
           }

           private static void RunTest(string[] activeArray)
           {
               string output = GetPrettyJoinOnePass(activeArray.AsEnumerable());
               string output2 = GetPrettyJoinClear(activeArray.AsEnumerable());
               Console.WriteLine("Testing with string: " + string.Join("", activeArray));
               Console.WriteLine("One Pass Result : " + output);
               Console.WriteLine("Clear Result    : " + output2 );
               Console.WriteLine();
           }
       }
    }

  • Whoops, I prefer tabs over spaces ;)

    I also left out StringBuilder and went for string concat for simplicity's sake.

    // Ryan

  • Here's my take in F#. Using pattern matching, the code reads just like the problem specification:

    #light

    let format (words:list<string>) =

       let rec makeList (words: list<string>) =

           match words with

               | [] -> ""

               | first :: [] -> first

               | first :: second :: [] -> first + " and " + second

               | first :: second :: rest -> first + ", " + second + ", " + (makeList rest)

       "{" + (makeList words) + "}"

    and the test case:

    printfn "%s" (format [])        

    printfn "%s" (format ["ABC"])

    printfn "%s" (format ["ABC"; "DEF"])

    printfn "%s" (format ["ABC"; "DEF"; "G"; "H"])

    yields:

    {}

    {ABC}

    {ABC and DEF}

    {ABC, DEF, G and H}

  • Here's my LINQ solution:

    public static string CommaQuibbling(IEnumerable<string> items)

    {

       Func<int, string> getSeparator = (i) => i == 0 ? string.Empty : (i == 1 ? " and " : ", ");

       string answer = string.Empty;

       return "{" + items

           .Reverse()

           .Select((s, i) => new { Index = i, Value = s })

           .Aggregate(answer, (s, a) => a.Value + getSeparator(a.Index) + s) + "}";

    }

  • I think most solutions posted here are convoluted. I also don't like building up strings and then later editing them to conform to the rules. Some of the posted solutions are very nice, though!

    I thought it'd be fun to build a short but sweet LINQed solution. Assume input is in 'IEnumerable<string> strings'.

    int last = strings.Count() - 1;

    Func<string, int, string> prefixer =

       delegate(string s, int index)

       {

           if (index == 0)

               return s;

           if (index == last)

               return " and " + s;

           return ", " + s;

       };

    return "{" + string.Concat(strings.Select(prefixer).ToArray()) + "}";

  • using System;

    using System.Collections.Generic;

    using System.Text;

    using MbUnit.Framework;

    namespace TestApp.Fun {

       /// <summary>

       /// Solution to problem at

       /// http://blogs.msdn.com/ericlippert/archive/2009/04/15/comma-quibbling.aspx

       /// </summary>

       public class Comma_Quibbling {

           public static string Concatenate(IEnumerable<string> sequence) {

               string remainderFormat = "{0}, ";

               string secondToLastFormat = "{0} and ";

               string lastFormat = "{0}";

               Queue<string> queue = new Queue<string>(3);

               StringBuilder sb = new StringBuilder("{");

               foreach (string item in sequence) {

                   queue.Enqueue(item);

                   if (queue.Count > 2) {

                       sb.AppendFormat(remainderFormat, queue.Dequeue());

                   }

               }

               if (queue.Count == 2) {

                   sb.AppendFormat(secondToLastFormat, queue.Dequeue());

               }

               if (queue.Count == 1) {

                   sb.AppendFormat(lastFormat, queue.Dequeue());

               }

               sb.Append("}");

               return sb.ToString();

           }

           [TestFixture]

           public class UnitTests {

               [Test]

               [Row(new string[] { }, "{}")]

               [Row(new string[] { "ABC" }, "{ABC}")]

               [Row(new string[] { "ABC", "DEF" }, "{ABC and DEF}")]

               [Row(new string[] { "ABC", "DEF", "G", "H" }, "{ABC, DEF, G and H}")]

               public void TestConcat(IEnumerable<string> sequence,

                                         string expectedResult) {

                   string result = Concatenate(sequence);

                   Assert.AreEqual<string>(expectedResult, result);

               }

           }

       }

    }

  • This looked like a fun problem, I'm a python guy though, so tried to solve it in python.

    In python I would convert the input to a list too. I don't think there is any performance benefit in looping over the input data directly, as concatenating to an existing string probably causes it to be re-allocated and copied, which I think negates any benefit gained from not doing the conversion to list up-front.

    def comma (data):

       seq = list(data)

       end = ""

       if len(seq) > 1:

           end = " and " + seq.pop ()

       return "{%s%s}" % (", ".join (seq), end)

  • Here's mine in python, along with the matching problem statement.

    to iterate with oxford commas, we follow these rules;

    A) Every item except the last two is followed by a comma and space
    B) The penultimate item is spearated by ' and '
    C) The last item stands alone.

    Here's the python;

       def noOxfordComma(sequence):  
         queue = []
         result = ""
         for item in sequence:
           queue.append(item)
           if len(queue) > 2: result = result + queue.pop() + ", "
         if len(queue) == 2: result = result + queue.pop() + " and "
         if len(queue) == 1: result = result + queue.pop()
         return "{" + result + "}"

  • Not as elegant as some of the other solutions but I will still post it.

           //We need to create comma separated list but with a twist.

           //The last word will have AND in front of it instead of a comma.

           //To achieve this, we will create a new list from the original list

           //while putting , in front of each word, except for the first word.

           //For the last word, we will replace comma with AND.

           private static string JoinWords2(IEnumerable<string> words)

           {

               List<string> output = new List<string>();

               foreach (string word in words)

               {

                   string separator = output.Count == 0 ? string.Empty : ", ";

                   output.Add(separator + word);

               }

               if(output.Count > 1)

               {

                   string lastWord = output[output.Count - 1].Substring(2); //SUBSTRING will get rid of the ", " in front of the actual word.

                   output[output.Count - 1] = " AND " + lastWord; //And we will prepend the word with AND.

                   //We are not doing search and replace on "," because the last word could very well be "," and

                   //search replace will break it.

               }

               return string.Format("{{{0}}}", string.Join(string.Empty, output.ToArray()));

           }

  • My earlier solution didnt handle all the scenarios.

    public static void Format(string pSomeText, IEnumerable<string> pStrings)

           {

               var x = pStrings

                           .Reverse()

                           .Skip(1)

                           .Reverse()

                           .DefaultIfEmpty()

                           .Aggregate((a, b) => a += ", " + b);

               var y = String.Concat(x,

                                    (pStrings.Count() > 1 ? " And " : ""),

                                     pStrings.DefaultIfEmpty().Last());

               Console.WriteLine(String.Format("{0} -> {{ {1} }}", pSomeText, y));

           }

          Format("Empty Sequence", new List<string> { });

          Format("Single Item", new List<string> { "ABC" });

          Format("Two Items", new List<string> { "ABC", "DEF" });

          Format("> 2 Items", new List<string> { "ABC", "DEF", "G", "H" });

  • // please read carefully very important comment in the next line

    // :)

    using System;

    using System.Text;

    using System.IO;

    using System.Collections.Generic;

    using System.Linq;

    namespace xTry {

       class MainClass {

           private static string delimiter;

           public static void Main()

           {

               TestConcat(new string[]{}, "{}");

               TestConcat(new []{"ABC"}, "{ABC}");

               TestConcat(new []{"ABC", "DEF"}, "{ABC and DEF}");

               TestConcat(new []{"ABC", "DEF", "G", "H"}, "{ABC, DEF, G and H}");

           }

           static void TestConcat(IEnumerable<string> strings, string expected)

           {

               var value = Concat(strings);

               Console.WriteLine("{0} == {1} => {2}", expected, value, expected == value);

           }

           static string Concat(IEnumerable<string> strings)

           {

               string res = "";

               delimiter=" and ";

               if(strings.Count()>0)

               {

                   res=strings.Reverse().Aggregate((workingSentence, next) => next + GetDelimiter() + workingSentence);

               }

               return "{"+res+"}";

           }

           private static string GetDelimiter()

           {

               string tmp=delimiter;

               delimiter=", ";

               return tmp;

           }

       }

    }

  • I don't see any Ruby here. This is unacceptable. And where are everyone's tests?

    module Enumerable

    def bracketed_english_join

    out = inject([]) { |array, item| array + [item, ', '] }

    '{' +

    case out.length

    when 0 then ''

    when 2 then out[0]

    else (

    out[out.length - 3] = ' and ';

    out[0, out.length - 1].join

    )

    end +

    '}'

    end

    end

    if __FILE__ == $0

    require 'test/unit'

    class BracketedEnglishJoinTestCase < Test::Unit::TestCase

    def test_empty_returns_empty_string

    assert_equal('{}', [].bracketed_english_join)

    end

    def test_single_returns_item_only

    assert_equal(

    '{ABC}',

    ['ABC'].bracketed_english_join

    )

    end

    def test_dual_returns_and_separated

    assert_equal(

    '{ABC and DEF}',

    ['ABC', 'DEF'].bracketed_english_join

    )

    end

    def test_many_returns_comma_then_and_separated

    assert_equal(

    '{ABC, DEF, G and H}',

    ['ABC', 'DEF', 'G', 'H'].bracketed_english_join

    )

    end

    end

    end

  • Oops, Fernando Nicolet already put together something very similar :(

Page 3 of 19 (277 items) 12345»