title: Buildings made from cubes

text:
# Question
Title: Buildings made from cubes
In this 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 . 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
# JavaScript (Node.js), \\$N=10\\$ in 4m02s1

*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

```
> 10 votes

# Answer
# Java 8, \\$n=14\\$ in 2m31s1

*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\\$)
> 9 votes

# Answer
# 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)

```
> 7 votes

# Answer
# Java 11, \\$n=17\\$ in about 8.5 minutes

### Based on Haskell solution by Christian Sievers – upvote his!

This answer is the result of learning enough Haskell to be able to understand Christian's answer, translating it into Java, applying numerous micro-optimizations, and throwing multiple cores at it. The exact runtime varies significantly depending on the number of cores available; this timing result is from my own two-core machine. A 48-core EC2 c5.24xlarge is able to compute \\$n=17\\$ in 16 seconds, and \\$n=20\\$ in 18 minutes.

Parallelism can be disabled by adding the JVM argument `-Djava.util.concurrent.ForkJoinPool.common.parallelism=0`. Single-threaded performance is slightly better than double that of the Haskell solution.

Some of the optimizations include:

* Representing a point using a single int value
* Using simplified hand-rolled collections based on int arrays, avoiding the primitive boxing required for the standard Java collections
* Reimplementing polyomino enumeration based on this paper -- my initial attempt at a direct translation of the Haskell code performed extra throwaway work that didn't actually contribute to the computation
* Replacing higher-level Stream-based implementations with inlined code, making it very ugly and verbose

The bulk of the processing time is spent in `Array.sort` calls in `normalizeInPlace`. Finding a way to compare polyomino transformations without sorting could easily result in a further 4x speedup. The forking is also not done very intelligently which leads to unbalanced tasks and unused cores at higher levels of parallelism.

```
import java.util.Arrays;
import java.util.concurrent.RecursiveTask;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongSupplier;
import java.util.function.ToLongFunction;

/**
 * Utility methods for working with an int that represents a pair of short values.
 */
class Point {
    static final int start = p(0, 0);
    static final int[] neighbors = new int[] {-0x10000, -0x1, 0x1, 0x10000};

    static int x(int p) {
        return (p >> 16) - 0x4000;
    }

    static int y(int p) {
        return (short)(p) - 0x4000;
    }

    static int p(int x, int y) {
        return ((x + 0x4000) << 16) | (y + 0x4000);
    }

    static int rot(int p) {
        return p(-y(p), x(p));
    }

    static int mirror(int p) {
        return p(-x(p), y(p));
    }
}

/**
 * Minimal primitive array-based collections.
 */
class IntArrays {
    /** Concatenates the end of the first array with the beginning of the second. */
    static int[] arrayConcat(int[] a, int aOffset, int[] b, int bLen) {
        int aLength = a.length - aOffset;
        int[] result = new int[aLength + bLen];
        System.arraycopy(a, aOffset, result, 0, aLength);
        System.arraycopy(b, 0, result, aLength, bLen);
        return result;
    }

    /** Adds a new value to a sorted set, returning the new result */
    static int[] setAdd(int[] set, int val) {
        int[] dst = new int[set.length + 1];
        int i = 0;
        for (; i < set.length && set[i] < val; i++) {
            dst[i] = set[i];
        }
        dst[i] = val;
        for (; i < set.length; i++) {
            dst[i + 1] = set[i];
        }
        return dst;
    }

    private static final int[] primes = new int[] {
            5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
            67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131
    };

    /**
     * Allocate an array large enough to hold a fixed-capacity hash table
     * that can contain "seen" points for generating polyominos of size n.
     */
    static int[] makeHashTable(int n) {
        return new int[primes[-(Arrays.binarySearch(primes, n * 3) + 1)]];
    }

    /** Inserts a new value to a hash table, in-place */
    static void hashInsert(int[] table, int val) {
        int pos = (val * 137) % table.length, startPos = pos;
        if (table[pos] != 0) {
            while ((table[pos = (pos + 1) % table.length]) != 0) {
                if (pos == startPos) {
                    throw new AssertionError("table full");
                }
            }
        }
        table[pos] = val;
    }

    /** Checks whether a hash table contains the specified value */
    static boolean hashContains(int[] table, int val) {
        int pos = (val * 137) % table.length, startPos = pos;
        while (true) {
            int curr = table[pos];
            if (curr == val) return true;
            if (curr == 0) return false;
            pos = (pos + 1) % table.length;
            if (pos == startPos) {
                throw new AssertionError("table full");
            }
        }
    }
}

/**
 * Recursively generates int arrays representing collections of Points,
 * applying a function to each array to compute a long, and returns the sum
 * of all such values.
 */
class PolyominoVisitor extends RecursiveTask<Long> {
    PolyominoVisitor(ToLongFunction<? super int[]> func, int n) {
        this(func, n, 0, 1, new int[0], IntArrays.makeHashTable(n), new int[]{Point.start});
    }

    private PolyominoVisitor(ToLongFunction<? super int[]> action, int n,
                             int i, int limit, int[] used, int[] seen, int[] untried) {
        this.func = action;
        this.n = n;
        this.start = () -> visit(i, limit, used, seen, untried);
    }

    private final boolean visitSmaller = true;
    private final ToLongFunction<? super int[]> func;
    private final int n;
    private final LongSupplier start;

    @Override
    protected Long compute() {
        return start.getAsLong();
    }

    private long visit(int i, int limit, int[] used, int[] seen, int[] untried) {
        long val = 0;
        if (used.length + 1 == n) {
            // reached the second to last level, so we can apply the function
            // directly to our children
            for (; i < limit; i++) {
                val += func.applyAsLong(IntArrays.setAdd(used, untried[i]));
            }
        } else if (used.length + 6 < n && limit - i >= 2) {
            // eligible to split
            PolyominoVisitor[] tasks = new PolyominoVisitor[limit - i];
            for (int j = 0; j < tasks.length; j++) {
                tasks[j] = new PolyominoVisitor(func, n,
                        i + j, i + j + 1, used, seen, untried);

            }
            invokeAll(tasks);
            for (PolyominoVisitor task : tasks) val += task.getRawResult();
            return val;
        } else {
            // recursively visit children
            int[] newReachable = new int[4];
            IntPredicate inSeen = p -> !IntArrays.hashContains(seen, p);
            for (; i < limit; i++) {
                int candidate = untried[i];
                int[] child = IntArrays.setAdd(used, candidate);
                int reachableCount = neighbors(candidate, inSeen, newReachable);
                int[] newSeen = seen.clone();
                for (int j = 0; j < reachableCount; j++) IntArrays.hashInsert(newSeen, newReachable[j]);
                int[] newUntried = IntArrays.arrayConcat(untried, i + 1, newReachable, reachableCount);
                val += visit(0, newUntried.length, child, newSeen, newUntried);
            }
        }
        if (visitSmaller && used.length > 0 && limit == untried.length) {
            val += func.applyAsLong(used);
        }
        return val;
    }

    /**
     * Write the greater-than-origin neighbors of the given point
     * that pass the provided predicate into the provided array,
     * returning the count written.
     */
    private static int neighbors(int p, IntPredicate pred, int[] dst) {
        int count = 0;
        for (int offset : Point.neighbors) {
            int n = p + offset;
            if (n > Point.start && pred.test(n)) {
                dst[count++] = n;
            }
        }
        return count;
    }
}

/**
 * Function that computes how many buildings are constructable on a given
 * polyomino base. Considers symmetry, returning 0 if the figure is not the
 * canonical version (i.e. has a smaller transformation).
 *
 * Adapted largely unchanged from Christian Sievers
 * https://codegolf.stackexchange.com/a/199919
 */
class BuildingCounter implements ToLongFunction<int[]> {
    private final int n;

    public BuildingCounter(int n) {
        this.n = n;
    }

    @Override
    public long applyAsLong(int[] fig) {
        return combinations(n - fig.length, fig);
    }

    private static int[] map(int[] fig, IntUnaryOperator func) {
        int[] result = new int[fig.length];
        for (int i = 0; i < fig.length; i++) {
            result[i] = func.applyAsInt(fig[i]);
        }
        return result;
    }

    private static int[] normalizeInPlace(int[] fig) {
        Arrays.sort(fig);
        int d = fig[0] - Point.start;
        for (int i = 0; i < fig.length; i++) {
            fig[i] -= d;
        }
        return fig;
    }

    private static int[] rot(int[] ps) {
        return normalizeInPlace(map(ps, Point::rot));
    }

    private static int[] mirror(int[] ps) {
        return normalizeInPlace(map(ps, Point::mirror));
    }

    private static int myf(int r, int sz, int[] fig) {
        int max = Integer.MIN_VALUE;
        for (int p : fig) {
            if (p > max) max = p;
        }
        int w = Point.x(max);
        if (w % 2 == 0) {
            int wh = w / 2;
            int myb = 0;
            for (int p : fig) {
                if (Point.x(p) == wh) myb++;
            }
            return c12(myb, (sz - myb)/2, r);
        } else {
            return c1h(sz, r);
        }
    }

    private static int mdf(int r, int sz, int[] fig) {
        int lo = Integer.MAX_VALUE;
        for (int p : fig) {
            int tmp = Point.y(p);
            if (tmp < lo) lo = tmp;
        }
        int mdb = 0;
        for (int p : fig) {
            if (Point.x(p) == Point.y(p) - lo) mdb++;
        }
        return c12(mdb, (sz-mdb)/2, r);
    }

    private static long combinations(int r, int[] fig) {
        int[][] alts = new int[7][];
        alts[0] = rot(fig);
        alts[1] = rot(alts[0]);
        alts[2] = rot(alts[1]);
        alts[3] = mirror(fig);
        alts[4] = mirror(alts[0]);
        alts[5] = mirror(alts[1]);
        alts[6] = mirror(alts[2]);
        int[] rfig = alts[0];
        int[] cmps = new int[7];
        for (int i = 0; i < 7; i++) {
            if ((cmps[i] = Arrays.compare(fig, alts[i])) > 0) {
                return 0;
            }
        }
        if (r == 0) {
            return 1;
        }
        int sz = fig.length;
        int qtfc = (sz % 2 == 0) ? c1q(sz, r) : sc1x(4, sz, r);
        int htfc = (sz % 2 == 0) ? c1h(sz, r) : sc1x(2, sz, r);
        int idfc = c1(sz, r);
        int[] fsc = new int[] {qtfc, htfc, qtfc,
                myf(r, sz, fig), mdf(r, sz, fig),
                myf(r, sz, rfig), mdf(r, sz, rfig)};
        int gs = 1;
        int allfc = idfc;
        for (int i = 0; i < fsc.length; i++) {
            if (cmps[i] == 0) {
                allfc += fsc[i];
                gs++;
            }
        }
        return allfc / gs;
    }

    private static int c1(int n, int t) {
        int v = 1;
        for (int x = 1; x <= t; x++) {
            v = v * (n+x-1) / x;
        }
        return v;
    }

    private static int c1h(int n, int t) {
        return c1d(n, t, 2);
    }

    private static int c1q(int n, int t) {
        return c1d(n, t, 4);
    }

    private static int c1d(int n, int t, int q) {
        if (t % q == 0) {
            return c1(n / q, t / q);
        } else {
            return 0;
        }
    }

    private static int sc1x(int m, int n, int t) {
        return c1(1 + n / m, t / m);
    }

    private static int c12(int s, int d, int t) {
        int sum = 0;
        for (int i = t/2; i >= 0; i--) {
            sum += c1(s, t-2*i) * c1(d, i);
        }
        return sum;
    }
}

public class Main {
    public static long count(int n) {
        return new PolyominoVisitor(new BuildingCounter(n), n).compute();
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            System.out.println(args[0] + ": " + count(Integer.parseInt(args[0])));
        } else {
            for (int i = 1; i <= 99; i++) {
                System.out.println(i + ": " + count(i));
            }
        }
    }
}

```

