Tic, Tac, stub your Toe

Question

Find the max number of Xs you can fit onto a rectangular tic-tac-toe board of length l and height h without ever having 3 consecutive Xs in a row diagonally, horizontally, or vertically.

This is a code-golf challenge so shortest code wins!

Input

A single line containing values l and h, representing the length and height of the tic-tac-toe board, separated by a space.

Constraints

1 ≤ l ≤ 2,147,483,647
1 ≤ h ≤ 2,147,483,647

Output

A single number representing the number of Xs that can fit on the tic-tac-toe board without three in a row

Sample Inputs and Outputs

Input -> Output
2 2 -> 4
3 3 -> 6
2 3 -> 4
4 4 -> 9

Explanation

4 Xs can fit on a 2x2 tic-tac-toe board without having 3 Xs in a row anywhere

6 Xs can fit on a 3x3 tic-tac-toe board without having 3 Xs in a row anywhere

4 Xs can fit on a 2x3 tic-tac-toe board without having 3 Xs in a row anywhere

9 Xs can fit on a 4x4 tic-tac-toe board without having 3 Xs in a row anywhere

Credits

Lukas Zenick for creating the problem

Extra Data

https://docs.google.com/spreadsheets/d/1qJvlxdGm8TocR3sh3leRIpqdzmN3bB_z8N-VrEKSCwI/edit

Answer 1

R, 270 bytes

function(x,y,z=expand.grid(rep(list(1:0),x*y)),l=lapply(1:2^(x*y),function(i)matrix(unlist(z[i,]),x)))max(sapply(l[sapply(l,function(m,f=function(m)apply(cbind(m,2,matrix(rbind(2,m),nrow(m))),1,function(x)max((y=rle(x))$l[!!y$v])))max(f(m),f(t(m[nrow(m):1,])))<3)],sum))

Try it online!

Unfortunately I didn't notice the 'fastest code' tag and started working on this assuming that it was 'code golf', so this isn't very fast (and I won't golf it any further). But it at least calculates the test cases without timing-out...

Answer 2

Wolfram Language (Mathematica), 402 bytes

Saved 250 bytes thanks to @py3_and_c_programmer.

This was originally a fastest-code challenge. Now it became a code-golf, but I'm too lazy to golf it.

f[m_,n_]:=Total@LinearProgramming[Table[-1,m*n],SparseArray[Flatten@MapIndexed[{#2[[1]],#}->1&,Flatten[{Table[m*i+j+k+1,{i,0,n-1},{j,0,m-3},{k,0,2}],Table[m*(i+k)+j+1,{i,0,n-3},{j,0,m-1},{k,0,2}],Table[m*(i+k)+j+k+1,{i,0,n-3},{j,0,m-3},{k,0,2}],Table[m*(i+k)+j-k+1,{i,0,n-3},{j,2,m-1},{k,0,2}]},2],{2}],{(m-2)n+m(n-2)+2(m-2)(n-2),m*n}],Table[{2,-1},(m-2)n+m(n-2)+2(m-2)(n-2)],Table[{0,1},m*n],Integers]

Try it online!

Using the built-in LinearProgramming. Gives the results from 1x1 to 9x9 in 40 seconds on TIO.

Answer 3

Ruby, 311 bytes

->m,n{(0...1<<(m*n)).map{|z|
  k=("%0#{m*n}b"%z).scan(/#{"(.)"*n}/)
}.reject{|w|
    (w.map(&:join).grep(/111/)[0]||w.transpose.map(&:join).grep(/111/)[0])||
    w.each_cons(3).any?{|x|x.transpose.each_cons(3).any?{|z|
      k=z.join.to_i(2)
      [273,84].any?{|z|k&z==z}
  }
}}.map{|c|c.flatten.count ?1}.max}

Try it online!

Nothing particular, still using brute force.

Answer 4

R + lpSolve, 202 194 149 bytes

function(m,n,`[`=`for`,x=outer(1:m,1:n*1i,`+`)){i[x,j[c(1,1i,1+1i,1i-1),F<-rbind(F,x%in%(0:2*j+i))]]
lpSolve::lp("max",!!x,F,"<",min(m*n,2),,seq(x))}

Try it online!

A golfed version of an external ILP solver-based solution, which I started working on when this was a fastest code challenge, but got closed. Works slower than Wolfram though, but still manages 8x8 on TIO.

In lieu of a proper explanation, here is an outdated, but somewhat ungolfed version:

library('lpSolve')

f = function(m, n, p = m*n, r = -1:1, l = {})
{  
  if(p == 1) return(1) # Edge case for 1x1
  for(i in 1:m) for(j in 1:n) for(k in 1:4)
  {
    d = list(          # Directions
      cbind(i+r, j),   # Vertical
      cbind(i, j+r),   # Horizontal
      cbind(i+r, j+r), # Diagonal
      cbind(i-r, j+r)  # Antidiagonal
    )
    x = matrix(0, m, n)
    try(x[d[[k]]] <- 1)
    l = rbind(l, c(x))
  }
  lp(direction = "max", objective.in = rep(1, p), const.mat = l, const.dir = "<=", const.rhs = 2, all.bin = T)
}

Answer 5

Python 3 (PyPy), 262 254 212 bytes

def f(x,y,D={}):
 R=[i for i in range(2**x)if'111'not in bin(i)]
 for _ in[0]*y:D={(a,b):bin(a).count('1')+max(D.get((b,c),0)for c in R if(a&b|a>>2&b>>1|a*4&b*2)&c<1)for a in R for b in R}
 return max(D.values())

Try it online!

-8 bytes thanks to 12944qwerty

Rows are encoded in binary, and R is the list of all possible rows.

In any given iteration i of the second for loop (starting from 0), D is a dictionary where D[a,b] is the largest number of Xs that can fit in an X by i board where the first two rows are a and b.

The new D is calculated by iterating over every possible first 2 rows a,b, and setting D[a,b] to the number of Xs in row a plus the maximum value of D[b,c] where c is every row that could follow a,b.

This algorithm takes time \$y\cdot8^x\$ and space \$4^x\$, solving 1x1 to 9x9 in 20s on TIO.

Answer 6

JavaScript (ES7), 149 bytes

Expects (width)(height).

w=>h=>eval("for(o=0,m=1<<w*h;M=--m;o=M|(g=k=>v=k&&1+g(k&k-1))(m)<o?o:v)for(p=q=0;(v=M&2**w-1)&v/2&v/4|v&p&q|v&p/2&q/4|q&(q=p)/2&(p=v)/4?0:M>>=w;);o")

Try it online!