Codingame『1D Spreadsheet』

問題

www.codingame.com

簡単に言うと

　1次元の命令付きセルを与えてあげるから、全部のセルの値を求めるプログラム組んでね。
ということ。
イメージとしては

[ ] [ ] [ ] [ ] [ ] [ ] ……

こういう箱(セル)がいっぱいあって

[命令0] [命令1] [命令2] [命令3] [命令4] ……

それぞれのセルに、セルの中身を決定するための命令が入ってる。

命令

　命令て何やねん、俺に命令すんなや！
って怒る人もいるだろうけど命令は4つ。
１、ただ値を格納するためにある！VALUE！
２、足し算は基本のキ！ADD！
３、足し算があるなら引き算もある！SUB！
４、割り算など不要、掛け算で十分！MULT！

引数

　命令には基本的に2つ引数がついてくる。
むしろついてこないと何を足したり引いたりしたらいいのかよくわからない。

　例えばこんな命令があったとする。

ADD 5 6

すると、この命令のあったセルに5+6つまり11を格納すればいい、ということになる。

[ADD 1 1] [MULT 3 2] [SUB 5 10] [VALUE 12 _]

こんな感じの命令ならこうなる。

[2] [6] [-5] [12]

参照とかあるんスよ

　全部値が入っていればいいんだけど、参照もある。めんどい。

[5] [7] [ADD $0 $1]

っていう状態だったとする。
ADDのあるセル、は0番目のセル5と1番目のセル7を足した12が入ることになる。

[5] [7] [12]

　んでもって、参照先からさらに参照しないといけないなんていう状態も容易に予想がつく。

[VALUE $2 _] [ADD $5 $3] [SUB $6 $1] ……

こんな感じ。
0番目のVALUEを実行するには2番目のSUBの結果を参照しないといけなくて、
2番目を実行するには6番目と1番目の結果を参照しないと……

要はこいつは電卓

　電卓作った人なら分かるだろうけど、基本的にスタックに積んでいく感じでいける。

コード

using System;
using System.Collections.Generic;

namespace _1D_Spreadsheet
{
    public class Program
    {
        //総コマンド数
        static int N;
        //1次元セル
        static int[] Cells;
        //コマンド
        static CCommand[] Commands;
        //コマンド実行用スタック
        static Stack<CCommand> CommandStack;

        public static void Main(string[] args)
        {
            N = int.Parse(Console.ReadLine());
            Cells = new int[N];
            Commands = new CCommand[N];
            CommandStack = new Stack<CCommand>();

            for (int i = 0; i < N; i++)
            {
                string[] s = Console.ReadLine().Split(' ');

                //セルの初期値(未決定値)としてint.MinValueを代入する
                Cells[i] = int.MinValue;

                Commands[i] = new CCommand(i, s[0], new CArgument(s[1]), new CArgument(s[2]));
            }

            for (int i = 0; i < N; i++)
            {
                //セルが未定ならスタックに乗せる
                if(Cells[i] == int.MinValue) CommandStack.Push(Commands[i]);

                while(CommandStack.Count != 0)
                {
                    TraceArgument();                
                }
            }

            string ans = string.Join(Environment.NewLine, Cells);

            Console.WriteLine(ans);
        }

        //参照を辿って処理する
        static void TraceArgument()
        {
            //arg1の参照を辿る
            while (CommandStack.Peek().Arg1.IsReference == true)
            {
                if (Cells[CommandStack.Peek().Arg1.Value] != int.MinValue) break;

                CommandStack.Push(Commands[CommandStack.Peek().Arg1.Value]);
            }

            //arg2の参照を辿る
            if (CommandStack.Peek().Arg2.IsReference == true)
            {
                if (Cells[CommandStack.Peek().Arg2.Value] != int.MinValue)
                {
                    Execute(CommandStack.Pop());    //arg1,arg2共に確定値の場合
                }
                else CommandStack.Push(Commands[CommandStack.Peek().Arg2.Value]);
            }
            else
            {
                Execute(CommandStack.Pop());    //arg1,arg2共に参照型でない場合
            }
        }

