From C to Java

[HighterDK]

Hello there guys, I was trying to create a program that would tell me in how many parts I have to split a given sequence of letters, so every piece is a hum... forgot the word (what are these sequences called? aca, baab, dcacd).

I was able to make it in java, but it's a bit slow, so I searched around a bit and found the solution in C. Problem is, I don't know anything about C yet, so could someone transform this code in java for me?

/* pal.c   */
/* OBI2004 */
/* Ulisses */
#include <stdio.h>

#define NMAX 2002
#define INF NMAX*NMAX

char str[NMAX], pal[NMAX][NMAX];
int n, partes[NMAX];

int main(void) {
  int i, j, smaller, val, teste = 1;

  while (scanf("%d", &n)==1 && n) {
    scanf(" %s", str);
    memset(pal, 0, sizeof(pal));

    for (i=0; i<n; i++)
      pal[i][i] = 1;
    for (j=1; j<n; j++)
      for (i=j-1; i>=0; i--)
pal[i][j] = ((str[i]==str[j]) && (i+1>=j-1 || pal[i+1][j-1]));

    for (j=0; j<n; j++) {
      if (pal[0][j]) {
parts[j] = 1;
      } else {
smaller = INF;
for (i=1; i<=j; i++) {
  if (pal[i][j] && parts[i-1]+1<smaller)
    smaller = parts[i-1]+1;
}
parts[j] = smaller;
      }
    }

    printf("Test %d\n", test++);
    printf("%d\n\n", parts[n-1]);
  }

  return 0;
}

[Belisarius]

Generally it's not a good idea to do a straight translation from C into Java because often Java has core libraries to do things that you'd normally need to do yourself in C. Why don't you post your Java code, and we can work on optimizing that. And if you can, beautify it before posting so it makes it easier to read and understand.

[HighterDK]

Ok, here is an example input file:

100
ajcfeafjegjccehhfeibcijdgiacbafbbaifagegcfigciehce agcjjaibdbbadeadjbjgjddiafggeaaegcghfgjihcicjjgach
100
gbdcbfjjbejbahfihaeiaecjgbaecccaffcjacidiaeajbjgcf eejjdgafacjedfbhedbegjeccgebciijciiigididddiaehgij
101
agihjadddhdcgfcgfihjgaebaeihaigcehjdjcidabhijbfejc fhejjefjdfhaibjjhicfdejacabjgcbcahdbbjafghheagehei f
101
icgaggegcijgahababdhhcgefcacjajjefbadhiigaeghgajhf jhifddidhjdhihebjajiifiedhbdiajhjjdcedhbccacbhfbhe b
0

Ps: The sequence is entirely on a single line, but for some reason it got split here.

Initially I went with the break around the biggest pal method, but it soon showed it weakness when it received the String ggeaaegfg into g, geaaeg, f, g instead of gg, eaae, gfg. So I had to creat a method to find if the biggest String was the best choice. Yet it still fails on number 3, where it finds 85 instead of 84.

import java.io.*;

public class pal2 {

	public static void main(String args[]) throws IOException {

		// Preparing
		BufferedReader pal = new BufferedReader(new FileReader("pal.in"));
		PrintWriter palO = new PrintWriter(new FileWriter("pal.out"));
		String read = pal.readLine();
		int cont = 1;

		// Reading the file
		while (Integer.parseInt(read) != 0) {

			// Reading
			read = pal.readLine();

			// Writing teste x on file
			palO.println("Test " + cont);

			// Caling the method that will do the job
			int a = getNum(read);
			palO.println(a);
			palO.println();

			// Increasing pal counter and reading next number
			cont++;
			read = pal.readLine();
		}

		pal.close();
		palO.close();

	} // p s v m (S a)

	// Recursive Method to discover the number of parts needed
	public static int getNum(String p) {

		// Always begin with one, since this is the least amount of parts the
		// given string will have
		int x = 1;

		// Do the silly test, is it a pal?
		if (isPalindrome(p))
			return x;

		// if not, Finding an optimized pal
		String pal = findBestPal(p, true);

		// No pals on the String? X becomes it's size
		if (pal.length() == 0)
			x = p.length();

		// If there are..
		else {

			// Find the break point
			int separador = p.indexOf(pal);

			// Call yourself again using the left and rigth String
			if (separador > 0) {
				x += getNum(p.substring(0, separador));
			}

			if (separador + pal.length() < p.length()) {
				x += getNum(p.substring(separador + pal.length()));
			}

		}

		// Return the value you found
		return x;

	} // getNum

	// This method chooses the best pal around which the String has to the split
	public static String findBestPal(String p, boolean optimize) {

		// Strings for the biggest and second biggest
		String biggest = "";
		String secBiggest = "";

		// Searching through the given String
		for (int limitLeft = 0; limitLeft < p.length() - 1; limitLeft++) {

			String temp = "";

			// Keep increasing the right limit and verifying
			for (int limitRight = limitLeft + 1; limitRight < p.length(); limitRight++) {

				// Cheking if the current substring is a pal
				if (isPalindrome(p.substring(limitLeft, limitRight + 1))) {
					temp = p.substring(limitLeft, limitRight + 1);

					// Optimizing to make sure this is the best String
					if (optimize == true)
						temp = optimizePal(temp, p);

					// If the temp you found is bigger then the previous one
					// than replace it
					if (temp.length() > biggest.length()) {
						secBiggest = biggest;
						biggest = temp;

					}

					// Dealing with a situation where aacac was split in a, aca,
					// c
					else if (temp.length() == biggest.length()) {

						// If the biggest pal is using part of the second
						// biggest pal, and you find another pal of equal size
						// than replace it.
						if (p.indexOf(secBiggest) + secBiggest.length() > p
								.indexOf(biggest)
								&& biggest.indexOf(secBiggest) == -1
								|| p.indexOf(secBiggest) < p.indexOf(biggest)
										+ biggest.length()
								&& biggest.indexOf(secBiggest) == -1)
							biggest = temp;
					}
				}
			}
		}
		return biggest;
	}

