[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1672.0. "A tiling problem from work" by RICKS::LEONARD (Tim Leonard, Cantab) Wed Oct 07 1992 18:29

    I need a solution to this problem for work, and don't see how to analyze
    it.  Unless someone helps out, I'll use simulation to find something
    good enough, and go with that.  Any ideas?
    
Given

  -- a rectangular checkerboard of black, red, and white squares, in which
  -- exactly one square in each row is non-white, and
  -- every red square has a black square somewhere below it in the same column,

find

  -- a placement of rectangular tiles on the checkerboard, such that
  -- every red square is supported (that is, the red square, and each square
     under it in its column down to a black square, is covered by tiles), and
  -- no black square is covered by a tile, and
  -- the cost of the tiles is minimized (a tile costs twice its height, except
     unit-width tiles cost their height).

Note that tiles may overlap, so red and white squares may be multiply covered.

That's the static version.  The dynamic version is:

Given a checkerboard, and a satisfactory placement of tiles, and a new row with
a red square to add to the top of the checkerboard, give an algorithm for
choosing a tile to cover the new red square that minimizes the cost of tiles in
the long run (after many new rows).

T.R	Title	User	Personal Name	Date	Lines
1672.1	first part solved	DESIR::BUCHANAN	The was not found.	`Thu Oct 08 1992 14:26`	29
	Tim, Let's deal with the static version first. Given any tile we can split it up into n tiles of unit height without changing the cost. So without loss of generality, all the tiles in the optimum solution have unit height. So we can reduce the problem to considering a single row. If a row contains a black square, then we cannot tile that square, and the row becomes split into two subrows, we are considered separately. Otherwise, a row may contain 1 or more essential squares (either red or supporting a red above). If there is just one, we tile just that 1 square. If there is more than one essential square, we tile the entire row (might as well). If a subrow contains 0 essential squares, we don't tile it. That's the static version solved. -------------------------------------------------------------------------------- Before tackling the dynamic version, can you tell me: (1) are happy with this solution to the static version? (2) in the dynamic version, can a new row contain a black tile? (3) when a new row is placed, may I only lay I tile? Thanks, Andrew.
1672.2	Sorry --- add another cost	RICKS::LEONARD	Tim Leonard, Cantab	`Thu Oct 08 1992 15:34`	9
	Damn. You've made it clear I left out a cost. Sorry. Each tile in a red square's support also costs one. If a red square is supported by more than one set of tiles, you're free to count only the minimum-cost support. (But in the dynamic version, you must decide what support to use at the time you create support for the new red square.) To answer your questions, a new row may indeed contain a black square, and yes, you're free to add more than one tile at each step.
1672.3	still confused	DESIR::BUCHANAN	The was not found.	`Fri Oct 09 1992 07:05`	15
	> Each tile in a red square's support also costs one. An ambiguity remains. If a tile supports two red squares, do we have to pay once or twice for it. Eg: r r b Suppose we have one tile to cover the top two rows. We pay a basic 1 for a tile of height 2 which is width more than 1. But what do we pay for the red tile support? 1? 2? ?? Andrew.
1672.4	Found a good-enough solution	RICKS::LEONARD	Tim Leonard, Cantab	`Fri Oct 09 1992 12:21`	22
	Well, I've now done the simulation, and found not only another bug in the specification of the problem, but found a solution that (in practice) works so well there's no need to look for an optimal solution. The bug in the specification was that the support of every red square must stop at the top of the red square. (That is, the top tile supporting a red square must cannot extend above the red square.) This constraint comes from the dynamic form of the actual problem, in which you can't put down a tile that extends above the current top of the board. That eliminates the example you used to pose your question. The answer to the question is that you must count a tile each time it is used as a support. The solution that works in practice is to separate ranges that have lots of black squares from ranges that have none (or almost none) after the initial one. In ranges with lots of new black squares, tile with unit-width columns. In ranges with rare black squares, make each tile the width of the whole range. Thanks for giving it your attention. Tim