c# - エリック・リッパートの挑戦「コンマを震わせる」、ベストアンサー？

Question

私はこの課題をstackoverflowコミュニティの注目を集めたかったのです。元の問題と答えはここにあります。ところで、あなたが以前にそれをフォローしていなかったなら、あなたはエリックのブログを読むことを試みるべきです、それは純粋な知恵です。

概要：

null以外のIEnumerableを受け取り、次の特性を持つ文字列を返す関数を記述します。

シーケンスが空の場合、結果の文字列は「{}」です。
シーケンスが単一アイテム「ABC」の場合、結果の文字列は「{ABC}」になります。
シーケンスが2項目シーケンス「ABC」、「DEF」の場合、結果の文字列は「{ABCandDEF}」になります。
シーケンスに「ABC」、「DEF」、「G」、「H」などの3つ以上の項目がある場合、結果の文字列は「{ABC、DEF、G、およびH}」になります。（注：オックスフォードコンマはありません！）

ご覧のとおり、私たち自身のJon Skeet（はい、同時に2つの場所にいることができることはよく知られています）が解決策を投稿しましたが、彼の（IMHO）は最もエレガントではありませんが、おそらくあなたはそれを打ち負かすことはできませんパフォーマンス。

どう思いますか？そこにはかなり良いオプションがあります。私は、（Fernando Nicoletの）selectメソッドとaggregateメソッドを含むソリューションの1つが本当に好きです。Linqは非常に強力であり、このような課題に時間を割くことで多くのことを学ぶことができます。私はそれを少しひねったので、それはもう少しパフォーマンスが高く、明確です（カウントを使用し、リバースを回避することによって）：

public static string CommaQuibbling(IEnumerable<string> items)
{
    int last = items.Count() - 1;
    Func<int, string> getSeparator = (i) => i == 0 ? string.Empty : (i == last ? " and " : ", ");
    string answer = string.Empty;

    return "{" + items.Select((s, i) => new { Index = i, Value = s })
                      .Aggregate(answer, (s, a) => s + getSeparator(a.Index) + a.Value) + "}";
}

score 33 · Accepted Answer

非効率的ですが、明確だと思います。

public static string CommaQuibbling(IEnumerable<string> items)
{
    List<String> list = new List<String>(items);
    if (list.Count == 0) { return "{}"; }
    if (list.Count == 1) { return "{" + list[0] + "}"; }

    String[] initial = list.GetRange(0, list.Count - 1).ToArray();
    return "{" + String.Join(", ", initial) + " and " + list[list.Count - 1] + "}";
}

私がコードを保守していた場合、より賢いバージョンよりもこれを好むでしょう。

score 28 · Accepted Answer

このアプローチはどうですか？純粋に累積的-バックトラッキングはなく、1回だけ繰り返します。生のパフォーマンスについては、LINQの答えがどれほど「きれい」であるかにかかわらず、LINQなどでうまくいくかどうかはわかりません。

using System;
using System.Collections.Generic;
using System.Text;

static class Program
{
    public static string CommaQuibbling(IEnumerable<string> items)
    {
        StringBuilder sb = new StringBuilder('{');
        using (var iter = items.GetEnumerator())
        {
            if (iter.MoveNext())
            { // first item can be appended directly
                sb.Append(iter.Current);
                if (iter.MoveNext())
                { // more than one; only add each
                  // term when we know there is another
                    string lastItem = iter.Current;
                    while (iter.MoveNext())
                    { // middle term; use ", "
                        sb.Append(", ").Append(lastItem);
                        lastItem = iter.Current;
                    }
                    // add the final term; since we are on at least the
                    // second term, always use " and "
                    sb.Append(" and ").Append(lastItem);
                }
            }
        }
        return sb.Append('}').ToString();
    }
    static void Main()
    {
        Console.WriteLine(CommaQuibbling(new string[] { }));
        Console.WriteLine(CommaQuibbling(new string[] { "ABC" }));
        Console.WriteLine(CommaQuibbling(new string[] { "ABC", "DEF" }));
        Console.WriteLine(CommaQuibbling(new string[] {
             "ABC", "DEF", "G", "H" }));
    }
}

score 5 · Accepted Answer

最初/最後の情報を必要とするストリームで多くのことを行っていた場合、次の拡張機能が必要です。

