People are rightfully pointing out that this can be compressed further.
My challenge to you: Implement a compressed representation along with the get_cell and set_cell methods, without resorting to lookup tables!
Also, check out Alejandra's blog at https://goose.love/!
(And yeah, you need 12 or 13 bits, not 10, if you don't want to eliminate symmetries.)
It follows the principle that one can represent a board by choosing k filled spots from 9 and then choosing k / 2 Os from k. These two combinations can be converted into an index, which can then be offset according to k to prevent collisions with indices from other ks. This offset is not pretty, but it works.
I haven't thoroughly tested my code, but the principle should work even if there's a bug or two :)
With some luck I'll find time to write a clearer explanation or a blog post.
I don’t see how that makes a difference. You can always replace a lookup table by code, for example:
a = [832, 54, 743]
func a(i) =
if i = 0 return 832
if i = 1 return 54
return 743
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
For pure functions taking finite inputs, the reverse is possible, too. For example, you can define and on booleans as a 2 × 2 array
and = [[false, false], [false, true]]
I think I would judge solutions not on avoiding lookup tables, but on size of the encoding and, for programs that produce equal size encodings, the total number of bytes in the programs, using “less is better” as criterion for both.
I agree that the challenge isn't rigorously defined. But the spirit is to not allow this kind of trick.