9
\$\begingroup\$

Background

Consider the shape \$T(n)\$ consisting of a triangular array of \$\frac{n(n+1)}{2}\$ unit regular hexagons:

enter image description here

John Conway proved that \$n = 12k + 0,2,9,11\$ if and only if \$T(n)\$ can be tiled (i.e. exactly covered without overlapping) with \$T(2)\$. At the same time, he also proved that no coloring argument could prove the fact. (Yes, this is yet another Conway challenge.)

Challenge

Let's define \$a_n\$ as the number of distinct tilings of \$T(n)\$ by \$T(2)\$. Compute as many terms of \$a_n\$ as possible in 10 minutes.

Reflection and/or rotation of a tiling is considered distinct from itself, unless the two are identical.

The program that prints the largest number of terms wins. In case of tie, the one that prints the last term in shorter time wins.

I have a Windows 10 machine with Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz and 32GB RAM, with Ubuntu 18.04 installed in WSL. Please include the instructions to run your code and where it works (Windows or Linux).

Output format (with test cases)

The submission should print the results infinitely for each \$n\$ starting from 0. Each line should include the values of \$n\$ and \$a_n\$. Here is first 21 lines of the expected output:

0 1
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 2
10 0
11 8
12 12
13 0
14 72
15 0
16 0
17 0
18 0
19 0
20 0
21 185328
22 0
23 4736520
24 21617456
25 0
26 912370744
27 0
28 0
29 0
30 0
31 0
32 0

Test cases for \$n \le 20\$ are generated using a naive Python 3 program. \$a_{21}\$ through \$a_{32}\$ (meaningful highest being \$a_{26}\$) were found using Arnauld's JS submission.

Notably, neither the full sequence 1, 0, 1, 0, 0, 0, ... nor the stripped-down one 1, 1, 2, 8, 12, 72, ... is on OEIS yet. As I don't have an OEIS account, I will let anyone interested to post this sequence (both versions) to OEIS (please leave a comment before you do). The sequence of nonzero indices is A072065. Edit: The sequence is on A334875, thanks to Lyxal.

Leaderboard

  1. Rust with rustc -O by Anders Kaseorg, Score 44 at 45s
  2. C++ with g++ -O3 by l4m2, Score 35 at 7min
  3. Javascript with node by Arnauld, Score 32 at 1.8s

Pending

  • (none)
\$\endgroup\$
6
  • \$\begingroup\$ Do reflections / rotations of a tiling count as the same tiling or different? \$\endgroup\$ May 13 '20 at 0:55
  • \$\begingroup\$ @LevelRiverSt They count as different (unless they exactly match, of course). e.g. T(9) has only one tiling modulo reflection/rotation, which has 3-fold rotational symmetry. It is distinct from its mirror image, so a_9 = 2. \$\endgroup\$
    – Bubbler
    May 13 '20 at 1:03
  • \$\begingroup\$ It start to seem that faster runner need external storage \$\endgroup\$
    – l4m2
    May 15 '20 at 17:12
  • \$\begingroup\$ @Bubbler are you sure conway meant T(2) by "tribone"? it doesn't look like a bone \$\endgroup\$
    – ngn
    May 16 '20 at 15:42
  • \$\begingroup\$ @ngn Changed the title, though I had to describe it in a roundabout way because the T(2) has only a generic name. Does it sound good now? (Note to others: multiple papers describe a "tribone" as a tile made of three hexagons in a straight line. The only source of naming T(2) a tribone seems to be Tilings by Ardila and Stanley, which I suspect to be wrong.) \$\endgroup\$
    – Bubbler
    May 20 '20 at 0:47
8
\$\begingroup\$

JavaScript (Node.js), N =  22 25  32 in ~2 seconds

A recursive search using bit masks and a cache to keep track of patterns whose result is already known.

It doesn't make much sense to try go further in Node. Using a binary matrix is significantly slower and BigInts are even slower. It should rather be ported to a language natively supporting 64-bit integers.

'use strict';

