Robert Eisele
Engineer, Systems Architect and DBA

Codefights: Poker Chips

Bart set up a circular poker table for his friends so that each of the seats at the table has the same number of poker chips. But when Bart wasn’t looking, someone rearranged all of the chips so that they are no longer evenly distributed! Now Bart needs to redistribute the chips so that every seat has the same number before his friends arrive. But Bart is very meticulous: to ensure that he doesn’t lose any chips in the process, he only moves chips between adjacent seats. Moreover, he only moves chips one at a time. What is the minimum number of chip moves Bart will need to make to bring the chips back to equilibrium?

Example
For chips = [1, 5, 9, 10, 5], the output should be
pokerChips(chips) = 12.
The array represents a circular table, so we are permitted to move chips between the last and the first index in the array. Thus Bart can bring the chips back to equilibrium with the following steps (1-indexed):

  • move 2 chips from seat 2 to seat 1 (2 moves);
  • move 3 chips from seat 3 to seat 2 (3 moves);
  • move 3 chips from seat 5 to seat 1 (3 moves);
  • move 4 chips from seat 4 to seat 5 (4 moves).

After this sequence of 12 moves, each seat will have 6 chips, and there is no sequence of fewer moves doing the same.

Input/Output

  • [execution time limit] 4 seconds (py)

  • [input] array.integer chips

    The chip counts of each seat.

    Guaranteed constraints:
    0 ≤ chips.length ≤ 106,
    0 ≤ chips[i] ≤ 100.

  • [output] integer

    The minimum number of moves required to restore the chip counts.

Solution

We have a table with \(n\) persons. Each person should have \(m\) chips, but accidentally got \(\mathbf{c}_i\) and our aim is to restore equilibrium with the least swaps. A swap can be made only with a direct neighbor on the table and only one chip at a time can be exchanged. It is obvious that \(m=\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{c}_{i-1}\) for the zero-indexed vector \(\mathbf{c}\).

We define a difference vector \(\mathbf{d}\) to know what must be moved from each person:

\[\mathbf{d} = m - \mathbf{c}\]

A flow vector \(\mathbf{f}\) describes how many chips must be moved from person \((i-1)\bmod n\) to person \(i\) and using it, we can define our cost-function, which shall be used for \(f_0\):

\[g(f_0; \mathbf{d}) = \sum\limits_{i=1}^{n} |\mathbf{f}_{i-1}|\]

Now each person \(i\) gets \(\mathbf{f}_i\) cards from left and hands \(\mathbf{f}_{(i+1)\bmod n}\) to the right. From the definition of \(\mathbf{f}_i\) follows

\[\begin{array}{rrl} &\mathbf{d}_i &= \mathbf{f}_i - \mathbf{f}_{(i+1)\bmod n}\\ \Leftrightarrow&\mathbf{f}_{(i+1) \bmod n} &= \mathbf{f}_i - \mathbf{d}_i \end{array}\]

Putting this knowledge into our cost function yields

\[\begin{array}{rl} g(f_0; \mathbf{d}) &= |\mathbf{f}_0| + |\mathbf{f}_1| + \dots + |\mathbf{f}_{n-1}|\\ &= |\mathbf{f}_0| + |\mathbf{f}_0-\mathbf{d}_0| + \dots + |\mathbf{f}_{n-1}-\mathbf{d}_{n-1}|\\ &= |\mathbf{f}_0| + |\mathbf{f}_0-\mathbf{d}_0|+|\mathbf{f}_0-\mathbf{d}_0-\mathbf{d}_1| + \dots + |\mathbf{f}_{0}-\sum\limits_{i=0}^{n-2}\mathbf{d}_{i}| \end{array}\]

This is interesting. We know already from here how to minimize a sum of absolute values: Using the median! Therefore

\[\begin{array}{rl} \mathbf{f}_0 &= \text{median}({0, \mathbf{d}_0, \mathbf{d}_0+\mathbf{d}_1, \mathbf{d}_0+\mathbf{d}_1+\mathbf{d}_2,\dots , \mathbf{d}_0 + ... + \mathbf{d}_{n-2}) }) \end{array}\]

Putting \(\mathbf{f}_0\) now back into \(g\) calculates the minimal number of swaps.

Python Implementation

The mathematical derivation can be implemented in Python quite easily:

import numpy as np
def pokerChips(chips):
  m = np.mean(chips)
  arr = []
  s = 0
  for x in chips:
    arr.append(s)
    s+= x - m
  f_0 = int(np.median(arr))
  res = 0
  for x in arr:
    res+= abs(x - f_0)
  return res

« Back to problem overview