23
\$\begingroup\$

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 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 TIC TAC 3x3

\$\endgroup\$
25
  • 1
    \$\begingroup\$ @Jonathan Yeah my bad. Diagonal, horizontal and vertical. \$\endgroup\$
    – JohnBGoode
    Oct 26, 2022 at 14:30
  • 1
    \$\begingroup\$ Welcome to code golf, and this looks like a nice challenge! A tiny improvement would be to format the test cases so that they can easily be input together into code to be tested, without a lot of separate copy-pasting: see here \$\endgroup\$ Oct 26, 2022 at 14:43
  • 3
    \$\begingroup\$ The sequence of the table's diagonals is on the OEIS - A181019. \$\endgroup\$ Oct 26, 2022 at 16:44
  • 12
    \$\begingroup\$ Since you've tagged it as a [fastest-code] challenge, you'll have to add how you're going to test the speed of each answer. E.g. are you going to test them on your own PC (in which case, what are the processor specs?) - and maybe installation instructions in answers might be useful then. Or, and this is probably easier, are you going by TIO or ATO execution time? EDIT: @pajonk beat me to it while I was typing.. \$\endgroup\$ Oct 27, 2022 at 6:30
  • 12
    \$\begingroup\$ TIO is discouraged for fastest-code challenges. Also, the fastest program that prints the answer for l = 9, h = 9 is going to be absurdly fast, and might just degenerate toward print(42) via “optimizations” that will be meaningless to measure and won’t correlate with speed for larger inputs. Take a look at other fastest-code challenges for inspiration—it’s better to structure them to ask for the most number of values of some sequence in a fixed amount of time, rather than for a single fixed value in the shortest time. \$\endgroup\$ Oct 27, 2022 at 15:04

6 Answers 6

4
\$\begingroup\$

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...

\$\endgroup\$
2
  • \$\begingroup\$ Well, probably time to revisit this, as it indeed became Codegolf :D \$\endgroup\$
    – Kirill L.
    Nov 5, 2022 at 16:28
  • \$\begingroup\$ Hmm... maybe I'll try to cut-off 69 bytes then... \$\endgroup\$ Nov 5, 2022 at 18:41
3
\$\begingroup\$

Wolfram Language (Mathematica), 402 bytes

Saved 250 bytes thanks to @py3_and_c_programmer.

This was originally a challenge. Now it became a , 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.

\$\endgroup\$
3
  • \$\begingroup\$ Now that it's a code-golf challenge (my fault), you might want to change it to this code: \$\endgroup\$ Nov 4, 2022 at 9:26
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ Nov 4, 2022 at 9:26
  • 1
    \$\begingroup\$ which is 250 bytes shorter. \$\endgroup\$ Nov 4, 2022 at 9:27
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I get 7 for (4,3), and your code seems to get 9 (I think). Can you check this... \$\endgroup\$ Oct 27, 2022 at 9:23
  • \$\begingroup\$ @DominicvanEssen: Should be fixed now \$\endgroup\$
    – G B
    Oct 28, 2022 at 7:49
2
\$\begingroup\$

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)
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ BTW, Python 3.10 has a function int.bit_count() which is shorter (and also multiple times faster) than bin(int).count('1') \$\endgroup\$ Oct 30, 2022 at 19:42
  • 1
    \$\begingroup\$ @97.100.97.109 PyPy currently only goes up to python 3.9 and is much faster. (on my computer f(9,9) using PyPy and bin(a).count('1') took 17 seconds while python3.11 with a.bit_count() took 60 seconds) \$\endgroup\$
    – gsitcia
    Oct 30, 2022 at 20:07
  • \$\begingroup\$ 254 chars by replacing in range(x) with in[0]*x \$\endgroup\$ Nov 7, 2022 at 22:03
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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