# Coin Forgery

Page 1 of 1

## 3 Replies - 1686 Views - Last Post: 06 April 2011 - 09:07 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=226405&amp;s=45f2bec9260eaf4f33b163d460380837&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 orange75

Reputation: 1
• 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){
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

• jaVanir

Reputation: 1013
• 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

### #3 orange75

Reputation: 1
• 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.

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11796
• Posts: 44,320
• 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.