### Invocation

```
javac Main.java
java Main 17

```

Try it online!

### Results

(when run without an argument)

```
...
16: 438030079
17: 2092403558
18: 10027947217
19: 48198234188
20: 232261124908
21: 1121853426115

```
> 5 votes

---
Tags: geometry, fastest-code
---


# Question
Title: Best free online resources to learn competitive programming
I am quite proficient in C++ and Java and want to learn competitive programming to participate in contests like Google codejam and other online contests held on sites like CodeChef and Codeforces. I would like to get information about any **free** resources including websites and courses to learn the "sport". Book suggestions are also welcome.

Please suggest some courses which have some practical work included and not just flat theory. I want to work on my problem solving skills rather than just learning algorithms and data structures.

# Answer
> 0 votes
# Practice Algorithmic Thinking

If there's one thing I believe programmers need to master, it's the process of dissecting a problem statement and planning their approach.

By this, I mean having the ability to approach an unseen challenge and think about what is being asked.

If I were you, I'd look at challenges posted around this website, ranging from trivial to difficult, and take the time to plan how you would solve the problem. That way, you'll be able to have a hands on experience with problem solving.

Once you do this enough, start placing time restrictions on your thinking time. Because I know from personal experience that competitive programming is most often timed. Once you have got that nailed, you should be ready for competitions.

In summary: practice. Y'all need to walk before y'all can run. I hope to see you as an active contributor around here!

---
Tags: tips
---


# Question
Title: Calculate the average longest common substring exactly
\[Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. \]

The longest common substring between two strings is the longest substring which is common to both. Please note this is *not* the same as the longest common **subsequence** whose fastest algorithm takes quadratic time.

The challenge is to compute the average length of the longest common substring between two independent and uniformly random chosen binary strings of length `n` each. Your output must be exact but can be given in any easy to understand human readable form.

# Examples for `n = 1..12`

* 1/2
* 9/8
* 7/4
* 295/128
* 361/128
* 6741/2048
* 15217/4096
* 8389/2048
* 291431/65536
* 2500643/524288
* 2657159/524288
* 22420789/4194304

# Score

Your score is the highest value of you can reach. I will run your code on my Linux machine for 1 minute and then kill the job to get the score.

I will maintain a leaderboard that shows the best score for each language used in an answer.

# Worked example

Following a request, here is the full set of distances for `n = 3`. I have not include strings B and A if A and B are already listed. This is because the distance function is symmetric.

```
000 000 3
000 001 2
000 010 1
000 011 1
000 100 2
000 101 1
000 110 1
000 111 0
001 001 3
001 010 2
001 011 2
001 100 2
001 101 2
001 110 1
001 111 1
010 010 3
010 011 2
010 100 2
010 101 2
010 110 2
010 111 1
011 011 3
011 100 1
011 101 2
011 110 2
011 111 2
100 100 3
100 101 2
100 110 2
100 111 1
101 101 3
101 110 2
101 111 1
110 110 3
110 111 2
111 111 3

```

# Leaderboard

* `n = 22` in **C++** by my pronoun is monicareinstate.
* `n = 18` in **Rust** by Plasma\_000.
* `n = 14` in **C** by Mitchel Spector.
* `n = 11` in **Python** with pypy 3 by Alex.

# Answer
# C++, n = 21 (40s on an AMD Ryzen 5 2500U)

This used to be a fast brute force answer that got up to n=17. That is currently preserved in the revision history.

```
#include <cstring>
#include <omp.h>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>

typedef unsigned uint;
typedef unsigned char byte;
const int threadnum = 8;
const int maxn = 22; //for 24 bytes total size of Row
struct Row; struct hasher { size_t operator ()(const Row& row) const; };
struct Row
{
    char max = 0;
    std::array<char, maxn+1> row {0};
    Row() { }
    Row(int nmax)
    {
        max = nmax;
    }
    bool operator ==(const Row& rhs) const
    {
        const uint64_t* x = reinterpret_cast<const uint64_t*>(this);
        const uint64_t* y = reinterpret_cast<const uint64_t*>(&rhs);
        return x[0] == y[0] && x[1] == y[1] && x[2] == y[2];
    }
};
uint64_t rotl(uint64_t x, char a)
{
    return (x << a) | (x >> (64 - a));
}
size_t hasher::operator() (const Row& row) const
{
    const uint64_t* mem = reinterpret_cast<const uint64_t*>(&row);
    //I tried really many different hashes...
    uint64_t h = mem[0]; h += rotl(h, 4);
    h         ^= mem[1]; h += rotl(h, 4);
    h         ^= mem[2]; h += rotl(h, 4);
    return h;
}
const short hashTableSize = 1009;
struct Map
{
    std::array<std::pair<Row, int>, hashTableSize> table {};
    Map()
    {
    }
    void add_or_add(const Row row, const int delta)
    {
        size_t hash = hasher()(row) % hashTableSize;
        while(table[hash].second != 0 && !(table[hash].first == row))
        {
            hash++;
            if(hash == hashTableSize) hash = 0; //just loop :)
        }
        if(table[hash].second == 0)
            table[hash].first = row;
        table[hash].second += delta;
    }
    void clear()
    {
        std::memset(table.data(), 0, sizeof(table));
    }
};

constexpr uint bitRev(uint n)
{
    n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
        n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
        n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
        n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
        n = ((n >>16) & 0x0000ffff) | ((n <<16) & 0xffff0000);
        return n;
}
constexpr bool is_substring(int target, char n, short subs, char m)
{
    //n=2, m=1 -> i from 0 to 1
    int max = n-m+1;
    bool flag = false;
    for(int i = 0; i < max; i++)
        flag |= (((target >> i) ^ subs) & ((1<<m) - 1)) == 0;
    return flag;
}
int supermax = 0;
int main()
{
    uint n; std::cin >> n;
    std::vector<uint64_t> sums(threadnum);
    uint64_t sum = 0;
#pragma omp parallel for num_threads(threadnum) schedule(dynamic)
    for(uint sa = 0; sa < 1<<~-n; sa++) //the second half is the bitwise complement of the first one
    {
        uint sb = bitRev(sa);
        sb ^= -(sb >> 31);
        sb >>= 32 - n;
        if(sb < sa) continue;
        //find a lower bound = len(the shortest non-substring of sa) - 1
        //if Row.max is immediately set to it, that reduces the number of states slightly
        char lb = 0; bool found = false;
        for(char len = 0; len < 10; len++)
        {
            for(short j = 0; j < (1<<len); j++)
                if(!is_substring(sa, n, j, len))
                {
                    lb = len - 1;
                    goto out;
                }
        }
        out:;
        Map dpcur;
        Map dpnext;
        dpcur.add_or_add(Row(lb), 1);
        int ans = 0;
        for(char j = 0; j < n; j++)
        {
            for(auto[row, cnt] : dpcur.table)
            {
                if(!cnt) continue;
                Row nr0 {}, nr1 {};
                nr0.max = nr1.max = row.max;
                for(char i = 0; i < n; i++)
                {
                    Row& r = (sa >> i)&1 ? nr0 : nr1;
                    r.row[i+1] = row.row[i] + 1;
                }
                char n0max = 0, n1max = 0;
                for(char i = 0; i < 23; i++)
                    n0max = std::max(n0max, nr0.row[i]);
                for(char i = 0; i < 23; i++)
                    n1max = std::max(n1max, nr1.row[i]);
                //possibly, cut an entire would-be branch that would never improve!
                if(n0max + n - j - 1 <= nr0.max)
                    ans += (cnt * nr0.max) << (n - j - 1);
                else
                    nr0.max = std::max(nr0.max, n0max), dpnext.add_or_add(nr0, cnt);
                if(n1max + n - j - 1 <= nr1.max)
                    ans += (cnt * nr1.max) << (n - j - 1);
                else
                    nr1.max = std::max(nr1.max, n1max), dpnext.add_or_add(nr1, cnt);
            }
            std::memcpy(dpcur.table.data(), dpnext.table.data(), sizeof(Map));
            dpnext.clear();
        }
        for(auto[row, cnt] : dpcur.table)
            ans += cnt * row.max;
        sums[omp_get_thread_num()] += ans;
        if(sb != sa)
            sums[omp_get_thread_num()] += ans;
    }
    for(uint64_t e : sums) sum += e;
    sum *= 2;
    printf("%ld\n", sum);
    uint64_t num = sum, denom = 1ll<<(2*n);
    while(num % 2 == 0) num /= 2, denom /= 2;
    printf("%ld/%ld\n", num, denom);
}

```

