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!

  • public static string WeirdString(IEnumerable<string> original)

    {

      // I found out that the StringBuilder is WAY faster than just "+"

      StringBuilder sb = new StringBuilder("{}");

      IEnumerable<string> reversed = original.Reverse();

      // Now the last element is the first

      bool andRatherThanComma = true;

      bool moreThanOne = false;

      foreach (string s in reversed)

      {

         if (moreThanOne)

         {

            // If this is NOT the last string in the original list and the first one in the reversed list...

            sb.Insert(andRatherThanComma ? " and " : ", ", 1);

            andRatherThanComma = false;

         }

         else

             moreThanOne = true;

         sb.Insert(s, 1); // insert the string after the first "{" : if it's the fisrt and the last one, we'll get {string}

      }

      return sb.ToString();

    }

  • Hey Eric, why don't you post this on stackoverflow and let the community bubble up the best answers and then you can dissect the best ones on your blog?

  •    /// <param name="delimiter">The delimeter placed before all elements except the first and last.</param>

       /// <param name="lastDelimiter">The delimiter placed before the last element.</param>

       /// <returns>an enumeration with the original elements interleaved with delimiters</returns>

       public static IEnumerable<T> Interleave<T>(this IEnumerable<T> baseEnumeration, T delimiter, T lastDelimiter) {

         using (var iter = baseEnumeration.GetEnumerator()) {

           // guard clause for empty source

           if (!iter.MoveNext()) yield break;

           //first iteration of loop is unrolled because the first item does not have a delimiter

           yield return iter.Current;

           if (!iter.MoveNext()) yield break;

           //This is a while loop with a break in the middle.  I reuse the loop termination test to decide which delimiter to

           // use, thus the body of the loop gets repeated.

           while (true) {

             T item = iter.Current;

             if (iter.MoveNext()) {

               yield return delimiter;

               yield return item;

             } else {

               yield return lastDelimiter;

               yield return item;

               yield break;

             }

           }

         }

       }

    I already had a concatenate a list to a string method.

       /// <summary>

       /// Interleaves the specified enumerable with the given delimiter

       /// </summary>

       /// <typeparam name="T">Basis type of the enumeration</typeparam>

       /// <param name="enumerableToInterleave">The enumerable to interleave.</param>

       /// <param name="delimiter">The delimiter.</param>

       /// <returns>Original enumeration inteleaved with the given delimiter</returns>

       public static IEnumerable<T> Interleave<T>(this IEnumerable<T> enumerableToInterleave, T delimiter) {

         return Interleave<T>(enumerableToInterleave, delimiter, delimiter);

       }

    and then the answer is trivial.

    public static string EnglishList(this IEnumerable<String> input) {

     return "{" } input.Interleave(", ", " and ").ConcatenateStrings() + "}";

    }

    This algorithm only iterates the enumerator once, and requires a single element buffer (the item variable) to detect the last element.  I think separating the inteleave problem from the concatenation problem makes the code read very clear in spite of the somewhat "clever" loop with an exit in the middle which is used in the interleave method.

  • So I should have read the specs a little further and realized that I needed to use the IEnumerable<string> methods in order to implement this algorightm.  Just to make sure my solution is still considered I made some adjustments.  Please see my revised version below.  

    ---

       class Program

       {

           static void Main(string[] args)

           {

               Console.WriteLine(AppendWords(null));

               Console.WriteLine(AppendWords(string.Empty));

               Console.WriteLine(AppendWords("ABC"));

               Console.WriteLine(AppendWords("ABC", "DEF"));

               Console.WriteLine(AppendWords("ABC", "DEF", "GHI"));

               Console.WriteLine(AppendWords("ABC", "DEF", "GHI", "JKL"));

               Console.ReadKey();

           }

           static string AppendWords(params string[] words)

           {

               return AppendWordsInternal(words);

           }

           static string AppendWordsInternal(IEnumerable<string> words)

           {

               if (words == null)

               {

                   return "{}";

               }

               StringBuilder builder = new StringBuilder();

               int appendedWords = 0;

               int totalWords = words.Count();

               int wordsRemaining = 0;

               builder.Append("{");

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

               while (enumerator.MoveNext())

               {

                   builder.Append(enumerator.Current);

                   appendedWords++;

                   wordsRemaining = totalWords - appendedWords;

                   if (appendedWords >= 1

                       && wordsRemaining >= 2)

                   {

                       builder.Append(", ");

                   }

                   else if (wordsRemaining == 1)

                   {

                       builder.Append(" and ");

                   }

               }

               builder.Append("}");

               return builder.ToString();

           }

       }

  •        public static string Join(IEnumerable<string> strings)

           {

               return JoinHelper(strings).Aggregate(new StringBuilder(), (sb, s) => sb.Append(s), sb => sb.ToString());

           }

           private static IEnumerable<string> JoinHelper(IEnumerable<string> strings)

           {

               yield return "{";

               string current = null;

               bool first = true;

               foreach (string item in strings)

               {

                   if (current != null)

                   {

                       if (!first)

                       {

                           yield return ", ";

                       }

                       first = false;

                       yield return current;

                   }

                   current = item;

               }

               if(current != null)

               {

                   if (!first)

                   {

                       yield return " and ";

                   }

                   yield return current;

               }

               yield return "}";            

           }

  • public static void Main()

    {

               PrintFriendlyArray(new string[]{"ABC"});

               PrintFriendlyArray(new string[] {"ABC", "DEF"});

               PrintFriendlyArray(new string[] {"ABC", "DEF","G","H"});

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

    }

    public static void PrintFriendlyArray(IEnumerable<string> strings)

    {

               StringBuilder friendlyString = new StringBuilder();

               friendlyString.Append("{");

               friendlyString.Append(strings.Aggregate((current, next) => (strings.LastOrDefault().Equals(next)?current + " and " + next: current + "," + next)));

               friendlyString.Append("}");

               Console.WriteLine(friendlyString);

    }

  • This is my first post ever, Eric. Apart from handling null, wouldn't this program work in all scenarios? I also see that my naming is not consistent. The method name should have been PrintFriendlyString instead of PrintFriendlyArray, right?

    This is the most straightforward and semantically nearest program I could think of.

    Reply if you find time.

  •    class Program

       {

           static void Main(string[] args)

           {

               Console.WriteLine(Lippertize(new string[0]));

               Console.WriteLine(Lippertize(new string[]{"ABC"}));

               Console.WriteLine(Lippertize(new string[]{"ABC", "DEF"}));

               Console.WriteLine(Lippertize(new string[]{"ABC", "DE, F", "G", "H"}));

               Console.ReadKey();

           }

           static string Lippertize(IEnumerable<string> source)

           {

               return "{" + Concat(source, ", ", " and ") + "}";

           }

           static string Concat(IEnumerable<string> source, string separator, string lastSeparator)

           {

               var firstItem  = true;

               var gotTwo = false;

               var lastSeparatorPos = 0;

               var sb = new StringBuilder();

               var quoted = from s in source

                            where !string.IsNullOrEmpty(s)

                            select s;

               foreach (var item in quoted)

               {

                   if (!firstItem)

                   {

                       gotTwo = true;

                       lastSeparatorPos = sb.Length;

                       sb.Append(separator);

                   }

                   else

                       firstItem = false;

                   sb.Append(item);

               }

               if (gotTwo) // step back and replace the last separator with the correct one:

               {

                   sb.Remove(lastSeparatorPos, separator.Length);

                   sb.Insert(lastSeparatorPos, lastSeparator);

               }

               return sb.ToString();

           }

       }

  • Quite verbose (even without the unit tests). But works.

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    using NUnit.Framework;

    namespace CommaQuibble

    {

       [TestFixture]

       public class QuibblerFixture

       {

           [Test]

           public void EmptyList()

           {

               IEnumerable<string> list = new[] {""};

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{}", quibbled);

           }

           private static string GetQuibbled(IEnumerable<string> list)

           {

               Quibbler quibbler = new Quibbler();

               return quibbler.Quibble(list);

           }

           [Test]

           public void OneItemInList()

           {

               IEnumerable<string> list = new[] {"ABC"};

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{ABC}", quibbled);

           }

           [Test]

           public void TwoItemsInList()

           {

               string[] list = new[] { "ABC", "DE" };

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{ABC and DE}", quibbled);

           }

           [Test]

           public void ThreeItemsInList()

           {

               string[] list = new[] { "ABC", "DE", "ZYXWV" };

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{ABC, DE and ZYXWV}", quibbled);

           }

           [Test]

           public void ManyMany()

           {

               string[] list = new[] { "ABC", "DE", "ZYXWV", "FG", "UT", "HI", "SR", "JK", "QP", "LM", "NO" };

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{ABC, DE, ZYXWV, FG, UT, HI, SR, JK, QP, LM and NO}", quibbled);

           }

           [Test]

           public void ViacheslavIvanov()

           {

               string[] list = new[] { "", ",", "}" };

               string quibbled = GetQuibbled(list);

               Assert.AreEqual("{, , and }}", quibbled);

           }

       }

       public class Quibbler

       {

           public string Quibble(IEnumerable<string> enumerable)

           {

               StringBuilder builder = new StringBuilder("{");

               string last = enumerable.Last();

               string first = enumerable.First();

               if(first == last)

               {

                   builder.Append(first);

               }

               else if(first != last)

               {

                   IEnumerable<string> rest = enumerable.Except(new[] { last });

                   string penultimate = rest.Last();

                   QuietStack stacked = new QuietStack(rest.Reverse());

                   while (stacked.Peek() != null)

                   {

                       string current = stacked.Pop();

                       builder.Append(current);

                       if (current != penultimate)

                           builder.Append(", ");

                   }

                   builder.AppendFormat(" and {0}", last);

               }

               builder.Append("}");

               return builder.ToString();  

           }

       }

       class QuietStack

       {

           private readonly Stack<string> m_Stack;

           public QuietStack(IEnumerable<string> collection)

           {

               m_Stack = new Stack<string>(collection);

           }

           public string Pop()

           {

               return m_Stack.Pop();

           }

           public string Peek()

           {

               try

               {

                   return m_Stack.Peek();

               }

               catch (InvalidOperationException)

               {

                   return null;

               }

           }

       }

    }

  • How to misuse LINQ:

           public void RunTest()
           {
               Console.WriteLine(new Class1().GetResult(new string[] { }));
               Console.WriteLine(new Class1().GetResult(new[] { "ABC" }));
               Console.WriteLine(new Class1().GetResult(new[] { "ABC", "DEF" }));

               Console.WriteLine(new Class1().GetResult(new[] { "ABC", "DEF", "GHI" }));
           }
           public string GetResult(IEnumerable<string> input)
           {
               var list = new List<string>(input);
               if (list.Count == 0) return "{}";
               if (list.Count == 1) return "{" + list[0] + "}";
               return "{" + string.Join(", ", list.Take(list.Count - 1).ToArray()) + " and " + list[list.Count - 1] + "}";
           }

  • I would go with Olivier and mdefalco here. My solution was almost identical to Olivier's.

    I really felt the need to some sort of recursive String.Format method.

    However, one that is closer to my heart is:

    public string Join(IEnumerable<string> strings)

           {

               if (strings == null || !strings.Any()) return "{}";

               var q = new Queue<string>(strings);

               var last = q.Dequeue();

               if (q.Count == 0) return "{" + last + "}";

               return "{" + string.Join(", ", q.ToArray()) + " and " + last + "}";

           }

  • Most of the F# posts use list pattern matching, conveniently ignoring that the input is a sequence, _not_ a list.  The following solution allows for pattern matching without incurring the cost of converting the sequence to a list.  It is declarative, scales roughly linearly when used with Parallel Extensions, and uses a StringBuilder at the concatenation stage for maximum efficiency.

    open System

    open System.Text

    let concat_string (list: string seq) =

       let tripleWise =

           Seq.append list [null]

           |> Seq.scan

               (fun (_, previousPrevious, previous) current ->

                   (previousPrevious, previous, current)

               )

               (null, null, null)

       let contents =

           tripleWise.AsParallel()

           |> PSeq.map

               (function

               | _, null, _ -> String.Empty

               | null, curr, null -> curr            

               | null, first, _ -> first

               | _, last, null -> sprintf " and %s" last

               | prev, curr, next -> sprintf ", %s" curr)

       let builder = StringBuilder()

       contents |> Seq.iter (fun item -> (builder.Append(item) |> ignore))

       sprintf "{%s}" (builder.ToString())

  • I like terse:

    string CommaQuibble(IEnumerable<string> words)

    {

       return string.Format("{{{0}}}", string.Join(", ", words.Take(words.Count() - 2).Concat(new[] {

                 string.Join(" and ", words.Skip(words.Count() - 2).ToArray()) }).ToArray()));

    }

    (should check for null, though)

  •        // Using SmartEnumerable by John Skeet http://msmvps.com/blogs/jon_skeet/archive/2007/07/27/smart-enumerations.aspx

           public string Concatenate(IEnumerable<string> sequence)

           {

               SmartEnumerable<string> smartSequence = sequence.AsSmartEnumerable();

               StringBuilder result = new StringBuilder();

               result.Append("{");

               foreach (var word in smartSequence)

               {

                   if (!word.IsFirst && !word.IsLast)

                   {

                       result.Append(", " + word.Value);

                   }

                   else if (!word.IsFirst && word.IsLast )

                   {

                       result.Append(" and " + word.Value);

                   }

                   else

                   {

                       result.Append(word.Value);

                   }

               }

               result.Append("}");

               return result.ToString();

           }

  • My quick solution as a full program.  My goals were to stay with an imperative C# style, make the main function readable and to maintain the stream nature of IEnumerable (no multiple passes, no duplication via creating a list/array which makes the problem too simple).

    The trick here is the one-off enumerator that adds an IsFirst/IsLast.  Its definitely a one-off class as written since it doesn't obey IEnumerable's specification -- though changing it to do so wouldn't be hard.  But you know what they say about code that's not yet needed.

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    using System.Collections;

    namespace MakeFancyString

    {

       class SpecialEnumerable : IEnumerable, IEnumerator

       {

       private IEnumerator<String> source;

       private int itemNumber;

       public SpecialEnumerable(IEnumerable<String> source)

       {

       this.source = source.GetEnumerator();

       Reset();

       }

       public IEnumerator GetEnumerator() { return this; }

       public bool IsFirst { get { return itemNumber == 0; } }

       public bool IsLast { get; private set; }

       public object Current { get; private set; }

       public bool MoveNext()

       {

       if (IsLast)

       return false;

       Current = source.Current;

       ++itemNumber;

       IsLast = !source.MoveNext();

               return true;

       }

       public void Reset()

       {

       source.Reset();

       Current = null;

       itemNumber = -1;

       IsLast = !source.MoveNext();

       }

       }

       class Program

       {

           static String MakeList(IEnumerable<String> input)

           {

               StringBuilder builder = new StringBuilder();

               builder.Append("{");

               var enumerable = new SpecialEnumerable(input);

               foreach (String item in enumerable)

               {

                   if (enumerable.IsFirst)

                       ;

                   else if (enumerable.IsLast)

                       builder.Append(" and ");

                   else

                       builder.Append(", ");

                   builder.Append(item);

               }

               builder.Append("}");

               return builder.ToString();

           }

           static void Main(string[] args)

           {

               Console.WriteLine(MakeList(new String[] { }));                              // {}

               Console.WriteLine(MakeList(new String[] { "ABC" }));                        // {ABC}

               Console.WriteLine(MakeList(new String[] { "ABC", "DEF", }));                // {ABC and DEF}

               Console.WriteLine(MakeList(new String[] { "ABC", "DEF", "GHI" }));          // {ABC, DEF and GHI}

               Console.WriteLine(MakeList(new String[] { "ABC", "DEF", "GHI", "JKL" }));   // {ABC, DEF, GHI and JKL}

           }

       }

    }

Page 6 of 19 (277 items) «45678»