2015年02月25日

C#で数値リストの圧縮

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その72

整列済みの number のリストがある。

[1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27]
このようなリストで数が3つ以上連続している部分を[1, 2, 3] -> [1, 3] のように両端のみを書くような記法を導入する。 ただし2個とびや3個とびなどn個とびの場合、[1, 3, 5, 7] -> [1, 7, 2]のように[start, stop, step]のような並びにする。 最初の例のリストであれば以下のようになる。
[1 [3, 6] 12, 13, [15, 25, 5], 26, 27]
このようなリストに変換をするコードを書いてください。

すみんせん。この問題が、どう書く?orgに掲載されたものなのかの確認ができていません m(_ _)m
僕のPCのどう書く?org用のフォルダ内にあったコードなので、たぶん、そうなのだろうと思いますので、ここに載せることとします。

C#のような言語だとリスト表現をどうするのか判断に迷いますね。
あくまでも文字列として表示することだけを目的とするのか、
内部表現として、問題が求めているようなリスト構造にするのか?
ここでは両方で書いてみました。
でも、どっちもあまりきれいなコードにはなりませんでした。

まずは、文字列として表現すれば良しとするコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            int[] nums = { 1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27, 28, 29, 30, 33, 36, 37, 90 };
            var str = CompactNumbers9(nums);
            Console.WriteLine(str);
        }

        private static string CompressNumbers(int[] nums) {
            return string.Format("[{0}]", CompressNumbers(nums, 0, int.MinValue, new List<int>()));
        }

        // もっと簡潔に書けそうなきがするが、僕の頭ではこれが精一杯。
        private static object CompressNumbers(int[] nums, int index, int prev, List<int> list) {
            int diff = (list.Count < 2) ? -1 : list[1] - list[0];
            if (index >= nums.Length)
                return Symbolize(list, diff);
            int curr = nums[index];
            string s = "";
            if (diff == curr - prev || list.Count <= 1) {
                list.Add(curr);
            }  else {
                if (list.Count == 2) {
                    list.RemoveAt(list.Count - 1);
                    s = Symbolize(list, diff) + ", ";
                    list = new List<int> { prev, curr };
                } else {
                    s = Symbolize(list, diff) + ", ";
                    list = new List<int> { curr };
                }
            }
            return s + CompressNumbers(nums, index + 1, curr, list);
        }

        private static string Symbolize(List<int> list, int diff) {
            int count = list.Count;
            if (count == 1)
                return string.Format("{0}", list[0]);
            else if (count == 2)
                return string.Format("{0}, {1}", list[0], list[1]);
            else if (diff > 1)
                return string.Format("[{0}, {1}, {2}]", list[0], list[count - 1], diff);
            else
                return string.Format("[{0}, {1}]", list[0], list[count - 1]);
        }
}

次に、内部表現として、圧縮したリストを表現するもの。
こっちは、CompressNumbers というクラスを定義しています。
結果は、List して、objectには、int or int[] が入るものとしましたが、 うーーん、これってどうなんだろう?C#的には、あまり良いデータ設計じゃないですね。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            CompressNumbers cn = new CompressNumbers(new int[] { 1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27 });
            cn.Execute();
            cn.Print();
            Console.ReadLine();
        }
    }

    class CompressNumbers {
        private List<object> result = new List<object>();
        private int[] nums;

        public CompressNumbers(int[] nums) {
            this.nums = nums;
        }

        public List<object> Execute() {
            Execute(0);
            return result;
        }

        private void Execute(int index, int start = -1, int stop = -1, int step = -1) {
            if (index >= nums.Length) {
                Symbolize(start, stop, step);
            } else {
                int curr = nums[index];
                int diff = curr - stop;
                if (step == -1)
                    Execute(index + 1, curr, curr, 0);
                else if (step == 0 || diff == step)
                    Execute(index + 1, start, curr, diff);
                else if (start + step == stop) {
                    Symbolize(start, start, 0);
                    Execute(index + 1, stop, curr, diff);
                } else {
                    Symbolize(start, stop, step);
                    Execute(index + 1, curr, curr, 0);
                }
            }
        }

        private void Symbolize(int start, int stop, int step) {
            if (step == 0)
                result.Add(start);
            else if (start + step == stop) {
                result.Add(start);
                result.Add(stop);
            } else if (step == 1)
                result.Add(new int[] { start, stop });
            else
                result.Add(new int[] { start, stop, step });
        }

        public void Print() {
            Console.Write("[");
            int count = 0;
            foreach (var o in result) {
                if (count++ > 0)
                    Console.Write(", ");
                if (o.GetType().IsArray) {
                    Console.Write("[{0}]", string.Join(", ", o as IEnumerable<int>));
                } else {
                    Console.Write("{0}", o);
                }
            }
            Console.Write("]");
        }
    }
}

  

Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年02月18日

