3 Replies - 383 Views - Last Post: 06 April 2011 - 09:07 PM Rate Topic: -----

#1 orange75  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 30
  • Joined: 11-November 10

Coin Forgery

Posted 06 April 2011 - 06:12 PM

So I'm trying to write up a program that will detect a coin forgery by dividing all of them into three piles and then comparing the weights as the bad one will weigh less, so the pile that weighs slightly less will contain the coin. It worked for two piles, however when I try to go for three, sometimes it gets the coin order right or it'll give me the position at the beginning and an different number at the end.

Here's what I have:

  import java.util.Random;
import java.util.Arrays;

public class SimpleFakeCoin {

	private Coin[] initializeCoins(int numCoins){
		Coin[] coins = new Coin[numCoins];
		for(int j = 0; j < coins.length; j++) coins[j] = new Coin(0.02, j);
		Random ran = new Random();
		Float f = numCoins*ran.nextFloat();
		int fakePosition = f.intValue();
		coins[fakePosition].setWeight(0.01);  // this is the fake coin
		System.out.println("The fake coin is a position "+fakePosition);
		return coins;
	}
	
	/**********************************************************
	 *   -1 means the left pan is heavier
	 *    0 means the pans have equal weight
	 *    1 means the right pan is heavier
	 **********************************************************/
	private int compareCoins(Coin[] left, Coin[] mid, Coin[] right){
		if(left.length != right.length||mid.length != right.length) System.out.println("unequal piles");
		double leftWeight = 0.0;
		for(int j = 0; j < left.length; j++) leftWeight += left[j].getWeight();
		double rightWeight = 0.0;
		for(int k = 0; k < right.length; k++) rightWeight += right[k].getWeight();
		double midWeight = 0.0;
		for(int q = 0; q < mid.length; q++) midWeight += mid[q].getWeight();
		if(leftWeight < rightWeight) return 1;
		else if (leftWeight > rightWeight) return -1;
		else return 0;
	}
	
	private void searchMessage(Coin[] coins){
		if (coins.length >= 1){
			System.out.println("searching from " + coins[0].getPosition()+ " to " + coins[coins.length - 1].getPosition());
		} else System.out.println("searching empty array");
	}

	private int findFakeCoin(Coin[] coins){
		if(coins.length == 0) return -1; // fake coin not found
		else if(coins.length == 1) return coins[0].getPosition();
		else {
			boolean oddNumCoins = coins.length % 3 == 1;
			int mid = coins.length/3;
			int mid2 = coins.length*2/3;
			Coin[] leftCoins = Arrays.copyOfRange(coins, 0, mid);
			Coin[] midCoins = Arrays.copyOfRange(coins, mid, mid2);
			Coin[] rightCoins = Arrays.copyOfRange(coins, mid2, coins.length);
			int result = compareCoins(leftCoins, midCoins, rightCoins);
			if(result == 1) { 
				searchMessage(leftCoins);
				return findFakeCoin(leftCoins);
			}
			else if(result == -1){ 
				searchMessage(rightCoins);
				return findFakeCoin(rightCoins);
			}
			else if (result == 0){
				searchMessage(midCoins);
				return findFakeCoin(midCoins);
			}
			else if(oddNumCoins) return coins[coins.length-1].getPosition();
			else return -1; // no fake coin found
		}
	}

	public static void main(String[] args) {
		SimpleFakeCoin fc = new SimpleFakeCoin();
		Coin[] coins = fc.initializeCoins(100);
		int fakeCoinPosition = fc.findFakeCoin(coins);
        System.out.println("The fake coin is found at position " + fakeCoinPosition);
	}
	
	private class Coin {  // inner class
		double weight;
		int position;
		
		Coin(double weight, int position){
			this.weight = weight;
			this.position = position;
		}
		
		double getWeight() {
			return weight;
		}
		
		void setWeight(double weight){
			this.weight = weight;
		}
		
		int getPosition(){
			return position;
		}
	}

}  


Is This A Good Question/Topic? 0
  • +

Replies To: Coin Forgery

#2 japanir  Icon User is offline

  • jaVanir
  • member icon

Reputation: 1010
  • View blog
  • Posts: 3,025
  • Joined: 20-August 09

Re: Coin Forgery

Posted 06 April 2011 - 06:51 PM

The best thing to do when trying to sort n objects, is to implement the Comparable interface in the class, and create an array of these objects.
call Arrays.sort to sort that array then:
http://www.java-tips...-interface.html
Anyways,if that tip doesn't help, can you please provide some more info about the problem?
Was This Post Helpful? 2
  • +
  • -

#3 orange75  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 30
  • Joined: 11-November 10

Re: Coin Forgery

Posted 06 April 2011 - 06:59 PM

I think the problem is that the coin weights don't always balance if the number of coins added isn't divisible evenly by three. I need to figure out how to add the coins to the mid pile because if there's extra coins in the right pile, it'll just assume that the forgery is in the other pile.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10558
  • View blog
  • Posts: 39,064
  • Joined: 27-December 08

Re: Coin Forgery

Posted 06 April 2011 - 09:07 PM

Are the piles part of the requirements? If not, I like japanir's idea of sorting the Coin[] to look for the forgery. Also, how is the use of the middle pile as "overflow" really that different from just using two piles? I follow what you are trying to do, but I'm not really following the reasoning behind some of this.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1