counterfeit_detection

counterfeit_detection a Python library which considers problems in which one or more counterfeit coins are to be identified by the fact that they do not have the standard weight.

Methods include:

• brute force: weigh every coin and report those with bad weight;
• combinatorial: assume there is only 1 bad coin, and that the number of coins is 2^n-1. carry out n weighings to determine the bad coin.
• compressed sensing: weigh a certain number of random subsets of the coins and solve an underdetermined linear system minimizing the l1 norm.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

counterfeit_detection is available in a MATLAB version and a Python version.

Reference:

1. Kurt Bryan, Tanya Leise,
   Making do with less: an introduction to compressed sensing,
   SIAM Review,
   Volume 55, Number 3, September 2013, pages 547-566.

Source Code:

• counterfeit_detection_brute.py, brute force approach to finding counterfeit coins;
• counterfeit_detection_combinatorial.py, combinatorial approach to finding a counterfeit coin;
• counterfeit_detection_compressed.py, compressed sensing approach to finding countereit coins.
• timestamp.py, prints the current YMDHMS date as a timestamp;

• counterfeit_detection_test.py, calls all the tests.
• counterfeit_detection_test.sh, runs all the tests.
• counterfeit_detection_test.txt, the output file.