C#でコラッツ・角谷の問題のステップ数(2^20まで)

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その71

■問題 (出題者:ところてん さん)
任意の数nを与えたときに
・nが偶数ならば2で割る (n=n/2)
・nが奇数ならば3倍して1を足す (n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
(すべての数について成り立つかは不明) 参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1〜2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

参考: コラッツの問題の成り立つ範囲
http://q.hatena.ne.jp/1115469752

C#のプログラミング的にもアルゴリズム的にも、普通のコードなので説明の必要はありませんね。
しいて言えば、コラッツ・角谷の予想が成立することが大前提で書かれたコードです。
成り立たないと無限ループに陥ります。まあ、その心配はなさそうですが...
また、オーバーフローは考慮していません。
もうすこし大きな値で確認するには、BigIntegerを使ったほうがよさげですね。


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Stopwatch sw = Stopwatch.StartNew();
            CollatzKakutani.PrintMaxStep((long)Math.Pow(2, 20));
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds + "ミリ秒");
            Console.ReadLine();
        }
    }

    static class CollatzKakutani {
        public static void PrintMaxStep(long limit) {
            long maxn = long.MinValue;
            long maxfn = long.MinValue;           
            for (long i = 1; i <= limit; i++) {
                long r = Calc(i);
                if (r > maxfn) {
                    maxfn = r;
                    maxn = i;
                }
            }
            Console.WriteLine("f({0})={1}", maxn, maxfn);
        }

        public static long Calc(long n) {
            long result = 0;
            while (n != 1) {
                result++;
                if (n % 2 == 0)
                    n = n / 2;
                else
                    n = n * 3 + 1;
            }
            return result;
        }
    }
}

僕のPCでの実行結果 (Releaseモード)
f(837799)=524
401ミリ秒
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年02月15日

C#で正整数のゲーデル数化

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その70

■問題 (出題者:nobsun さん)
正の整数 n を引数としてとり, 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数 goedel を定義してください.

ただし,n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk] をなすとし,dk が 1 の位,d1 が 10^(k-1) の位です.また,pk は k番目の素数です.
goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108


ゲーデル数とは何かについては、僕はほとんど何も分かってません(^^;;。
でも、定義が明確に書いてあるので、僕にもプログラムが書けますね。
コメントにも書いてありますが、素数を列挙するメソッドは効率無視です。
ここでは、整数 n は、int型としましたので、最大でも、intで表せる桁数分(つまり10個)しか素数を求めないから これで問題ないですね。

戻り値は、BigIntegerにしました。なので、.NET Framework4 以降が対象です。
BigIntegerは、論理上は大きさに上限、下限がないので、int.MaxValueを引数に与えても正しいゲーデル数を返します。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Console.WriteLine(Goedel(9));
            Console.WriteLine(Goedel(81));
            Console.WriteLine(Goedel(230));
            Console.WriteLine(Goedel(4321));
            Console.WriteLine(Goedel(54321));
            Console.WriteLine(Goedel(654321));
            Console.WriteLine(Goedel(7654321));
            Console.WriteLine(Goedel(87654321));
            Console.ReadLine();
        }

        static BigInteger Goedel(int num) {
            BigInteger result = 1;
            string s = num.ToString();
            var ite = GetPrimes().GetEnumerator();
            foreach (var c in s) {
                ite.MoveNext();
                result *= BigInteger.Pow(ite.Current, c - '0');
            }
            return result;
        }
        
        // 素数を列挙する。効率は無視。
        static IEnumerable<int> GetPrimes() {
            for (int i = 2; i < int.MaxValue; i++) {
                bool isPrime = true;
                for (int j = 2; j < i; j++)
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                if (isPrime)
                    yield return i;
            }
        }
    }
}

