• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

jigsaw Java puzzle

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi friends,
Need help on one of the puzzle in java , here is the snippet:

A farmer wants to reorganize the crops growing in his farm. The farm is in the form of an N X M grid with each cell in the grid being a square plot. Each plot has to be planted with a variety of crop. The farmer has 26 varieties of crops that he can plant. The plant varieties are represented by lowercase English alphabets. He wants to follow the following condition while planting:In each row, there must be at least 2 different varieties of crops ( any number of crops can be used in a column)No two nearby (Top, bottom, left, right) plots can have the same variety of crops.Given the current state of the farm, find the minimum number of plots that have to replant with a different crop so that the above conditions are satisfied. Input The first line contains two integers N and M, the dimensions of the farm.The next N lines contain M lowercase characters from‘a’ to ‘z’ representing the crop variety at that plot. Output Output a single integer denoting the minimum number of plots that have to be replanted in order to satisfy the conditions imposed.


Example 1 input:

4   4
acaa
dddd
bbbb
ccce

Output 6
Explanation: In this Example, We may replant the farm to look like:
acac
dede
baba
cece

This arrangement of crop varieties satisfies the given conditions and the cost of this replacement is 6.


code snippet:

import java.util.Scanner;
class Solution {
public static void main(String[] args)
{

   int n;
   Scanner in = new Scanner(System
   n = in.nextInt();
   in.nextLine();
   String[] crops = new String[n];
   for (int i=0;i<n;i++){
   crops[i]=in.nextLine().trim
   }
   System.out.print(replant(crops)
}

public static int replant(String[] crops){
   // Write your code here
   // Return the number of replanted crops
   return 0;
   }
}


 
Saloon Keeper
Posts: 3407
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Rahul,

welcome to the ranch and enjoy the stay!

Have you thought of some strategy yet?

My first idea was to count, for all the elements, how many 'wrong' neighbors each has, and start changing that element with the according highest number, and repeat, until the total of wrongs are 0. However, that is not a strategy that leads to a guaranteed minimum number of changes. For instance, given this input array:
a a a
a a a
a a a

The center element has a 'wrong index' of 4, so you might start changing that one, leading to
a a a
a b a
a a a

However, that will lead to 5 changes until succes, while this configuration

a b a
b a b
a b a
only needs 4 changes.

So my first thought was to use a simple straightforward Breath First Search, hoping that the values of N and M will not be too large. Is this a HackerRank problem? If so, the constraints will be given. And in that case, a clue might be to look at the category of the problem: is it easy, medium or hard? But maybe tomorrow some more clever strategy comes to my mind.
 
Rahul vaidya
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Piet,

Indeed the constraint is given ,

Constraints

1 < N,M ≤ 500
Each character in the grid is a lowercase English
alphabet.

pardon me but i was not able to find the category of the problem...

my initial step was to move ahead with the 2D matrix scenario but sure that hasn't worked out...
 
Rahul vaidya
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
any update guys...need help
 
Piet Souris
Saloon Keeper
Posts: 3407
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Rahul,

unfortunately, I could not come up with a strategy that would lead to a guaranteed minimal number of changes. I was thinking of a Cell class, with integers x and y, a char as content and the number of equal neighbors (up, down, left, right). I was, as I wrote, also thinking of some A* strategy, by changing first those cells that have highest number of wrong neighbors. But as I showed in my example, that does not necessarily work. Also, the maximum size of 500 x 500 with potentially 25.000 cells to change does not invite to some brute forrce approach.

Does anyone know of some handy theoreme that is applicable here?

But have you thought of some structure, that is suitable to this problem?

My thought was to have a TreeSet of Cells that need to be changed, ordered by the number of wrong neightbors, change the first one, see what remains of that list, et cetera. But taht would still be brute force, and is not so easy to implement. Still trying to find some theory that might be of use, here.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!