This uses OpenMP for multi-threading. To be compiled with `clang++ -std=c++17 -Ofast -march=native -flto -fopenmp file.cpp`.

## Explanation I tried (please don't use it as a Rust translation guide)

The longest common substring can be found in \\$O(n^2)\\$ time via dynamic programming. That dynamic programming can be calculated (if the strings are \\$s\\$ and \\$t\\$) via the formula $$dp\_{i,j} = \begin{cases}dp\_{i-1,j-1} + 1& s\_i = t\_j\\0& \text{otherwise}\end{cases}$$ (and then the answer is just the highest value in \\$dp\\$). A naive solution would be to iterate over pairs of strings of length \\$n\\$ (resulting in \\$O(4^n n^2)\\$ time complexity). However, instead of simply doing that, my program only iterates over all possible values of the first string. Then, it simply does that, but instead of storing a proper dynamic programming array (that wouldn't be possible because there is no second string), it stores an array of all *possible* rows in it with counters of how many ways exist to reach this row. To calculate the next array of possible rows from the current array of possible rows, my program simply tries all of them with both possible values of the next bit in the second string. This leads to a speedup, because if two prefixes of the second string lead to the same state, they can be "merged" into one execution path.

I suspect this is similar to the optimization from the top answer in a similar challenge but for Levenshtein distance, but the explanation there is so bad I couldn't understand it at all.

The optimization that got this to 21: if at a certain point a possible row is encountered such that all its numbers are too small to ever improve the length of the longest substring in it, it can be directly calculated how much it will add to the answer.

Takes input as a single number from `stdin`. Outputs `734551/131072` for 13, `392340511/67108864` for 14, `1630366263/268435456` for 15, `6751032665/1073741824` for 16, `6967595579/1073741824` for 17, `114759115773/17179869184` for 18, `235733542633/34359738368` for 19, `1933121200141/27877906944` for 20 and `7912473298597/1099511627776` for 21.
> 9 votes

# Answer
# Wolfram Language (Mathematica), n=12 (~53s TIO)

```
t=0;
For[i=0,i<2^a,i++,
   For[j=0,j<2^(a-1),j++,
    t=t+Length@LongestCommonSubsequence[IntegerDigits[i,2,a],IntegerDigits[j,2,a]]]]

```

Try it online!
> 4 votes

# Answer
# Python 3 ~~308~~ 293 bytes, n=10 (30sec TIO)

```
a=lambda S,T:max((*(i+1 for i in range(len(S)) for j in range(len(S)-i)if S[j:j+i+1]in T),0));b=lambda i,n:'0'*(n-len(bin(i)[2:]))+bin(i)[2:]
for n in range(1,11):m=2**n;t=sum([a(b(i,n),b(j,n))for i in range(m)for j in range(m)]);y=bin(t);v=2**(len(y)-len(y.rstrip('0')));print(t/v,'/',4**n/v)

```

Try it online!

Not elegant or super fast but it's the first time I've been able to get something like this on so few lines. Potential speed up possible with numpy functions.

I feel like this problem is similar to Project Euler Question 701. Maybe with an algorithm for that this problem could be done in sub-exponential time.
> 2 votes

# Answer
# Rust, (n=15 ~6 sec, n=16 ~25 sec on 2.5GHz intel i7)

More heavily parallelised rewrite of @monicareinstate's answer in rust

> src/main.rs

```
use rayon::prelude::*;

const MAX_N: usize = 22;

const ARRAY_SIZE: usize = 1 << MAX_N;

static mut LOOKUP: [u8; ARRAY_SIZE] = [0; ARRAY_SIZE];

#[inline]
fn longest_sub(left: u32, right: u32, bits: u8) -> (u8, u8) {
    // Uses of unsafe are sound here since we are only reading immutably
    let mask = (1u32 << bits) - 1;
    let unshifted = mask & !(left ^ right);
    let max_unshifted = unsafe { *LOOKUP.get_unchecked(unshifted as usize) };
    let max_shifted = (1..bits)
        .map(|shift| {
            let mask = (1u32 << (bits - shift)) - 1;
            let shift_l = mask & !((left >> shift) ^ right);
            let shift_r = mask & !(left ^ (right >> shift));
            unsafe {
                std::cmp::max(
                    *LOOKUP.get_unchecked(shift_l as usize),
                    *LOOKUP.get_unchecked(shift_r as usize),
                )
            }
        })
        .max()
        .unwrap();

    let max = std::cmp::max(max_unshifted, max_shifted);
    if left == right {
        (max, 1)
    }
    else {
        (2 * max, 2)
    }
}

#[inline]
fn calculate(bits: u8) -> (u64, u64) {
    for number in 1..1usize << bits {
        // Safe since we have no other references to LOOKUP in the current program
        unsafe {
            *LOOKUP.get_unchecked_mut(number) = 1 + LOOKUP.get_unchecked(number & (number >> 1))
        }
    }

    (0..1u32 << bits)
        .into_par_iter()
        .flat_map(move |left| {
            (left..1u32 << bits)
                .into_par_iter()
                .map(move |right| longest_sub(left, right, bits))
        })
        .map(|(max, weight)| (max as u64, weight as u64))
        .reduce(|| (0, 0), |a, b| (a.0 + b.0, a.1 + b.1))
}

fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let line = line.trim();
    let number = line.parse().unwrap();

    let (num, denom) = calculate(number);
    let (num, denom) = {
        let (mut a, mut b) = (num, denom);
        while a % 2 == 0 && b % 2 == 0 {
            a /= 2;
            b /= 2;
        }
        (a, b)
    };
    println!("{}/{}", num, denom);
}

```

> Cargo.toml

```
[package]
name = "golf"
version = "0.1.0"
authors = ["Plasma_000"]
edition = "2018"

[profile.release]
opt-level = 3
lto = true

[dependencies]
rayon = "1.3"

```

> Build with

```
RUSTFLAGS="-Ctarget-cpu=native" cargo +nightly build --release

```

Using nightly compiler 1.43.0

This performs a very slightly faster than the @monicareinstate's current answer on my machine:

```
❯ time "echo 15 | ./target/release/golf"
Benchmark #1: echo 15 | ./target/release/golf
  Time (mean ± σ):      5.872 s ±  0.114 s    [User: 21.332 s, System: 0.127 s]
  Range (min … max):    5.665 s …  6.017 s    10 runs

```

VS @monicareinstate's

```
❯ time "echo 15 | ./a.out"
Benchmark #1: echo 15 | ./a.out
  Time (mean ± σ):      5.983 s ±  0.092 s    [User: 22.038 s, System: 0.120 s]
  Range (min … max):    5.868 s …  6.157 s    10 runs

```

EDIT: well done @monicareinstate on your latest edit, you have me beat :)
> 2 votes

# Answer
# Java, n=11 (~30-35 sec on TIO)

```
import java.util.ArrayList;
import java.util.List;
class Main{
  public static void main(String[] args){
    for(int n=1; ; n++){
      String binaryFormat="%"+n+"s";
      int sum=0, c=0;
      double powerOf2=Math.pow(2,n);
      for(int a=0; a<powerOf2; a++){
        String binaryA=toBinary(n,a);
        for(int b=0; b<powerOf2/2; b++){
          String binaryB=toBinary(n,b);
          sum += solve(binaryA, binaryB);
          c++;
        }
      }
      System.out.println(n+": "+sum+"/"+c);
    }
  }

  private static String toBinary(int n, int a){
    return String.format("%"+n+"s", Integer.toBinaryString(a)).replace(' ','0');
  }

  private static int solve(String a,String b){
    String s=a+2+b+3;
    List<Integer> M = new ArrayList<>();
    for(int c : s.getBytes())
      M.add(c);
    List<Integer> S = suffixList(M, 51);
    List<Integer> I = new ArrayList(S);
    for(int i=0; i<S.size(); i++)
      I.set(S.get(i), i);
    int L=0,R=0,m=0,h=0;
    for(int i=0; i<S.size(); i++){
      if(I.get(i)!=0){
        int j=S.get(I.get(i)-1);
        while(s.charAt(i+h)==s.charAt(j+h))
          h++;
        if(h>m){
          int len = a.length();
          int sortedMid = (i-j)*(j-len)>0 ? j
                                          : (i-j)*(i-len)>0 ? len
                                                            : i;
          if(len == sortedMid){
            m=h;
            L=i<j?i:j;
            R=L+h;
          }
        }
        if(h>0)
          h--;
      }
    }
    return R-L;
  }

  private static List<Integer> suffixList(List<Integer> s, int K){
    int n=s.size();
    s.add(0);s.add(0);s.add(0);
    int n0=(n+2)/3, n1=(n+1)/3, n2=n/3;
    int n02=n0+n2;
    int adj=n0-n1;
    int length=(n+adj)/3;
    List<Integer> A=new ArrayList<>();
    for(int x=0; x<n+adj; x++)
      if(x%3!=0)
        A.add(x);
    A.add(0);A.add(0);A.add(0);
    radixPass(K,s,A,2,n02);
    radixPass(K,s,A,1,n02);
    radixPass(K,s,A,0,n02);
    List<Integer> B=new ArrayList<>();
    for(int i=0; i<n02; i++)
      B.add(0);
    int[] t=new int[3];
    int m=0;
    for(int i=0; i<n02; i++){
      int x=A.get(i);
      int[] u=new int[3];
      for(int j=x; j<x+3; j++)
        u[j-x]=s.get(j);
      if(t[0]!=u[0]||t[1]!=u[1]||t[2]!=u[2])
        m++;
      t=u;
      B.set(x/3+x%3/2*n0, m);
    }
    if(n02==1)
      for(int i=0; i<n02; i++)
        A.set(i, 0);
    else{
      List<Integer> X = suffixList(B,m);
      for(int i=0; i<n02; i++)
        A.set(i, X.get(i));
    }
    List<Integer> I = new ArrayList<>(A);
    for(int i=0; i<n02; i++)
      I.set(A.get(i), i+1);
    B = new ArrayList<>();
    for(int x:A)
      if(x<n0)
        B.add(3*x);
    radixPass(K,s,B,0,n0);
    List<Integer> R = new ArrayList<>();
    int p=0;
    for(int T=adj; T<n02; ){
      int x = A.get(T);
      boolean bool = x>=n0;
      int b = bool?1:0;
      int i=(x-b*n0)*3-~b;
      int j=B.get(p);
      if(p==n0
         || (bool ? s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&s.get(i+1)<s.get(j+1)) || (s.get(i)==s.get(j)&&s.get(i+1)==s.get(j+1)&&I.get(A.get(T)-n0+1)<I.get(j/3+n0))
                  : s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&I.get(A.get(T)+n0)<I.get(j/3)))){
        R.add(i);
        T++;
      }else{
        R.add(j);
        p++;
      }
    }
    for(int i=p; i<n0; i++)
      R.add(B.get(i));
    return R;
  }

  private static void radixPass(int K, List<Integer> s, List<Integer> a, int o, int n){
    int[] c=new int[K+3];
    for(int i=0; i<n; i++)
      c[s.get(a.get(i)+o)+1]++;
    for(int i=0; i<K+3; i++)
      c[i]+=c[i<1?c.length-1:i-1];
    List<Integer> A = new ArrayList<>(a);
    for(int i=0; i<n; i++){
      int x=A.get(i);
      int j=s.get(x+o);
      a.set(c[j], x);
      c[j]++;
    }
  }
}

```

