Combinaciones únicas de paneles con bloques - Código en Java

Question

Tengo un proyecto en el que tengo que crear un panel a partir de bloques que son 3x1 y 4.5x1. Para la integridad estructural, los espacios entre los bloques no deben alinearse en filas adyacentes. Tengo que calcular todas las combinaciones posibles. Algunos ejemplos son un panel de 7.5x1 con 2 soluciones posibles, un panel de 7.5x2 con 2 soluciones posibles, un panel de 12x3 con 4 formas posibles y un formato de 27x5 con 7958 formas posibles. Mi problema es que cuando me meto en los anchos más altos, obtengo más soluciones, entonces debería. Creo que esto tiene que ver con que existe la posibilidad de que obtenga tablas duplicadas, pero no puedo ver dónde está sucediendo ni cómo solucionarlo. Cualquier ayuda sería muy apreciada. El código sigue a continuación.

import java.util.ArrayList; 
import java.util.List; 

import puzzle.Row; 

public class panel { 
/** 
* This program will return the number of unique tables that for structural  integrity don't have blocks that line up 
* in adjacent rows. The width is to be between 3 and 48 and the height between 1 and 10. The width 
* should also be a multiple of 0.5. 
* 
* @param width, height 
* @return totalTables 
*/ 
public static void main(String[] args) { 
    int width = 0; 
    int height = 0; 

    // Check to make sure that two arguments were passed. 
    if (args.length != 2) { 
     System.out.println("Please enter both a height and a width."); 
     System.exit(1); 
    } else { 
     // Check that a data type of double was entered. 
     if ((args[0].matches("^[0-9]+(\\.[0-9]+)?$")) && 
       (Double.valueOf(args[0].trim()).doubleValue() >= 3.0) && 
       (Double.valueOf(args[0].trim()).doubleValue() <= 48.0) && 
       (Double.valueOf(args[0].trim()).doubleValue()) % 0.5 == 0) { 
      width = (int) (Double.valueOf(args[0].trim()).doubleValue() * 2); // Double the width so that we are working with an integer. 
     } else { 
      System.out.println("Please enter a number for your width that is between 3 and 48 and divisable by 0.5."); 
      System.exit(1); 
     } 
     // Check that a data type of integer was entered. 
     if ((args[1].matches("^[0-9]+$")) && (Integer.valueOf(args[1]) >= 1) && (Integer.valueOf(args[1]) <= 10)) { 
      height = Integer.valueOf(args[1].trim()).intValue(); 
     } else { 
      System.out.println("Please enter an integer for your height that is between 1 and 10."); 
      System.exit(1); 
     } 

     List<Row> allRows = new ArrayList<Row>(); // Holds all the possible rows and needed information 
     findAllRows(width, 0, 0, allRows); 
     findMatches(allRows); 
     long totalTables = findUniqueTables(allRows, height); 
     System.out.println(totalTables); 
    } 
} 

/** 
* Recursively calculates all possible row combinations for supplied width. 
* Row configuration is stored in binary format with 1 indicating gaps. Each bit is 
* represented by 3 inches. The bits 1, 2, nth are dropped as they are not needed. 
* 
* i.e. width of 12 would produce 
* width = 12 * 2 = 24 
* 
* Bricks    Binary    Stored Binary Decimal Value 
* 6 x 6 x 6 x 6  0 1 0 1 0 1 0 1  1 0 1 0 1  21 
* 9 x 9 x 6   0 0 1 0 0 1 0 1  0 1 0 0 1  9 
* 9 x 6 x 9   0 0 1 0 1 0 0 1  0 1 0 1 0  10 
* 6 x 9 x 9   0 1 0 0 1 0 0 1  1 0 0 1 0  18 
*/ 

public static void findAllRows(int width, int currLen, int rowConfig, List<Row> root) { 
    if (currLen + 6 == width) { 
     root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row. 
     return; 
    } else if (currLen + 9 == width) { 
     rowConfig = rowConfig << 1; 
     root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row. 
     return; 
    } else if (currLen + 6 > width) { 
     return; // Current configuration is longer than the width is allowed. Do not add. 
    } else { 
     int nextConfig = (rowConfig << 2) + 1; // 
     findAllRows(width, currLen + 6, nextConfig, root); 

     nextConfig = (rowConfig << 3) + 1; 
     findAllRows(width, currLen + 9, nextConfig, root); 
    } 
    return; 
} 

/** 
* Finds all possible row matches for the given row that do not have gaps that line up. 
*/ 
public static void findMatches(List<Row> rows) { 
    for (Row row : rows) { 
     for (Row rowC : rows) { 
      if (matchesBelow(row.getGaps(), rowC.getGaps())) { 
       row.addChilcRows(rowC.getGaps()); 
      } 
     } 
    } 
} 

/** 
* Does a bitwise AND to see if there are any gaps that line up. If there are no gaps then 
* the resulting AND should equal to 0. 
*/ 
public static boolean matchesBelow(int row, int rows) { 
    if ((row & rows) == 0) { 
     return true; 
    } else { 
     return false; 
    } 
} 

/** 
* Finds all the unique tables and returns the count. 
*/ 
public static long findUniqueTables(List<Row> allRows, int height) { 
    long tableCount = 0; 
    for (Row row : allRows) { 
     tableCount += findTables(row, height); 
    } 
    return tableCount; 
} 


/** 
* This makes all possible tables. 
*/ 
public static long findTables(Row row, int tableHeight) { 
    long count; 
    if (tableHeight == 1) { 
     return 1; 
    } else { 
     count = 0; 
     for (int i = 0; i < row.getChildRowsSize(row); i++) { 
      count += findTables(row, tableHeight -1); 
     } 
    } 
    return count; 
} 
} 

