x
COSC 1P03 Assignment 4 (I'd put a recursion pun here, but... I'm tired) Objective: To devise, and implement, a recursive solution. This time, with backtracking! Background: It's time to move to bigger and better things! And of course, the most common factor when considering a big move is... the crippling instinct to hoard everything you've ever accumulated, and haul all your worthless crap over to the new home! Thankfully, everything's already boxed-up, though the boxen are of different dimensions. The moving van is available in different dimensions and geometries, and you need to be able to neatly fit everything in. Of course, not every combination of boxen and moving vans will work out, even if the maximum theoretical volume exceeds the total volume to stow (since hacking boxen in half with a chainsaw is frowned upon). There are many algorithms for packing the boxen, but we'll be using a single specific mandatory one. Before we get to the algorithm, let's cover the requirements: • Each box will have a width and a height ◦ These are expressed in feet ◦ You may not tip over the box, or rotate it (that would damage the contents) • Every box will be exactly one foot deep ◦ Since you can't rotate, this just means you're placing boxen in discrete layers • All boxen must be placed stably: ◦ The bottom-most boxen must be right on the floor of the van ◦ Boxen may stack on boxen, but only if completely supported • When such solutions exist, you must always prefer the furthest-back layer, and the leftmost side ◦ You can just consider 'layer zero' to be the furthest-back • A solution only exists if all boxen can be placed • You'll encounter the most-treasured boxen first, so you can't consider looking for a place for later boxen until the current one's placed somewhere ◦ Yes, this can technically force a 'fail' state even if it wouldn't have otherwise been possible You'll be getting the data for both the van and the boxen from a single text file. • The text file will either be onelayer_tricky.txt or something specified as a command- line argument • The first line is the dimensions of the van: depth height width ◦ These three are tab-separated • The second line is the number of boxen • And then, for however many boxen: height width ◦ Again, tab-separated ◦ You don't need to worry about the depth of a box, since it's always 1 foot On the next page, we'll walk through an example with only a single depth, to clarify the algorithm. This perspective is equivalent to 'looking into the van'. We first try to place box 0: • It needs to be 'on the ground', and we're prioritizing the left where possible • This means there's only one place to try Next will be box 1: • It violates two constraints in the first possible x-position • The same goes for the second position • At the third possible position, it fits! For box 2, it's easy to see what'll happen: • It'll try at x:0, x:1, x:2, x:3, x:4, and then find a place at x:5 For box 3, it'll just go at the leftmost position. Before we get any farther, a couple notes: • We don't need to actually 'place' the boxen, per se. We only need to keep track of the current height at each x-coordinate (for each layer of depth) • We haven't addressed the major catch: backtracking Backtracking? Consider the following: If we were to only try placing them, as-is, we'd place 0 at the left, 1 on top of that, and 2 starting at x:2 (Yes, I know it's missing a single line: indicating 4 boxes. Oops) This leaves us with: Box 3 has nowhere to go, but only because of how box 1 was placed. • We can't move box 1 onto box 2 • We can unwind what we've done, and decide to put box 1 at position x:2 Now, Box 2 can go on top of Box 1, and Box 3 has plenty of space at the left: Of course, obviously, it isn't the end result that matters, but rather the algorithm that got us here. We have some obvious trivial cases: • There are no more boxen to place: success • The current x:position (or x:position, plus offset for the width of the box) is out of bounds: fail • We're at a depth (more on this later) out of bounds: fail We need to solve each 'frame' of the problem at some position (depth and x), for some box number. We start by solving for box 0, at 0,0. • If we're out of boxen to place, we've solved it! • If we've 'gone too deep', we've failed the current subproblem! • If we're too high in the x:position, we need to try solving for the subproblem of the same box number, but starting from the left at the next depth in ◦ The result of that will dictate whether or not this whole subproblem can be solved • We check if the current box can fit 'here': ◦ We check if its height fits ◦ We check the adjacent blocks (according to the box's width), to ensure their 'floor height' matches here ◦ If it doesn't fit here, we need to try solving for the subproblem of the same box number, but the next x:position in ▪ The result of that will dictate whether or not this entire subproblem can be solved • Since we know the box fits here, we temporarily assume it goes here ◦ This includes setting it down (increasing the perceived height at the position(s) of the box) • We now see if we can solve the subproblem of trying to place the next box number at the starting point ◦ If we can, then we've solved it ◦ If we can't, then we need to: ▪ 'Pick the current box back up again' (i.e. decrease the heights back down) ▪ Let the result of solving the subproblem for the current box at the next position dictate whether or not this subproblem is solveable You might notice two things: • Adding 'depth' just means one extra trivial case, and one extra case for recursion • Even at its most complicated, this only needs two-dimensional arrays, since the 'value' can be the height at a given spot Basic requirements: It seems pretty complicated, eh? I swear it isn't, once you write it. (e.g. the recursive function in my sample solution was only 20 lines) Anyhoo, here are the requirements: • You must load the problem from a text file • If a filename is provided as a command-line argument, use that ◦ Otherwise, assume onelayer_tricky.txt • It must recursively solve this problem, according to the algorithm above ◦ This is the 'recursion' assignment. Do it right, or don't do it • If the problem is not solveable, indicate as such • If the problem is solveable, show the heights at each position of the van Submission: Bundle up your solution, data files, and a sample execution (pretty much everything the marker needs to easily grade your work) into a .zip file, and submit it through Sakai. Some reminders: • .zip means .zip. Use a rar or 7z, and you'll get a zero • You're not writing your solution in one IDE and then converting to Dr. Java ◦ Unless you've made prior arrangements, you're using only Dr. Java, or you're getting zero