32
\$\begingroup\$

Introduction

Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use crosses. The first person who places three crosses in a row loses. An interesting fact is that the maximum amount of crosses before someone loses, is equal to 6:

X X -
X - X
- X X

That means that for a 3 x 3 board, the maximum amount is 6. So for N = 3, we need to output 6.

Another example, for N = 4, or a 4 x 4 board:

X X - X
X X - X
- - - -
X X - X

This is an optimal solution, you can see that the maximum amount of crosses is equal to 9. An optimal solution for a 12 x 12 board is:

X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X

This results in 74.

The task

The task is simple, given an integer greater than 0, output the maximum amount of crosses that can be placed with no three X's adjacent in a line along a row, column or diagonally.

Test cases

N     Output
1     1
2     4
3     6
4     9
5     16
6     20
7     26
8     36
9     42

More information can be found at https://oeis.org/A181018.

Rules

  • This is , so the submission with the least amount of bytes wins!
  • You may provide a function or a program.
\$\endgroup\$
32
  • 7
    \$\begingroup\$ So the question just boils down to using the formulas in the page you linked... \$\endgroup\$
    – nicael
    Jan 6, 2016 at 18:51
  • 2
    \$\begingroup\$ Related post over on Math. \$\endgroup\$ Jan 6, 2016 at 18:52
  • 7
    \$\begingroup\$ @nicael As far as I can see, the OEIS article only contains lower bounds. \$\endgroup\$ Jan 6, 2016 at 18:57
  • 6
    \$\begingroup\$ Would be cool to see this as a fastest code challenge. \$\endgroup\$
    – Luke
    Jan 10, 2016 at 19:04
  • 4
    \$\begingroup\$ Not a codegolf solution, but I have been playing with a "visual" solver the past few days. You can access the jsfiddle here: jsfiddle.net/V92Gn/3899 It attempts to find solutions via random mutations. It won't stop if it finds the "correct" answer, but it can get to many of the correct solutions much quicker than those answers below. \$\endgroup\$
    – styletron
    Jan 12, 2016 at 14:31

6 Answers 6

13
\$\begingroup\$

CJam (58 56 bytes)