MoveNext, Current呼び出してるのは煩雑なので、LInq to Object の Zip メソッド使って Goedel メソッドを書き直してみました。
そうなると、当然ながら、Aggregate 使ったほうが楽ですね。
メソッドチェーンがいい感じです。LINQ最高!
ただ、Aggregateは、慣れるまでは、直感的ではないのが玉に瑕ですね。

        static BigInteger Goedel(int num) {
            var gedel = num.ToString()
                           .Select(c => c - '0')
                           .Zip(GetPrimes(), (d, p) => BigInteger.Pow(p, d))
                           .Aggregate((r, n) => r * n);
            return gedel;
        }
       

以下、結果です。

512
768
108
75600
174636000
5244319080000
2677277333530800000
25968760179275365452000000

  
Posted by gushwell at 21:30Comments(0)TrackBack(0)

2015年02月11日

C#で仲間はずれの判定

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その69 

■問題 (出題者:にしお さん)
リストxsが渡されたときに

* 全部の要素が同じ値である(例:[1, 1, 1, 1])、
* 一つだけ仲間はずれがある(例:[1, 2, 1, 1, 1])、
* その他

を識別する関数を作ってください。 また判定後に「全部の要素が同じ値」の場合にはその値、 「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。
型にうるさい言語のために:リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。
追記:リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

この問題は、Linq to ObjectのGroupBy使えば良さそうですね。 
NakamaHazure というクラスを作成しています。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Execute(new int[] { 1, 1, 1, 1, 1 });
            Execute(new int[] { 1, 1, 1, 2, 1 });
            Execute(new int[] { 1, 1, 1, 2, 3 });
            Execute(new int[] { 1, 1, 1, 1, 1, 2, 1,1 ,1 });
            Console.ReadLine();
        }

        private static void Execute(IEnumerable<int> nums) {
            var nh = new NakamaHazure(nums);
            GroupType gt = nh.Classify();
            Console.Write(gt+ " ");
            if (gt == GroupType.LeftOut)
                Console.Write(nh.Divide());
            Console.WriteLine();
        }
    }

    public enum GroupType {
        Buddy,
        LeftOut,
        Mixed,
    }

    public class NakamaHazure {
        IGrouping<int, int>[] groups;
        public NakamaHazure (IEnumerable<int> nums) {
            groups = nums.GroupBy(x => x).ToArray();
        }

        public GroupType Classify() {
            if (groups.Length == 1)
                return GroupType.Buddy;
            if (groups.Length == 2 && groups.Count(n => n.Count() == 1) == 1)
                return GroupType.LeftOut;
            return GroupType.Mixed;
        }

        // Classify() == LeftOut のときのみ結果を保証する
        public Tuple<int,int> Divide() {
            var q = groups.OrderBy(x => x.Count());
            return Tuple.Create(
                q.First().Key,
                q.Skip(1).First().Key
            );
        }
    }
 }
  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

2015年02月08日

C#で与えられた文字列でピラミッド

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その68

「ピラミッドを作る」の続編です。 与えられた文字列を使って下の例のようなピラミッドを書いてください。 頂点は与えられた文字列の最後の一文字、 底辺は与えられた文字列の各文字の間に空白が入ったものになります。
>>> pyramid("hoge")
   e  
  g e 
 o g e
h o g e



>>> pyramid("abracadabra")
          a         
         r a        
        b r a       
       a b r a      
      d a b r a     
     a d a b r a    
    c a d a b r a   
   a c a d a b r a  
  r a c a d a b r a 
 b r a c a d a b r a
a b r a c a d a b r a


※ ごめんなさい、出題者がわかりません。

