N coins in a line

Qn: There are n coins in a line. You can pick one coin from either end. You are playing it against an opponent. Both of you play optimally. What is the maximal value you can collect if you play first?

This is a very common question.
Here are links to geeksforgeeks website and leetcode discussing this problem

As explained in above posts, you can create the recurrence relation as:

F(i,j) = Max(A, B)

Where A = F(i) + Min( F[i+2,j], F[i+1,j-1])

B = F(j) + Min( F[i+1,j-1], F[i,j-2])

You assume you picked ith coin and your opponent picked either (i+1)th or jth coin optimally and you have to maximize it.
It’s straightforward to implement it using recursion while ensuring that you do not do duplicate calculations.
Here’s simple implementation using recursion:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.IO;
    using System.Diagnostics;

    class Solution
    {
        private const ulong INIT_VALUE = ulong.MaxValue;
        private static ulong[,] f;

        public static ulong GetMaxValue(List coins, int i, int j)
        {
            Debug.Assert(j >= i);

            if (f[i, j] != INIT_VALUE)
            {
                return f[i, j];
            }

            if (i == j)
            {
                return coins[i];
            }

            if (j - i == 1)
            {
                return Math.Max(coins[i], coins[j]);
            }
            ulong i1j1 = 0, i2j = 0, ij2 = 0;

            if (i + 1 < coins.Count && j > 0)
            {
                f[i + 1, j - 1] = GetMaxValue(coins, i + 1, j - 1);
                i1j1 = f[i + 1, j - 1];
            }

            if (i + 2 < coins.Count)
            {
                f[i + 2, j] = GetMaxValue(coins, i + 2, j);
                i2j = f[i + 2, j];
            }

            if (j - 2 < coins.Count)
            {
                f[i, j - 2] = GetMaxValue(coins, i, j - 2);
                ij2 = f[i, j - 2];
            }

            f[i, j] = Math.Max(coins[i] + Math.Min(i1j1, i2j),
                            coins[j] + Math.Min(i1j1, ij2));
            return f[i, j];
        }

        private static void InitF(int size, ulong val = INIT_VALUE)
        {
            f = new ulong[size, size];
            for (var i = 0; i < size; ++i)
            {
                f[i, i] = val;
                for (var j = i + 1; j < size; ++j)
                {
                    f[i, j] = val;
                    f[j, i] = val;
                }
            }
        }

        static void Main(string[] args)
        {
            var coins = new List() { 8, 15, 3, 7 };
            InitF(coins.Count);
            var max = GetMaxValue(coins, 0, coins.Count - 1);
            Console.WriteLine(max);
        }
    }

The recursive solution has its drawbacks when no. of recursive function calls become too many. That can lead to StackOverflow exception due to saving of too many function pointers without doing any calculation. If you have to make more than 2 recursive calls, usually you would face the stack overflow exception.

The above problem has a simpler version where N coins in a line but you can pick 1, 2 or 3 coins only from a single end.. like a stack. Problem statement is here

Solution of it both recursive and non-recursive is as below:

   
    class StackedCoins123
    {
//        F(i) = 
//        V(i) + Min(F(i+2), F(i+3), F(i+4))
//V(i) + V(i+1) + Min(F(i+3), F(i+4), F(i+5))
//V(i) + V(i+1) + V(i+2) + Min(F(i+4), F(i+5), F(i+6))

        private const ulong INIT_VALUE = ulong.MaxValue;
        public static ulong[] scores;

        public static ulong GetMaxScore(List coins, int start)
        {
            if (start >= coins.Count)
            {
                return 0;
            }

            if (coins.Count <= 3)
            {
                ulong sum = 0;
                foreach (var c in coins) sum += c;
                return sum;
            }

            if (scores[start] != INIT_VALUE)
            {
                return scores[start];
            }

            var scorei2 = GetMaxScore(coins, start + 2);
            var scorei3 = GetMaxScore(coins, start + 3);
            var scorei4 = GetMaxScore(coins, start + 4);
            var scorei5 = GetMaxScore(coins, start + 5);
            var scorei6 = GetMaxScore(coins, start + 6);

            var sum1 = coins[start];
            var sum2 = sum1 + (((start+1) < coins.Count) ? coins[start+1] : 0); 
            var sum3 = sum2 + (((start+2) < coins.Count) ? coins[start+2] : 0);

            var score1 = sum1 + Math.Min(scorei2, Math.Min(scorei3, scorei4));
            var score2 = sum2 + Math.Min(scorei5, Math.Min(scorei3, scorei4));
            var score3 = sum3 + Math.Min(scorei6, Math.Min(scorei5, scorei4));

            scores[start] = Math.Max(Math.Max(score1, score2), score3);
            return scores[start];
        }

        public static ulong GetMaxScoreNonRecursive(List coins)
        {
            int start = coins.Count - 1;
            scores[start] = coins[start];
            scores[start-1] = coins[start] + coins[start-1];
            scores[start-2] = coins[start] + coins[start-1] + coins[start-2];

            for (int i = start-3; i >= 0; --i)
            {
                var score1 = coins[i] + Math.Min(scores[i + 2], Math.Min(scores[i + 3], scores[i + 4]));
                var score2 = coins[i] + coins[i+1] + Math.Min(scores[i + 3], Math.Min(scores[i + 4], scores[i + 5]));
                var score3 = coins[i] + coins[i+1] + coins[i+2] + Math.Min(scores[i + 4], Math.Min(scores[i + 5], scores[i + 6]));
                scores[i] = Math.Max(score1, Math.Max(score2, score3));
            }
            return scores[0];
        }

        public static void InitScores(int len)
        {
            scores = new ulong[len+6];
            for(var i=0; i<len; ++i)
            {
                scores[i] = INIT_VALUE;
            }
            for (int i = len; i  0)
            {
                string str = file.ReadLine();
                str = file.ReadLine();
                var coins = str.Split(' ').Select(s => ulong.Parse(s)).ToList();
                InitScores(coins.Count);
                var max = GetMaxScoreNonRecursive(coins);
                Console.WriteLine(max);
            }
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s