[Flags]
public enum StreamPosition
{
   First = 1, Last = 2
}

public static IEnumerable<R> MapWithPositions<T, R> (this IEnumerable<T> stream, 
    Func<StreamPosition, T, R> map)
{
    using (var enumerator = stream.GetEnumerator ())
    {
        if (!enumerator.MoveNext ()) yield break ;

        var cur   = enumerator.Current   ;
        var flags = StreamPosition.First ;
        while (true)
        {
            if (!enumerator.MoveNext ()) flags |= StreamPosition.Last ;
            yield return map (flags, cur) ;
            if ((flags & StreamPosition.Last) != 0) yield break ;
            cur   = enumerator.Current ;
            flags = 0 ;
        }
    }
}

次に、最も簡単な（最速ではなく、さらにいくつかの便利な拡張メソッドが必要になる）ソリューションは次のようになります。

public static string Quibble (IEnumerable<string> strings)
{
    return "{" + String.Join ("", strings.MapWithPositions ((pos, item) => (
       (pos &  StreamPosition.First) != 0      ? "" : 
        pos == StreamPosition.Last   ? " and " : ", ") + item)) + "}" ;
}

score 3 · Accepted Answer

ここではPythonのワンライナーとして


>>> f=lambda s:"{%s}"%", ".join(s)[::-1].replace(',','dna ',1)[::-1]
>>> f([])
'{}'
>>> f(["ABC"])
'{ABC}'
>>> f(["ABC","DEF"])
'{ABC and DEF}'
>>> f(["ABC","DEF","G","H"])
'{ABC, DEF, G and H}'

このバージョンの方がわかりやすいかもしれません


>>> f=lambda s:"{%s}"%" and ".join(s).replace(' and',',',len(s)-2)
>>> f([])
'{}'
>>> f(["ABC"])
'{ABC}'
>>> f(["ABC","DEF"])
'{ABC and DEF}'
>>> f(["ABC","DEF","G","H"])
'{ABC, DEF, G and H}'

score 2 · Accepted Answer

免責事項: 私はこれを新しいテクノロジをいじる言い訳として使用したため、私のソリューションは、明快さと保守性に対する Eric の当初の要求を実際には満たしていません。

素朴な列挙子の解決策 (foreach手動で列挙子をいじる必要がないため、これの変種の方が優れていることは認めます。)

public static string NaiveConcatenate(IEnumerable<string> sequence)
{
    StringBuilder sb = new StringBuilder();
    sb.Append('{');

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

    if (enumerator.MoveNext())
    {
        string a = enumerator.Current;
        if (!enumerator.MoveNext())
        {
            sb.Append(a);
        }
        else
        {
            string b = enumerator.Current;
            while (enumerator.MoveNext())
            {
                sb.Append(a);
                sb.Append(", ");
                a = b;
                b = enumerator.Current;
            }
            sb.AppendFormat("{0} and {1}", a, b);
        }
    }

    sb.Append('}');
    return sb.ToString();
}

LINQ を使用したソリューション

public static string ConcatenateWithLinq(IEnumerable<string> sequence)
{
    return (from item in sequence select item)
        .Aggregate(
        new {sb = new StringBuilder("{"), a = (string) null, b = (string) null},
        (s, x) =>
            {
                if (s.a != null)
                {
                    s.sb.Append(s.a);
                    s.sb.Append(", ");
                }
                return new {s.sb, a = s.b, b = x};
            },
        (s) =>
            {
                if (s.b != null)
                    if (s.a != null)
                        s.sb.AppendFormat("{0} and {1}", s.a, s.b);
                    else
                        s.sb.Append(s.b);
                s.sb.Append("}");
                return s.sb.ToString();
            });
}

TPLによるソリューション

このソリューションでは、プロデューサー/コンシューマーキューを使用して入力シーケンスをプロセッサに供給しながら、少なくとも 2 つの要素をキューにバッファリングします。プロデューサーが入力シーケンスの最後に到達すると、最後の 2 つの要素を特別な処理で処理できます。

後から考えると、コンシューマーを非同期で動作させる理由はありません。これにより、同時キューが不要になりますが、前に述べたように、これを新しいテクノロジーをいじる言い訳として使用しているだけです :-)

