26
\$\begingroup\$

Your task is to output all possible ways to end a game with a tie (all rows, columns, and diagonals are completely filled and do not have 3 X's or 3 O's, and there are exactly 5 X's and 4 O's in total) in Tic-Tac-Toe (assuming X goes first):

OXO  XXO  XOX  OXX
XOX  OOX  XOX  XOO
XOX  XXO  OXO  OXX

XOX  XOX  OXX  XXO
OOX  XOO  XOO  OOX
XXO  OXX  XOX  XOX

XOX  OXX  OXO  XOO
XXO  XXO  OXX  OXX
OXO  OOX  XOX  XXO

OXO  XXO  XOX  OOX
XXO  OXX  OXX  XXO
XOX  XOO  OXO  OXX

(It does not need to be arranged in the above way.)

Rules

  • Output can be in any convenient format.
  • You may use different characters to represent X and O as long as they are distinct.
  • Standard loopholes are forbidden.
  • This is , so the shortest code in bytes wins.
\$\endgroup\$
4
  • 6
    \$\begingroup\$ For output OXO/XOX/XOX, is OXOXOXXOX allowed? And what about 010101101, 10101101, or even 269488385? \$\endgroup\$
    – tsh
    Jul 14, 2022 at 4:00
  • \$\begingroup\$ @tsh Can you explain what 269488385 represents? \$\endgroup\$ Jul 14, 2022 at 4:53
  • 2
    \$\begingroup\$ @thejonymyster ah, sorry for the typo. It is \$10101101_{(16)} = 269488385_{(10)}\$. Maybe I want to say 173 (\$173_{(10)}=10101101_{(2)}\$) instead... \$\endgroup\$
    – tsh
    Jul 14, 2022 at 5:34
  • 2
    \$\begingroup\$ @tsh Yes, but not the last two. \$\endgroup\$
    – Yousername
    Jul 14, 2022 at 12:16

15 Answers 15

12
\$\begingroup\$

Jelly,  16  15 bytes

“œNZjr⁽⁾ƈ‘+⁹BUƬ

A niladic Link that yields a list of lists of lists (a 2 by 8 array of flattened boards) with 1s representing Xs and 0s representing Os.

Try it online! Or see them in the format and order given in the question here.

How?

Using only reflection in one axis is terser than using four rotational symmetries like in my original 16-byte code (below).

“œNZjr⁽⁾ƈ‘+⁹BUƬ - Link: no arguments
“œNZjr⁽⁾ƈ‘      - Code page indices = [30,78,90,106,114,141,142,156]
          +⁹    - add 256 -> [286, 334, 346, 362, 370, 397, 398, 412]
            B   - to binary
              Ƭ - collect up while distinct applying:
             U  -   reverse each

Previous @16 bytes:
“⁾⁽ʠ⁷‘ḤBs€3ZṚ$Ƭ€

A niladic Link that yields a list of lists of lists of lists (a 4 by 4 array of 2d boards) with 1s representing Os and 0s representing Xs.

Try it online! Or see them in the format and order given in the question here.

How?

“⁾⁽ʠ⁷‘ḤBs€3ZṚ$Ƭ€ - Link: no arguments
“⁾⁽ʠ⁷‘           - Code page indices = [142,141,165,135]
      Ḥ          - double -> [284,282,330,270]
       B         - to binary -> [[1,0,0,0,1,1,1,0,0],
                                 [1,0,0,0,1,1,0,1,0],
                                 [1,0,1,0,0,1,0,1,0],
                                 [1,0,0,0,0,1,1,1,0]]
        s€3      - split each into threes -> [[[1,0,0],
                                               [0,1,1],
                                               [1,0,0]],
                                              [[1,0,0],
                                               [0,1,1],
                                               [0,1,0]],
                                              [[1,0,1],
                                               [0,0,1],
                                               [0,1,0]],
                                              [[1,0,0],
                                               [0,0,1],
                                               [1,1,0]]]
               € - for each:
              Ƭ  -   collect up while distinct applying:
             $   -     last two links as a monad:
           Z     -       transpose  }
            Ṛ    -       reverse    } - together these rotate a quarter
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Jesus christ, lol. \$\endgroup\$ Jul 14, 2022 at 14:38
7
\$\begingroup\$

Desmos, 142 138 123 120 112 111 bytes

-8 bytes thanks to @fireflame

-1 byte thanks to @Steffan

X=x-[0...3]4+.5
\mod([23312905373,30555191537,48690981746,53478745886]/2^{3\floor(y)+\floor(X)},2)>.99\{0<X<3\}

Try It On Desmos!

Rendered in desmos

