Kółko i krzyżyk z tylko krzyżami

32

Wprowadzenie

Wszyscy znają grę w kółko i krzyżyk, ale w tym wyzwaniu wprowadzimy mały zwrot akcji. Będziemy używać tylko krzyży . Pierwsza osoba, która stawia trzy krzyże z rzędu, przegrywa. Ciekawym faktem jest to, że maksymalna liczba krzyży, zanim ktoś straci, wynosi 6 :

X X -
X - X
- X X

Oznacza to, że dla planszy 3 x 3 maksymalna kwota wynosi 6 . Tak więc dla N = 3 musimy wyprowadzić 6.

Kolejny przykład, dla N = 4 lub płyty 4 x 4:

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

To optymalne rozwiązanie, widać, że maksymalna liczba krzyży wynosi 9 . Optymalne rozwiązanie dla płyty 12 x 12 to:

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

Daje to 74 .

Zadanie

Zadanie jest proste, biorąc pod uwagę liczbę całkowitą większą niż 0, wypisuje maksymalną liczbę krzyży, które można umieścić bez trzech X sąsiadujących w linii wzdłuż rzędu, kolumny lub po przekątnej.

Przypadki testowe

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

Więcej informacji można znaleźć na https://oeis.org/A181018 .

Zasady

  • To jest , więc wygrywanie z najmniejszą ilością bajtów wygrywa!
  • Możesz podać funkcję lub program.
Adnan
źródło
7
Pytanie sprowadza się więc do użycia formuł na stronie, którą
dowiązałeś
2
Powiązany post na temat matematyki.
AdmBorkBork
7
@nicael Z tego, co widzę, artykuł OEIS zawiera tylko dolne granice.
Martin Ender
6
Byłoby fajnie widzieć to jako najszybsze wyzwanie dla kodu.
Łukasz
4
Nie jest to rozwiązanie dla codegolfa, ale przez ostatnie kilka dni grałem solwerem „wizualnym”. Możesz uzyskać dostęp do jsfiddle tutaj: jsfiddle.net/V92Gn/3899 Próbuje znaleźć rozwiązania poprzez losowe mutacje. Nie zatrzyma się, jeśli znajdzie „poprawną” odpowiedź, ale może dotrzeć do wielu poprawnych rozwiązań znacznie szybciej niż te poniżej.
styletron

Odpowiedzi:

11

Pyth, 57 51 49 bajtów

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

Podobnie jak rozwiązanie CJam @ PeterTaylor, jest to brutalna siła, więc działa w czasie O (n 2 2 n 2 ). Tłumacz online nie kończy się w ciągu minuty dla n = 4.

Wypróbuj tutaj dla N <4.

Wypróbuj funkcję przekątnych .

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
lirtosiast
źródło
13

CJam ( 58 56 bajtów)

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

Jest to niezwykle powolne i zajmuje dużo pamięci, ale dla ciebie to w .

Sekcja

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

Θ(aX)a1.83928675Θ(aX2)Θ(aX4)


O(Xa3X)

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;
    }
}
Peter Taylor
źródło
W czym działa skuteczne podejście?
lirtosiast
@ThomasKwa, och, wciąż jest wykładniczy, ale myślę, że uzasadnione jest nazywanie go wydajnym, ponieważ pozwolił mi wydłużyć sekwencję OEIS o 3 terminy.
Peter Taylor
@ThomasKwa, a dokładniej, to O(n a^n)gdzie a ~= 5.518.
Peter Taylor
4

DO, 460 456 410 407 362 351 318 bajtów

To jest naprawdę zła odpowiedź. To niezwykle wolne podejście z użyciem brutalnej siły.Staram się trochę pograć w golfa, łącząc forpętle.

#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));}

Przypadki testowe

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

Bez golfa

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 */
}

Edycja: Zadeklaruj zmienne int jako nieużywane parametry; usuń współrzędną y, po prostu użyj indeksu; przenieś zmienną na listę parametrów zamiast globalnej, napraw niepotrzebne parametry przekazywane do s(); połącz w pętle, usuń niepotrzebne nawiasy; zastępuje &&się *, ||w +; makro-ify kontrola 3 w rzędzie