public static string ConcatenateWithTpl(IEnumerable<string> sequence)
{
    var queue = new ConcurrentQueue<string>();
    bool stop = false;

    var consumer = Future.Create(
        () =>
            {
                var sb = new StringBuilder("{");
                while (!stop || queue.Count > 2)
                {
                    string s;
                    if (queue.Count > 2 && queue.TryDequeue(out s))
                        sb.AppendFormat("{0}, ", s);
                }
                return sb;
            });

    // Producer
    foreach (var item in sequence)
        queue.Enqueue(item);

    stop = true;
    StringBuilder result = consumer.Value;

    string a;
    string b;

    if (queue.TryDequeue(out a))
        if (queue.TryDequeue(out b))
            result.AppendFormat("{0} and {1}", a, b);
        else
            result.Append(a);

    result.Append("}");
    return result.ToString();
}

簡潔にするために単体テストは省略されています。

score 2 · Accepted Answer

これは単純な F# ソリューションで、前方反復を 1 回だけ実行します。

let CommaQuibble items =
    let sb = System.Text.StringBuilder("{")
    // pp is 2 previous, p is previous
    let pp,p = items |> Seq.fold (fun (pp:string option,p) s -> 
        if pp <> None then
            sb.Append(pp.Value).Append(", ") |> ignore
        (p, Some(s))) (None,None)
    if pp <> None then
        sb.Append(pp.Value).Append(" and ") |> ignore
    if p <> None then
        sb.Append(p.Value) |> ignore
    sb.Append("}").ToString()

(編集: これは Skeet のものと非常によく似ていることがわかりました。)

テストコード:

let Test l =
    printfn "%s" (CommaQuibble l)

Test []
Test ["ABC"]        
Test ["ABC";"DEF"]        
Test ["ABC";"DEF";"G"]        
Test ["ABC";"DEF";"G";"H"]        
Test ["ABC";null;"G";"H"]

score 2 · Accepted Answer

私はシリアル・コンマのファンです。私は食べて、撃って、去ります。