NOTE: The fractions aren't normalized like in the challenge description. The decimal values the fractions represent are correct, though.

Try it online with indefinite printing - times out after 60 sec or try it online with given argument \\$n\\$.

Only just got it working, so will try to improve its performance later on.

**Short explanation of my solution:**

I first modified *@MitchSchwartz*' Python 2 answer for the *Longest common substring in linear time* challenge so it will loop over the binary-string pairs we want to check. This challenge asks for the starting and ending index of the longest common substring between two strings, in lineair time (\\$O(n)\\$ complexity).
His answer implements 'The Skew Algorithm' described in Juha Kärkkäinen's & Peter Sanders' *Simple Linear Work Suffix Array Construction* article, with the implementation of the Longest Common Prefix part using the algorithm described in Toru Kasai's, Gunho Lee's, Hiroki Arimura's, Setsuo Arikawa's, and Kunsoo Park's *Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications* article.

Since we basically want to check all binary-string pairs \\$A\\$ and \\$B\\$, where \\$A\\$ are binary strings for integers \\$a\\$ in the range \\$a=\[0, 2^n)\\$ and \\$B\\$ are binary strings for integers \\$b\\$ in the range \\$b=\[0,\frac{2^n}{2})\\$ (similar as the existing Mathematica answer does), I've modified *@MitchSchwartz*' ungolfed answer to take the difference between the found indices, and sum those together for our numerator (the denominator will be \\$n^{2n-1}\\$ for any given \\$n\\$).

Here is that modified Python code:
Try it online printing indefinitely or try it online with given input \\$n\\$ (which produces \\$n=9\\$ in about 25-30 sec on TIO).

Since I'm not too skilled with Python, I decided to port everything to Java which I use on a daily basis. This allows me to make performance enhancing modifications (which I will try to do later on) easier. And I also knew that the larger \\$n\\$ would become, the better the performance of the Java program in comparison to the Python program would be (which can also be seen by checking some \\$n\\$ in both programs on TIO - i.e. the inputs \\$n=1,5,7,9\\$ will take approximately 1.5, 2.25, 1.75, 4.0 seconds in Java, but 0.02, 0.1, 1.5, 30.0 seconds in Python 2 respectively.

**Long explanation:**

*TODO: I will describe the actual implementation and perhaps add some comments to the code later on. This already took long enough to modify and port to Java for now.*
> 1 votes

# Answer
# C (gcc), 1769 bytes, n=14 in 31 sec. on TIO

**n=15 in 2 min 7sec on my MacBook Pro (3.1 GHz Intel Core i7)**

**NOTE: If you test this program to see how far it can get in one minute, change `#define END` to be some larger number, say `(17)`. The value of `(14)` was picked so as not to time out in 1 minute on TIO.**

**Output will be computed from `n = START` to `n = END`.**

**Do not change the `#define CUTOFF` value -- this is the point at which long longs are needed, instead of just longs.**

```
#include <stdlib.h>
#include <stdio.h>

#define START (1)
#define END (14)

#define CUTOFF (15)

// Find length of longest common substring of binary numbers a and b, of length l.
int f(int a, int b, int l)
  {
   int i, j;

   for (int lengthOfMatch=1, mask=1; lengthOfMatch<=l; lengthOfMatch++, mask = 2*mask+1)
      {
       for (i=0; i <= l-lengthOfMatch; i++)
          {
           for (j=0; j <= l-lengthOfMatch; j++)
                {
                   if ( ((a>>i)& mask) == ((b>>j) & mask) )
                     {
                      if (lengthOfMatch == l)
                        return lengthOfMatch;

                      goto NextMatchLength;
                     }
                } // for j
          } // for i

       return lengthOfMatch - 1;

NextMatchLength:
       ;
      } // for lengthOfMatch

 return 0;
} // f

int main(void)
{
 for (int numberOfBits=START; numberOfBits <= END; numberOfBits++)
  {
   if (numberOfBits >= CUTOFF)
     {
      long long t=0;

      for (int a=0;a<(1<<numberOfBits);a++)
         {
          for (int b=0; b<a; b++)
              t += f(a, b, numberOfBits);
         } // for a

// Make up for the entries f(a, a, numberOfBits) that weren't counted above.
      t += numberOfBits*(1<<(numberOfBits-1));

      printf("%d => %lld/%lld\n", numberOfBits, t, 1ll<<(2*numberOfBits-1));
     }
    else
     {
      long t=0;

      for (int a=0;a<(1<<numberOfBits);a++)
         {
          for (int b=0; b<a; b++)
              t += f(a, b, numberOfBits);
         } // for a

// Make up for the entries f(a, a, numberOfBits) that weren't counted yet.
      t += numberOfBits*(1<<(numberOfBits-1));

      printf("%d => %ld/%ld\n", numberOfBits, t, 1l<<(2*numberOfBits-1));
     }
   }

exit(0);
} // main

```

Try it online!

---

**Sample output for \\$n=15\\$ from my MacBook Pro (3.1 GHz Intel Core i7) -- 2 min 7 sec.**

```
$ time ./l5
1 => 1/2
2 => 9/8
3 => 56/32
4 => 295/128
5 => 1444/512
6 => 6741/2048
7 => 30434/8192
8 => 134224/32768
9 => 582862/131072
10 => 2500643/524288
11 => 10628636/2097152
12 => 44841578/8388608
13 => 188045056/33554432
14 => 784681022/134217728
15 => 3260732526/536870912

real    2m6.814s
user    2m5.842s
sys 0m0.402s

```
> 1 votes

---
Tags: string, combinatorics, fastest-code
---


title: Find the binary period

text:
# Question
Title: Find the binary period
We know that not all fractions have a terminating binary representation. However every fraction can be written as a leading portion followed by a repeating portion. For example \\$1/3\\$ starts with \\$0.\\$ and then just repeats \\$01\\$ endlessly. This corresponds to the bar notation taught in primary school. For example

$$ 1/3 = 0.\overline{01} $$

Where the portion with the bar is the repeating section.

For numbers with a terminating representation, (e.g. \\$1/2 = 0.1\\$) the repeating section is just \\$0\\$, since there are endless implicit zeros at the end of a terminating representation.

We will call the minimum1 length of the repeating section the binary period of the fraction.

Your task is to write a program or function which takes a positive integer \\$n\\$ as input and outputs the binary period of \\$1/n\\$.

This is so answers will be scored in bytes with fewer bytes being better.

OEIS A007733

---

1: We say minimum because if you duplicate a section again it keeps a valid representation. (e.g. \\$0.\overline{01} = 0.\overline{0101}\\$)

# Answer
# Jelly, 9 bytes

```
2*Ɱ%µẠȧQL

```

A monadic Link accepting a positive integer, `n`, which yields a positive integer, the period.

**Try it online!** Or see the test-suite.

### How?

```
2*Ɱ%µẠȧQL - Link: integer, n
2         - literal two
  Ɱ       - map across [1..n]
 *        - exponentiate -> [1,2,4,8,...,2^n]
   %      - modulo n -> [1%n,2%n,4%n,8%n,...,2^n%n]
    µ     - start a new monadic chain - call that X
     Ạ    - all (X)? -> 0 if we reach zero, else 1 - i.e. 0 if n is a power of 2
       Q  - de-duplicate (X) -> the repeating 2^k%n values
      ȧ   - logical AND -> 0 if n is a power of 2 else Q(X)
        L - length (0 has a length of 1 (after an implicit make_digits))

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 30 bytes

```
Length@@#&@@RealDigits[1/#,2]&