\$\endgroup\$
4
  • \$\begingroup\$ Some ideas for 112 bytes. Could be -3 more; can you find a way to avoid the .99? desmos.com/calculator/py6mtjzkif \$\endgroup\$ Jul 17, 2022 at 1:52
  • \$\begingroup\$ Doing it in the form 0<{mod(__,2)>=1} works but that seems to be more bytes \$\endgroup\$ Jul 17, 2022 at 2:25
  • \$\begingroup\$ @Steffan It does need to be stored in the variable. That's because of {} in the next line and when pasted that it doesn't work with inbuilt functions because it doesn't convert them to \operatorname so the only way to do it is to store it in a variable and use it in the next line instead. \$\endgroup\$ Jul 21, 2022 at 1:41
  • \$\begingroup\$ @Steffan Oh neat, I didn't calculate the difference in bytes and assumed the inline way would take longer (because it usually does). I'll make the edit! \$\endgroup\$ Jul 21, 2022 at 2:04
6
\$\begingroup\$

///, 97 bytes

/g/ \/\///a/OXOgb/XXOgc/XOXgd/OXXge/XOOgf/OOX /abcdccdbcdaeabcf
cfcefeefbbddbddb
cbadbdccafcbcead

Try it online!

I tried rearranging them so that more duplicates would appear together but it didn't save any bytes. I'm sure theres more that can be done here though. Good luck to whoever takes this on in Regenerate, I did not have the guts.

Note: /// programs do not take any input, so don't worry about the input being used in the TIO link, lol.

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 17 bytes

»~qǔ:ṙ⁋»₆τ¦₈+b:RJ

Try it Online! Port of 05AB1E thanks to Steffan.

          ¦       # Cumulative sums of...
        ₆τ        # Base 64 digits of...
»~qǔ:ṙ⁋»          # Compressed integer
           ₈+     # + 256
             b    # Convert each to binary
              :RJ # Append each matrix reversed
\$\endgroup\$
2
  • \$\begingroup\$ @KevinCruijssen Oops. Will fix \$\endgroup\$
    – emanresu A
    Jul 14, 2022 at 8:16
  • 1
    \$\begingroup\$ 17 bytes by porting osabie: Try it Online! \$\endgroup\$
    – naffetS
    Jul 14, 2022 at 22:28
5
\$\begingroup\$

R, 113 111 110 bytes

Edit: -1 byte, and from that idea -1 more, and then another -1 more, all thanks to pajonk

for(i in 0:511)sum(a<-matrix(i%/%2^(0:8)%%2,3))==5&all(rowSums(rbind(a,t(a),diag(a),a[1:3*2+1]))%%3)&&print(a)

Try it online!

Outputs tic-tac-toe matrices using 1s for Xs and 0s for Os.

