Q38 7セグメントコードの反転

C#のソース

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

class Program
{
    struct JyoutaiDef
    {
        internal List<int> NumList;
        internal int Cost;
    }

    static void Main()
    {
        int[,] ChangeCntArr = new int[9 + 1, 9 + 1];
        for (int I = 0; I <= 9; I++) {
            for (int J = 0; J <= 9; J++) {
                ChangeCntArr[I, J] = DeriveChangeCnt(I, J);
            }
        }

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.NumList = new List<int>();
        WillPush.Cost = 0;
        stk.Push(WillPush);

        int AnswerCost = int.MaxValue;
        var AnswerNumArrList = new List<int[]>();

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //下限値枝切り
            if (AnswerCost < Popped.Cost) continue;

            //クリア判定
            if (Popped.NumList.Count == 10) {
                if (AnswerCost > Popped.Cost) {
                    AnswerCost = Popped.Cost;
                    AnswerNumArrList.Clear();
                }
                AnswerNumArrList.Add(Popped.NumList.ToArray());

                var sb = new System.Text.StringBuilder();
                sb.AppendFormat("コストが{0}の解候補を発見。", AnswerCost);
                for (int I = 0; I <= Popped.NumList.Count - 1; I++) {
                    sb.Append(Popped.NumList[I]);
                    if (I < Popped.NumList.Count - 1) sb.Append('→');
                }
                Console.WriteLine(sb.ToString());
                continue;
            }

            for (int I = 0; I <= 9; I++) {
                if (Popped.NumList.Contains(I)) continue;

                //対称解の除外で、0は中央までに存在
                if (I == 0 && Popped.NumList.Count > 5) continue;

                WillPush.NumList = new List<int>(Popped.NumList) { I };

                WillPush.Cost = Popped.Cost;
                if (Popped.NumList.Count > 0) {
                    WillPush.Cost += +DeriveChangeCnt(Popped.NumList.Last(), I);
                }

                stk.Push(WillPush);
            }
        }
    }

    //切り替え回数を求める
    static int DeriveChangeCnt(int pFromInt, int pToInt)
    {
        Func<int, int> DeriveBitFunc = (pInt) =>
        {
            if (pInt == 0) return Convert.ToInt32("1111110", 2);
            if (pInt == 1) return Convert.ToInt32("0110000", 2);
            if (pInt == 2) return Convert.ToInt32("1101101", 2);
            if (pInt == 3) return Convert.ToInt32("1111001", 2);
            if (pInt == 4) return Convert.ToInt32("0110011", 2);
            if (pInt == 5) return Convert.ToInt32("1011011", 2);
            if (pInt == 6) return Convert.ToInt32("1011111", 2);
            if (pInt == 7) return Convert.ToInt32("1110000", 2);
            if (pInt == 8) return Convert.ToInt32("1111111", 2);
            if (pInt == 9) return Convert.ToInt32("1111011", 2);
            return 0;
        };

        int FromBit = DeriveBitFunc(pFromInt);
        int ToBit = DeriveBitFunc(pToInt);
        int wkXOR = FromBit ^ ToBit;

        int ChangeCnt = 0;
        do {
            int ModVal = wkXOR % 2;
            if (ModVal == 1) ChangeCnt++;
            wkXOR /= 2;
        } while (wkXOR > 0);
        return ChangeCnt;
    }
}

実行結果

省略
コストが14の解候補を発見。4→1→7→3→2→0→8→9→5→6
コストが14の解候補を発見。4→1→7→3→2→0→8→6→5→9
コストが13の解候補を発見。4→1→7→0→8→6→5→9→3→2
コストが13の解候補を発見。2→8→0→6→5→9→3→7→1→4
コストが13の解候補を発見。2→0→8→6→5→9→3→7→1→4
コストが13の解候補を発見。0→8→6→5→9→4→1→7→3→2

解説

深さ優先探索で解いてます。