Buildings made from cubes

Question

In this fastest-code challenge, you are provided with a set of \$n\$ identical blocks and need to determine how many unique buildings can be constructed with them. Buildings must satisfy the following rules:

1. No overhangs - each block must either be on the ground or supported by one or more blocks directly underneath it.
2. All blocks must be aligned to a unit-sized grid.
3. All blocks in a building must be connected to at least one other block by at least one face, and the blocks must form a single connected unit.
4. Buildings are not unique if they can be mapped to another building by reflection or rotation in the X/Y plane.

e.g. These are the same:

5. If a building is rotated between horizontal and vertical, that does result in a different building

e.g. These are different:

A building with two storeys each of two rooms:

A building with one storey containing 4 rooms:

The challenge is to determine how many different house designs are possible using a given number of cubes. Input and output are both a single integer (using any standard method).

Clearly for 1 cube, only 1 design is possible. For 2 cubes, 2 designs are possible (lying down and standing up). For 3 cubes, there are 4 possibilities, and for 4 cubes there are 12 (see images below; please note the colours are just for display to make it easier to see the individual cubes, but don’t have any significance beyond that).

The first 8 terms are:

n  | output
1  | 1
2  | 2
3  | 4
4  | 12
5  | 35
6  | 129
7  | 495
8  | 2101

Draft sequence on OEIS.

This is fastest-code. The winning entry is the one that can determine the number of buildings for the highest value of \$n\$. If more than one answer can calculate the result for the same \$n\$ within 10 minutes, the one that is fastest for that value wins. This will be tested on an 8th generation Core i7 with 16 GB RAM running Ubuntu 19.10. There must therefore be a freely available interpreter or compiler for any code posted. Default loopholes and IO rules apply.

Cube images generated using usecubes.

Sandbox link

Answer 1

JavaScript (Node.js), \$N=10\$ in 4m02s¹

^{1: on an Intel Code i7, 7th Gen}

This only includes some trivial optimizations and is therefore quite inefficient. It does at least confirm the results listed in the challenge.