この問題の解決策が常に必要であり、3 つの言語で解決しました (C# ではありません)。any で機能するメソッドを作成することにより、次のソリューションを適応させます（Luaでは、答えを中括弧で囲みません）：concatIEnumerable

function commafy(t, andword)
  andword = andword or 'and'
  local n = #t -- number of elements in the numeration
  if n == 1 then
    return t[1]
  elseif n == 2 then
    return concat { t[1], ' ', andword, ' ', t[2] }
  else
    local last = t[n]
    t[n] = andword .. ' ' .. t[n]
    local answer = concat(t, ', ')
    t[n] = last
    return answer
  end
end

score 2 · Accepted Answer

別の変形 - コードを明確にするために、句読点と反復ロジックを分離します。そして、まだパフォーマンスについて考えています。

純粋な IEnumerable/string/ で要求どおりに機能し、リスト内の文字列を null にすることはできません。

public static string Concat(IEnumerable<string> strings)
{
    return "{" + strings.reduce("", (acc, prev, cur, next) => 
               acc.Append(punctuation(prev, cur, next)).Append(cur)) + "}";
}
private static string punctuation(string prev, string cur, string next)
{
    if (null == prev || null == cur)
        return "";
    if (null == next)
        return " and ";
    return ", ";
}

private static string reduce(this IEnumerable<string> strings, 
    string acc, Func<StringBuilder, string, string, string, StringBuilder> func)
{
    if (null == strings) return "";

    var accumulatorBuilder = new StringBuilder(acc);
    string cur = null;
    string prev = null;
    foreach (var next in strings)
    {
        func(accumulatorBuilder, prev, cur, next);
        prev = cur;
        cur = next;
    }
    func(accumulatorBuilder, prev, cur, null);

    return accumulatorBuilder.ToString();
}

F# は確かにずっと良く見えます:

let rec reduce list =
    match list with
    | []          -> ""
    | head::curr::[]  -> head + " and " + curr
    | head::curr::tail  -> head + ", " + curr :: tail |> reduce
    | head::[] -> head

let concat list = "{" + (list |> reduce )  + "}"

score 2 · Accepted Answer

レイトエントリー:

public static string CommaQuibbling(IEnumerable<string> items)
{
    string[] parts = items.ToArray();
    StringBuilder result = new StringBuilder('{');
    for (int i = 0; i < parts.Length; i++)
    {
        if (i > 0)
            result.Append(i == parts.Length - 1 ? " and " : ", ");
        result.Append(parts[i]);
    }
    return result.Append('}').ToString();
}

score 1 · Accepted Answer

Linqはかなり読みやすいコードを提供していると思います。このバージョンは、0.89秒で100万の「ABC」を処理します。

using System.Collections.Generic;
using System.Linq;

namespace CommaQuibbling
{
    internal class Translator
    {
        public string Translate(IEnumerable<string> items)
        {
            return "{" + Join(items) + "}";
        }

        private static string Join(IEnumerable<string> items)
        {
            var leadingItems = LeadingItemsFrom(items);
            var lastItem = LastItemFrom(items);

            return JoinLeading(leadingItems) + lastItem;
        }

        private static IEnumerable<string> LeadingItemsFrom(IEnumerable<string> items)
        {
            return items.Reverse().Skip(1).Reverse();
        }

        private static string LastItemFrom(IEnumerable<string> items)
        {
            return items.LastOrDefault();
        }

        private static string JoinLeading(IEnumerable<string> items)
        {
            if (items.Any() == false) return "";

            return string.Join(", ", items.ToArray()) + " and ";
        }
    }
}

score 1 · Accepted Answer

public static string CommaQuibbling(IEnumerable<string> items)
{
   var itemArray = items.ToArray();

   var commaSeparated = String.Join(", ", itemArray, 0, Math.Max(itemArray.Length - 1, 0));
   if (commaSeparated.Length > 0) commaSeparated += " and ";

   return "{" + commaSeparated + itemArray.LastOrDefault() + "}";
}

score 1 · Accepted Answer

return String.Concat(
    "{",
    input.Length > 2 ?
        String.Concat(
            String.Join(", ", input.Take(input.Length - 1)),
            " and ",
            input.Last()) :
    String.Join(" and ", input),
    "}");

score 1 · Accepted Answer

foreach を使ってみました。ご意見をお聞かせください。

private static string CommaQuibble(IEnumerable<string> input)
{
    var val = string.Concat(input.Process(
        p => p,
        p => string.Format(" and {0}", p),
        p => string.Format(", {0}", p)));
    return string.Format("{{{0}}}", val);
}

public static IEnumerable<T> Process<T>(this IEnumerable<T> input, 
    Func<T, T> firstItemFunc, 
    Func<T, T> lastItemFunc, 
    Func<T, T> otherItemFunc)
{
    //break on empty sequence
    if (!input.Any()) yield break;

    //return first elem
    var first = input.First();
    yield return firstItemFunc(first);

    //break if there was only one elem
    var rest = input.Skip(1);
    if (!rest.Any()) yield break;

    //start looping the rest of the elements
    T prevItem = first;
    bool isFirstIteration = true;
    foreach (var item in rest)
    {
        if (isFirstIteration) isFirstIteration = false;
        else
        {
            yield return otherItemFunc(prevItem);
        }
        prevItem = item;
    }

    //last element
    yield return lastItemFunc(prevItem);
}

score 1 · Accepted Answer

これは私のものですが、Marcのものとほとんど同じで、順序が若干異なり、単体テストも追加しました。

using System;
using NUnit.Framework;
using NUnit.Framework.Extensions;
using System.Collections.Generic;
using System.Text;
using NUnit.Framework.SyntaxHelpers;

namespace StringChallengeProject
{
    [TestFixture]
    public class StringChallenge
    {
        [RowTest]
        [Row(new String[] { }, "{}")]
        [Row(new[] { "ABC" }, "{ABC}")]
        [Row(new[] { "ABC", "DEF" }, "{ABC and DEF}")]
        [Row(new[] { "ABC", "DEF", "G", "H" }, "{ABC, DEF, G and H}")]
        public void Test(String[] input, String expectedOutput)
        {
            Assert.That(FormatString(input), Is.EqualTo(expectedOutput));
        }

        //codesnippet:93458590-3182-11de-8c30-0800200c9a66
        public static String FormatString(IEnumerable<String> input)
        {
            if (input == null)
                return "{}";

            using (var iterator = input.GetEnumerator())
            {
                // Guard-clause for empty source
                if (!iterator.MoveNext())
                    return "{}";

                // Take care of first value
                var output = new StringBuilder();
                output.Append('{').Append(iterator.Current);

                // Grab next
                if (iterator.MoveNext())
                {
                    // Grab the next value, but don't process it
                    // we don't know whether to use comma or "and"
                    // until we've grabbed the next after it as well
                    String nextValue = iterator.Current;
                    while (iterator.MoveNext())
                    {
                        output.Append(", ");
                        output.Append(nextValue);

                        nextValue = iterator.Current;
                    }

                    output.Append(" and ");
                    output.Append(nextValue);
                }


                output.Append('}');
                return output.ToString();
            }
        }
    }
}

score 1 · Accepted Answer

public static string CommaQuibbling(IEnumerable<string> items)
{
  int count = items.Count();
  string answer = string.Empty;
  return "{" + 
      (count==0)  ?  ""  :  
         (  items[0] + 
             (count == 1 ? "" :  
                 items.Range(1,count-1).
                     Aggregate(answer, (s,a)=> s += ", " + a) +
                 items.Range(count-1,1).
                     Aggregate(answer, (s,a)=> s += " AND " + a) ))+ "}";
}

次のように実装されます。

if count == 0 , then return empty,
if count == 1 , then return only element,
if count > 1 , then take two ranges, 
   first 2nd element to 2nd last element
   last element

score 1 · Accepted Answer

私はジョンの答えがとても気に入りましたが、それは私が問題にアプローチした方法とよく似ているからです. 2 つの変数を具体的にコーディングするのではなく、FIFO キュー内に実装しました。

まったく同じことをする 15 の投稿があると思っていたので奇妙ですが、そのようにしたのは私たちだけのようです。ああ、これらの回答を見ると、Marc Gravell の回答は私たちが使用したアプローチに非常に近いですが、彼は値を保持するのではなく、2 つの「ループ」を使用しています。

しかし、LINQ と regex と配列の結合に関するこれらすべての回答は、クレイジーな話のように思えます。:-)

