Retry invalid inputs without switching players; after a legal move, check whether the board has become empty:
val game = new Chomps(6)
var player = 1
while (game.Count() > 0) {
  game.Display()
  var accepted = false
  var x = 0
  var y = 0
  while (!accepted) {
    try {
      println("Player " + player + ": enter x, then y")
      x = scala.io.StdIn.readInt()
      y = scala.io.StdIn.readInt()
      accepted = game.Legal(x, y)
      if (!accepted) println("That cell is not a legal move; try again.")
    } catch {
      case _: NumberFormatException => println("Please enter integer coordinates.")
    }
  }
  game.Move(x, y)
  if (game.Count() == 0)
    println("Player " + player + " loses; player " + (3 - player) + " wins.")
  else player = 3 - player
}
Only a move at can remove the poisoned bottom-left token, and that move removes the entire remaining order ideal, so the empty-board test identifies the losing player correctly. Any other legal move preserves that token. Every accepted move strictly decreases the finite token count, giving at most 36 accepted moves. Invalid attempts do not change the board or the turn. As usual for this interactive fragment, the user is assumed eventually to supply another readable input rather than permanently ending the input stream or retrying forever.
Use column heights and update the cached count by the number of removed cells:
class Chomps(N: Int) {
  require(N > 0 && N.toLong * N.toLong <= Int.MaxValue)
  private val height = Array.fill(N)(N)
  private var remaining = (N.toLong * N.toLong).toInt

  def Count(): Int = remaining

  def Legal(x: Int, y: Int): Boolean =
    0 <= x && x < N && 0 <= y && y < height(x)

  def Move(x: Int, y: Int): Unit = {
    require(Legal(x, y), "illegal move")
    var i = x
    while (i < N && height(i) > y) {
      remaining -= height(i) - y
      height(i) = y
      i += 1
    }
  }

  def Display(): Unit = {
    require(N < 10, "single-digit display labels required")
    var y = N - 1
    while (y >= 0) {
      print(y + "  ")
      var x = 0
      while (x < N) {
        print(if (y < height(x)) "* " else "  ")
        x += 1
      }
      println()
      y -= 1
    }
    print("   ")
    var x = 0
    while (x < N) { print(x + " "); x += 1 }
    println()
  }
}
The strengthened representation invariant includes . The move loop's processed columns have their final truncated heights, unprocessed columns retain their old heights, and each subtraction removes exactly the corresponding height reduction. Because heights are nonincreasing, once a column is no higher than y, neither is any later column; stopping there is valid. A legal move removes at least one token and leaves a order ideal.
The constructor computes in Long and checks representability before converting, avoiding integer overflow in the cached Int count. Legal rejects out-of-range coordinates before indexing. The methods meet the bounds in part (a); Display additionally checks its stated single-digit-label assumption.
Use sparse dot product by merging indices: only equal coordinate indices can contribute, so merge the two increasing index streams:
def dotProduct(vec1: Node, vec2: Node): Double = {
  require(vec1 != null && vec2 != null)
  require(vec1.index == vec2.index, "dimension mismatch")
  var p = vec1.next
  var q = vec2.next
  var answer = 0.0
  while ((p ne vec1) && (q ne vec2)) {
    if (p.index < q.index) p = p.next
    else if (q.index < p.index) q = q.next
    else {
      answer += p.value * q.value
      p = p.next
      q = q.next
    }
  }
  answer
}
The loop invariant states that the accumulator contains all common-coordinate products already passed, while no unprocessed smaller coordinate can acquire a future partner. If one current index is smaller, the other list has no remaining entry at that index, so its product is zero. Equal indices add their product and advance both. Once either list ends, all remaining coordinates of the other have zero partners.
Thus the code computes the dot product in coordinate order, subject to floating-point rounding, using time and constant auxiliary storage. It does not scan implicit zeros or alter either vector, and it also handles both arguments referring to the same header.
Append nonzero entries in increasing index order; repeatedly calling setElement would unnecessarily rescan earlier entries and could make construction quadratic.
def makeVector(elems: Array[Double]): Node = {
  require(elems != null)
  val head = makeZeroVector(elems.length)
  var tail = head
  var i = 0
  while (i < elems.length) {
    val v = elems(i)
    require(!v.isNaN && !v.isInfinity)
    if (v != 0.0) {
      val fresh = new Node(v, i, tail, head)
      tail.next = fresh
      head.prev = fresh
      tail = fresh
    }
    i += 1
  }
  head
}
The loop invariant says that the list represents exactly the nonzero entries of the processed input prefix, in their original coordinate order, and tail is the final node or the header when none exist. Every append preserves the cycle and ordering. At exit, all input coordinates have their intended values. Construction takes time and data nodes, where is the array length and the number of nonzeros, plus one header. The input array is unchanged.
An absent coordinate already has value zero. If found, unlink its node in both directions:
def zeroElement(vector: Node, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) {
    p.prev.next = p.next
    p.next.prev = p.prev
  }
}
Identity comparison with the header prevents treating its dimension field as a data index. The splice preserves reciprocal links even when removing the only data node: the two header links then point to the header again. All other coordinates are unchanged, and an absent coordinate causes no mutation. The running time is , with constant work after the node is located.
Assume vector is a well-formed header satisfying the sparse-vector representation invariant; checking that whole invariant on each operation would require traversing the list. Check the requested bounds and value, then find the first stored coordinate at or after the target.
def setElement(vector: Node, value: Double, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  require(value != 0.0 && !value.isNaN && !value.isInfinity)
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) p.value = value
  else {
    val fresh = new Node(value, index, p.prev, p)
    p.prev.next = fresh
    p.prev = fresh
  }
}
The scan excludes all smaller stored indices. An existing coordinate is updated without duplicating it; otherwise the new node is spliced immediately before p, with both directions repaired. The header also serves as the insertion boundary after the final data node. Strict index order and nonzero storage are preserved. The cost is search and pointer work, where is the number of stored entries.
Permit any nonnegative dimension, including the empty vector:
def makeZeroVector(size: Int): Node = {
  require(size >= 0, "negative vector length")
  val head = new Node(0.0, size, null, null)
  head.prev = head
  head.next = head
  head
}
This establishes the circular-link representation invariant in time and uses one header regardless of the number of implicit zeros. For the nonzero dimension mentioned in part (b), simply use size > 0 at that call site.
A list header is a permanent dummy node that represents the list boundary rather than a data entry. A circular linked list links the last node back to the first or to the header. A singly linked list stores only a successor; a doubly linked list stores both successor and predecessor references.
A header provides a stable object even for an empty list, makes insertions and deletions at the ends resemble interior operations, and can hold metadata such as the vector length in this question. In a circular header-based representation, the empty list is the header linked to itself.
A doubly linked list permits backward traversal and constant-time unlinking of a known node without searching for its predecessor. It uses an extra reference per node and requires more pointer updates and a stronger consistency invariant. Finding a node by an arbitrary index can still require a linear scan: bidirectional links alone do not provide random access.
Use the trait and node definition above. The reference to a “stack” in this part is a wording error: the declared class and operations implement a FIFO queue.
class ListQueue extends Queue[Int] {
  private var first: QueueNode = null
  private var last: QueueNode = null
  private var size = 0