        /// <summary>
        /// コマンドの実行
        /// </summary>
        /// <param name="com">コマンド</param>
        static void Execute(CCommand com)
        {
            switch (com.Operation)
            {
                case "VALUE":
                    Cells[com.CellNumber] = OperationValue(com.Arg1);
                    break;
                case "ADD":
                    Cells[com.CellNumber] = OperationAdd(com.Arg1, com.Arg2);
                    break;
                case "SUB":
                    Cells[com.CellNumber] = OperationSub(com.Arg1, com.Arg2);
                    break;
                case "MULT":
                    Cells[com.CellNumber] = OperationMult(com.Arg1, com.Arg2);
                    break;
            }
        }

        /// <summary>
        /// 値の代入
        /// </summary>
        /// <param name="arg1">引数</param>
        /// <returns>参照先が未決定の場合int.MinValue</returns>
        static int OperationValue(CArgument arg1)
        {
            int v = GetValue(arg1);

            if (v == int.MinValue) return v;
            else return v;
        }

        /// <summary>
        /// 足し算
        /// </summary>
        /// <param name="arg1">引数1</param>
        /// <param name="arg2">引数2</param>
        /// <returns>値が未決定の場合int.MinValue</returns>
        static int OperationAdd(CArgument arg1, CArgument arg2)
        {
            int v1, v2;

            v1 = GetValue(arg1);
            if (v1 == int.MinValue) return v1;

            v2 = GetValue(arg2);
            if (v2 == int.MinValue) return v2;

            return v1 + v2;
        }

        /// <summary>
        /// 引き算
        /// </summary>
        /// <param name="arg1">引数1</param>
        /// <param name="arg2">引数2</param>
        /// <returns>値が未決定の場合int.MinValue</returns>
        static int OperationSub(CArgument arg1, CArgument arg2)
        {
            int v1, v2;

            v1 = GetValue(arg1);
            if (v1 == int.MinValue) return v1;

            v2 = GetValue(arg2);
            if (v2 == int.MinValue) return v2;

            return v1 - v2;
        }

        /// <summary>
        /// 掛け算
        /// </summary>
        /// <param name="arg1">引数1</param>
        /// <param name="arg2">引数2</param>
        /// <returns>値が未決定の場合int.MinValue</returns>
        static int OperationMult(CArgument arg1, CArgument arg2)
        {
            int v1, v2;

            v1 = GetValue(arg1);
            if (v1 == int.MinValue) return v1;

            v2 = GetValue(arg2);
            if (v2 == int.MinValue) return v2;

            return v1 * v2;
        }


        /// <summary>
        /// 引数が参照タイプか値タイプかを判断して返す
        /// </summary>
        /// <param name="arg">引数</param>
        /// <returns>値。参照先が未決定な場合int.MinValue</returns>
        static int GetValue(CArgument arg)
        {
            if (arg.IsReference == true)
            {
                if (Cells[arg.Value] != int.MinValue) return Cells[arg.Value];
                else return int.MinValue;
            }
            else
            {
                return arg.Value;
            }
        }
    }

    /// <summary>
    /// コマンドクラス
    /// </summary>
    public class CCommand
    {
        public int CellNumber;
        public string Operation;
        public CArgument Arg1;
        public CArgument Arg2;

        public CCommand(int cellNumber, string operation, CArgument arg1, CArgument arg2)
        {
            CellNumber = cellNumber;
            Operation = operation;
            Arg1 = arg1;
            Arg2 = arg2;
        }
    }

    /// <summary>
    /// 引数クラス
    /// </summary>
    public class CArgument
    {
        //参照タイプかどうか
        public bool IsReference;
        //参照タイプの場合は参照先アドレス、そうでなければ値
        public int Value;

        public CArgument(bool isReference, int value)
        {
            IsReference = isReference;
            Value = value;
        }

        public CArgument(string Arg)
        {
            if (Arg.Contains("$") == true)   //参照タイプの場合
            {
                IsReference = true;
                Value = int.Parse(Arg.Split('$')[1]);
            }
            else if (Arg == "_") //Value命令の第2引数
            {
                Value = int.MinValue;
            }
            else    //値の場合
            {
                Value = int.Parse(Arg);
            }
        }
    }
}