let ts = new Date;

for(let n = 0; n <= 32; n++) {
  console.log(
    n.toString().padStart(2) + ' ' +
    solve(n).toString().padStart(10) + ' ' +
    '(' + ((new Date - ts) / 1000).toFixed(2) + ')'
  );
}

function solve(n) {
  // trivial cases
  if(![0, 2, 9, 11].includes(n % 12)) {
    return 0;
  }
  if(n == 0) {
    return 1;
  }

  // We work on a triangle stored as an array of bit masks:
  //   8 7 6 5 4 3 2 1 0 | 
  //  -------------------+---  With this format, the tribones
  //   . . . . . . . . A | 0   are turned into the following
  //   . . . . . . . A A | 1   trominos:
  //   . . . . . . B B C | 2   
  //   . . . . . D B C C | 3    X O    and    . X
  //   . . . . D D E E F | 4    O .           O O
  //   . . . G H H E F F | 5   
  //   . . G G H I I J J | 6   where 'X' is the arbitrary anchor
  //   . K L L M I N J O | 7   point used in this code
  //   K K L M M N N O O | 8
  let a = Array(n).fill(0),
      cache = a.map(_ => new Object);

  // recursive search, starting at (x, y) = (0, 0)
  return (function search(x, y) {
    // if we've reached the last row, make sure it's complete
    if(y == n - 1) {
      if(a[y] == (1 << n) - 1) {
        return 1;
      }
      return 0;
    }

    // if we are beyond the last column, go on with the next row
    if(x < 0) {
      y++;

      // either return the result from the cache right away
      if(cache[y][a[y]] !== undefined) {
        return cache[y][a[y]];
      }
      // or do a full search
      return cache[y][a[y]] = search(y, y);
    }

    // if (x, y) is already set, advance to the next column
    if(a[y] >> x & 1) {
      return search(x - 1, y);
    }

    let res = 0;
 
    // try to insert X O
    //               O .
    if(x && !(a[y] >> x - 1 & 1)) {
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
      res += search(x - 2, y);
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
    }

    // try to insert . X
    //               O O
    if(!(a[y + 1] >> x + 1 & 1)) {
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
      res += search(x - 1, y);
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
    }

    return res;
  })(0, 0);
}

Try it online!

Output

 0          1 (0.00)
 1          0 (0.00)
 2          1 (0.00)
 3          0 (0.00)
 4          0 (0.00)
 5          0 (0.00)
 6          0 (0.00)
 7          0 (0.00)
 8          0 (0.00)
 9          2 (0.00)