Y mi puzzle.Row clase.

package puzzle; 

import java.util.ArrayList; 
import java.util.List; 

public class Row { 
int gaps; 
int width; 
List<Long> potChildRows = new ArrayList<Long>(); 

public Row(int width, int gaps) { 
    this.gaps = gaps; 
    this.width = width; 
} 

public int getGaps() { 
    return this.gaps; 
} 

public int getWidth() { 
    return this.width; 
} 

public long getChildRowsSize(Row row) { 
    return row.potChildRows.size(); 
} 

public void addChilcRows(long row) { 
    this.potChildRows.add(row); 
} 
} 

Answer 1

Creo que acabo de resolver la tarea. A pesar de que han pasado dos meses desde que se hizo la pregunta, pensé que parecía un problema divertido de resolver, así que le di una oportunidad. No deseo publicar mi código debido a la etiqueta "Tarea" (incluso después de 2 meses), así que simplemente describiré mi enfoque. Utilicé Python, pero intentaré traducir cualquier terminología en Java.

En primer lugar, me parece que está realizando un seguimiento de más datos de los que necesita. Acabo de mantener un ArrayList de dobles de modo que para cualquier doble i, i se refería a un bloque ix1. La lista se ordenó de manera que row[0] fuera el bloque más a la izquierda y row[row.length-1] fuera el bloque más a la derecha. Por ejemplo, [3, 3, 4.5] se refiere a una fila de longitud 10.5 usando, de izquierda a derecha, un bloque de 3x1, otro bloque de 3x1 y un bloque de 4.5x1. Usando esta estructura simple puedo visualizar fácilmente mi configuración. Mi longitud de fila es tan fácil como agregar todos los elementos (es decir, 3 + 3 + 4.5 = 10.5). Mis espacios son tan fáciles como mantener un total acumulado mientras recorro mi lista (es decir, mis espacios son 3 y 3 + 3 = 6). Usando este tipo de datos más simple, puedes simplificar enormemente tu código.

Además, me pareció útil pensar en el problema como un Depth-First Search modificado. Usando DFS y dado un árbol binario, comenzando desde la raíz primero intenta ir a la izquierda. Luego tratas de ir a la izquierda pero a uno el último nodo. Y así. En lugar de "izquierda" y "derecha", piense "3" y "4.5", donde el valor del nodo es el ancho y deja de atravesar el árbol una vez que el ancho sea mayor que el ancho deseado, width. Si encuentra un nodo con un valor de exactamente width, esa ruta ahora es una fila posible, recuérdelo. En otras palabras, construye sus filas de izquierda a derecha primero probando N bloques de 3x1 (por ejemplo, width + 2.5 >= N*3 >= width). Luego intenta (N-1) bloques de 3x1 y 1 bloque de 4x1 (el 4x1 es el derecho). Luego (N-2) 3x1s, uno 4x1 y uno más 3x1. Y así. Sin cambios de bits, ninguna variable rowConfig, solo una ArrayList de anchos de bloque. Además, como sistemáticamente viajó por cada ruta (es decir, probó cada combinación) una vez y solo una vez, sabe que ha probado todas las combinaciones y sabe que no hay duplicados.

Ahora, construyendo su muro. Esto también se puede tratar como un DFS modificado. Imagine un árbol n-aria donde n es igual al número de posibles filas de ancho width. Usando el mismo enfoque sistemático, pruebe cada ruta hasta que tenga una pared de altura height (ya que cada fila es de altura 1). Pero recuerda, solo quieres atravesar un camino si ninguno de los huecos es ajustable. Intenta construir la pared una fila a la vez, de abajo hacia arriba. Al agregar una nueva fila a la parte superior de la pared si y solo si ninguno de sus huecos es adherente a los huecos en la fila superior, puede confiar en que su muro parcial siempre es válido. Allí, una vez que tocas height, sabes que tienes un muro válido. Registre la ruta y continúe hasta que no queden más rutas válidas para explorar.

Pido disculpas por no responder mientras todavía estaba haciendo su tarea.Me interesaría saber cómo su solución final difería de la mía.