#! /usr/bin/env python
#
def counterfeit_detection_combinatorial ( logn, coin, correct ):

#*****************************************************************************80
#
## counterfeit_detection_combinatorial detects a counterfeit coin.
#
#  Discussion:
#
#    N = 2^(logn) - 1 coins are given.  All but one have the correct weight.
#    Identify the fake coin in logn weighings.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    22 March 2019
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Kurt Bryan, Tanya Leise,
#    Making do with less: an introduction to compressed sensing,
#    SIAM Review,
#    Volume 55, Number 3, September 2013, pages 547-566.
#
#  Parameters:
#
#    Input, integer logn, the number of coins is 2^logn - 1.
#
#    Input, real coin(2^logn-1), the weights of the coins.
#
#    Input, real correct, the correct weight of a single coin.
#
#    Output, integer suspect, the index of the suspected counterfeit coin.
#
  import numpy as np

  n = 2 ** logn - 1
#
#  The PHI matrix encodes the binary representations of 1 through n.
#  For n = 7:
#
#    1 0 1 0 1 0 1
#    0 1 1 0 0 1 1
#    0 0 0 1 1 1 1
#
#  We compute column J of the PHI matrix, and multiply by COIN(J),
#  and add that to W.  W = PHI * COIN.
#
  w = np.zeros ( logn )
  phi = np.zeros ( logn )

  for j in range ( 0, n ):
    for i in range ( 0, logn ):
      if ( phi[i] == 0 ):
        phi[i] = 1
        break
      phi[i] = 0
    w[0:logn] = w[0:logn] + phi[0:logn] * coin[j]
#
#  The suspected coin is found because the incorrect entries in W
#  form the binary representation of the index.
#
  suspect = 0
  good = correct * 2 ** ( logn - 1 )
  factor = 1
  for i in range ( 0, logn ):
    if ( w[i] != good ):
      suspect = suspect + factor
    factor = factor * 2
#
#  Subtract 1 for Python base 0 indexing...
#
  suspect = suspect - 1

  return suspect

def counterfeit_detection_combinatorial_test ( logn ):

#*****************************************************************************80
#
## counterfeit_detection_combinatorial_test tests counterfeit_detection_combinatorial.
#
#  Discussion:
#
#    N = 2^(logn) - 1 coins are given.  All but one have the correct weight.
#    Identify the fake coin in logn weighings.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    22 March 2019
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Kurt Bryan, Tanya Leise,
#    Making do with less: an introduction to compressed sensing,
#    SIAM Review,
#    Volume 55, Number 3, September 2013, pages 547-566.
#
#  Parameters:
#
#    Input, integer logn, the number of coins is 2^logn - 1.
#    A value of 3 is typical.
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'counterfeit_detection_combinatorial_test' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Test counterfeit_detection_combinatorial,' )
  print ( '  which can identify one counterfeit coin among 2^logn-1 coins' )
  print ( '  using just logn comparisons.' )

  n = 2 ** logn - 1
#
#  Set the data.
#
  correct = 17.0
  coin = correct * np.ones ( n );
#
#  Select one coin at random to have the wrong weight.
#
  fake = np.random.randint ( 0, n )
  coin[fake] = coin[fake] + 0.5 * np.random.normal ( 1 )

  suspect = counterfeit_detection_combinatorial ( logn, coin, correct )
#
#  Compare actual fake to your suspect.
#
  print ( '' )
  print ( '  %d coins were checked' % ( n ) )
  print ( '  The fake coin was number %d' % ( fake ) )
  print ( '  %d comparisons were made' % ( logn ) )
  print ( '  The suspected coin is number %d' % ( suspect ) )

  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  logn = 3
  counterfeit_detection_combinatorial_test ( logn )
  timestamp ( )