function build(n) {
  let layer = [],
      cube = new Set,
      count = 0,
      x, y;

  for(y = 0; y < n; y++) {
    for(layer[y] = [], x = 0; x < n; x++) {
      layer[y][x] = 0;
    }
  }

  function fill(k, alignTop) {
    let x, y;

    if(k == 0) {
      if(!cube.has(layer + '')) {
        let transf;

        count++;

        cube.add(layer + '');
        cube.add((transf = rotate(n, layer)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');

        cube.add((transf = mirror(layer)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');
      }
      return;
    }

    let y0;

    for(y0 = 0; !layer[y0].some(v => v); y0++) {}

    for(y = Math.max(0, y0 - 1); y < n; y++) {
      for(x = 0; x < n; x++) {
        if(
          !layer[y][x] && (
            (y && layer[y - 1][x]) ||
            (y < n - 1 && layer[y + 1][x]) ||
            (x && layer[y][x - 1]) ||
            (x < n - 1 && layer[y][x + 1])
          )
        ) {
          for(let i = 1; i <= (alignTop ? k : k - y0 - 1); i++) {
            layer[y][x] = i;
            fill(k - i, alignTop || !y);
            layer[y][x] = 0;
          }
        }
      }
    }
  }

  for(y = 0; y < n; y++) {
    for(let i = 1; i <= n - y; i++) {
      layer[y][0] = i;
      fill(n - i, !y);
      layer[y][0] = 0;
    }
  }

  return count;
}

function rotate(n, layer) {
  let rot = [],
      x, y;

  for(y = 0; y < n; y++) {
    for(rot[y] = [], x = 0; x < n; x++) {
      rot[y][x] = layer[n - x - 1][y];
    }
  }
  return align(rot);
}

function mirror(layer) {
  return align([...layer].reverse());
}

function align(layer) {
  while(!layer[0].some(v => v)) {
    let s = layer.shift();
    layer = [...layer, s];
  }
  while(!layer[0].some((_, y) => layer[y][0])) {
    layer = layer.map(r => {
      return [...r.slice(1), 0];
    });
  }
  return layer;
}

Try it online! (up to \$N=8\$)

Output

N = 1 --> 1
time: 10.352ms
N = 2 --> 2
time: 0.935ms
N = 3 --> 4
time: 0.877ms
N = 4 --> 12
time: 2.530ms
N = 5 --> 35
time: 9.060ms
N = 6 --> 129
time: 33.333ms
N = 7 --> 495
time: 157.160ms
N = 8 --> 2101
time: 1559.707ms
N = 9 --> 9154
time: 18555.900ms
N = 10 --> 41356
time: 242855.989ms

Answer 2

Java 8, \$n=14\$ in 2m31s¹

^{1. Using the AdoptOpenJDK8 distribution, on a 2-core Amber Lake Intel Core i5-based Mac. On an Amazon EC2 m5.xlarge, takes 1m16s.}

This takes an inductive approach where, for each rank, it builds off all the buildings of the previous rank by placing cubes in all legal positions (on top of and next to existing cubes), and then removing buildings that are (possibly transformed) duplicates of other buildings. This means that to enumerate the buildings in a rank, all previous ranks must be also be computed. Both compute time and memory are constrained resources — this algorithm relies on keeping millions of Building objects in memory — so I've had a hard time computing beyond \$n=14\$ on my machine even without the 10 minute time limit.

This solution includes a parallel-Stream-based approach (which can be enabled with the parallel JVM system property) which is faster on a multi-core system but also more memory-hungry. This approach was used for the timing results above. The non-parallel approach takes almost twice as long to count \$n=14\$ but is able to do so using only a third of the memory.

Garbage collector settings and tuning can have a significant impact on the runtime and ability of the process to complete. I've also tested with OpenJDK 13, but for whatever reason have seen the best results on 8 so far.

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public final class Building {
    /**
     * A flattened two-dimensional matrix of heights (see toIndex).
     * Buildings are always assumed to be "aligned", such that they exactly
     * fit within their (width, height) bounding box.
     */
    private final byte[] stacks;
    private final int hashCode;
    private final byte width;
    private final byte height;

    public Building() {
        this(new byte[]{1}, 1);
    }

    private Building(byte[] stacks, int width) {
        assert stacks.length % width == 0;
        this.stacks = stacks;
        this.width = (byte) width;
        this.height = (byte) (stacks.length / width);
        this.hashCode = 31 * width + Arrays.hashCode(stacks);
    }

    /**
     * Return the building created by adding a cube at the specified coordinates.
     * The coordinates must be within the current building bounds or else
     * directly adjacent to one of the sides, but this is not validated.
     */
    Building add(int x, int y) {
        if (x < 0) {
            byte[] newStacks = widen(true);
            newStacks[y * (width + 1)]++;
            return new Building(newStacks, width + 1);
        } else if (x < width) {
            byte[] newStacks;
            if (y < 0) {
                newStacks = new byte[stacks.length + width];
                System.arraycopy(stacks, 0, newStacks, width, stacks.length);
                y = 0;
            } else if (y * width < stacks.length) {
                newStacks = Arrays.copyOf(stacks, stacks.length);
            } else {
                newStacks = Arrays.copyOf(stacks, stacks.length + width);
            }
            newStacks[toIndex(x, y)]++;
            return new Building(newStacks, width);
        } else {
            byte[] newStacks = widen(false);
            newStacks[x + y * (width + 1)]++;
            return new Building(newStacks, width + 1);
        }
    }

    byte[] widen(boolean shift) {
        byte[] newStacks = new byte[stacks.length + height];
        int writeIndex = shift ? 1 : 0;
        for (int i = 0; i < stacks.length; i++) {
            newStacks[writeIndex++] = stacks[i];
            if (i % width == width - 1) {
                writeIndex++;
            }
        }
        return newStacks;
    }
    int toIndex(int x, int y) {
        return x + y * width;
    }

    boolean inBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < width && y < height;
    }

    /**
     * Return a stream of all legal buildings that can be created by adding a
     * cube to this building.
     */
    Stream<Building> grow() {
        int wider = width + 2;
        int max = (height + 2) * wider;

        return StreamSupport.stream(new Spliterators.AbstractSpliterator<Building>(max, 0) {
            int i = -1;

            @Override
            public boolean tryAdvance(Consumer<? super Building> action) {
                while ((++i) < max) {
                    // Try adding a cube to every position on the grid,
                    // as well as adjacent to it
                    int x = i % wider - 1;
                    int y = i / wider - 1;
                    int index = toIndex(x, y);
                    if (x < 0) {
                        if (y >= 0 && y < height) {
                            if (stacks[index + 1] > 0) {
                                action.accept(add(x, y));
                                return true;
                            }
                        }
                    } else if (x < width) {
                        if (y < 0) {
                            if (stacks[index + width] > 0) {
                                action.accept(add(x, y));
                                return true;
                            }
                        } else if (y < height) {
                            // it is on the existing grid
                            if (stacks[index] > 0) {
                                action.accept(add(x, y));
                                return true;
                            } else {
                                // is it adjacent to a stack?
                                for (Direction d : Direction.values()) {
                                    int x2 = x + d.x, y2 = y + d.y;
                                    if (inBounds(x2, y2) && stacks[toIndex(x2, y2)] > 0) {
                                        action.accept(add(x, y));
                                        return true;
                                    }
                                }
                            }
                        } else if (stacks[index - width] > 0) {
                            action.accept(add(x, y));
                            return true;
                        }
                    } else if (y >= 0 && y < height) {
                        if (stacks[index - 1] > 0) {
                            action.accept(add(x, y));
                            return true;
                        }
                    }
                }
                return false;
            }
        }, false);
    }

    Building reflect() {
        byte[] newStacks = new byte[stacks.length];
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                newStacks[y + x * height] = stacks[toIndex(x, y)];
            }
        }
        return new Building(newStacks, height);
    }

    Building rotate() {
        byte[] newStacks = new byte[stacks.length];
        for (int x = 0; x < width; x++) {
            for (int y = 0, x2 = height - 1; y < height; y++, x2--) {
                newStacks[x2 + x * height] = stacks[toIndex(x, y)];
            }
        }
        return new Building(newStacks, height);
    }

    Collection<Building> transformations() {
        List<Building> bs = new ArrayList<>(7);
        Building b1 = this, b2 = this.reflect();
        bs.add(b2);
        for (int i = 0; i < 3; i++) {
            bs.add((b1 = b1.rotate()));
            bs.add((b2 = b2.rotate()));
        }
        return bs;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Building building = (Building) o;
        return width == building.width &&
                Arrays.equals(stacks, building.stacks);
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    private enum Direction {
        N(0, 1), E(1, 0), S(0, -1), W(-1, 0);

        final int x;
        final int y;
        Direction(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int count(int rank) {
        long start = System.nanoTime();
        Collection<Building> buildings = new HashSet<>();

        for (int i = 1; i <= rank; i++) {
            if (i == 1) {
                buildings = Arrays.asList(new Building());
            } else if (Boolean.getBoolean("parallel")) {
                // Using parallel streams is generally faster, but requires
                // more memory since more Buildings are retained before being
                // discarded
                ConcurrentMap<Building, Integer> map =
                        new ConcurrentHashMap<>(buildings.size() * 4);
                AtomicInteger atomicInt = new AtomicInteger();
                buildings.parallelStream()
                        .flatMap(Building::grow)
                        .forEach(b -> {
                            map.putIfAbsent(b, atomicInt.incrementAndGet());
                        });
                // Keep only the buildings that do not have a transformation
                // with a lower index
                buildings = map.entrySet().parallelStream()
                        .filter(entry -> {
                            int index = entry.getValue();
                            for (Building b2 : entry.getKey().transformations()) {
                                Integer index2 = map.get(b2);
                                if (index2 != null && index2 < index) {
                                    return false;
                                }
                            }
                            return true;
                        })
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList());
            } else {
                Set<Building> set = new HashSet<>(buildings.size() * 4);
                // Only add a building to the set if it doesn't already have a
                // transformation in it.
                buildings.stream()
                        .flatMap(Building::grow)
                        .forEach(b -> {
                            if (!set.contains(b)) {
                                for (Building t : b.transformations()) {
                                    if (set.contains(t)) return;
                                }
                                set.add(b);
                            }
                        });
                buildings = set;
            }
            System.err.println(i + " --> " + buildings.size());
            long now = System.nanoTime();
            double ms = ((double) now - start) / 1000000;
            System.err.println("time: " + (ms < 1000 ? ms + " ms" : ms / 1000 + " s"));
        }
        return buildings.size();
    }

    public static void main(String[] args) {
        System.out.println(Building.count(Integer.parseInt(args[0])));
    }
}

Try it online! (non-parallel, up to n=12)

Invocation

javac Building.java
java -XX:+UseParallelGC -Xms14g -Xmx14g -Dparallel=true Building 14

ParallelGC is the default on Java 8, but is included in case you are using a later version JDK where G1GC is the default.

Output

1 --> 1
time: 0.410181 ms
2 --> 2
time: 97.807367 ms
3 --> 4
time: 99.648279 ms
4 --> 12
time: 101.00362 ms
5 --> 35
time: 102.4856 ms
6 --> 129
time: 105.723149 ms
7 --> 495
time: 113.747058 ms
8 --> 2101
time: 130.012756 ms
9 --> 9154
time: 193.924776 ms
10 --> 41356
time: 436.551396 ms
11 --> 189466
time: 991.984875 ms
12 --> 880156
time: 3.899371721 s
13 --> 4120515
time: 18.794214388 s
14 --> 19425037
time: 151.782854829 s
19425037

(For reference, \$15 \rightarrow 92{,}038{,}062\$)

Answer 3

Haskell, \$n=16\$ in about 9 minutes

As observed by @xnor in the comments, we can break the problem down into two parts: generate polyominoes (where I reused a lot from here, then count the ways to distribute the remaining cubes.

The symmetries are accounted for by using Burnside's lemma. So we need to know how many buildings of a given symmetric shape are fixed by a symmetry. Consider for example a shape has one mirror symmetry where the axis of reflection goes through \$s\$ squares of the shape and the reflection identifies \$d\$ pairs of further squares of the shape (so its size is \$s+2d\$). Then the buildings of this shape with \$r\$ additional cubes that have this symmetry correspond to the solutions of \$x_1+\dots+x_s+2y_1+\dots+2y_d=r\$ with nonnegative integers. The number of solutions is added to the total number of possibly equivalent buildings, and the sum divided by two. Note that a rotational symmetry always fixes zero or one square of a shape.

Compile the code with something like ghc -O2 -o buildings buildings.hs. The executable takes one optional parameter. If it is given, it will compute the number of buildings with that many cubes. Otherwise, it will compute all values.

{-# LANGUAGE BangPatterns #-}

import Data.List (sort)
import qualified Data.Set as S
import System.Environment (getArgs)

data P = P !Int !Int deriving (Eq, Ord)

start :: P
start = P 0 0

neighs :: P -> [P]
neighs (P x y) = [ p | p <- [P (x+1) y, P (x-1) y, P x (y+1), P x (y-1)],
                       p > start ]

count :: Int -> Int -> S.Set P -> S.Set P -> [P] -> Int
count 0 c _ _ _ = c
count _ c _ _ [] = c 
count n c used seen (p:possible) =
  let !c' = count n c used seen possible
      !n' = n-1
      next = S.insert p used
      !sz = S.size next
      !c'' = c' + combinations n' sz (S.toAscList next)
      new = [ n | n <- neighs p, n `S.notMember` seen ]
  in count n' c'' next (foldr S.insert seen new) (new++possible)

class Geom g where
  translate :: Int -> Int -> g -> g
  rot :: g -> g
  mirror :: g -> g

instance Geom P where
  translate !dx !dy (P x y) = P (x+dx) (y+dy)
  rot (P x y) = P (-y) x
  mirror (P x y) = P (-x) y

instance (Geom g, Ord g) => Geom [g] where
  translate !dx !dy = map $ translate dx dy
  rot = sort . map rot
  mirror = sort . map mirror

normalize :: [P] -> [P]
normalize fig = let (P x y) = head fig
                in translate (-x) (-y) fig

-- fixed points of horizontal mirror symmetry
myf :: Int -> Int -> [P] -> Int
myf r sz fig =
  let w = (maximum [ x | P x _ <- fig ])
      wh = w `div` 2
      myb = sum [ 1 | P x _ <- fig, x == wh ]
  in if even w -- odd width! 
     then c12 myb ((sz-myb) `div` 2) r
     else c1h sz r

-- fixed points of diagonal mirror symmetry
mdf :: Int -> Int -> [P] -> Int
mdf r sz fig =
  let lo = minimum [ y | P _ y <- fig ]
      mdb = sum [ 1 | P x y <- fig, x == y-lo ]
  in c12 mdb ((sz-mdb) `div` 2) r

combinations :: Int -> Int -> [P] -> Int
combinations r sz fig = 
  let rotated = take 4 $ iterate (normalize . rot) fig
      rfig = rotated !! 1
      mirrored = map (normalize . mirror) rotated
      alts = tail rotated ++ mirrored
      cmps = map (compare fig) alts
      -- All fixed points computations assume that the symmetry exists.
      -- fixed points of quarter turn:
      qtfc = if even sz then c1q sz r else sc1x 4 sz r 
      -- fixed points of half turn:
      htfc = if even sz then c1h sz r else sc1x 2 sz r
      -- fixed points of reflections:
      mirror_fc = [ fun r sz f |
                    f   <- [ fig, rfig ],
                    fun <- [ myf, mdf ]    ]
      -- all possibilities, i.e. fixed points of identity:
      idfc = c1 sz r
      fsc = [ qtfc, htfc, qtfc] ++ mirror_fc
      -- fixed points of symmetries that really exist:
      allfc = idfc : [ fc | (fc,EQ) <- zip fsc cmps ]
      -- group size of symmetry group:
      gs = length allfc
      res = if r==0 then 1 else sum allfc `div` gs
  in if any (GT ==) cmps
      -- only count if we have the smallest representative
      then 0 else res 

-- Number of ways to express t as sum of n nonnegative integers.
-- binomial(n+t-1, n-1)
c1 n t = foldl (\v x -> v * (n+x-1) `div` x) 1 [1..t]

-- Number of ways to express t as twice the sum of n/2 nn-integers
c1h n t | even t    = c1 (n `div` 2) (t `div` 2)
        | otherwise = 0

-- Number of ways to express t as four times the sum of n/4 nn-integers.
c1q n t | t `mod` 4 == 0 = c1 (n `div` 4) (t `div` 4)
        | otherwise      = 0

-- Number of ways to express t as an nn-integer plus m times the sum
-- of n/m nn-integers
sc1x m n t = c1 (1 + n `div` m) (t `div` m)

-- Number of ways to express t as the sum of s nn-integers
-- plus twice the sum of d nn-integers
c12 s d t = sum [ c1 s (t-2*t2) * c1 d t2 | t2 <- [ 0 .. t `div` 2 ] ]

count_buildings :: Int -> Int
count_buildings n = count n 0 S.empty S.empty [start]

output :: Int -> IO ()
output n = putStrLn $ show n ++ ": " ++ show (count_buildings n)

main = do args <- getArgs
          case args of
            []  -> mapM_ output [1..]
            [n] -> output (read n)

Try it online!

Results

15: 92038062
16: 438030079
17: 2092403558
18: 10027947217   (2 1/2 h)
19: 48198234188   (10 h)
20: 232261124908  (40 h)