2q~:Xm*{7Yb#W=}:F,Xm*{ee{~0a@*\+}%zS*F},_Wf%:z&Mf*1fb:e>

This is incredibly slow and uses a lot of memory, but that's for you.

Dissection

2q~:Xm*        e# Read input into X and find Cartesian product {0,1}^X
{7Yb#W=}:F,    e# Filter with a predicate F which rejects arrays with a 111
Xm*            e# Take the Cartesian product possible_rows^X to get possible grids
{              e# Filter out grids with an anti-diagonal 111 by...
  ee{~0a@*\+}% e#   prepending [0]*i to the ith row
  zS*F         e#   transposing, joining on a non-1, and applying F
},
_Wf%:z         e# Copy the filtered arrays and map a 90 degree rotation
&              e# Intersect. The rotation maps horizontal to vertical and
               e# anti-diagonal to diagonal, so this gets down to valid grids
Mf*            e# Flatten each grid
1fb            e# Count its 1s
:e>            e# Select the maximum

The number of valid rows is a tribonacci number and is \$\Theta(a^X)\$ where \$a\$ is the tribonacci constant, \$1.83928675\ldots\$. The number of grids generated in the Cartesian product is \$\Theta(a^{X^2})\$; the second filter will reduce the number somewhat, but the intersection is still probably \$\Theta(a^{X^4})\$.


An "efficient" approach ("merely" \$O(X a^{3X})\$) uses dynamic programming. Ungolfed in Java:

public class A181018 {
    public static void main(String[] args) {
        for (int i = 1; i < 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    private static int calc(int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        if (n < 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j < rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i < rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h < n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i < rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j < rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p & q) | ((p << 2) & (q << 1)) | ((p >> 2) & (q >> 1));
                    for (int k = 0; k < rows.length; k++) {
                        int r = rows[k];
                        if ((r & mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] & 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc > nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc > max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i < n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) < (1 << (n - 1))) {
            if (val > 0) rows[j++] = val * 2;
            if ((val & 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ What does the efficient approach run in? \$\endgroup\$
    – lirtosiast
    Jan 11, 2016 at 1:03
  • \$\begingroup\$ @ThomasKwa, oh, it's still exponential, but I think it's justified to call it efficient because it's allowed me to extend the OEIS sequence by 3 terms. \$\endgroup\$ Jan 11, 2016 at 7:26
  • \$\begingroup\$ @ThomasKwa, to be precise, it's O(n a^n) where a ~= 5.518. \$\endgroup\$ Jan 11, 2016 at 19:00
11
+200
\$\begingroup\$

Pyth, 57 51 49 bytes

L.T.e+*]Ykbbsef!s.AMs.:R3ssmyBdsm_BdCBcTQsD^U2^Q2

Like @PeterTaylor's CJam solution, this is brute-force, so it runs in O(n22n2) time. The online interpreter doesn't finish within a minute for n=4.

Try it here for N<4.

Try the diagonals function.

L.T.e+*]Ykbb         y(b): diagonals of b (with some trailing [])
s e                  sum of the last (with most ones) array such that
f                    filter lambda T:
 ! s .AM                none of the 3 element sublists are all ones               
   s .:R3               all 3 element sublists
   s s                  flatten
   myBd                 add the diagonals
   sm_B d               add the vertically flipped array and transpose
   CBcTQ                array shaped into Q by Q square, and its transpose
 sD ^U2 ^Q2             all binary arrays of length Q^2 sorted by sum
\$\endgroup\$
4
\$\begingroup\$

C, 460 456 410 407 362 351 318 bytes

This is a really bad answer. It's an incredibly slow brute force approach. I'm trying to golf it a bit more by combining the for loops.

#define r return
#define d(x,y)b[x]*b[x+y]*b[x+2*(y)]
n,*b;s(i){for(;i<n*(n-2);++i)if(d(i%(n-2)+i/(n-2)*n,1)+d(i,n)+(i%n<n-2&&d(i,n+1)+d(i+2,n-1)))r 1;r 0;}t(x,c,l,f){if(s(0))r 0;b[x]++;if(x==n*n-1)r c+!s(0);l=t(x+1,c+1);b[x]--;f=t(x+1,c);r l>f?l:f;}main(c,v)char**v;{n=atol(v[1]);b=calloc(n*n,4);printf("%d",t(0,0));}

Test Cases

$ ./a.out 1
1$ ./a.out 2
4$ ./a.out 3
6$ ./a.out 4
9$ ./a.out 5
16$

Ungolfed

n,*b; /* board size, board */

s(i) /* Is the board solved? */
{
    for(;i<n*(n-2);++i) /* Iterate through the board */
            if(b[i%(n-2)+i/(n-2)*n]&&b[i%(n-2)+i/(n-2)*n+1]&&b[i%(n-2)+i/(n-2)*n+2] /* Check for horizontal tic-tac-toe */
                    || b[i] && b[i+n] && b[i+2*n] /* Check for vertical tic-tac-toe */
                    || (i%n<n-2
                            && (b[i] &&b [i+n+1] && b[i+2*n+2] /* Check for diagonal tic-tac-toe */
                                    || b[i+2*n] && b[i+n+1] && b[i+2]))) /* Check for reverse diagonal tic-tac-toe */
                    return 1;
    return 0;
}

t(x,c,l,f) /* Try a move at the given index */
{
    if(s(0)) /* If board is solved, this is not a viable path */
            return 0;
    b[x]++;
    if(x==n*n-1) /* If we've reached the last square, return the count */
            return c+!s(0);

    /* Try it with the cross */
    l=t(x+1,c+1);

    /* And try it without */
    b[x]--;
    f=t(x+1,c);

    /* Return the better result of the two */
    return l>f?l:f;
}

main(c,v)
char**v;
{
    n=atol(v[1]); /* Get the board size */
    b=calloc(n*n,4); /* Allocate a board */
    printf("%d",t(0,0)); /* Print the result */
}

Edit: Declare int variables as unused parameters; remove y coordinate, just use index; move variable to parameter list rather than global, fix unnecessary parameters passed to s(); combine for loops, remove unnecessary parentheses; replace && with *, || with +; macro-ify the 3-in-a-row check

\$\endgroup\$
5
  • \$\begingroup\$ How slow is it? \$\endgroup\$
    – xenia
    Jan 9, 2016 at 12:31
  • \$\begingroup\$ @Loovjo tried on my PC with some small changes to make it faster, 15ms for n=5, 12 sec for n=6 (input +1, time * 800)! \$\endgroup\$
    – edc65
    Jan 9, 2016 at 14:26
  • \$\begingroup\$ @edc65 That was my experience. Anything greater than 5 the performance was dramatically slower. I didn't bother with trying inputs greater than 6. \$\endgroup\$ Jan 9, 2016 at 14:50
  • \$\begingroup\$ I started with 7 when I posted my comment. We'll see \$\endgroup\$
    – edc65
    Jan 9, 2016 at 14:53
  • \$\begingroup\$ You can squeeze out a few more chars with #define d(x,y)b[x]*b[x+y]*b[x+y+y]; by changing the start of s to s(i,m){for(m=n-2; and replacing all instances of n-2; and by changing b[x]++ to b[x++]++ and then replacing x==n*n-1 with x==n*n, x+1 with x, and x with x-1. \$\endgroup\$ Jan 16, 2016 at 22:33
4
\$\begingroup\$

C 263 264 283 309

Edit A few bytes saved thx @Peter Taylor - less than I hoped. Then 2 bytes used to allocate some more memory, now I can try larger size, but it's becoming very time consuming.

Note While adding the explanation, I found out that i'm wasting bytes keeping the grid in the R array - so that you can to see the solution found ... it's not requested for this challenge!!
I removed it in the golfed version

A golfed C program that can actually find the answer for n=1..10 in reasonable time.

s,k,n,V[9999],B[9999],i,b;K(l,w,u,t,i){for(t=u&t|u*2&t*4|u/2&t/4,--l; i--;)V[i]&t||(b=B[i]+w,l?b+(n+2)/3*2*l>s&&K(l,b,V[i],u,k):b>s?s=b:0);}main(v){for(scanf("%d",&n);(v=V[i]*2)<1<<n;v%8<6?B[V[k]=v+1,k++]=b+1:0)V[k]=v,b=B[k++]=B[i++];K(n,0,0,0,k);printf("%d",s);}

My test:

7 -> 26 in 10 sec
8 -> 36 in 18 sec
9 -> 42 in 1162 sec

Less golfed and trying to explain

#include <stdio.h>

int n, // the grid size
    s, // the result
    k, // the number of valid rows 
    V[9999], // the list of valid rows (0..to k-1) as bitmasks
    B[9999], // the list of 'weight' for each valid rows (number of set bits)
    R[99],  // the grid as an array of indices pointing to bitmask in V
    b,i; // int globals set to 0, to avoid int declaration inside functions

// recursive function to fill the grid
int K(
  int l, // number of rows filled so far == index of row to add
  int w, // number of crosses so far
  int u, // bit mask of the preceding line (V[r[l-1]])
  int t, // bit mask of the preceding preceding line (V[r[l-2]])
  int i) // the loop variables, init to k at each call, will go down to 0
{
  // build a bit mask to check the next line 
  // with the limit of 3 crosses we need to check the 2 preceding rows
  t = u&t | u*2 & t*4 | u/2 & t/4; 
  for (; i--; )// loop on the k possibile values in V
  {
    R[l] = i; // store current row in R
    b = B[i] + w; // new number of crosses if this row is accepted
    if ((V[i] & t) == 0) // check if there are not 3 adjacent crosses
      // then check if the score that we can reach from this point
      // adding the missing rows can eventually be greater
      // than the current max score stored in s
      if (b + (n + 2) / 3 * 2 * (n - l - 1) > s)
        if (l > n-2) // if at last row
          s = b > s ? b : s; // update the max score
        else  // not the last row
          K(l + 1, b, V[i], u, k); // recursive call, try to add another row
  }
}

int main(int j)
{
  scanf("%d", &n);

  // find all valid rows - not having more than 2 adjacent crosses
  // put valid rows in array V
  // for each valid row found, store the cross number in array B
  // the number of valid rows will be in k
  for (; i<1 << n; V[k] = i++, k += !b) // i is global and start at 0
    for (b = B[k] = 0, j = i; j; j /= 2) 
      b = ~(j | -8) ? b : 1, B[k] += j & 1;
  K(0,0,0,0,k); // call recursive function to find the max score
  printf("%d\n", s);
}
\$\endgroup\$
4
  • \$\begingroup\$ This is essentially the same as my Java program but depth-first rather than breadth-first. I think you should be able to save at least a dozen characters by porting my buildRows method; maybe as many as 20 if for(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v; is valid. (I don't have access to a C compiler right now). \$\endgroup\$ Jan 13, 2016 at 10:18
  • 1
    \$\begingroup\$ @PeterTaylor i'll give it a look ... just the word tribonacci is scaring me \$\endgroup\$
    – edc65
    Jan 13, 2016 at 11:03
  • \$\begingroup\$ Your hard-coded 999 means that you would want to ignore that part. Although maybe you should really make it not hard-coded, so that in principle you can tackle larger inputs than 11 or 12. \$\endgroup\$ Jan 13, 2016 at 11:14
  • \$\begingroup\$ @PeterTaylor it would work great if I had a .bitCount method in C to count bits. But in that initial fase I'compuitng the bit count in B, not only the bit masks in V \$\endgroup\$
    – edc65
    Jan 13, 2016 at 15:25
2
\$\begingroup\$

Ruby, 263 bytes

This is also a brute force solution and faces the same problems as the C answer by Cole Cameron, but is even slower since this is ruby and not C. But hey, it's shorter.

c=->(b){b.transpose.all?{|a|/111/!~a*''}}
m=->(b,j=0){b[j/N][j%N]=1
x,*o=b.map.with_index,0
c[b]&&c[b.transpose]&&c[x.map{|a,i|o*(N-i)+a+o*i}]&&c[x.map{|a,i|o*i+a+o*(N-i)}]?(((j+1)...N*N).map{|i|m[b.map(&:dup),i]}.max||0)+1:0}
N=$*[0].to_i
p m[N.times.map{[0]*N}]

Test cases

$ ruby A181018.rb 1
1
$ ruby A181018.rb 2
4
$ ruby A181018.rb 3
6
$ ruby A181018.rb 4
9
$ ruby A181018.rb 5
16

Ungolfed

def check_columns(board)
  board.transpose.all? do |column|
    !column.join('').match(/111/)
  end
end

def check_if_unsolved(board)
  check_columns(board) && # check columns
    check_columns(board.transpose) && # check rows
    check_columns(board.map.with_index.map { |row, i| [0] * (N - i) + row + [0] * i }) && # check decending diagonals
    check_columns(board.map.with_index.map { |row, i| [0] * i + row + [0] * (N - i) }) # check ascending diagonals
end

def maximum_crosses_to_place(board, index=0)
  board[index / N][index % N] = 1 # set cross at index
  if check_if_unsolved(board)
    crosses = ((index + 1)...(N*N)).map do |i|
      maximum_crosses_to_place(board.map(&:dup), i)
    end
    maximum_crosses = crosses.max || 0
    maximum_crosses + 1
  else
    0
  end
end

N = ARGV[0].to_i
matrix_of_zeros = N.times.map{ [0]*N }

puts maximum_crosses_to_place(matrix_of_zeros)
\$\endgroup\$
1
\$\begingroup\$

Haskell, 143 bytes

In some ways this is not done, but I had fun so here goes:

  • Because checking for the horizontal "winning" pattern returns invalid if applied across different rows, input of N<3 returns 0
  • The "arrays" are integers unpacked into bits, so easily enumerable
  • ((i ! x) y) gives the ith bit of x times y, where negative indices return 0 so the range can be constant (no bounds checking) and fewer parentheses when chained
  • Because the bounds are not checked, it checks 81*4=324 patterns for every possible maximum, leading to N=3 taking my laptop 9 seconds and N=5 taking too long for me to let it finish
  • Boolean logic on 1/0 is used for T/F to save space, for example (*) is &&, (1-x) is (not x), etc.
  • Because it checks integers instead of arrays, (div p1 L)==(div p2 L) is needed to make sure a pattern isn't checked across different rows, where L is the row length and p1, p2 are positions
  • The value of a possible maximum is its Hamming Weight

Here's the code:

r=[0..81]
(%)=div
s=sum
i!x|i<0=(*0)|0<1=(*mod(x%(2^i))2)
f l=maximum[s[i!x$1-s[s[1#2,l#(l+l),(l+1)#(l+l+2),(1-l)#(2-l-l)]|p<-r,let  a#b=p!x$(p+a)!x$(p+b)!x$s[1|p%l==(p+mod b l)%l]]|i<-r]|x<-[0..2^l^2]]
\$\endgroup\$

Your Answer

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

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