Calculates 3x3 matrices of binary digits of 0...511, and checks whether any of the column sums, row sums, diagonal or antidiagonal are equal to zero modulo 3 (meaning that they're all Xs (3 = 0 mod 3) or all 0s (0)).

\$\endgroup\$
5
  • \$\begingroup\$ -1 byte. \$\endgroup\$
    – pajonk
    Jul 14, 2022 at 14:27
  • \$\begingroup\$ @pajonk - Thanks, and thanks for the idea from that, too! \$\endgroup\$ Jul 14, 2022 at 14:56
  • 1
    \$\begingroup\$ I thought about using 2n+1, but this seemed longer and I didn't bother to check. Well, I was wrong. \$\endgroup\$
    – pajonk
    Jul 14, 2022 at 16:47
  • \$\begingroup\$ 110 bytes \$\endgroup\$
    – pajonk
    Jul 15, 2022 at 19:03
  • \$\begingroup\$ @pajonk Thanks again! \$\endgroup\$ Jul 15, 2022 at 20:20
5
\$\begingroup\$

Ruby, 90 ... 45 bytes

"s*.-0	".bytes{|k|puts"%09b"%$.+=k}

Try it online!

How it works:

  • If we can flatten the array, this means we only have to output 16 numbers between 115 and 412.
  • Instead of using the numbers directly, I sort them and use the successive difference. This limits the range to 1-115, which is within the boundaries of ASCII
\$\endgroup\$
3
  • \$\begingroup\$ Perhaps unprintables might help? \$\endgroup\$
    – emanresu A
    Jul 14, 2022 at 8:55
  • \$\begingroup\$ @emanresuA: Only if I keep them in the 8-bit range. \$\endgroup\$
    – G B
    Jul 14, 2022 at 9:39
  • \$\begingroup\$ ("%09b"%c).scan /.{,3}/ saves a byte \$\endgroup\$
    – ovs
    Jul 14, 2022 at 10:52
2
\$\begingroup\$

Python 3, 64 bytes

  • -2 bytes suggested by pxeger.
for i in'ƍŎţåĞŲñƎŪã­ƜŚsµ':print(f"{ord(i):09b}")

Try it online!

A really boring answer. Or 65 bytes without unprintable.


And this is a (somehow) interesting 94 bytes answer:

print(*["OXOOXXOX\n"[int(i):][:3]for i in str(0x2267c4d16c9d1787f15058d56ba14c7aacee2a628cf)])

-2 bytes suggested by G B. Maybe it can be golfed more.

\$\endgroup\$
2
  • \$\begingroup\$ 64 bytes for the flat version: Try it online! \$\endgroup\$
    – pxeger
    Jul 14, 2022 at 8:34
  • \$\begingroup\$ how big for ascii-only? my phone can't print some of "without unprintable" characters, lol \$\endgroup\$ Jul 16, 2022 at 11:04
2
\$\begingroup\$

brainf***, 264 bytes

-.-.+.-.+.-..+.-.>.<..+...-...+.>.<.-...+...-..>.<.+.-.+..-...+.>.<.-...+..-.+.-.>.<.+.-..+...-..>.<..+...-..+.-.>.<.+.-...+..-.+.>.<.-....+...-.>.<.+.-.+.-..+.-.+.>.<.-.+..-...+.-.>.<.+...-....+.>.<.-.+.-..+.-.+.-.>.<..+..-...+..>.<..-...+..-..>.<.+.-..+.-.+.-.+.

Try it online!

Outputs the games separated by nulls. ÿ is O and þ is X.
It's hard-coded, manipulating address 1 to switch between 255 (ÿ) and 254 (þ) as needed. After each game, >.< moves the pointer to address 2, prints 0 (null), and returns to address 1. A few bytes were saved by modifying the order of the games.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 25 19 18 15 bytes

•“ª?’즾Ô*•bº9ô

-9 bytes thanks to @CommandMaster

Outputs the results as a list of flattened strings, each consisting of nine 1/0 for X/O respectively.

Try it online. (Feel free to remove the footer that pretty-prints the results to see the actual result.)

Explanation:

•“ª?’즾Ô*• # Push compressed integer 2639961594228296764259
  b         # Convert it to binary: 100011110001110011010011101010101101010110101011100011011100101101100011
   º        # Mirror it: 100011110001110011010011101010101101010110101011100011011100101101100011110001101101001110110001110101011010101101010101110010110011100011110001
    9ô      # Split it into parts of size 9: ["100011110","001110011","010011101","010101101","010110101","011100011","011100101","101100011","110001101","101001110","110001110","101011010","101101010","101110010","110011100","011110001"]
            # (after which the list is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •“ª?’즾Ô*• is 2639961594228296764259.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 19 bytes using symmetry \$\endgroup\$ Jul 14, 2022 at 9:55
  • \$\begingroup\$ @CommandMaster Smart! Thanks. :) \$\endgroup\$ Jul 14, 2022 at 10:46
  • \$\begingroup\$ Does base 64 save any bytes? \$\endgroup\$
    – emanresu A
    Jul 14, 2022 at 11:26
  • \$\begingroup\$ @emanresuA 05AB1E lacks a single-byte builtin for 64, so probably not. In some cases using a base for which a single-byte builtin is available (10,26,36,95,100,255,256,1000) for the base-list is indeed shorter, but to change the base-49 list to a base-95 list would increase the compressed larger integer, making the byte-count the same in this case. \$\endgroup\$ Jul 14, 2022 at 14:38
  • 1
    \$\begingroup\$ •“ª?’즾Ô*•bº9ô 15 bytes \$\endgroup\$ Jul 19, 2022 at 19:37
1
\$\begingroup\$

Charcoal, 31 bytes