  def enqueue(x: Int): Unit = {
    require(size < Int.MaxValue, "queue size limit")
    val fresh = new QueueNode(x, null)
    if (last == null) first = fresh
    else last.next = fresh
    last = fresh
    size += 1
  }

  def dequeue(): Int = {
    require(first != null, "empty queue")
    val answer = first.value
    first = first.next
    size -= 1
    if (first == null) last = null
    answer
  }

  def clear(): Unit = {
    first = null
    last = null
    size = 0
  }

  def isEmpty: Boolean = size == 0
  def length: Int = size
}
Appending links the fresh node after the old tail, or establishes both endpoints when empty. Removing the head preserves the tail unless the final node was removed, in which case both endpoints become null. Clearing only discards the endpoint references; it need not visit or overwrite unreachable nodes. Thus all operations are in the usual pointer-operation/allocation cost model, with later garbage collection excluded from an individual operation's bound. The representation invariant and abstraction function show the specified sequence changes, including empty/singleton transitions.
Keep a head, a tail and a cached length:
private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0
The representation invariant requires and a finite acyclic null-terminated linked list of exactly size nodes starting at first. When size == 0, both endpoints are null. Otherwise last is precisely the final reachable node and last.next == null.
The abstraction function maps the chain from first to last to its payload sequence. Initially all pointers are null and the cached size is zero, giving the empty abstract queue. A tail pointer makes append constant-time; the cached size makes the length query constant-time without traversing the chain.
A node needs a stored value and one successor reference:
final class QueueNode(val value: Int, var next: QueueNode)
A null successor terminates the chain. The stored value need not be mutable for a FIFO queue, because enqueue creates a node and dequeue removes one rather than changing its payload.
The abstract FIFO queue state is a finite sequence , initially empty. Because the interface returns Int length, use the representable-size model . Its operations are:
trait Queue[A] {
  // State q: finite sequence of A; initially [].
  // Pre: length(q) < Int.MaxValue. Post: q = q0 ++ [x].
  def enqueue(x: A): Unit

  // Pre: q is nonempty. Post: return head(q0); q = tail(q0).
  def dequeue(): A

  // Post: q = [].
  def clear(): Unit

  // Post: q unchanged; return q.isEmpty.
  def isEmpty: Boolean

  // Post: q unchanged; return length(q).
  def length: Int
}
The unchanged-state clauses on the two queries are part of their postconditions. dequeue removes exactly the oldest remaining element, while clear discards all entries regardless of the old state. The size bound can be omitted in an unbounded mathematical model, but it must be reconciled with fixed-width lengths in an implementation.
Maintain a remaining rectangle with its top-right corner at (i,j):
def searchMonotone(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
  val n = f.length
  val m = if (n == 0) 0 else f(0).length
  var i = 0
  var j = m - 1
  while (i < n && j >= 0) {
    val v = f(i)(j)
    if (v == x) return Some((i, j))
    else if (v < x) i += 1
    else j -= 1
  }
  None
}
The loop invariant is that any match must lie in rows and columns . Smaller corner values exclude the current row, larger ones exclude the current column, as shown in part (d). The loop variant is nonnegative while the rectangle is nonempty and decreases by one on every unsuccessful inspection. When the loop exits, the rectangle is empty, so absence is established.
At most entries are inspected when both dimensions are positive, giving running time and auxiliary space. An empty dimension causes no entry access. Duplicates do not affect the argument, since every exclusion uses a strict inequality relative to the target.

There are unlisted articles, also show them or only show them.