# Tag Info

Haskell, 320…236 230 bytes length<$>iterate(\h->nub[r$x:y:u|u<-h,t<-u,x<-n t\\u,y<-n x\\u,([x,x,y]\$$u>>=n))/=[x,y]])[[l,0<l]] r u=minimum[sort(!!i).p.map(*j).m a<>u|a<-u,j<-l,i<-[0..5]] n=(<>p l).m m=zipWith(-) p=permutations l=[-1..1] import Data.List Try it online! An infinite list whose $n$-th ... 14 C, 7 terms The seventh term is 19846102. (The first six are 1, 1, 2, 22, 515, 56734, as stated in the question). #include <stdio.h> #include <string.h> #include <stdint.h> #define N 7 #define ctz __builtin_ctzl typedef uint64_t u64; static u64 board[N*N] = { 0 }; static u64 adjacency_matrix[N*N] = { 0 }; static u64 count = 0; static ... 12 Python 3, 480 433 406 364 309 299 295 bytes Looked like a good point to start my PPCG career (or not?). def C(s): S,*a={''},0,1;n=d=r=1 for c in s:d=c*d*1jor d;n+=d;a+=n,;r*=not{n}&S;x,*a=a;S|={x+t+u*1jfor t in A for u in A} return r from itertools import*;A=-1,0,1;n,y=int(input())-2,0;x={*filter(C,product(*[A]*n))} while x:s=x.pop();S=*(-u for u in ... 12 Python 3.8 (pre-release), 371 ... 338 336 bytes Takes as input a list of complex numbers, denoting the boundary coordinates in counterclockwise order. -9 bytes thanks to @ovs -2 bytes thanks to @Bubbler import itertools as Z def f(P):Q=P*2;I=Q.index;L=len;return any(L({*map(complex.__sub__,T:=(J:=lambda x,y:Q[(j:=I(p[x])):I(p[y],j)+1])(0,1),U:=J(3,4)[::-1]... 12 JavaScript (ES10), 250 ... 228 227 bytes n=>(e=g=(a,[x]=a)=>+e?e=0:(x&=-x)?a.map((_,s)=>[b=1<<s,...s?[1,b+=~-b,b]:[]].map((m,d)=>d|x>>s&&g(a.flatMap(S=(v,y)=>(S|=y>s?v:(e|=(v^=M=x*m>>!d*s)&M,m^=1<<[s+~y,y+1,s-y,y][d],v))?v:[])))):n++)([...Array(n)].map(_=>2**n---1))|n Try it online! How? The ... 11 GAP and its kbmag package, 711 682 658 bytes Note that the kbmag package consists not only of GAP code, it contains C programs that have to be compiled (see the package's README file). LoadPackage("kbmag");I:=function(p,q,n)local F,H,R,r,s,x,c;F:=FreeGroup(2);s:=F.1;r:=F.2;R:=KBMAGRewritingSystem(F/[s^2,r^p,(s*r)^q]);AutomaticStructure(R);H:=... 11 C++, Not competing After spending so long on the golfing side of this challenge, I was curious to see what I could do from a fastest-code perspective. Here is my C++ attempt, which should be able to run up to $n=8$ on every computer, and $n=9$ if you have enough RAM and patience. The approach is the same as my other answer, but optimized for speed ... 9 An extension to @Grimy's code gets N=8 This just underlines that @Grimy deserves the bounty: I could prune the search tree by extending the code to check, after each finished polyomino, that the remaining free space is not partitioned into components of size not divisible by N. On a machine where the original code took 2m11s for N=7, this takes 1m4s, and ... 9 Rust, 11 (hopefully correct) terms use ::std::ops::{Add, Sub, Mul}; use ::std::rc::Rc; use ::std::hash::{Hash, Hasher}; use ::std::collections::HashSet; use ::std::iter; use ::std::fmt::{self, Formatter, Display}; use ::std::time::Instant; type Coord = i128; #[derive(Copy, Clone, PartialEq, Eq, Debug)] struct Vec3([Coord; 3]); impl Vec3 { fn dot(self,... 8 Python 2, 300 265 163 bytes -35 bytes after suggestions from @xnor, @ovs, and largely @user202729 (removing evenly divisible check allowed for a one-liner + lambda) -102 bytes following encouragement + general suggestions by @user202729 lambda l,w,h:all(w*h-len({((e-(p&4)*e//2)*1j**p+p/8+p/8/w*1j)%w%(1j*h)for e in l for p in c})for c in combinations(range(8*... 8 JavaScript (ES6), 196 ... 185 182 bytes Takes input as a binary matrix. Returns a Boolean value. f=m=>!/1/.test(m)||m.some((r,y)=>r.some((v,x)=>v&&[0,1,2,3].some(d=>([X,V]=(g=d=>[v=x+--d%2,R=m[y+--d%2]||0,R[v]])(d))&g(d+1&3)&&(r[x]=V[X]=R[r[x]=V[X]=R[v]=0,o=f(m),v]=1)&o))) Try it online! This algorithm is ... 8 C# and SAT: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 37, 43 If we limit the bounding box, there is a fairly obvious expression of the problem in terms of SAT: each translation of each orientation of each free polyomino is a large conjunction; for each polyomino we form a disjunction over its conjunctions; and then we require each disjunction to be true and the ... 8 C#, score: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 38, 44 # ## #.. ### .##. #### ..#.. ##### ###.. ##.... ###### ####.. ..##... .###... ####### .#####. ..###... ..###... ..###### ######## ..##..... .###..... #######.. ######### ..#####.. .###...... .####..... .######... ########## .########. .###....... .####...... .####...... .#######... ########### .#... 8 Python 2, 53 bytes lambda p,q,n:p/n*q+q/n*(p%n)-min(0,n-p%n-q%n)*(p>n<q) Adapts the formula given in this paper, which is: def f(p,q,n):a=p%n;b=q%n;return(p*q-[a*b,(n-a)*(n-b)][a+b>=n and p>=n and q>=n])/n 8 05AB1E, 31 30 17 bytes ø‚O0δÚDWδåsεÔg<}Q Try it online or verify all test cases. Explanation: ø # Zip/transpose the (implicit) input-matrix, swapping rows/columns ‚ # Pair it together with the (implicit) input-matrix O # Take the sum of each row of both matrices # Remove any leading/trailing rows/columns of ... 8 Ruby, 290 270 bytes ->n,p=[[2,3]],s=2{s<n ?(q=[] p.map{|a|a.product(d=[w=n*3,1,~w,-w,-1,-~w],d).map{|i|r=[];t=0 c=a+b=[i+i,i.sum] a&b==r&&12.times{|j|t+=a.count b[j%2]+d[j/2];c=c.map!{|k|j%2<1?k%w*(2+w)-k:k/w+k%w*w}.sort!.map{|m|m-c+n};r<<c*1} t>1&&q<<r.min}} f[n,q&q,s+2]):p.size} Try it online! A ... 7 Python 2, 48 bytes f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1)) Try it online! Takes the largest of the four rotations in terms of list comparison. Based on FlipTack's solution. The code uses Python 2's ability to compare objects of different types. The base case value of 0 is harmless for max because it's smaller than any list. Also, zip produces a ... 7 Haskell Now that not only the comments document that Peter Taylor was the first one to give enough terms to search on OEIS, I can give my results. ( 1 - 10) 2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, (11 - 15) 22927, 74137, 241461, 790838, 2603210, (16 - 18) 8604861, 28549166, 95027832, (19 - 22) 317229779, 1061764660, 3562113987, 11976146355 Earlier, I ... 7 J, 51 48 79 bytes (1-'10+1'rxin'012'{~2,@,.],|:)*1&#.(,~&{:-:,&(0{#/.~)+0{,)&(|.^:({.>{:)@-.&0)+/ Try it online! +31 thanks to Bubbler for catching a bug not revealed by the original cases NOTE: All test cases are passing again when I run locally on j902, but this now fails on TIO due to a J regex bug on linux/TIO. Consider the column ... 6 2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, 22927, 74137, 241461, 790838, 2603210, 8604861, 28549166, 95027832 I'm going to put a stake in the ground before Christian Sievers posts an answer for n=18. This is as far as I can go with the current code and 16GB of RAM. I've already had to sacrifice some speed to reduce the memory usage, and I'm going to have to ... 6 Ruby, 202 bytes ->n{(r=[*0..n]).product(r,r,r).map{|i|p,b,c,d=i;b>c||c>d||b+c+d>p||p*p-b*b-c*c-d*d!=n||0.upto(p-d<<1){|j|s=" "*j+"*---\\ / "[j%2*4,4]*p*2;(k=b*4-j)>0&&s[0,k]=" "*k;puts s[0,[p*4+1-j,p*4+1-c*4+j].min]}}} Try it online! Uses formula per the OEIS sequence: search for solutions where n = p**2 - b**2 -c**2 - d**2. ... 6 JavaScript (ES7), 233 bytes Takes input as (w)(h)(p), where $p$ is a binary matrix describing the polyomino. Returns $0$ or $1$. Similar to my original answer, but uses a more complex expression to update the cells of the matrix instead of explicitly rotating the polyomino. w=>h=>g=(p,m=Array(w*h).fill(o=1))=>+m.join?(R=i=>i--?m.map((F,X)... 6 JavaScript (V8), 500 bytes Lots of golfing possible. M=>{R=M.map(m=>m.join);if(R.find(r=>r.match(/10+1/)))return;o = [];for(i=n=0;i<R[L="length"];i++)if((r=R[i]).includes1){if(n)return;n=0;o.push([r.indexOf1,r.lastIndexOf1])}else{if(o[L])n=1;else continue}if(o.every(r=>r==o)){}else if(o.every(r=>r==o))o=... 6 APL (Dyalog Extended), 48 bytes (SBCS) Anonymous tacit prefix function. Takes Boolean (0/1) matrix with 0s indicating the shape. Requires 0-based indexing. {(=/⍵-⍥⍴e)∧i≡,e←(⊂∘⊃+∘⍳∘|1+⊃∘⌽-⊃)i←⍸⍵}1⍉⍤⌂deb⍣2⊢ Try it online! 0…⊢⁠ with 0 as left argument and the unmodified argument as right argument: …⍣2 repeat twice …⍤⌂deb delete ending (leading and trailing)... 6 JavaScript (ES6), 175 166 bytes Expects a list of binary strings. m=>m.map(M=r=>(M|=v='0b'+r|0,m&=v||~0,v),m=~0).map(v=>v?(b=v+(v&-v))&b-1?3:v^m?2^v<M:1:0).join.match(^0*(1+{s=(g=m=>m?2+g(m&m-1):'')(m)}|{s}1+)0*)&&M*2&M/2&m^m Try it online! How? Step 1 We first convert the input matrix $m[\:]$ into a ... 5 Python 2, 338 335 330 Try it online! from itertools import* n,k=input() O=[(*k,)] R=range(k) exec"O={min(tuple(sorted(zip(*[[x-min(p)for x in p]for p in f])))for q in permutations(zip(*(o+(r,))))for f in product(*[[p,[-x for x in p]]for p in q]))for o in O for s in o for r in[tuple(s[i]+x*(i==j)for i in R)for j in R for x in-1,1]if not r in o};"*~-n ... 5 Python 3, 136 131 bytes lambda S:g(int((len(S)*'{:0<6}').format(*S),2))<1 g=lambda b:b*all(b>>i&t^t or g(t<<i^b)for i in range(30)for t in(67,131,193,194)) Try it online! Input: A list of strings, each string must be a binary string. The length of the strings can be different. Output: True if the shape can be tiled, False otherwise. ... 5 APL (Dyalog Unicode), 70 65 bytes +/{∧/∊2≤|(⊢-¯3↓¨,$$+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳2↓⎕⍴3 Try it online! Full program version of the code below, thanks to Adám. APL (Dyalog Unicode), 70 bytes {+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳3⍴⍨0⌈⍵-2} Try it online! How it works The code above is equivalent to the following ...