corn

import java.util.*;
/*
 * Danny Davis & Andrew Akiyama
 * Project 3b
 * ACM-ICPC live archive: 7127 Number Game
 *
 * Project Description: Alice and Bob are playing a game on a line of N
 *squares. The line is initially populated with one of
 *each of the numbers from 1 to N. Alice and Bob take
 *turns removing a single number from the line, subject
 *to the restriction that a number may only be removed
 *if it is not bordered by a higher number on either side. When the number is removed, the square that
 *contained it is now empty. The winner is the player who removes the 1 from the line. Given an initial
 *configuration, who will win, assuming Alice goes first and both of them play optimally?
 */
public class Project_3b
{
     public static void main(String[] args)
        {
            boolean isAlice = false;
            int a = Integer.MIN_VALUE;
            int b = Integer.MAX_VALUE;
            //int [] initState = { 2, 1, 3, 4 };             // Bob - Good
            //int [] initState = { 1, 3, 2, 4 };            // Alice - Good
            int [] initState = { 1, 3, 2 };                // Bob - Good
            //int [] initState = { 2, 5, 1, 6, 4, 3 };        // Alice - Good

            int value = value(initState, isAlice, a, b);//returns the winner assuming optimality

           ////////////////////////////////////////////////////////////////////////////////////
           ////Prints the winner //////////////////////////////////////////////////////////////
           ////////////////////////////////////////////////////////////////////////////////////
            if (value > 0)
                System.out.println("Alice");
            else if (value < 0)
                System.out.println("Bob");

        }

     //////////////////////////////////////////////////////////////////////////
     ////// Value function                             ////////////////////////
     //////////////////////////////////////////////////////////////////////////
     @SuppressWarnings("unused")
    public static int value ( int [] initState, boolean isAlice, int a, int b )
     {
         //returns an int greater than 0 if Alice wins or an int less than 0 if Bob wins
         ArrayList<int[]> succesors = getSuccesors( initState, a, b );
         for ( int i = 0; i < succesors.size(); i++)
         {
             //if the state is a terminal state
             if ( isGoalState(succesors.get(i)) )//return the state's utility
                 return a;
             //else if the next agent is MAX:
             else if ( isAlice )
             {
                 return maxValue( succesors.get(i), a, b );// return maxValue(state, a, b)
             }
             //else if the next agent is MIN:
             else
             {
                 return minValue( succesors.get(i), a, b );// return minValue(state, a, b)
             }
         }
        return 1;
     }

     /////////////////////////////////////////////////////////////////////////
     ///////// Max Value function                       //////////////////////
     /////////////////////////////////////////////////////////////////////////
     public static int maxValue ( int [] state, int a, int b )
     {
         boolean isAlice = false;
         int v = Integer.MIN_VALUE;// initialize v = negative infinity
         //for each successor of state:
         ArrayList<int[]> succesors = getSuccesors( state, a, b );
         for ( int i = 0; i < succesors.size(); i++ )
         {
             v = Math.max(v, value(succesors.get(i), isAlice, a, b));
             if (v >= b)
                 return v;
             a = Math.max(a, v);
         }
         return v;
     }

     /////////////////////////////////////////////////////////////////////////
     ///////// Min Value function                        //////////////////////
     /////////////////////////////////////////////////////////////////////////
     public static int minValue ( int [] state, int a, int b )
     {
         boolean isAlice = true;
         int v = Integer.MAX_VALUE;// initialize v = positive infinity
         //for each successor of state:
         ArrayList<int[]> succesors = getSuccesors( state, a, b );
         for ( int i = 0; i < succesors.size(); i++ )
         {
             v = Math.min(v, value(succesors.get(i), isAlice, a, b));
             if (v <= a)
                 return v;
             b = Math.min(b, v);
         }
         return v;
     }

     /////////////////////////////////////////////////////////////////////////
     ///////// isGoalState function                      /////////////////////
     /////////////////////////////////////////////////////////////////////////
     public static boolean isGoalState ( int [] state )
     {
         //Scan's through state array, if it has a # 1 left in it, false is returned for goal state
         // otherwise true is returned for goal state
         for ( int i = 0; i < state.length; i++ )
         {
             if ( state[i] == 1 )
                 return false;
         }
         return true;
     }

     /////////////////////////////////////////////////////////////////////////
     ////////// get Successor function                       ///////////////////
     /////////////////////////////////////////////////////////////////////////
     public static ArrayList<int[]> getSuccesors ( int [] state, int a, int b )
     {
         ArrayList<int[]> succesors = new ArrayList<int[]>();
         //loops through search space
         for ( int i = 0; i < state.length; i++ )
         {
             //if it is the first index of the array it only checks if the number is greater than the number to the right.
             //if it is larger than the number to the right then it is a possible successor.
             if ( i == 0)
             {
                 if ( state[i] > state[i+1] )
                 {
                	 int [] stateHold = new int [state.length];
                     for ( int j = 0; j < state.length; j++ )
                     {
                    	 int z = state[j];
                    	 stateHold[j] = z;
                     }
                     stateHold[i] = -1;//-1 represents an empty square
                     succesors.add(stateHold);
                 }
             }
             //if i is not the last index of the array it checks the number to the let and to the right.
             else if ( i != (state.length-1))
             {
                 if ( state[i] > state[i-1] && state[i] > state[i+1] )
                 {
                     int [] stateHold = new int [state.length];
                     for ( int j = 0; j < state.length; j++ )
                     {
                    	 int z = state[j];
                    	 stateHold[j] = z;
                     }
                     stateHold[i] = -1;//-1 represents an empty square
                     succesors.add(stateHold);
                 }
             }
             //otherwise i is the last number of the array and it only checks the number to the left
             else
             {
                if ( state[i] > state[i-1] )
                {
                	int [] stateHold = new int [state.length];
                    for ( int j = 0; j < state.length; j++ )
                    {
                   	 int z = state[j];
                   	 stateHold[j] = z;
                    }
                    stateHold[i] = -1;//-1 represents an empty square
                    succesors.add(stateHold);
                }
             }
         }
        return succesors;
     }
}