```

Try it online!
> 0 votes

# Answer
# Python 3, 70 bytes

```
f=lambda k,a=1:k%2and(a/k%1and f(k,a*2+1)or len(bin(a))-2)or f(k//2,a)

```

Try it online!
> 0 votes

# Answer
# Charcoal, 33 bytes

```
Ｎθ⊞υ¹Ｗ¬№﹪υθ﹪⊕Συθ⊞υ⊕ΣυＩ⊕⌕﹪⮌υθ﹪⊕Συθ

```

Try it online! Link is to verbose version of code. Sadly all my attempts to golf this down tended to break on edge cases such as `1` or other powers of `2`. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υ¹

```

Start with a list containing just `2⁰`.

```
Ｗ¬№﹪υθ﹪⊕Συθ

```

See if the next power of 2 is equivalent (modulo n) to any of the elements in the list.

```
⊞υ⊕Συ

```

If not then push that power of 2 to the list.

```
Ｉ⊕⌕﹪⮌υθ﹪⊕Συθ

```

Print the difference in the two exponents.
> 0 votes

# Answer
# Python, 49 bytes

```
lambda n:len({2**-~k%n*(n&~-n)for k in range(n)})

```

An unnamed function accepting a positive integer, `n`, which returns a positive integer, the period.

**Try it online!**
> 0 votes

---
Tags: code-golf, number, binary, rational-numbers
---


title: What's a half on the clock?

text:
# Question
Title: What's a half on the clock?
In my room, I have this geeky clock (click for full size):

Most of these are not difficult to figure out, but the one for 4-o-clock is particularly tricky:

Normally, a fraction like 1/2 doesn't make sense in modular arithmetic since only integers are involved. The correct way, then, is to see this as the *inverse* of 2, or to put it another way,  is that number  where . Put this way, a moment's thought will reveal that  because .

However, simply finding the *multiplicative* inverse would be far too easy as a challenge. So let's bump up the difficulty to exponentiation, or in other words, finding the modular logarithm or discrete logarithm of 2. In this case, 3 is the modular logarithm of 2 with respect to 7. For those of you with number theory/abstract algebra background, this means calculating the multiplicative order of 2 modulo n.

## The Challenge

Given a positive **odd** integer `n` greater than 1, output the smallest positive integer `x` where .

## Examples

```
n x
3 2
5 4
7 3
9 6
11 10
13 12
15 4
17 8
19 18
21 6
23 11
25 20
27 18
29 28
31 5
33 10
35 12
37 36
39 12
41 20
43 14
45 12
47 23
49 21
51 8
53 52
55 20
57 18
59 58
61 60
63 6
65 12
67 66
69 22
71 35
73 9
75 20
77 30
79 39
81 54
83 82
85 8
87 28
89 11
91 12
93 10
95 36
97 48
99 30
101 100
103 51
105 12
107 106
109 36
111 36
113 28
115 44
117 12
119 24
121 110
123 20
125 100
127 7
129 14
131 130
133 18
135 36
137 68
139 138
141 46
143 60
145 28
147 42
149 148
151 15
153 24
155 20
157 52
159 52
161 33
163 162
165 20
167 83
169 156
171 18
173 172
175 60
177 58
179 178
181 180
183 60
185 36
187 40
189 18
191 95
193 96
195 12
197 196
199 99
201 66

```

# Answer
> 18 votes
# Jelly, 6 bytes

```
R2*%i1

```

Try it online!

### How it works

```
R2*%i1  Input: n

R       Range; yield [1, ..., n].
 2*     Compute [2**1, ..., 2**n].
   %    Hook; take all powers modulo n.
    i1  Get the index of the first 1.
        Indices are 1-based, so index k corresponds to the natural number k.

```

# Answer
> 13 votes
# Pyth - ~~9~~ 8 bytes

```
f!t.^2TQ

```

Test Suite.

`f`ilters from default of 1 till it finds some x such that modular exponentiation with 2 and the input equals 1.

# Answer
> 11 votes
## Python, 32 bytes

```
f=lambda n,t=2:t<2or-~f(n,2*t%n)

```

Starting with 2, doubles modulo n until the result is 1, recursively incrementing each time, and ending with a count of 1 for the initial value of 2.

# Answer
> 8 votes
## Mathematica, 24 bytes

```
2~MultiplicativeOrder~#&

```

I just used a built-in for this.

# Answer
> 7 votes
# APL, 8 bytes

```
1⍳⍨⊢|2*⍳

```

This is a monadic function train that accepts an integer on the right and returns an integer. To call it, assign it to a variable.

Explanation (calling the input `x`):

```
      2*⍳    ⍝ Compute 2^i for each i from 1 to x
   ⊢|        ⍝ Get each element of the resulting array modulo x
1⍳⍨          ⍝ Find the index of the first 1 in this array

```

Note that the result may be incorrect for large inputs since the exponential gets rounded.

# Answer
> 6 votes
# Pyth, 14 bytes

```
VQIq%^2hNQ1hNB

```

Explanation:

```
VQIq%^2hNQ1hNB

                # Implicit, Q = input
VQ              # For N in range(0, Q)
  Iq      1     # If equals 1
    %^2hNQ      # 2^(N + 1) % Q
           hN   # Print (N + 1)
             B  # Break

```

Try it here

# Answer
> 5 votes
# JavaScript (ES6), 28 bytes

```
f=(n,t=2)=>t<2||-~f(n,2*t%n)

```

Based on @xnor's brilliant recursive approach.

# Answer
> 5 votes
# 05AB1E, 11 bytes

Code:

```
DUG2NmX%iNq

```

Explanation:

```
DUG2NmX%iNq

D            # Duplicates the stack, or input when empty
 U           # Assign X to last item of the stack
  G          # For N in range(1, input)
   2Nm       # Calculates 2 ** N
      X      # Pushes X
       %     # Calculates the modulo of the last two items in the stack
        i    # If equals 1 or true, do { Nq }
         N   # Pushes N on top of the stack
          q  # Terminates the program
             # Implicit, nothing has printed, so we print the last item in the stack

```

# Answer
> 5 votes
# Julia, ~~25~~ 24 bytes

```
n->endof(1∪2.^(1:n)%n)

```

This is simple - `2.^(1:n)%n` finds the powers of 2 within the set,  is `union`, but serves as `unique` and returns only one of each unique power (and because it's an infix operator, I can union with 1 to save a byte over the `∪(2.^(1:n)%n)` approach). Then `endof` counts the number of unique powers, because once it hits 1, it'll just repeat the existing powers, so there'll be as many unique values as the power that produces 1.

# Answer
> 5 votes
## Seriously, 14 bytes

```
1,;╗R`╙╜@%`Míu

```

Hex Dump:

```
312c3bbb5260d3bd4025604da175

```

Try It Online

Explanation:

```
 ,;╗           Make 2 copies of input, put 1 in reg0
    R          push [0,1,...,n-1]
     `    `M   map the quoted function over the range
      ╙        do 2^n
       ╜@%     modulo the value in reg0
1           íu Find the 1-index of 1 in the list.

```

# Answer
> 4 votes
## Haskell, 30 bytes

```
n%1=1
n%t=1+n%(2*t`mod`n)
(%2)

```

Helper argument `t` is doubled modulo `n` each step until it equals 1.

# Answer
> 2 votes
# Japt, 17 bytes

```
1oU f@2pX %U¥1} g

```

Try it online!

This would be three bytes shorter if Japt had a "find the first item that matches this condition" function. *Starts work on one*

### How it works

```
1oU f@2pX %U¥1} g   // Implicit: U = input number
1oU                 // Generate a range of numbers from 1 to U.
                    // "Uo" is one byte shorter, but the result would always be 0.
    f@        }     // Filter: keep only the items X that satisfy this condition:
      2pX %U¥1      //  2 to the power of X, mod U, is equal to 1.
                g   // Get the first item in the resulting list.
                    // Implicit: output last expression

```

# Answer
> 2 votes
# Julia, ~~33~~ 26 bytes

```
n->findfirst(2.^(1:n)%n,1)

```

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

We construct an array as 2 raised to each integer power from 1 to `n`, then we find the index of the first 1 in this array.

Saved 7 bytes thanks to Glen O!

# Answer
> 2 votes
# CJam, 15 bytes

```
2qi,:)f#_,f%1#)

```

Peter Taylor saved a byte. Neat!

# Answer
> 2 votes
# PARI/GP, 20 bytes

```
n->znorder(Mod(2,n))

```

# Answer
> 2 votes
## Perl 5, 29 bytes

```
$n=<>;{2**++$_%$n-1?redo:say}

```

Hat tip.

# Answer
> 2 votes
# MATL, 13 bytes

```
it:Hw^w\1=f1)

```

Runs on Octave with the current GitHub commit of the compiler.

Works for input up to `51` (due to limitations of the `double` data type).

### Example

```
>> matl it:Hw^w\1=f1)
> 17
8

```

### Explanation

```
i             % input, "N"
t:            % vector from 1 to N
Hw^           % 2 raised to that vector, element-wise
w\            % modulo N
1=            % true if it equals 1, element-wise
f1)           % index of first "true" value

```

# Answer
> 2 votes
# Unicorn, ~~1307 1062~~ 976 bytes

```
( ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨  (     2 )    ✨✨✨✨✨✨✨✨✨✨ 2    ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ (   2 ✨✨✨✨✨✨✨    ) ) (  ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨     ( ) )

```

I'm attempting to make unicorn a serious golfing language but that's a bit difficult...

Hopefully I'll find a way to retain the "unicorn-ness" of the language while making *much* less bytes

---

Picture:

##

Uses a custom encoding.

This answer is non-competing because it uses a version of Unicorn made after this language

# Answer
> 2 votes
# , 11 chars / 22 bytes

```
↻2ⁿḁ%ï>1)⧺ḁ

```

`Try it here (Firefox only).`

Uses a while loop. This is one of the few times a while loop is better than mapping over a range.

# Explanation

```
          // implicit: ï = input, ḁ = 1
↻2ⁿḁ%ï>1) // while 2 to the power of ḁ mod input is greater than 1
  ⧺ḁ      // increment ḁ
          // implicit output

```

# Answer
> 1 votes
# Prolog, 55 bytes

**Code:**

```
N*X:-powm(2,X,N)=:=1,write(X);Z is X+1,N*Z.
p(N):-N*1.

```

**Explained:**

```
N*X:-powm(2,X,N)=:=1, % IF 2^X mod N == 1
     write(X)         % Print X
     ;Z is X+1,       % ELSE increase exponent X
     N*Z.             % Recurse
p(N):-N*1.            % Start testing with 2^1

```

**Example:**

```
p(195).
12

```

Try it online here

# Answer
> 1 votes
# Japt , 9 bytes

```
©2pU %N¶1

```

Try it

# Answer
> 1 votes
# Python 3, 37 bytes

```
f=lambda n,x=1:2**x%n==1or 1+f(n,x+1)

```

Try it online!

Thanks Maria Miller for saving me 1 byte.

# Answer
> 1 votes
# C (gcc), 35 bytes

```
i;f(n){for(i=1;(1<<i++)%n-1;);--i;}

```

Gives accurate results up to \\$x=31\\$, otherwise the result is 32.

Try it online!

---
Tags: code-golf, number-theory
---


title: Error-correct text

text:
# Question
Title: Error-correct text
Correct a single-letter typo in a fixed text.

**Input:** The paragraph below but with exactly one typo, where a single letter `a-zA-Z` is replaced by a different letter `a-zA-Z`. To be clear, the letter isn't replaced everywhere it appears, but just in that one place. For example, the first word "In" might become "IZ". Non-letter characters like spaces or punctuation cannot be affected.

**Output:** The paragraph exactly as below, without the typo. A trailing newline is OK.

> In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

TIO with text

The text is taken from the Wikipedia article Error detection and correction. But, your code may not fetch the text from Wikipedia or elsewhere, as per the standard loophole.

Any site-default string I/O is acceptable. Fewest bytes wins. Please check that your solution works for all 23001 possible inputs, if you're able to run that much.

# Answer
# Python 2, ~~136~~ ... ~~97~~ 96 bytes

```
def f(s,n=0):k=s[:n>>7]+chr(n%128)+s[n/128+1:];return 0x2e838ca8118c7496+hash(k)and f(s,n+1)or k

```

Try it online!

Simply replace each character in the given input with each possible letter, then check if the hash matches the correct string. I use Python 2 `hash` function, which is deterministic and has no collision within our search space.

This program checks if the function returns correct output for all possible input. It takes ~2 hours to run on my computer

*Thanks @Jitse for saving -22 bytes with recursion!*
> 21 votes

# Answer
# MATLAB with Communications Toolbox, ~~88~~ ~~64~~ 59 bytes

```
Z=rsdec(gf([+input('') 879 323],10),532,530);disp([Z.x ''])

```

This uses a (1023, 1021) Reed-Solomon code shortened to (532, 530). This is a systematic, non-binary code with alphabet size 1023, which can correct any single-symbol error.

The number 1023 has been selected because, in Reed-Solomon codes, both the alphabet size and the maximum input length must be of the form *n* = 2*m*−1 for *m* integer. Since the input text has alphabet size bounded by 95 (number of printable ASCII characters) and length 530, *m* = 9 (*n* = 511) would be too small, and *m* = 10 (*n* = 1023) is enough.

The error-correcting code has first been applied to the input message to obtain the parity bits. This has been done offline. The submitted program only implements the decoder.

### Encoder

Each ASCII character in the input is considered as a symbol from a 1023-size alphabet, and then the code is applied using the `gf` and `rsenc` functions.

Note that the code is not part of the submitted solution, and is not golfed.

```
x = 'In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.';
x_ext = [zeros(1,491) double(x)]; % convert to code points. Zero-pad to length 1021
y_ext = rsenc(gf(x_ext, 10), 1023, 1021); % encode
y = y_ext(492:end); % remove zero padding
y = double(y.x); % convert to double
check_symbols = y(numel(x)+1:end)

```

This gives `check_symbols = [879 323]`. The encoded codeword is the input expressed as code points with these two numbers appended.

### Decoder

This is a program that reads the input text as a string from STDIN and displays the corrected text in STDOUT.

```
Z=rsdec(gf([+input('') 879 323],10),532,530);disp([Z.x ''])

```

The parity-check symbols are appended to the code points of the input, and the result is provided to the decoder with code parameters `532`, `530`, which define the shortened code. This causes the decoder to implicitly assume zero-padding. The `gf` and `rsdec` functions are used for this. The result `Z` is converted to char.

Note that `+` is used instead of `double` to save bytes; and similarly, `[... '']` is used instead of `char(...)`.

### Example run
> 14 votes

# Answer
# Jelly,  ~~30~~  25 bytes

```
JœPjⱮØẠɗ€⁸Ẏ1,ȷ9ḥ⁼“×Ṙ*-’ƲƇ

```

A full program printing the result (as a monadic Link it yields a list of one list of characters).

**Try it online!**

### How?

Changes each character (including non-`A-Za-z` ones) to every character in `A-Za-z` and checks if a hashed value is equal to that of the required input. The hash function was chosen so that none of the \\$450 \times 51 + 79 \times 52 = 27058\\$ possible states for each \\$451 \times 51 = 23001\\$ inputs hash to the same value as the expected output\*.

The program to check for collisions is here (I split the 2-char check into 5 parts and ran for over 1h to completion).

* smaller hash functions might work for just visited states which could save bytes (although if a collision does exist further on than the correct match then an  must be appended).
> 11 votes

# Answer
# C (gcc), ~~260~~ ~~259~~ ~~247~~ ~~226~~ ~~223~~ ~~217~~ ~~215~~ ~~214~~ ~~198~~ 189 bytes

```
y;*R=L"ė|h0\"k5&j4Đzm7ſ4sM6~0=a[z@z4zp4y j,-#3#mu7qĘdd";char n,k,t,u,r,c,x;f(char*s){for(n=y=23;n--;c?u=n:0,r?x=r,t=n:0)for(r=R[n],c=R[n+y],k=y;k--;r^=s[y*n+k])c^=s[y*k+n];s[y*t+u]^=x;}

```

Try it online!

---

*Now with 9 fewer bytes, thanks to @ceilingcat!*

---

*Thanks to @Bubbler for golfing 16 bytes off!*

*I haven't updated the readable version to include @Bubbler's modifications, but the biggest improvement is in the XOR computation loop. The shorter approach starts at the desired values `R[n]` and `R[n+23]`, and repeatedly does an XOR, which will yield `0` at the end (except at the bad character). My answer had the loop starting at `0`, and checking for the values `R[n]` and `R[n+23]` at the end.*

---

**I've added a readable version of the code, commented and with whitespace, at the end of the answer.**

---

This doesn't use an md5sum or hash function, since that's not available in C without using an external library. Here's how this program works instead:

Imagine the input text, except for the final `'.'`, arranged in a square. The XOR of each row and the XOR of each column are computed, and they're compared with the correct XOR values from the original text. One row XOR value and one column XOR value will not be what they should, and that tells you which character to fix, and which bits to flip to make it right.

---

---

Here's the more readable version of my last version of the code (before @Bubbler and @ceilingcat's improvements), commented and with whitespace:

```
f(char*s)
   {
/*****
   The original text contains 530 characters.

   Using the fact that 23 * 23 = 529, view the text as
   arranged in a 23 x 23 square (plus the '.' at the end,
   which doesn't matter since it can't be changed).
*****/

// The string R below is 46 characters long.
// It consists of the XOR of each of the 23 rows in the original text,
// folllowed by the XOR of each of the 23 columns.
    char *R = "\x17|h0\"k5&j4\x10zm7\x7f""4sM6~0=a[z@z4zp4y j,-#3#mu7q\030dd",
         n,k,t,u,r,c,x;

    for (n = 23; n--; )
       {
// Compute the XOR of row n of the input string, and store it in r.
// In the same loop, compute the XOR of column n of the input, and store it in c.
        r = c = 0;

        for (k = 23; k--; )
           {
            r ^= s[23*n+k];
            c ^= s[23*k+n];
           }

// If the computed row value doesn't equal the row value from the original text,
// save the bad row number in t.  Also save (in x) the bits that are wrong.
        if (r-R[n])
          {
           t=n;
           x=r^R[n];
          }

// If the computed column value doesn't equal the column value from the original text,
// save the bad column number in u.  There's no need to save the bits that are wrong,
// since they're guaranteed to be the same as the bits that are wrong for the row.
        u = c-R[n+23] ? n : u; // Golfed equivalent of:
                               // if (c != R[n+23]) u=n;
       }

// Fix the bad character, which is in row t and column u, by flipping the bits in x.
     s[23*t+u]^=x;
    }

```
> 10 votes

# Answer
# Ruby, ~~122 121 119~~ 113 bytes

```
->s{s[a=(0..9).sum{|x|",JEDI>(:6#"[x].ord==(0..529).sum{|w|s[w].ord*w[x]}%84?0:2**x}]=""<<50998-s.sum+s[a].ord;s}

```

Try it online!

### How:

Compare partial sums applying different masks to the string:

```
In information theory and coding theory with applicati [...]
X X X X X X X X X X X X X X X X X X X X X X X X X X X  -> "I nomto hoyad [...]"
XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX  XX -> "Innfmaonhey d [...]"
XXXX    XXXX    XXXX    XXXX    XXXX    XXXX    XXXX   -> "In imatiheord [...]"

```

With 10 partial sums (and the total sum of the original string) we have enough information to detect and fix a single error.

Incidentally, the partial sums modulo 84 converted to ASCII form the word "JEDI" and an Australian smiley, which I hope bring some imaginary bonus point.

### Why not hash?

From the Ruby documentation:

***The hash value for an object may not be identical across invocations or implementations of Ruby. If you need a stable identifier across Ruby invocations and implementations you will need to generate one with a custom method.***

I'm lazy. That's why.
> 8 votes

# Answer
# JavaScript (Node.js), 78 bytes

This is a port of xnor's great answer.

```
s=>(t=118,u=10340,g=k=>Buffer(s).map(x=>(u+=t-=k&x-96)-531*t?x:x+t))(g(~0))+''

```

Try it online!

---

# JavaScript (Node.js),  ~~121 118~~  116 bytes

```
s=>[...s+'jEIM'].some(c=>[...s].some(C=>Buffer(o=p+c+s.slice(++i)).map(c=>k=k*99^c,k=p+=C)|k==0x6B9400B8,i=p=''))&&o

```

Try 10 random test cases online!

## How?

### Replacement letters

All letters in the original paragraph appear at least twice, except ***j***, ***E***, ***I*** and ***M*** that appear only once and may disappear in the modified paragraph.

That's why we do:

```
[...s + 'jEIM'].some(c => ...)

```

This way, it is guaranteed that each possible replacement letter is tried.

### Hash

Using a built-in hash would be rather lengthy in Node:

```
require('crypto').createHash('md5').update(string).digest('hex')

```

Instead of that, we use the following custom 32-bit hash:

```
Buffer(string).map(c => k = k * 99 ^ c, k = 0)

```

This was (rather painfully) tested against all possible inputs.
> 6 votes

# Answer
# Python 3, 83 bytes

```
def f(s,t=118,u=-10340):
 for x in s:t-=x-96;u-=t
 *l,=s;l[u//t]+=t;return bytes(l)

```

Try it online!

We compute a custom numerical checksum that let us locate and fix the error. This means don't need to try possible changes until we find one that works. As a result, the code run very fast, letting us test all 23,001 possible inputs in under 2 seconds in the linked TIO.

Input and output are as bytestrings, which requires Python 3.

**The checksum**

It's a bit easier to understand the idea using the code below.

```
def f(s):
 t=50998-sum(s)
 k=13447420-sum(i*x for i,x in enumerate(s))
 i=k//t
 l=list(s)
 l[i]+=t
 return bytes(l)

```

Try it online!

The core is the checksum, which gives two values. The correct string (and only it) gives the values `(50998, 13447420)`, which are used in the code above.

```
def checksum(s):
 t=sum(s)
 u=sum(i*x for i,x in enumerate(s))
 return(t,u)

```

Try it online!

The checksum not only lets us know whether the string is correct, but the difference from the checksum to the real string lets us deduce what the error is and fix it. This doesn't rely on the typoes being with letters.

**How does it work?**

The checksum consists of two parts, each of which is a number.

The part `t=sum(s)` is simply the sum of the (ASCII) values in the string. Given a string with a single typo from the original, we can figure out the numerical difference between the original and typoed character by comparing the sum to the original's sum of 50998. For example, if we find a sum of 51001, we know that the typo increased a character by 3, such as `a->d` or `M->P`.

So, we know the amount that the character is off, but not which one. That is, we don't know the index. For that, we use the additional information given in the second value `u` of the checksum,

```
u=sum(i*x for i,x in enumerate(s))

```

Here, we add up all the characters, but each one is given a multiplier equal to its index, so zero times the initial character plus one times the next one, up to 529 times the last one.

The idea is similar to a classic puzzle:

> You have 10 bags of coins. Each bag has 10 gold coins that each weigh 10 grams, except one bag is filled with lighter counterfeits that each weigh 9 grams but otherwise look normal. You have a digital scale that displays exact numerical weight. How can you determine which bag has the counterfeits, using only a single weighing?

The solution is to number the bags 1 to 10, and put 1 coin from bag 1 on the scale, 2 coins from bag 2, up to 10 coins from bag 10. That's 55 coins total, so if all the coins had been real, they'd weigh 550 grams. But, each counterfeit coins lowers the total weight by 1 gram. So, since the fake bag will contribute its index-number of underweight coins, which is however many grams under 550 we see. This tell uses which bag is fake. (We could also have zero-indexed 0-9 and used 45 coins.)

The checksum `u` works just like this. Suppose that the typo is index `j`, and it's off by an amount `d` as determined by the first checksum value `t`. Then, the index `j` will contribute to the error in `u` with a multiplier equal to `j`, so it will be off by `j*d`. Knowing both `d` and `j*d` lets us find the typoed index `j` by dividing.

**Fixing the error**

The error is fixed as `*l,=s;l[u//t]+=t;return bytes(l)`. This converts the string to a list, modifies the indexed value in place with `+=`, and then converts back a bytestring. This is pretty ugly. Note that strings and bytestring are immutable in Python, unlike lists, so we couldn't just modify the string directly.

I'm still not really clear what default string I/O permits, despite having given it the go-ahead in the challenge. If we can do input and output on lists of ASCII values, then we can save a lot of code, especially by modifying the input list in place.

*61 bytes*

```
def f(l,t=118,u=-10340):
 for x in l:t-=x-96;u-=t
 l[u//t]+=t

```

Try it online!

**Optimizations**

```
def f(s,t=118,u=-10340):
 for x in s:t-=x-96;u-=t
 *l,=s;l[u//t]+=t;return bytes(l)

```

We save some characters in the above code with a few optimizations.

Instead of computing the checksum values `(t,u)` and subtracting the target values, we get the differences directly by initializing `t` and `u` to to their target values and subtracting the contributions for each character iteratively. Passing in the original string would make them end up both as zero, giving a divide-by-zero error in the code.

Instead of using `enumerate` to compute the weighted sum `u`, we repeatedly subtract the running sum `t`, which subtracts each character value successively more times. This effectively computes the weighted sum for the reversed string, that is with the biggest weights at the front. But we end up with a negative index that goes from the back, so it works out.

Finally, we are able to obtain shorter-to-write checksum values `(t,u) = (118,-10340)` instead of `(50998, 13447420)` by using a slightly different checksum that first subtracts 96 from each ASCII value. This is the rounded average ASCII value for the text, so subtracting it makes the string values average out to roughly zero. This make the checksums have both positive and negative summands that make them close to zero. These values of `(118,-10340)` are tantalizingly close to being one digit shorter, and one is negative, but I didn't see a way to shorten them.

I was originally planning to do all checksums computations modulo some prime to make the resulting values shorter to write, but they are short enough anyway that it's not nearly worth it, even without the optimization above.
> 6 votes

# Answer
# Perl 5 `-MDigest::MD5=md5_base64 -F`, 86 bytes

```
map{//;for$j(a..z,A..Z){$_=$j;(aNCL7lqAQsi7llQYWh7r8A eq md5_base64@F)&&say@F}$_=$'}@F

```

Try it online!

Brute force method. Runs each character position through all possibilities until it finds that the md5 checksum matches the original message.

Proof that no other single character change matches the checksum.
> 5 votes

# Answer
# C (gcc), ~~181~~ 163 bytes

```
n,*R=L"[z@z4zp4y j,-#3#mu7qĘddė|h0\"k5&j4Đzm7ſ4sM6~0=a",u,v,x,y;f(char*s){for(n=529;n--;s[n]^=u&v)for(y=23,u=R[n/y+y],v=R[x=n%y];y--;u^=s[n-x+y])v^=s[23*y+x];}

```

Try it online!

-13 bytes thanks to @ceilingcat using the L-string trick. -5 bytes by moving the remaining local variables to the global scope; it doesn't matter if they are `int` or `char` because the ultimate destination is `s[n]^=u&v`, i.e. assignment to `char`.

A small improvement over Mitchell Spector's C answer. Instead of keeping track of which row and column have the typo, this one computes for *every char* the XOR-sums of its own row and column. If both are nonzero (they are necessarily equal), correct the current cell (which is the only offending cell) right away.

### Commented

```
// declare global(?) variables n,u,v,x,y
// and initialize *R to point to the XOR hash array
n,*R=L"[z@z4zp4y j,-#3#mu7qĘddė|h0\"k5&j4Đzm7ſ4sM6~0=a",u,v,x,y;

// the function: takes char array and modifies it in place
f(char*s){
  // loop over first 529 chars backwards...
  for(n=529;n--;s[n]^=u&v)
    // loop over the chars on the same row/col as n,
    // initialize u=row hash, v=col hash
    for(y=23,u=R[n/y+y],v=R[x=n%y];y--;
      // collect XOR sums of row/col
      u^=s[n-x+y])v^=s[23*y+x];
    // at this point, go back to s[n]^=u&v
    // i.e. fix the typo if both sums are nonzero
}

```
> 4 votes

# Answer
# PHP, 91 bytes

```
for(;($a=$argn)[$i];$i++){for($j=9;++$j<123;crc32($a)!=3603504069?:die($a))$a[$i]=chr($j);}

```

Try it online!

Brute force version, actually checking with replacing each letter with all ASCII between codes 10 and 122 (many useless checks, but it saves bytes for example initializing `$j` to 9 instead of 64, those results can't be positive anyway)

As noted by @LuisMendo and @PeterCordes (thanks), this works because `crc32` can reliably detect every burst of up to 32 bit errors, and in the ASCII-encoded input, replacing a character will cause a burst of 14 (7\*2) bit errors at most.
> 4 votes

# Answer
# APL (Dyalog Unicode), 94 bytes

```
g←252|1⊥⊢⍪⎕AV⍳⊣
252|⊢+0,⍨∘(,'⊂⍷≠Eæ×(í/7Ãs·¨\=Ð¨⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-

```

Try it online!

Uses the vector of Unicode codepoints as the I/O format. Otherwise it would cost me 11 bytes to convert from/to strings:

# APL (Dyalog Unicode), 105 bytes

```
g←252|1⊥⊢⍪⎕AV⍳⊣
⎕UCS 252|46,⍨∘(,-+'⊂⍷≠Eæ×(í/7Ãs·¨\=Ð¨⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-∘⎕UCS

```

Try it online!

Uses the row/col checksum approach as in Mitchell Spector's C answer. Because bitwise XOR is not a built-in function in APL, I had to use plain sum and negation instead.

### How it works

```
g←252|1⊥⊢⍪⎕AV⍳⊣  ⍝ Auxiliary function: checksums g matrix → checksum vector
          ⎕AV⍳⊣  ⍝ Convert string written in APL SBCS to integer
        ⊢⍪       ⍝ Append the checksum vector at the bottom of the matrix
      1⊥         ⍝ Column-wise sum
  252|           ⍝ Modulo 252

⍝ Main function: Correct the typo based on checksum
252|⊢+0,⍨∘(,'⊂⍷≠Eæ×(í/7Ãs·¨\=Ð¨⍎ëáØ@'∘g∘.⌊⍨'#⌿O⍒`=~{└⊤Üã/cëÖ¶⌹⌹bð'g⍉)23 23⍴-
23 23⍴-  ⍝ Negate each element and reshape into 23x23 matrix, discarding the last '.'
(...)    ⍝ Pass to the inner tacit function...
'...'g⍉    ⍝ Check rows against the row checksums
∘.⌊⍨       ⍝ Outer product by minimum (rows and columns reversed) with...
'...'∘g    ⍝ Check columns against the column checksums
           ⍝ Result = all-zero matrix except at the typo (difference mod 252)
,          ⍝ Flatten the result
0,⍨∘     ⍝ Append a zero to account for the last '.'
252|⊢+   ⍝ Fix the typo using the offset

```
> 2 votes

# Answer
# Java 10, ~~140~~ ~~139~~ 137 bytes

```
s->{var r=s;for(int i=0;;i++)for(var c='z';c>65;c-=c==97?7:1)if((r=s.substring(0,i)+c+s.substring(i+1)).hashCode()==0xA89D0862)return r;}

```

-2 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

Also uses an hash like most other answers. The hash of the expected text is `-1466103710`. All other possible double replacements of letters cause no collisions, which has been verified locally with this test program. (Obviously times out on TIO since it has to do \\$(52\times 530)^2=759\text{,}553\text{,}600\\$ iterations, including calculating the hash-code and substituting characters in each iteration. It takes between 8 and 9 minutes locally.)

```
s->{                    // Method with String as both parameter and return-type
  var r=s;              //  Result-String (starting at the input to save bytes)
  for(int i=0;;i++)     //  Loop `i` upwards from 0 indefintely:
    for(var c='z';c>65; //   Inner loop over the characters `c` in the ASCII range ['z','A']
        c-=c==97?7:1)   //   skipping the characters "`_^]\[" between 'a' and 'Z':
      if((r=s           //    Set `r` to the input-String,
             .substring(0,i)+c+s.substring(i+1))
                        //    with the `i`'th character replaced with `c`
         .hashCode()==0xA89D0862)
                        //    And if its hash-code is -1466103710:
        return r;}      //     Return `r` as result

```
> 2 votes

# Answer
# Charcoal, ~~52~~ 49 bytes

```
θＪ↨²⮌Ｅ =&%ce9KG*¬⁼§γΣＥΦθ＆μＸ²κ⌕γλι⁰§γ⁻²⁸ΣＥθ∧⁻κⅈ⌕γι

```

Try it online! Link is to verbose version of code. Works with all printable ASCII, not just letters. I originally wanted to do a Hamming check on all of the letters in the input but I was too ill to implement that at the time and by the time I got better I realised that @GB's modular sums would suit Charcoal better anyway. Explanation:

```
θ

```

Print the input string.

```
Ｅ =&%ce9KG*

```

Loop over 10 partial sums. These characters are the result of cyclically indexing the appropriate sum from the correct input back into the predefined printable ASCII variable.

```
ΣＥΦθ＆μＸ²κ⌕γλ

```

Filter on the desired characters for this sum and take the sum of their indices within the predefined printable ASCII variable.

```
Ｊ↨²⮌...¬⁼§γ...ι⁰

```

Interpret those sums that don't match as a number in base 2 LSB first, and jump to that character, which will be the incorrect character.

```
§γ⁻²⁸ΣＥθ∧⁻κⅈ⌕γι

```

Subtract the sum of all the other printable character indices from 28 which gives the index (modulo 95) of the current character.

@xnor's algorithm can be implemented in 42 bytes:

```
θ≔⁻⁵⁰⁹⁹⁸ΣＥθ℅ιηＪ÷⁻¹³⁴⁴⁷⁴²⁰ΣＥθ×℅ικη⁰§γ⁺η⌕γＫＫ

```

Try it online! Link is to verbose version of code. Works with all printable ASCII, not just letters, but fails if the input is correct (would cost 3 bytes to fix). Explanation:

```
θ

```

Print the input string.

```
≔⁻⁵⁰⁹⁹⁸ΣＥθ℅ιη

```

Calculate the size of the error.

```
Ｊ÷⁻¹³⁴⁴⁷⁴²⁰ΣＥθ×℅ικη⁰

```

Calculate and jump to the position of the error.

```
§γ⁺η⌕γＫＫ

```

Correct the character that is in error.
> 2 votes

# Answer
# C (gcc), 125 bytes

Note: my code includes 2 unprintable characters `\x0c` and `\0x01` in the string literal which aren't visible in the snippet.

```
b,i,j,m,n;C(char*T){b=i=n=0;for(;i<10;b|=("N<Syr4Zd"[i]!=m)<<i++)for(m=j=0;T[j];n^=!i*T[j++])m^=(1&j>>i)*T[j];T[b]^=120^n;}

```

Try it online!

The `i`th character in the literal is the XOR of all the characters in the original text at positions whose `i`th bit is `1`. The program performs the same XOR on the modified text. The computed value will be different iff the modified character is in a position with `i`th bit `1`. This gives us all the bits of the modified character's position.

Finally, we modify the character such that the XOR of all characters is that of the original text(120).
> 2 votes

# Answer
# Python 3, 364 bytes

Output is bz2 encoded. Input is ignored. Code contains unprintable characters, so here is the hex version. Utf-8 encoded version is 55 bytes regular code + 309 bytes compressed data. See commented lines in the header of the TIO link.

```
import bz2
lambda s:bz2.decompress(b'BZh91AY&SY\xd3\xaa\xfe\xfd\x00\x00(\x15\x80@\x05\x02"?\xf7\xff\xa00\x01F\n\x86\x82bI\xfa\x14\xf4&\x99\r\n\x00\x06\x80\x00\x04\xa6\x84\x9a\x9e\xd455<\xa6\x99\x19\x10o\xcf|b5oN"\x06V\xab\xd0\xa3\x8awA\xbb}\x8a=\xa6\xcc\x9b#\x1a\xcd\x94Q\x83%Lp\xc9-n\x99\xd9\xee\xb5\xbc\xb4xc\x1a\xeaz\x03\xe49*\x90\xc9E\xf8\xa1y\xb7q\xcb!O\xbeA\xf5\rj\xd9Vg2\xec\xe9&A\x08\xb0\x91\x0c\xde\x05_m\xeb.\xa8\x9a~\x0b?\xec\x0e+\x14\xf0q\x05\x19\xa3O\x84\xb0\xbb\xea\xb6\xc3d\xab\xa6\xa3\x1b\x02c\xd3\x8fE\x99F\xf8\xdf\x07\x95\xdam\x10\x1b!\xb0m\xd7m\xb9\xdf\x9d:&\x0e\x13\xa4{S\xa3\x9ao\x95\x98\r\x995#\xdb\xbb\x17\x1d`2\xd0\x1d7$\xb5E\xe1Y9\xf4u\xbd\xcc9\x01va\x0e\x12\x7fA\x06\xa6[\xceg>\x05\xc8T\xaf\x87\x1a\t\x18Hcq\x87\x04\xa2\xa5\xf8\xc2\x0643\xbci\x14\x14\xbe5\xd77\x99w\'\xba&\r\x19b\x1ck\x16\x10&v\xd0\xb9\xe1W\xc3\x82{\xbe\xdb-\x81\xb0\xac\xc8A\xfc]\xc9\x14\xe1BCN\xab\xfb\xf4').decode('ascii')

```

Try it online!
> 0 votes

---
Tags: code-golf, text-processing, error-correction
---


title: Counting polyominoes on (hyper-)cubes

text:
# Question
Title: Counting polyominoes on (hyper-)cubes
This challenge like some of my previous challenges will have you counting free polyforms, which are generalizations of Tetris pieces.

This challenge will have you count polyomino-like polyforms on hypercubes. In particular, this challenge is to write a program that takes in three parameters:

* `n`, which represents an \\$n\\$-dimensional hypercube,
* `m`, which represents \\$m\\$-dimensional faces of the hypercube, and
* `k`, which represents the number of cells in the polyform,

and outputs the number of ways to choose \\$k\\$ (\\$m\\$-dimensional) faces on the \\$n\\$-cube such that the \\$m\\$-faces are connected at \\$(m-1)\\$-faces. These polyforms are "free" which means they should be counted up to the rotations/reflections of the \\$n\\$-cube.

Again, this is a challenge, so shortest code wins.

---

# Example 1

Okay, this is all very abstract, so this warrants an example.

When `n=3`, we're talking about the \\$3\\$-dimensional (ordinary) cube. When `m=2` this means we're talking about the \\$2\\$-dimensional (square) faces. And we're talking about `k` of these, joined along \\$1\\$-dimensional faces (edges).

When `k=3`, there are two such polyforms (on the left) up to rotations/reflections of the cube. When `k=4` there are also two polyforms (on the right).

# Example 2

In this second example, `n=3` still, so we're again talking about the \\$3\\$-dimensional (ordinary) cube. When `m=1` this means we're talking about the \\$1\\$-dimensional faces (edges). And we're talking about `k` of these, joined along \\$0\\$-dimensional faces (corners).

When `k=4` there are four such polyforms.

---

# Data

```
n | m | k | f(n,m,k)
--+---+---+---------
3 | 2 | 3 | 2       (Example 1, left)
3 | 2 | 4 | 2       (Example 1, right)
3 | 1 | 4 | 4       (Example 2)
2 | 1 | 2 | 1
3 | 0 | 0 | 1
3 | 0 | 1 | 1
3 | 0 | 2 | 0
3 | 1 | 3 | 3
3 | 1 | 5 | 9
3 | 1 | 6 | 14
3 | 1 | 7 | 19
3 | 1 | 8 | 16
3 | 1 | 9 | 9
3 | 3 | 0 | 1
3 | 3 | 1 | 1
3 | 3 | 2 | 0
4 | 1 | 4 | 7
4 | 1 | 5 | 21
4 | 1 | 6 | 72
4 | 1 | 7 | 269
4 | 1 | 8 | 994
4 | 1 | 9 | 3615
4 | 2 | 3 | 5
4 | 2 | 4 | 12
4 | 2 | 5 | 47
5 | 1 | 4 | 7
5 | 1 | 5 | 27
5 | 2 | 0 | 1
5 | 2 | 1 | 1
5 | 2 | 2 | 1
5 | 2 | 3 | 5
5 | 2 | 4 | 20
5 | 3 | 4 | 16
5 | 3 | 5 | 73
5 | 4 | 4 | 3
6 | 1 | 6 | 121

```

# Answer
> 2 votes
# Python 3, 389

```
import itertools as I
S=sorted
P=I.product
def C(n,m,k):
 Q=[((-1,)*(n-m)+(0,)*m,)]
 for i in' '*(k-1):Q=set(tuple(S(q+(v,)))for q in Q for v in P(*[(-1,0,1)]*n)if sum(map(abs,v))==n-m if not v in q and any(sum((a!=b)*(1+2*a*b)for a,b in zip(v,u))==2for u in q))
 return sum(all(S(q)<=S(zip(*r))for X in I.permutations(zip(*q))for r in P(*((p,tuple(-x for x in p)) for p in X)))for q in Q)

```

Try it online!

Basically just finds all connected polyominos, and discards ones which can be rotated into a lexicographically smaller polyomino, with rotations being brute-forced.

Can definitely be improved but it's my bedtime.

---
Tags: code-golf, geometry, combinatorics, polyomino
---