score 1 · Accepted Answer

これが私の提出物です。署名を少し変更して、より一般的なものにしました。.NET 4 機能を使用する ( String.Join()using IEnumerable<T>)、それ以外の場合は .NET 3.5 で動作します。目標は、大幅に簡素化されたロジックで LINQ を使用することでした。

static string CommaQuibbling<T>(IEnumerable<T> items)
{
    int count = items.Count();
    var quibbled = items.Select((Item, index) => new { Item, Group = (count - index - 2) > 0})
                        .GroupBy(item => item.Group, item => item.Item)
                        .Select(g => g.Key
                            ? String.Join(", ", g)
                            : String.Join(" and ", g));
    return "{" + String.Join(", ", quibbled) + "}";
}

score 1 · Accepted Answer

http://blogs.perl.org/users/brian_d_foy/2013/10/comma-quibbling-in-perl.htmlでの返信に基づいて、Perl で記述されたソリューションとテストコードをいくつか示します。

#!/usr/bin/perl

use 5.14.0;
use warnings;
use strict;
use Test::More qw{no_plan};

sub comma_quibbling1 {
   my (@words) = @_;
   return "" unless @words;
   return $words[0] if @words == 1;
   return join(", ", @words[0 .. $#words - 1]) . " and $words[-1]";
}

sub comma_quibbling2 {
   return "" unless @_;
   my $last = pop @_;
   return $last unless @_;
   return join(", ", @_) . " and $last";
}

is comma_quibbling1(qw{}),                   "",                         "1-0";
is comma_quibbling1(qw{one}),                "one",                      "1-1";
is comma_quibbling1(qw{one two}),            "one and two",              "1-2";
is comma_quibbling1(qw{one two three}),      "one, two and three",       "1-3";
is comma_quibbling1(qw{one two three four}), "one, two, three and four", "1-4";

is comma_quibbling2(qw{}),                   "",                         "2-0";
is comma_quibbling2(qw{one}),                "one",                      "2-1";
is comma_quibbling2(qw{one two}),            "one and two",              "2-2";
is comma_quibbling2(qw{one two three}),      "one, two and three",       "2-3";
is comma_quibbling2(qw{one two three four}), "one, two, three and four", "2-4";

score 1 · Accepted Answer

古き良き配列を使用することが制限だとは思いません。配列と拡張メソッドを使用した私のバージョンは次のとおりです。

public static string CommaQuibbling(IEnumerable<string> list)
{
    string[] array = list.ToArray();

    if (array.Length == 0) return string.Empty.PutCurlyBraces();
    if (array.Length == 1) return array[0].PutCurlyBraces();

    string allExceptLast = string.Join(", ", array, 0, array.Length - 1);
    string theLast = array[array.Length - 1];

    return string.Format("{0} and {1}", allExceptLast, theLast)
                 .PutCurlyBraces();
}

public static string PutCurlyBraces(this string str)
{
    return "{" + str + "}";
}

string.Joinメソッドと、インデックスを介して最後の要素にアクセスできる可能性があるため、配列を使用しています。拡張方法はDRYだからこそここに。

list.ToArray()パフォーマンスの低下はand呼び出しによるものだと思いますが、string.Join全体として、コードの一部を読んで維持するのが楽しいものであることを願っています。

score 1 · Accepted Answer

C# 以外の回答がいくつかあり、元の投稿では任意の言語での回答を求めていたので、C# プログラマーの誰も触れていないように見える別の方法を示すことにしました: DSL です!

(defun quibble-comma (words)
  (format nil "~{~#[~;~a~;~a and ~a~:;~@{~a~#[~; and ~:;, ~]~}~]~}" words))

抜け目のない人は、Common Lisp には実際にはIEnumerable<T>ビルトインがないことに気付くでしょう。したがって、FORMATここでは適切なリストに対してのみ機能します。しかし、もしあなたがを作ったならIEnumerable、あなたは確かFORMATにそれに取り組むために拡張することができます. （Clojureにはこれがありますか？）

また、これを読んで趣味の良い人(Lisp プログラマーを含む!) は、おそらくそこにあるリテラルに気分を害するでしょう"~{~#[~;~a~;~a and ~a~:;~@{~a~#[~; and ~:;, ~]~}~]~}"。それが優れたFORMATDSL を実装しているとは言いませんが、文字列をまとめる強力な DSLがあると非常に便利だと思います。Regex は、文字列を引き裂くための強力な DSL であり、文字列を結合するための (一種の) DSL ですが、愚かなほど弱いものです。string.Format

こういうことは、みんなよく書いていると思います。いったいなぜ、これに対応するユニバーサルで洗練された DSL が組み込まれていないのでしょうか? おそらく、「Perl」が最も近いと思います。

score 1 · Accepted Answer

楽しみのために、C# 4.0 の新しい Zip 拡張メソッドを使用します。

private static string CommaQuibbling(IEnumerable<string> list)
{
    IEnumerable<string> separators = GetSeparators(list.Count());
    var finalList = list.Zip(separators, (w, s) => w + s);
    return string.Concat("{", string.Join(string.Empty, finalList), "}");
}

private static IEnumerable<string> GetSeparators(int itemCount)
{
    while (itemCount-- > 2)
        yield return ", ";

    if (itemCount == 1)
        yield return " and ";

    yield return string.Empty;
}

score 1 · Accepted Answer

複雑な集計コードをスキップして、ビルド後に文字列をクリーンアップするのはどうですか?

public static string CommaQuibbling(IEnumerable<string> items)    
{
    var aggregate = items.Aggregate<string, StringBuilder>(
        new StringBuilder(), 
        (b,s) => b.AppendFormat(", {0}", s));
    var trimmed = Regex.Replace(aggregate.ToString(), "^, ", string.Empty);
    return string.Format(
               "{{{0}}}", 
               Regex.Replace(trimmed, 
                   ", (?<last>[^,]*)$", @" and ${last}"));
}

更新: コメントで指摘されているように、これはコンマを含む文字列では機能しません。他のバリエーションをいくつか試しましたが、文字列に何を含めることができるかについての明確なルールがなければ、可能な最後の項目を正規表現と一致させるのに実際の問題が発生するため、これは制限についての良い教訓になります.

c# - エリック・リッパートの挑戦「コンマを震わせる」、ベストアンサー？

27 に答える 27

Related

Reference