Cole Cameron
źródło
Jak wolne jest to
Loovjo,
@Loovjo próbował na moim komputerze z kilkoma małymi zmianami, aby przyspieszyć, 15ms dla n = 5, 12 sekund dla n = 6 (wejście +1, czas * 800)!
edc65
@ edc65 To było moje doświadczenie. Cokolwiek większego niż 5, wydajność była znacznie wolniejsza. Nie zawracałem sobie głowy próbowaniem danych wejściowych większych niż 6.
Cole Cameron
Zacząłem od 7, kiedy opublikowałem swój komentarz. Zobaczymy
edc65
Możesz wycisnąć jeszcze kilka znaków #define d(x,y)b[x]*b[x+y]*b[x+y+y]; zmieniając początek sna s(i,m){for(m=n-2;i zastępując wszystkie wystąpienia n-2; i zmieniając b[x]++się b[x++]++i następnie zastąpienie x==n*n-1z x==n*n, x+1z x, i xz x-1.
Peter Taylor
4

C 263 264 283 309

Edytuj Kilka bajtów zaoszczędzonych dzięki @Peter Taylor - mniej niż się spodziewałem. Następnie 2 bajty przydzieliły więcej pamięci, teraz mogę wypróbować większy rozmiar, ale staje się to bardzo czasochłonne.

Uwaga Dodając wyjaśnienie, odkryłem, że marnuję bajty, utrzymując siatkę w tablicy R - abyś mógł zobaczyć znalezione rozwiązanie ... nie jest wymagane dla tego wyzwania !!
Usunąłem go w wersji golfowej

Program C w golfa, który w rozsądnym czasie może faktycznie znaleźć odpowiedź dla n = 1..10.

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);}

Mój test:

7 -> 26 w 10 sek.
8 -> 36 w 18 sek.
9 -> 42 w 1162 sek

Mniej gra w golfa i próbuję wyjaśnić

#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);
}
edc65
źródło
Zasadniczo jest to to samo, co mój program Java, ale najpierw głębokość, a nie szerokość. Myślę, że powinieneś być w stanie zapisać co najmniej tuzin znaków, przenosząc moją buildRowsmetodę; może nawet 20, jeśli for(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v;jest ważne. (Obecnie nie mam dostępu do kompilatora C).
Peter Taylor
1
@PeterTaylor dam mu spojrzenie ... tylko słowo tribonacci mnie przeraża
edc65
Twój zaszyfrowany 999oznacza, że ​​chcesz zignorować tę część. Chociaż może naprawdę powinieneś sprawić, by nie był zakodowany na stałe, aby w zasadzie poradzić sobie z większymi wejściami niż 11 lub 12.
Peter Taylor
@PeterTaylor działałoby świetnie, gdybym miał metodę .bitCount w C do liczenia bitów. Ale w tej początkowej fazie dopasowuję liczbę bitów w B, nie tylko maski bitów w V
edc65
2

Rubinowy, 263 bajty

Jest to również rozwiązanie brutalnej siły i napotyka te same problemy, co odpowiedź C Cole'a Camerona, ale jest jeszcze wolniejsze, ponieważ jest rubinowe, a nie C. Ale hej, jest krótszy.

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}]

Przypadki testowe

$ 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

Bez golfa

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)
Siim Liiser
źródło
1

Haskell, 143 bajty

W pewnym sensie tak się nie dzieje, ale dobrze się bawiłem, więc oto:

  • Ponieważ sprawdzanie poziomego wzorca „wygrywającego” zwraca wartość niepoprawną, jeśli zostanie zastosowane w różnych wierszach, wprowadzenie N <3 zwraca 0
  • „Tablice” to liczby całkowite rozpakowane w bity, więc łatwo je policzyć
  • ((i! x) y) daje i-ty bit x razy y, gdzie indeksy ujemne zwracają 0, więc zakres może być stały (bez sprawdzania granic) i mniejszej liczby nawiasów po połączeniu
  • Ponieważ granice nie są sprawdzane, sprawdza 81 * 4 = 324 wzorce dla każdego możliwego maksimum, co prowadzi do N = 3 zajmuje mojemu laptopowi 9 sekund i N = 5 trwa zbyt długo, żebym mógł zakończyć
  • Logika logiczna na 1/0 jest używana dla T / F do oszczędzania miejsca, na przykład (*) to &&, (1-x) to (nie x) itp.
  • Ponieważ sprawdza tablice liczb całkowitych zamiast tablic, (div p1 L) == (div p2 L) jest potrzebny, aby upewnić się, że wzorzec nie jest sprawdzany w różnych wierszach, gdzie L jest długością wiersza, a p1, p2 są pozycjami
  • Wartością możliwego maksimum jest jego Masa Hamminga

Oto kod:

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]]
Michael Klein
źródło