10          0 (0.00)
11          8 (0.00)
12         12 (0.01)
13          0 (0.01)
14         72 (0.01)
15          0 (0.01)
16          0 (0.01)
17          0 (0.01)
18          0 (0.01)
19          0 (0.01)
20          0 (0.01)
21     185328 (0.05)
22          0 (0.05)
23    4736520 (0.24)
24   21617456 (0.60)
25          0 (0.60)
26  912370744 (2.18)
27          0 (2.18)
28          0 (2.18)
29          0 (2.18)
30          0 (2.18)
31          0 (2.18)
32          0 (2.18)
\$\endgroup\$
6
  • \$\begingroup\$ @Bubbler I think this is going to be the last version. You may want to run it again on your own machine. (NB: Since this is using 32-bit integers, it simply can't work for N > 32.) \$\endgroup\$
    – Arnauld
    May 13 '20 at 13:46
  • \$\begingroup\$ Trying to get more terms by switching to BigInt made Node crash (JS heap out of memory)... \$\endgroup\$
    – Bubbler
    May 14 '20 at 6:53
  • \$\begingroup\$ Seems you use lots of memory, how much? \$\endgroup\$
    – l4m2
    May 15 '20 at 16:51
  • \$\begingroup\$ Oh you actually only go to 26. 33 is out-of-time \$\endgroup\$
    – l4m2
    May 15 '20 at 17:05
  • \$\begingroup\$ paste.ubuntu.com/p/x97FJtvVQb \$\endgroup\$
    – l4m2
    May 15 '20 at 17:06
7
\$\begingroup\$

Rust, \$n \le 44\$ in 42 seconds

Build with rustc -O. Uses about 800 MiB of memory for \$n = 38\$, and \$39 \le n \le 44\$ are trivial. \$n = 45\$ will almost definitely run out of both time and memory on any reasonable system.

It works by dynamic programming where the states are the presence or absence of hexagons at \$(k - 1, 1), \dotsc, (k - 1, i), (k, i + 1), \dotsc, (k, k)\$; we advance \$i\$ to \$i + 1\$ by considering the addition of tribone \$(k, i + 1), (k - 1, i), (k - 1, i + 1)\$ or \$(k, i + 1), (k - 1, i + 1), (k, i + 2)\$.

use std::iter::Peekable;
use std::mem;

struct Merge<Xs: Iterator, Ys: Iterator>(Peekable<Xs>, Peekable<Ys>);

impl<Xs: Iterator<Item = (u64, u128)>, Ys: Iterator<Item = (u64, u128)>> Iterator
    for Merge<Xs, Ys>
{
    type Item = (u64, u128);
    fn next(&mut self) -> Option<(u64, u128)> {
        if let Some(x) = self.0.peek() {
            if let Some(y) = self.1.peek() {
                if x.0 < y.0 {
                    self.0.next()
                } else if x.0 > y.0 {
                    self.1.next()
                } else {
                    let x = self.0.next().unwrap();
                    let y = self.1.next().unwrap();
                    Some((x.0, x.1 + y.1))
                }
            } else {
                self.0.next()
            }
        } else {
            self.1.next()
        }
    }
}

fn main() {
    for n in 0..63 {
        if 0xa05 & 1 << n % 12 == 0 {
            println!("{} 0", n);
        } else {
            let mut count: Vec<(u64, u128)> = vec![(!(!0 << n) << 1, 1)];
            let mut count1 = vec![];

            for k in (1..n + 1).rev() {
                for i in 0..k - 1 {
                    count1.extend(Merge(
                        Merge(
                            count
                                .iter()
                                .filter(|&&(b, _)| !b & 3 << i == 0)
                                .map(|&(b, c)| (b & !(3 << i), c))
                                .peekable(),
                            count
                                .iter()
                                .filter(|&&(b, _)| !b & 6 << i == 0)
                                .map(|&(b, c)| (b & !(6 << i), c))
                                .peekable(),
                        )
                        .peekable(),
                        count
                            .iter()
                            .filter(|&&(b, _)| b & 2 << i == 0)
                            .map(|&(b, c)| (b | 2 << i, c))
                            .peekable(),
                    ));
                    mem::swap(&mut count, &mut count1);
                    count1.clear();
                    if i == 1 {
                        count.retain(|&(b, _)| b & 6 != 2);
                    }
                }
                count.retain(|&(b, _)| b & 1 << k == 0);
            }
            assert_eq!(count.len(), 1);
            assert_eq!(count[0].0, 0);
            println!("{} {}", n, count[0].1);
        }
    }
}

Try it online!

(TIO times out after \$n = 37\$.)

Output

0 1
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 2
10 0
11 8
12 12
13 0
14 72
15 0
16 0
17 0
18 0
19 0
20 0
21 185328
22 0
23 4736520
24 21617456
25 0
26 912370744
27 0
28 0
29 0
30 0
31 0
32 0
33 3688972842502560
34 0
35 717591590174000896
36 9771553571471569856
37 0
38 3177501183165726091520
39 0
40 0
41 0
42 0
43 0
44 0
\$\endgroup\$
7
  • \$\begingroup\$ I don't seem to understand the second paragraph; is this broken profile dynamic programming? \$\endgroup\$ May 17 '20 at 2:43
  • \$\begingroup\$ @mypronounismonicareinstate I haven’t heard that term, and it’s hard to figure out what it means without referencing the Google cache of a post on a blog that went down, but it seems to be essentially the same idea. \$\endgroup\$ May 17 '20 at 2:54
  • \$\begingroup\$ It does run up to n=44 in 45 seconds on my PC (and fails while trying to allocate more memory at around 3 minutes). Nice job. \$\endgroup\$
    – Bubbler
    May 19 '20 at 6:07
  • \$\begingroup\$ I tried your text way in C++, and on \$n=44\$ there are \$100483899\$ elements, or 1.6GB if each element use 16 bytes(two int64s). How you use 800MB on \$n=38\$? \$\endgroup\$
    – l4m2
    May 20 '20 at 16:02
  • \$\begingroup\$ Oh you ran backward \$\endgroup\$
    – l4m2
    May 20 '20 at 16:06
1
\$\begingroup\$

\$T(33) = 3688972842502560 \$

> 1 0
> 2 1
> 3 0
> 4 0
> 5 0
> 6 0
> 7 0
> 8 0
> 9 2
> 10 0
> 11 8
> 12 12
> 13 0
> 14 72
> 15 0
> 16 0
> 17 0
> 18 0
> 19 0
> 20 0
> 21 185328
> 22 0
> 23 4736520
> 24 21617456
> 25 0
> 26 912370744
> 27 0
> 28 0
> 29 0
> 30 0
> 31 0
> 32 0
> 33 3688972842502560

Process returned 0 (0x0)   execution time : 71.730 s
Press any key to continue.

Code

#include <map>
#include <stdio.h>
#include <algorithm>
const int N = 33;
typedef unsigned long long ulong;

#define long ulong

std::map<ulong, long> A, B;
int i; long base;
template<bool last = false>
void bitfsh(ulong j, ulong d) {
    if (!j) {
        if(!last || d==0) B[d] += base;
        return;
    }
    int p = sizeof(ulong)*8-1-__builtin_clzll(j);
    if (d & 2ULL<<p) {
        bitfsh<last> (j ^ 1ULL<<p, d ^ 3ULL<<p);
    }
    if (p && (j & 1ULL<<p-1)) {
        bitfsh<last> (j ^ 3ULL<<p-1, d ^ 1ULL<<p);
    }
}
template<bool last = false>
long run() {
    B.clear();
    for (auto p=A.begin(); p!=A.end(); ++p) {
        ulong j = (*p).first;
        if (j%65536==0) fprintf(stderr, "%d %lld\r", i, j);
        base = (*p).second;
        if(base) bitfsh<last> (j, (1ULL<<i)-1);
    }
    std::swap (A, B);
    fprintf(stderr, "%60c\r", ' ');
    return A[0];
}
const ulong fs = sizeof(long) << N-1;
int main() {
    A[0] = 1;
    for (i=1; i<N; ++i) {
        //fprintf(stderr, "%d\n", i);
        printf ("> %d %llu\n", i, run ());
    }
    printf ("> %d %llu\n", i, run<true> ());
    exit(0);
}

T(45) = 1.9935928828199593078904655e+31

Ran in 31953.963 s on my computer(including state backups), and use approximately 4.5GB disk.

Use @Anders Kaseorg 's solution but with disk as storage. For each \$k,i\$ amounts of items can be found here. TIO

\$\endgroup\$
3
  • \$\begingroup\$ Sorry, but if it is for Visual Studio (I'm guessing from <windows.h>), I can't run it on my PC. Could you change the code to be gcc(or any other free C++ compiler)-compatible, or share an instruction to run the code as-is? \$\endgroup\$
    – Bubbler
    May 19 '20 at 5:20
  • \$\begingroup\$ @Bubbler The windows.h is of historical reason, you can remove it \$\endgroup\$
    – l4m2
    May 19 '20 at 7:00
  • \$\begingroup\$ Score: n=35 at 7 minutes (core dumped shortly after that). Btw, g++ complained that there was already a typedef called ulong, so I inserted #define ulong uulong right before the typedef. \$\endgroup\$
    – Bubbler
    May 19 '20 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.