いろいろな書き方が考えられますね。 最初に書いたバージョンはこれ。
static void Pyramid1(string s) {
    int length = s.Length;
    for (int n = 0; n < length; n++) {
        // 左側の空白を表示
        int spCount = length - n - 1;
        Console.Write(new string(' ', spCount));
        // 右側の文字部分を表示
        var ls = s.Skip(spCount);
        foreach (var c in ls)
            Console.Write(c + " ");
        Console.WriteLine();
    }
}
メソッドの中で出力も行っているのが気に入らなかったので、 文字列の組み立てだけを行うメソッドにして見ました。 ついでに、上記メソッドの最後の foreach文の箇所をLINQ to Ojectを使って 書き直してみました。
static IEnumerable<string> Pyramid2(string s) {
    int length = s.Length;
    for (int n = 0; n < length; n++) {
        // 左側の空白の数
        int spCount = length - n - 1;
        // 右側の文字部分を表示
        yield return s.Skip(spCount)
                      .Aggregate(new string(' ', spCount), (x, c) => x + c + " ");
    }
}
出力までやるには、以下のようなコードを書きます。
        static void Main(string[] args) {
            Pyramid2("abracadabra").ToList().ForEach(Console.WriteLine);
            Console.ReadLine();
        }
ここまで書いたのだから、全部 LINQ使っちゃえ、って書いたのが次に示すコード。 ここまでやると、黒魔術的なにおいがしてきます。
static IEnumerable<string> Pyramid3(string s) {
    return Enumerable.Range(0, s.Length).Reverse()
            .Select(
                n => s.Skip(n).Aggregate(new string(' ', n), (x, c) => x + c + " ")               
            );
}
再帰処理だと、どんな感じになるのかなと想い、書いてみたのが次のコード。 これが一番すっきりしている感じがします。
static string Pyramid(string s) {
    return PyramidRec(s.Length - 1, s);
}

// indexは、abracadabra の場合は、10,9,8,7,... と変化していく。
// 左側に詰める空白の数
static string PyramidRec(int index, string s) {
    if (index < 0)
        return "";
    string line = new string(' ', index) +
                  s.Skip(index).Aggregate("", (x, c) => x + c + " ");
    return line + Environment.NewLine + PyramidRec(index - 1, s);
}
再帰処理でのyield return って煩雑なので、戻り値を string にして、 改行込みの結果を返すようにしています。 もちろん、コンソールに出力するには、以下のように書けばOK.
Console.WriteLine(Pyramid("abracadabra"));
  
Posted by gushwell at 21:30Comments(0)TrackBack(0)

2015年02月01日

C#で長方形の交差判定

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その67

■問題 (出題者:にしお さん)
ここに二つの長方形があります。左上隅のx座標、y座標、右下隅のx座標、y座標を それぞれleft, top, right, bottomとします。
また、おのおのの長方形についてleft < right, top < bottom が成り立つものとします。
この二つの長方形が重なっているかどうかを判定するコードを書いてください。
なお辺で接する場合(例えば(0, 0, 100, 100)と(100, 0, 200, 100))は 重なっていないものとします。
なお変数名に関して、例えば1番目の長方形の左上隅x座標がleft[0]なのかleft1なのか、 それともrect1.leftなのかは自由に選んで構いません。


IsOverlap というメソッド書いたのですが、WindowsFormsの場合は、 Rectangleクラスに、IntersectsWith というメソッドがあって、それを使うだけでした。
こんな短いメソッドですが、自作するときは、よくよく考えないとバグりますね。

using System;
using System.Drawing;
using System.Windows.Forms;


namespace Doukaku.Org {
    static class Program {
        static void Main() {
            Console.WriteLine(IsOverlap(
                new Rectangle(0, 0, 100, 100),
                new Rectangle(100, 0, 200, 100)).ToString());

            Console.WriteLine(
                new Rectangle(0,0,100,100).IntersectsWith(
                new Rectangle(100,0,200,100)).ToString());
        }

        private bool IsOverlap(Rectangle r1, Rectangle r2) {
            if ((r1.Left < r2.Right) && (r2.Left < r1.Right) &&
                (r1.Top < r2.Bottom) && (r2.Top < r1.Bottom))
                return true;
            return false;
        }              
    }
}

  
Posted by gushwell at 22:30Comments(0)TrackBack(0)