Thread: Intro

Hi all,

This is a test post to see if it will let me do it. I've tried posting a real question numerous times but it said post denied every time. I'm a newbie to Java and need some help finishing class methods.

--- Update ---

Well...of course it worked this time.....here is what I was going to post:

I have attempted to solve ACM-ICPC problem #5950. The instructions for it are as such:
Input

Input to this program may be supplied via standard input or via a text file named on the command line.

Input consists of silhouettes of one or more pieces and a silhouette of the hole in the window. A silhouette is presented as an ASCII graphic composed of blanks and a specific non-blank character (as described further below). A blank character indicates locations where no glass exists. The non-blank characters indicate the presence of glass (or, in the case of the hole's silhouette, a location where we wish to place some glass).

Each silhouette consists of 1 to 8 lines, each line containing 1 to 8 characters. Each line of a silhouette will have at least one non-blank character. Each silhouette is presented in a separate sequence of lines.

The first piece is rendered using the character `A', then the next piece with a `B', and so on. There will be at most 8 pieces. After the final piece, the silhouette of the hole is rendered using the character `%'. The transition from one silhouette to the next is signaled by the change of character. The end of the hole's silhouette is signaled by the end of input.

Output

If an arrangement of the pieces that exactly and completely fills the hole’s silhouette is possible, print that silhouette filled in with the alphabetic characters indicating the positioning of the pieces. (If more than one arrangement is possible, you may show any one of them.) The filled-in silhouette should be printed as far to the left as possible without distorting the shape of the silhouette. There should be no blanks spaces at the ends of the output lines.

If no such arrangement is possible, print a line consisting of the phrase "The window cannot be repaired." (including the closing period).

Examples

Given the input

A
AAA
A
A
AAA
B
BBB
B
B
BB
B
CC
C
%
%%%%
%%%%
%%%%
%%%%
%%%%

the output would be

B
ABBB
AAAB
ACCB
ACBB
AAAB

Given the input

A
B
C
%%
%%

the output would be

The window cannot be repaired.

Notes

The main() function for this program is found in the class StainedGlass.Reconstructor.
The main algorithm used by the Reconstructor class' solve(...) function is an example of backtracking. You don't need to know that, as CS361 is not a pre-requisite for this course, but just in case you were curious...
Backtracking is a solution technique of "last resort". It tends to run in time that grows exponentially with the size ofthe input set, which is why this problem is limited to no more than 8 fairly small pieces of glass. Even at that, the solution needs some heuristics ("tricks") to improve the performance by not wasting time on partial solutions that are likely to pay off in the long run.

The Hole and Glass classes are actually similar in some respects. You may be able to get some insight into how to implement the Hole functions by studying the Glass class.
I have suggested a reasonable data structure for the Hole, and provided the input code for it. You may change that data structure if you like.
I have attempted to finish the Hole.java file. I was given the Reconstructor / Glass files.

Reconstructor

package StainedGlass;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
 
 
public class Reconstructor {
 
 
    private Glass[] pieces;
    private Hole window;
    private boolean solved;
 
 
 
 
 
    public  Reconstructor(BufferedReader input) throws IOException
    {
        solved = false;
 
        readSilhouettes(input);
    }
 
 
    private void readSilhouettes(BufferedReader input) {
        final int MAXPIECES = 8;  // At most 8 pieces
        final int MAXLINES = 8*(MAXPIECES+1);  // At most 8 pieces plus a hole, each at most 8 lines long
 
        String[] lines = new String[MAXLINES];
        int[] startingLine = new int[MAXPIECES+1];
        Arrays.fill(startingLine, -1);
 
        int numLines = 0;
        try {
            while (numLines < MAXLINES) {
                lines[numLines] = input.readLine();
                if (lines[numLines] == null) // after EOF
                    break;
                ++numLines;
            }
        } catch (IOException e)
        {
            // do nothing
        }
        char lastDescriptor = 'A';
        int holeStart = 0;
        for (int i = 0; i < numLines; ++i) {
            char c = findNonBlank(lines[i]);
            if (c == '%') {
                holeStart = i;
                break;
            } else {
                lastDescriptor = c;
                if (startingLine[c-'A'] < 0)
                    startingLine[c-'A'] = i;
            }
        }
        int numPieces = lastDescriptor - 'A' + 1;
        startingLine[numPieces] = holeStart;
        pieces = new Glass[numPieces];
        for (char piece = 'A'; piece <= lastDescriptor; ++piece) {
            int pieceNum = piece - 'A';
            String[] pieceLines = Arrays.copyOfRange(lines, startingLine[pieceNum], startingLine[pieceNum+1]);
            pieces[pieceNum] = new Glass(pieceLines);
        }
        String[] holeLines = Arrays.copyOfRange(lines, holeStart, numLines);
        window = new Hole(holeLines);
    }
 
    /**
     * Find the first non-blank character in a string
     * @param string
     * @return the first non-blank character or ' ' if all are blank
     */
    private char findNonBlank(String string) {
        for (int i = 0; i < string.length(); ++i)
            if (string.charAt(i) != ' ')
                return string.charAt(i);
        return ' ';
    }
 
 
    private void printSolution() {
        if (solved)
            System.out.print (window.toString());
        else
            System.out.println ("The window cannot be repaired.");
    }
 
    /**
     * Attempt to place a piece in the window, then recursively solve the remaining part of the puzzle.
     * Continue until solved or determined to be unsolvable.
     * 
     * @param pieceNum piece to place in the window
     */
    private void solve(int pieceNum) {
        if (pieceNum >= pieces.length) {
            solved = window.filled();
        } else {
            Glass p = pieces[pieceNum];
            // System.err.println ("Attempting to insert\n" + p);
            tryToInsert (p, pieceNum);
            if (!solved) {
                Glass p2 = p.flip();
                // System.err.println ("Attempting to insert flipped\n" + p2);
                tryToInsert (p2, pieceNum);
            }
        }
    }
 
    public void tryToInsert (Glass p, int pieceNum)
    {
        for (int xoffset = 0; xoffset <= window.getWidth() - p.getWidth() && !solved; ++xoffset)
            for (int yoffset = 0; yoffset <= window.getHeight() - p.getHeight() && !solved; ++yoffset)
                if (window.fits(p, xoffset, yoffset))
                {
                    window.insert(p, xoffset, yoffset);
                    // System.err.println ("Inserted into window\n" + window);
                    solve (pieceNum+1);
                    if (solved)
                        return;
                    window.remove(p);
                    // System.err.println ("Removed piece from window\n" + window);
                }
    }
 
 
    private class GlassCompare implements Comparator<Glass> {
 
        @Override
        public int compare(Glass g1, Glass g2) {
            return g2.area() - g1.area();
        }
 
    }
 
 
    /**
     * Attempt to solve the puzzle.
     * 
     * @param pieceNum piece to place in the window
     */
    private void solve() {
        int total = 0;
        for (int i = 0; i < pieces.length; ++i)
            total += pieces[i].area();
        if (total == window.area()) {
            // The areas match, so there's at least a possibility that the 
            // glass pieces can fill up the window. 
 
            // Sort the pieces so that we try the largest ones first - this speeds things
            // up on average because smaller pieces are more likely to "fit" temporarily into
            // incorrect positions, which can lead us to explore a lot of dead ends.
            Arrays.sort(pieces, new GlassCompare());
 
            // Start solving beginning with piece 0
            solve(0);
        }
    }
 
 
 
    public static void main (String[] argv) throws FileNotFoundException
    {
        BufferedReader inScan = null;
        if (argv.length > 0) {
            FileReader infile = new FileReader("test0.txt");
            inScan = new BufferedReader(infile);
        } else {
            inScan = new BufferedReader(new InputStreamReader(System.in));
        }
 
        try {
            Reconstructor cw = new Reconstructor(inScan);
            cw.solve();
            cw.printSolution();
        } catch (IOException e) {
            System.err.println ("Input format error: " + e);
        }
    }
 
 
}

Glass

/**
 * 
 */
package StainedGlass;
 
 
/**
 * A single piece of stained glass.
 * 
 * @author zeil
 *
 */
public class Glass {
    private int width;
    private int height;
    private char descriptor;
    private char[][] chars;
 
    /**
     * Initializes a piece of glass given a representation in lines of text.
     * 
     * For example; given lines == {"  W", " WW", "  W"}, we would get a Glass piece
     * with width 2, height 3, and a descriptor of 'W', such that charAt(0,0) == ' '
     * and charAt(0,1) == 'W' 
     * 
     * @param text  array of strings. Each represents a single line across the glass piece. Blanks indicate
     *     horizontal positions where no glass is present. A letter indicates a position where class of a "color"
     *     denoted by that letter can be found.
     */
    public Glass (String[] text)
    {
        width = 0;
        height = text.length;
        int leftOffset = Integer.MAX_VALUE;
 
        for (int i = 0; i < height; ++i) {
            for (int w = 0; w < text[i].length(); ++w) {
                if (text[i].charAt(w) != ' ') {
                    descriptor = text[i].charAt(w);
                    width = Math.max(width, w+1);
                    leftOffset = Math.min(leftOffset, w);
                }
            }
        }
        width -= leftOffset;
 
        chars = new char[height][width];
        for (int h = 0; h < height; ++h) {
            for (int w = leftOffset; w < text[h].length(); ++w)
                chars[h][w-leftOffset] = text[h].charAt(w);
            for (int w = text[h].length() - leftOffset; w < width; ++w)
                chars[h][w] = ' ';
        }
 
    } 
 
 
 
	/**
     * Returns the character indicating the presence or absence of glass at position
     * (w,h) in this piece. 
     * 
     * If w or h are out of bounds, returns ' ' (no glass).
     *  
     * @param x x position (starts at 0, increases moving to the right)
     * @param y y position (starts at 0, increases moving down the glass)
     * @return descriptor if glass is present at that location, ' ' otherwise
     */
    public char charAt(int x, int y) {
        if (y < 0 || y >= height)
            return ' ';
        if (x < 0 || x >= width)
            return ' ';
        return chars[y][x];
    }
 
 
    /**
     * @return the width
     */
    public int getWidth() {
        return width;
    }
 
    /**
     * @return the height
     */
    public int getHeight() {
        return height;
    }
 
    /**
     * @return the descriptor character indicating the presence of glass
     */
    public char getDescriptor() {
        return descriptor;
    }
 
 
 
 
 
    /**
     * Produces a new piece of glass by flipping this one around its vertical axis;
     * E.g.,  AAA           AAA
     *          A   becomes A
     *         A              A
     */
    public Glass flip()
    {
        String[] flippedLines = new String[height];
        for (int y = 0; y < height; ++y) {
            StringBuffer buf = new StringBuffer();
            for (int x = width-1; x >= 0; --x)
                buf.append(chars[y][x]);
            flippedLines[y] = buf.toString();
        }
        return new Glass(flippedLines);
    }
 
 
    /**
     * The area is the total number of positions occupied by colored glass
     * 
     * @return area of this piece
     */
     public int area()
    {
         int total = 0;
         for (int h = 0; h < height; ++h)
             for (int w = 0; w < width; ++w)
                 if (chars[h][w] != ' ')
                     ++total;
         return total;
    }
 
 
    public String toString()
    {
        StringBuffer buf = new StringBuffer();
        for (int h = 0; h < height; ++h) {
            int w = width-1;
            while (w >= 0 && chars[h][w] == ' ')
                --w;
            for (int x = 0; x <= w; ++x)
                buf.append(chars[h][x]); 
            buf.append('\n');
        }
        return buf.toString();
    }
 
    public boolean equals (Object o)
    {
        try {
            Glass g = (Glass)o;
            if (width != g.width || height != g.height || descriptor != g.descriptor) {
                return false;
            }
            for (int h = 0; h < height; ++h)
                for (int w = 0; w < width; ++w)
                    if (charAt(w,h) != g.charAt(w,h))
                        return false;
            return true;        
        } catch (Exception e) {
            return false;
        }
    }
 
 
 
 
}

Hole - The hint I was given was that most of the methods in this file are really similar to Glass.java. I've done my best to finish these methods. It compiles but doesn't work properly when I test it with input I get the same result "The window cannot be repaired." I have been testing with the examples provided in the link above as well as my own.

A
%

AA
%%

AA
A
%%
%

AA
BB
%%
%%

etc. Can you guys help me pick out what I did wrong in Hole.java? Keep in mind this is the first time I've seen Java :/

/**
 * 
 */
package StainedGlass;
 
public class Hole {
	private int width;
	private int height;
	private char descriptor;
	private char[][] chars;
 
	/**
	 * Initializes a hole given a representation in lines of text.
	 * 
	 * For example; given lines == {"  %", " %%", "  %"}, we would get a Hole
	 * with width 2, height 3, such that charAt(0,0) == ' ' and charAt(0,1) ==
	 * '%'
	 * 
	 * @param text
	 *            array of strings. Each represents a single line across the
	 *            glass piece. Blanks indicate horizontal positions where no
	 *            glass is present. A '%' indicates a position where glass could
	 *            be placed. A letter indicates a position where glass has been
	 *            placed.
	 */
	public Hole(String[] text) // I probably don't need the descriptor...review
								// this hunch before submission
	{
		width = 0;
		height = text.length;
		int leftOffset = Integer.MAX_VALUE;
 
		for (int i = 0; i < height; ++i) {
			for (int w = 0; w < text[i].length(); ++w) {
				if (text[i].charAt(w) != ' ') {
					descriptor = text[i].charAt(w);
					width = Math.max(width, w + 1);
					leftOffset = Math.min(leftOffset, w);
				}
			}
		}
		width -= leftOffset;
 
		chars = new char[height][width];
		for (int h = 0; h < height; ++h) {
			for (int w = leftOffset; w < text[h].length(); ++w)
				chars[h][w - leftOffset] = text[h].charAt(w);
			for (int w = text[h].length() - leftOffset; w < width; ++w)
				chars[h][w] = ' ';
		}
	}
 
	/**
	 * Returns the character indicating the presence or absence of glass at
	 * position (w,h) in this piece.
	 * 
	 * If w or h are out of bounds, returns ' ' (no glass).
	 * 
	 * @param x
	 *            x position (starts at 0, increases moving to the right)
	 * @param y
	 *            y position (starts at 0, increases moving down the glass)
	 * @return descriptor if glass is present at that location, ' ' otherwise
	 */
	public char charAt(int x, int y) {
		// your code here
		if (y < 0 || y >= height)
			return ' ';
		if (x < 0 || x >= width)
			return ' ';
		return chars[y][x];
	}
 
	/**
	 * @return the width
	 */
	public int getWidth() {
		// your code here
		return width;
	}
 
	/**
	 * @return the height
	 */
	public int getHeight() {
		// your code here
		return height;
	}
 
	/**
	 * Determines whether a given piece of glass would fit into the empty spaces
	 * of this hole if the piece were shifted over by (xoffset,yoffset) from the
	 * upper left corner of the hole.
	 * 
	 * @param g
	 *            a piece of glass
	 * @param xoffset
	 *            horizontal offset
	 * @param yoffset
	 *            vertical offset
	 * @return true if the glass could be placed in empty spaces in this hole
	 * 
	 */
	public boolean fits(Glass g, int xoffset, int yoffset) {
		// your code here
		try {
			for (xoffset = 0; xoffset <= width; ++xoffset)
				for (yoffset = 0; yoffset <= height; ++yoffset)
					if (g.area() == xoffset)
						return true;
			return false;
		} catch (Exception e) {
			return false;
		}
	}
 
	/**
	 * Inserts a piece of glass into the empty spaces of this hole, shifting the
	 * piece over by (xoffset,yoffset) from the upper left corner of the hole.
	 * '%' empty spots in this hole are filled with the descriptor for the
	 * glass.
	 * 
	 * Pre-requisite: fits(g, xoffset, yoffset)
	 * 
	 * @param g
	 *            a piece of glass
	 * @param xoffset
	 *            horizontal offset
	 * @param yoffset
	 *            vertical offset
	 * 
	 */
	@SuppressWarnings("null")
	public void insert(Glass g, int xoffset, int yoffset) {
		// your code here
		int[] OS = null;
		int key;
 
			for(xoffset = 1; xoffset <= width; ++xoffset)
			{
				key = OS[xoffset];
				for (yoffset = 1; yoffset <= height; --yoffset)
				{
					OS[yoffset+1] = OS[yoffset];
				}
				OS[yoffset+1] = key;
			}
 
 
	}
 
	/**
	 * Removes a piece of glass previously fitted into this hole, All spaces in
	 * this hole currently occupied by descriptors for g are made empty
	 * (replaced by '%')
	 * 
	 * @param g
	 *            a piece of glass
	 * @return true if the glass could be placed in empty spaces in this hole
	 * 
	 */
	public void remove(Glass p) {
		// your code here
		p = null;
	}
 
	/**
	 * Is the hole completely filled?
	 * 
	 * @return true if all empty spaces have been filled with glass
	 */
	public boolean filled() {
		// your code here
		try {
			for (int h = 0; h < height; ++h)
				for (int w = 0; w < width; ++w)
					if (charAt(w, h) == ' ') // If position is empty return
												// false
						return false;
			return true; // Otherwise true
		} catch (Exception e) {
			return false; // Exception thrown return false
		}
	}
 
	/**
	 * The area is the total number of positions that are occupied by colored
	 * glass and that are empty and could be so filled.
	 * 
	 * @return area of this piece
	 */
	public int area() // Mostly the same as Glass.java (just need to account for
						// empty as well
	{
		// your code here
		int total = 0;
		for (int h = 0; h < height; ++h)
			for (int w = 0; w < width; ++w)
				if (chars[h][w] != ' ' || chars[h][w] == ' ')
					++total;
		return total;
	}
 
	public String toString() // Should be the same as in Glass.java
	{
		// your code here
		StringBuffer buf = new StringBuffer();
		for (int h = 0; h < height; ++h) {
			int w = width - 1;
			while (w >= 0 && chars[h][w] == ' ')
				--w;
			for (int x = 0; x <= w; ++x)
				buf.append(chars[h][x]);
			buf.append('\n');
		}
		return buf.toString();
	}
 
	public boolean equals(Object o) // Should be the same as in Glass.java, just
									// needed to change Glass
									// to Hole
	{
		// your code here
		try {
			Hole g = (Hole) o;
			if (width != g.width || height != g.height
					|| descriptor != g.descriptor) {
				return false;
			}
			for (int h = 0; h < height; ++h)
				for (int w = 0; w < width; ++w)
					if (charAt(w, h) != g.charAt(w, h))
						return false;
			return true;
		} catch (Exception e) {
			return false;
		}
	}
}

Edit: Posted before the OP updated the post with the request for help.

Welcome! It worked here, so try a regular post again. If you're still getting errors, come back here to post them and ask a mod to help you.

Ok thank you I will try again!