F⪪”{∨I⦄↶r↘G”⁹«⎚⪪ι³F⁴«D⟲»»‖F³«D⟲

Try it online! Link is to verbose version of code. Outputs all 16 3×3 boards consecutively without vertical separation. Explanation:

F⪪”{∨I⦄↶r↘G”⁹«

Split the compressed string OXOXOXXOXXOXOOXXXOXOXXXOOXO into three substrings of 9 letters and loop over each substring.

Clear the canvas.

⪪ι³

Split the substring into three substrings of three letters and print each on its own line.

F⁴«

Repeat four times:

Output the current canvas state.

Rotate the canvas.

»»‖

Reflect the last board.

F³«D⟲

Manually output three rotations, and allow the final rotation to implicitly print.

Since the output is difficult to read, here's a 38 byte version which spaces out the boards: Try it online! Link is to verbose version of code.

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 51 bytes

ṁ₃{{0|1}ᵐ².c+5∧.{|\|↺ʰ↻ᵗ{bᵐhᵐg}|↺ᵗ↻ʰ↰₄}ᶠ{⊇Ċ≠}ᵐ²∧}ᶠd

Try it online!

Absurdly long but at least it's not boring hardcoding. I'm sure there are shorter ways to describe the constraints of the matrix.

Explanation

ṁ₃                                 Take a 3x3 matrix
  {                          }ᶠ    Find all:
   {0|1}ᵐ².                          The matrix is filled with 0s and 1s
   .c+5∧                             The sum of all elements is 5
   .{                      }ᶠ        Find all:
     |                                 The original matrix
      \|                               The transpose
        ↺ʰ↻ᵗ{bᵐhᵐg}|                   The anti-diagonal
                    ↺ᵗ↻ʰ↰₄             The diagonal
   {⊇Ċ≠}ᵐ²∧                          Each row must have at least two different elements
d                                   Remove duplicates
\$\endgroup\$
5
  • \$\begingroup\$ 40 \$\endgroup\$ Jul 15, 2022 at 23:18
  • 1
    \$\begingroup\$ @UnrelatedString 37 as a generator \$\endgroup\$
    – DLosc
    Jul 16, 2022 at 1:14
  • 1
    \$\begingroup\$ 33 with a shorter method of generating "3x3 matrix with four 0's and five 1's" \$\endgroup\$
    – DLosc
    Jul 16, 2022 at 1:44
  • 1
    \$\begingroup\$ @DLosc Nice! You should post it \$\endgroup\$
    – Fatalize
    Jul 16, 2022 at 23:17
  • \$\begingroup\$ Oh, there's another byte to shave off from my code for the diagonal \$\endgroup\$ Jul 17, 2022 at 2:05
1
\$\begingroup\$

lin, 50 bytes

\OX9`/\ \­ƎŪãŖţåƍŲñеƜŚs <chars g:

Try it here! Generates a list of lists where each row is a tied board.

Copy-paste-friendly version for testing (includes pretty-printing):

\OX9`/\ ; g: ((( 3cols ( str outln ) map ) ' n\ outln ) map ) '
[173 398 362 227 342 355 229 397 370 241 157 286 181 412 346 115]

Explanation

  • \OX9`/\ get all length-9 sequences of X's and O's
  • \... <chars convert string to charcodes
  • g: use charcodes as indices in list of length-9 sequences
\$\endgroup\$
3
  • \$\begingroup\$ why non-competing? \$\endgroup\$ Jul 16, 2022 at 15:44
  • \$\begingroup\$ @thejonymyster I've been quite actively developing/bug-fixing lin over the past few days; unfortunately, I doubt the submission above would work in a previous version released before this challenge was made. \$\endgroup\$ Jul 16, 2022 at 16:32
  • \$\begingroup\$ @Steffan wow good to know! Thanks for letting me know \$\endgroup\$ Jul 17, 2022 at 7:53
0
\$\begingroup\$

Rust, 168 bytes

let g=|m|[7,292,146,180,56,448,73,448,84,273].iter().all(|b|b&m!=*b);let f=||(0..512).filter(|m:&u16|m.count_ones()==4&&g(*m)&&g(!m)).fold((),|_,b|print!("{b:0>9b}
"));

Attempt This Online!

Prints the result in binary. 1=X and 0=O

\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 97 bytes


9$*0512$*
1
¶$`
+`(1+)\1
$+0
01
1
.+(.{9})
$1
G`(1.*){5}
...
[$&]
A`(\d)(.)*\1(?<-2>.)*(?(2)^)\1

Try it online! Outputs each board with the rows marked in the format [101][101][010] using 1 for X and 0 for O. Explanation:


9$*0512$*
1
¶$`

Count up to 511 in unary, with padding. (0 gets listed twice, but we'll delete that later anyway.)

+`(1+)\1
$+0
01
1

Convert to binary.

.+(.{9})
$1

Trim the result back down to 9 digits.

G`(1.*){5}

Keep those with (at least) 5 Xs. (Boards with 6 or more Xs will always have at least one winning line so will get eliminated anyway.)

...
[$&]

Split into three groups of three.

A`(\d)(.)*\1(?<-2>.)*(?(2)^)\1

Omit boards which aren't ties (i.e. wins or invalid). See my answer to Tic-Tac-Toe - X or O? for how the regular expression works.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -Mbigint, 65 bytes

say for 0xce63b1b72b558eb54e8f3c5cae35aab53a73->to_bin()=~/.{9}/g

Try it online!

Uses 1 for X and 0 for O; Outputs flat strings, one grid per line.

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