[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](/questions/tagged/code-golf "show questions tagged '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>
[![TIC TAC 2x2](https://i.stack.imgur.com/B4y2Z.png)](https://i.stack.imgur.com/B4y2Z.png) [![TIC TAC 3x3](https://i.stack.imgur.com/nWB0e.png)](https://i.stack.imgur.com/nWB0e.png)
  
[Answer]
# [R](https://www.r-project.org/), 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!](https://tio.run/##bZDbboMwEETf8xWOkgdvta3KpY2CypcgKhEwqSVjkDGtnZ@ny6UllfrmOeOZXa0ZrSxtUdpWpGM96NLKVnOHHm@pcF2hq6erkRU3ouNK9pYHyTOge/AAqFJVdJ3yxMJ3PjH8bZDQFNZIxwc9x26ZxJyCAGQ43i9Blf08tmSDdboJWPzyInVFVohrrZkBSUBt2i/6SAsFW4ubx3CfGiVIwFFl@70/fubrAjUlsOaWN9maTwKczLcIcuwH6tsuQ3NCYAcW7zYU/YeiCb3eoXhBpz8ontB5d7hnLxMLQsbNoNnFs0Yw1ZaFUj5hVjaif2wHyz6EETB@Aw "R – 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]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 402 bytes
Saved 250 bytes thanks to [@py3\_and\_c\_programmer](https://codegolf.stackexchange.com/users/110681/py3-and-c-programmer).
This was originally a [fastest-code](/questions/tagged/fastest-code "show questions tagged 'fastest-code'") challenge. Now it became a [code-golf](/questions/tagged/code-golf "show questions tagged '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!](https://tio.run/##fZBBSwMxEIX/ykJBts0EmvSkYKkgQkGhYG9DKKlN13Q3syXNQQn57Wu26oKoPc2b8L034TkdXo3Twb7ortuj2wBt1M3tug26WTxaMtqvfFt57ZylCtd62xjkAtyEFDwftT@ZO@/1Oz40OgRDiyd9XNLOvJkdxpFEFErBKPG5uIIvBONniptYdmA1ExAtTIG4SBAPWTk@y6rOSiYF33BpWT3OhgGfDbi4gNd/GS7k818G@fNCAqkg9s5YOi7HxFxJeTJ5Xs@6r2eIjhJ6/7/wwE0hY@dilxRMZfxJdfctrrylgPlLhU0Fnxd77GWutejfBBTXSXUf "Wolfram Language (Mathematica) – Try It Online")
Using the built-in [`LinearProgramming`](http://reference.wolfram.com/language/ref/LinearProgramming.html). Gives the results from `1x1` to `9x9` in 40 seconds on TIO.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 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!](https://tio.run/##3ZFhT4MwEIa/8ysatpkW8RjbEo0Z8jdMkCxdw3CbFAYlbND@dix2MzNR42e/Xe/e93r3XFmvT/0m6O@eMpd3eAoA/nKJM4cTAhktOtlKC6F9gO3JdNTpvFrbk5ZAxSjH3qizMRBbZz1iKSiTXcJEJ5vBgxBuhhb45nGXbzmBtEwK7Pm@75FoGkvZgCgpr4q8Sn7REWmaNZBQ9rpiOa/wnADlp7CTR3m8avKNoDXmYYMWhvYg8tUWz8g5Hc3u5@7DIv6U72/aIGiVLitLKYOASQabNypEwoHlNRco9IfSUfVpYMhp/SHYRDqMdfgjxz@S1J//I5ZIXozNV4w49MnyMGx7IU2Nkl7v4Iy927HnzMxJLKuoRYWwD7A4k83k9YtLcwbl2C/CVtr94TC2NFq489gMn1b1Wk/ghs@kfwc "Ruby – Try It Online")
Nothing particular, still using brute force.
[Answer]
# [R](https://www.r-project.org/) + `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!](https://tio.run/##FY7BCoJAFEX3fYUKwXt6g8ZVDLr1B1pKMGUKT/Rpk8VA9O1mm7s4i3OuX7uoXLuXNotMSiMUrnal6ybvEMrptbSejB1hrKZG4DLH/JE6oK8bMtiQyf4jB8OoioO/id6pQtiL7ulo87TPhPly2Q3zeRrerbXDTMl4DQniOKBCUiQYZWunipyBZ/ugwPxdtw8kkWhk7IlnL7pQR4LNtv4A "R – 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]
# [Python 3 (PyPy)](http://pypy.org/), ~~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!](https://tio.run/##XZDRaoQwEEXf/YqBgmbsdDExCCtdn/YL9lWkJNZsA20Uq0Xp7rdb47YU9u1y5swdmG4e3lqXPnVzNy/La2PAsIlmOh6@r5gHcDqUFkzbgwXroFfu3DARxxNaE3HOI9cOfqCtYxarYFNfVlImVTznawtTpDH3c4W7uh3dwCIe4eOHmthxd24GxjTVSAn61dqXncAapkJ9UUUhQl0U/KJiGepYYFg/801UN9FHvcVrAH0zjL2DW/OXeh@bT4a4dL1djxomSCDCA8jgj6SUbiQL/p30zpEkN7L/JaVhlize/4QT8AQrb5acJGW0J56RSEhklGYkRbX8AA "Python 3 (PyPy) – 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]
# 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!](https://tio.run/##bYtLDoJAEET3noK4mHSjyEdiokOPJ@AQRPkoYDNiho13x9ad0aSqk5fqdy1cMZ7ul@ER3PhczhXNE5mGTOmKDpYV34EpWvcUZ9nkNzqnIOg1U/6Emloyjlql4lUNrWqDGBF6zPjIB4dvdSBLkQZHuUp8f5IH5cJEmj6dGpR9X2ErbBVYGlBILIdheowOuTE0adS8xPnEt5G7ctNxDRUkKEEvDL108b1sUfJZdosfZ/vfSVHyWfbzCw "JavaScript (Node.js) – Try It Online")
]