Please show all steps and answer question according to what is asked in question: Programming Question

The best way to learn a data structure or an algorithm is to code it up$.$ In this assignment, we have a programming

exercise for which you will be asked to write some code and submit it$.$ You may also be asked to include a write$-$up

about your code in the PDF file that you submit. Make sure to maintain your academic integrity carefully, and

protect your own work. All code submissions will be checked for plagiarism at the end of the term. It is much better

to take the hit on a lower mark than risking much worse consequences by committing an academic offence.

$[10]$ Consider the game of "Sorting Hockey Pucks" as depicted in the following diagrams $($Figure $1$ and $2).$ Initially, a

sequence of $N$ hockey pucks are placed at the START area. The pucks are numbered $1,2,3,$dots,$N$ but are arbitrarily

ordered. The goal of the player is to move the pucks out of the EXIT on the left side in the exact order of $1,2,3,$

dots,$N.$ However, it might not be possible to move out all $N$ pucks in that exact order. We will write a program to

determine $K,$ the largest number of the pucks that can be moved out in the exact order of $1,2,$dots,$K.$

As you can see in the diagram, there is a BUFFER LINE that you may temporarily move the pucks to$.$ One important

rule about moving a puck into$/$out of the buffer line is that the puck can only turn left as indicated by the turning

arrows in the figures.

Figure $1$: Example of the initial state of a game

Figure $2$: The final state of the above game example.Download the starter file A$1$Q$2.$ java, and complete the solve function. It takes an array, and returns $K,$ the largest

number of the pucks that can be moved out in the exact order of $1,2,$dots,$K.$ If the array is of length $N,$ then its

elements are guaranteed to be a permutation of the $N$ integers from $1$ to $N.$

Your implementation must make use of one or more Stack or Queue objects, and you will explain the usage of

them in your PDF file.

Read all instructions in the starter code carefully. In particular, make sure to NOT modify the parts of the starter code

that says $"$DO NOT MODIFY" in the comments, e$.$g$.,$ the package declaration "package A$1"$ and the import lines.

As an example, for the game shown in Figure $1,$ the input array would be $[4,5,2,1,3],$ and the solve function

should return $3,$ according to the final state illustrated in Figure $2.$

The main function of the starter code includes a few test cases that you may use to test your own code. These test cases

are not meant to be exhaustive so passing them does not necessarily mean your program is correct. You're encouraged

to create more test cases to test your program more thoroughly.

You may setup the Java project using any programming IDE of your choice such as IntelliJ, Eclipse, VSCode, or Notepad

$$ it doesn't matter as long as the A$2$Q$2.$ java file is correct. Be careful: sometimes the IDE automatically inserts lines

of code such as the package declaration and imports. Make sure to double$-$check your code before submission to remove

any unnecessary those extra lines since they may cause all test cases to fail in auto$-$testing.

What to include in your submission:

In the PDF file a$1$sol.pdf$,$ provide a clear description of how your algorithm works. In particular, explain clearly

why a stack or a queue is used and how you use it$.$ Your writing for this part should be concise: one or two

paragraphs should be enough, and do not exceed one page.

Your A$1$Q$2.$java file with the complete implementation your solution. This is the only Java file you submit, i$.$e$.,$

any new class that you add must be included within this file.

The marking of this question will be $50\%$ based on the correctness of the code in A$1$Q$2.$java $($passed test cases in

auto$-$testing$),$ and $50\%$ based on the written answers provided in the PDF file.