3 ms·

OP here! People are rightfully pointing out that this can be compressed further. My challenge to you: Implement a compressed representation along with the get

OP here! 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/ https://goose.love/! (And yeah, you need 12 or 13 bits, not 10, if you don't want to eliminate symmetries.)

kqr 3y ago
I thought the point of the article (actual working implementations) was fairly obvious, and I'm sorry to see people miss it!
Someone 3y ago
> without resorting to lookup tables! I don’t see how that makes a difference. You can always replace a lookup table by code, for example: a = [832, 54, 743] vs func a(i) = if i = 0 return 832 if i = 1 return 54 return 743 The classic example of this are the definitions of cons, car and cdr in SICP as lambdas: (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))) See https://stackoverflow.com/a/21769444 https://stackoverflow.com/a/21769444 for an explanation. 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]] and then do a and[x, y] lookup to evaluate it. That’s why some functional languages (for example scala) do not make a distinction between array indexing, hash table lookups, and function calls. After all, they all are mathematical functions taking a single value and producing one. 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.
- cbarrick 3y ago
  I would consider an if-chain to be a lookup table. A sufficiently smart compiler would treat it as one. I agree that the challenge isn't rigorously defined. But the spirit is to not allow this kind of trick.
ashdnazg 3y ago
This code encodes a board into [0, 6045] which fits in 13 bits: https://gist.github.com/ashdnazg/5cca7de6bac0eef4532d0c635c69184a https://gist.github.com/ashdnazg/5cca7de6bac0eef4532d0c635c6... 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.
- cbarrick 3y ago
  Ooo exciting. Keep me posted when you write it up!

kqr 3y ago

I thought the point of the article (actual working implementations) was fairly obvious, and I'm sorry to see people miss it!

Someone 3y ago

> without resorting to lookup tables! I don’t see how that makes a difference. You can always replace a lookup table by code, for example: a = [832, 54, 743] vs func a(i) = if i = 0 return 832 if i = 1 return 54 return 743 The classic example of this are the definitions of cons, car and cdr in SICP as lambdas: (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))) See https://stackoverflow.com/a/21769444 https://stackoverflow.com/a/21769444 for an explanation. 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]] and then do a and[x, y] lookup to evaluate it. That’s why some functional languages (for example scala) do not make a distinction between array indexing, hash table lookups, and function calls. After all, they all are mathematical functions taking a single value and producing one. 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.

cbarrick 3y ago
I would consider an if-chain to be a lookup table. A sufficiently smart compiler would treat it as one. I agree that the challenge isn't rigorously defined. But the spirit is to not allow this kind of trick.

ashdnazg 3y ago

This code encodes a board into [0, 6045] which fits in 13 bits: https://gist.github.com/ashdnazg/5cca7de6bac0eef4532d0c635c69184a https://gist.github.com/ashdnazg/5cca7de6bac0eef4532d0c635c6... 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.

cbarrick 3y ago
Ooo exciting. Keep me posted when you write it up!