	// Is the String a pal?
	public static boolean isPalindrome(String p) {

		for (int i = 0; i < p.length() / 2; i++) {
			if (p.charAt(i) != p.charAt(p.length() - i - 1)) {
				return false;
			}
		}
		return true;
	}

	// Méthod to make sure the best pal is being choosen
	public static String optimizePal(String temp, String p) {

		// Limits to search for new pals
		int position = p.indexOf(temp);
		int limitLeft = position + temp.length() / 2 - 1;
		int limitLeftExt = position;
		int limitRight = position + temp.length() / 2 + 1;
		int limitRightExt = position + temp.length() - 1;

		// New pals
		String biggestLeft = "";
		String biggestRight = "";

		// String with the temporary pal
		String tempPal = "";

		// Searching the right and left ones
		biggestLeft = searchLeft(p, limitLeft, limitLeftExt);
		biggestRight = searchRight(p, limitRight, limitRightExt);

		// If the pal you found has letters that are part of a bigger pal ignore
		// it
		if (searchLeft(p, limitLeftExt - 1, limitLeftExt).length() > biggestLeft
				.length())
			return temp;
		if (searchRight(p, limitRightExt, limitRightExt + 1).length() > biggestRight
				.length())
			return temp;

		// Resizing the String after the new pals have been removed from it and
		// then find the new pal
		int positionLeft = p.indexOf(biggestLeft);
		int positionRight = (p.substring(limitRight)).indexOf(biggestRight)
				+ limitRight;
		if (biggestRight.length() >= 2 && biggestLeft.length() >= 2)
			temp = findBestPal(p.substring(positionLeft + biggestLeft.length(),
					positionRight), false);

		if (temp.length() > 0) {
			return temp;
		}
		return biggestRight;

	}

	private static String searchRight(String p, int limitRight,
			int limitRightExt) {

		String biggestRight = "";

		for (int limitPrinc = limitRight; limitPrinc <= limitRightExt; limitPrinc++) {
			for (int limitSec = limitPrinc + 1; limitSec < p.length(); limitSec++) {
				String pal = p.substring(limitPrinc, limitSec + 1);
				if (isPalindrome(pal) && pal.length() > biggestRight.length())
					biggestRight = pal;
			}
		}
		return biggestRight;
	}

	private static String searchLeft(String p, int limitLeft, int limitLeftExt) {

		String biggestLeft = "";

		for (int limitPrinc = limitLeft; limitPrinc >= limitLeftExt; limitPrinc--) {
			for (int limitSec = limitPrinc - 1; limitSec > 0; limitSec--) {
				String pal = p.substring(limitSec, limitPrinc + 1);
				if (isPalindrome(pal) && pal.length() > biggestLeft.length())
					biggestLeft = pal;
			}
		}
		return biggestLeft;
	}

} // public class pal

[Belisarius]

Wow, this is a hard one, what with the need to find the fewest palindromes.

You've obviously solved #3 already on paper or something; what is the program doing wrong? What should the answer be and what is the program spitting out?

[HighterDK]

I really don't know where it's going wrong. I have some input files given to me and their correct output. Everything goes well on all of then, even on one with 2000 letters. But for some reason, on number 3 my program is splitting something wrong somewhere and I get 85 parts as answer instead of 84.

[Belisarius]

Is it given that #3 has 84 parts instead of 85? I was hoping for output from the program and the correct output; it makes debugging much easier.

[HighterDK]

This is the program output:

Test 1
80

Test 2
77

Test 3
85

Test 4
73

This is the correct output:

Test 1
80

Test 2
77

Test 3
84

Test 4
73

Format:
Test X
test_result
==> skip line
Test X+1
test_result
==> skip line
Test X+2
test_result

[Belisarius]

I meant you don't actually have the list of palindromes that can be compared against a list from the program?

[HighterDK]

Oh sorry, I don't. I was only given the number of parts each string has.

[Belisarius]

This reminds me of a program I once wrote in a programming contest that had the requirement of finding the fewest number of coins with which to make change. The problem was that you couldn't just use a greedy algorithm, as there were occasions that using the largest coins first actually forced you into a situation where you'd end up using more coins than necessary.

As I've understood your program, you find the largest possible palindrome, and assume it's part of the solution. It's a good guess, but unfortunantly wrong. I think that's why your getting 85 instead of 84; the way you're doing it is fundamentally flawed.

This might be an NP-Complete problem, I'm willing to bet some of the older coders could tell us. If this is a programming assignment, it's a tough one.

[HighterDK]

Yes, I know that find the biggest palidrome simple won't work and that's why I made a method to deal with it(optimizePal). Basically this method checks if there aren't any other palidromes around the one you have that might use parts of it. So if the palidrome was geaaeg this method would check if there aren't any palidrome that might use ge or eg as a part of it. If there are, like in ggeaaegcg, the palidrome will be resized so it doesn't end up destroing the other two (on the example above it would be resized to eaae).

And yes, it was a programming assignment.

[Belisarius]

Ah, I see. Forgive me for not noticing that earlier; I assumed the method did something else.

The problem lies in that I don't think there's a clever way to solve this problem; you need to check *all* combinations, and then choose the smallest one. You unfortunantly found a clever way to find a a solution has a higher probability of being correct, but not a way to find the correct solution.

As I mentioned earlier, I think this is an NP-Complete problem, but I lack the background in discrete mathematics to say it with authority.

The good news is you can stop trying to be clever and do it the brute force way. If you do come up with a better solution, let me know. It's an interesting problem.