Puzzles with Java-1: Traveler and the coins

Posted on: 30 May 2019

Category: Technical

Blog Views: 434

Traveler and the coins

 

Problem: 

A traveller has less than 400 coins with him. Along the way he meets 4 vagabonds. To the first vagabond he gives 4 coins and of the remaining coins he gives 1/4 th of the coins to the same vagabond. To the second vagaond he gives 4 coins and of the remaining coins he gives 1/4 th of the coins... this goes on for the 3rd and the 4th vagabond. After he has given the coins to the 4th vagabond he has some coins still left and none of the coins are cut while distributing.

How many coins did the traveller have?

Approach:

Before jumping to the solution of this puzzle lets note down some important points about this puzzle:

  • there are 4 vagabonds
  • the number of coins to be given upfront is 4
  • Maximum number of coins the traveller had is less than 400
  • At any point when dividing the coins the total number of the coins was divisable by 4 (quarter of the remaining coins) 

Class Variables:

First lets define some class variables for constants. By defining class variables, not only will the code be readable and re-usable, it would also be flexible since at any point you can change the number of vegabonds, max allowed coins etc. The class variables would look like this:

private int NUM_VEGABOND = 4;
private int NUM_COINS_UPFRONT = 4;
private int MAX_ALLOWED_COINS = 1000;
 
 
 

Building Blocks:

A typical program should have smaller methods or functions with intuitive names. In this example we will be looping through number of coins starting from 1 to 400 and with each iteration there will be some conditions we will look for. Those conditions are:

Do we have more than zero coins (or atleast one coin)?

A simple method for this would look like this. (num is the input of number of coins in the current iteration)

private boolean hasMoreThanZeroCoins(int num) {

return num > 0;
}

Do we have enough coins to divide with?

At any point the number of coins should be greater than 4 (num of vegabond), since we cannot cut the coins

private boolean hasEnoughCoins(int num) {

return num > NUM_VEGABOND;

}

Are the coins exactly divisible?

At any point the number of coins should be exactly divisible by 4 (number of vegabonds)

private boolean isDivisable(int num) {

return num % NUM_VEGABOND == 0;
}
 
Now that we have these methods, the core logic of the program would be to:
  • loop through 4 (num of vegabond) to 400 (Max coins)
    • ​for each iteration loop through 1 to 4 (number of vegabonds)
      • ​subtract 4 (num of vegabonds) from current number
      • if the remaining number is greater than 0 and has enough coins and is exactly divisble by 4 (num of vegabonds) then subract 1/4th of the remaining coins

​The solve() method will look like this:

public void solve()

{
for (int currentNum = NUM_VEGABOND; currentNum < MAX_ALLOWED_COINS; currentNum++)
{
int remainingCoins = currentNum;
for (int currentVegabond = 0; currentVegabond <NUM_VEGABOND ; currentVegabond++)
{
remainingCoins = remainingCoins - NUM_COINS_UPFRONT;
if (hasMoreThanZeroCoins(remainingCoins) && hasEnoughCoins(remainingCoins)  && isDivisable(remainingCoins)  )
{
remainingCoins = remainingCoins - remainingCoins / NUM_VEGABOND;
}
else
{
remainingCoins = 0;
}
}
if (remainingCoins > 0 && remainingCoins < currentNum )
{
System.out.println("Total coins is :" + currentNum);
}
}
}
 
The complete program would look like this:
 
 
public class Vagabond 
{
 
private int NUM_VEGABOND = 4;
private int NUM_COINS_UPFRONT = 4;
private int MAX_ALLOWED_COINS = 400;
 
public void solve()
{
for (int currentNum = NUM_VEGABOND; currentNum < MAX_ALLOWED_COINS; currentNum++)
{
int remainingCoins = currentNum;
for (int currentVegabond = 0; currentVegabond <NUM_VEGABOND ; currentVegabond++)
{
remainingCoins = remainingCoins - NUM_COINS_UPFRONT;
if (hasMoreThanZeroCoins(remainingCoins) && hasEnoughCoins(remainingCoins)  && isDivisable(remainingCoins)  )
{
remainingCoins = remainingCoins - remainingCoins / NUM_VEGABOND;
}
else
{
remainingCoins = 0;
}
}
if (remainingCoins > 0 && remainingCoins < currentNum )
{
System.out.println("Total coins is :" + currentNum);
}
}
}
 
private boolean hasMoreThanZeroCoins(int num)
{
return num > 0;
}
 
private boolean hasEnoughCoins(int num)
{
return num > NUM_VEGABOND ;
}
 
private boolean isDivisable(int num)
{
return num % NUM_VEGABOND == 0;
}
 
public static void main(String[] args) {
new Vagabond().solve();
}
 
 
 

Answer:

244.

When you run the program you will get the output:

Total coins is :244

When you run the program with max coins as 1000, you will get more than one answer:

Total coins is :244

Total coins is :500

Total coins is :756
 

Tags: Puzzles with Java






List of blogs (Technical)

  Puzzles with Java-1: Traveler and the coins
The design of everyday things- a gas stove
Trunk based development- A journey