Encode each number by swapping base 2 with base 5, without changing
the digits. So binary 11011 (27) is represented as base-5 11011 (756).
This allows you to sum up to 4 such numbers without experiencing
overflow from one digit to the next (since 4 1's adds up to just 4).
Essentially, you are performing b additions in parallel. If the
numbers you are summing are all the same, and the pseudoliberty count
(#libs) is no more than 4, then each base-5 digit of the sum will
equal 0 or #libs.
With a slight modification, you can also eliminate the pseudoliberty
count completely and just use a single number. Take the largest code
value you will need, add 1, multiply by four, round up to the next
power of 5, and add this value to every code value, and now you can
just use the test
if (code_sum <= threshold) {
&& ((code_sum code_sum div threshold
! All you have to do is to add a sufficiently large fixed value to
every single representation.
Intersperse double-zeroes inside your input value, so binary 11011 is
encoded as 1001000001001. Now summing up to 7 such values is
guaranteed not to overflow one triad of bits to another, so
essentially you're performing b binary additions in parallel.
That's it. Divide the sum by
a little bit more than 3b bits. 3b bits seems to be very much
This could be made more compact, but then bitmasking wouldn't be as easy.
. Any coordinate is just a sequence of bits. Each bit can be encoded
separately. So the problem reduces to how to encode a single bit (0 or
1) so that the sum of up to 4 values equals a given number (say 0)
only if the bit is equal each time.
For bitmasking ease, you can use 3 bits per bit. Spread each input
number out like this: the
Up to 4 times 1 (mod 0) equals 0 only if
On 11/14/07, John Tromp <[EMAIL PROTECTED]> wrote:
> On Nov 14, 2007 5:03 PM, Imran Hendley <[EMAIL PROTECTED]> wrote:
> >
> > On Nov 14, 2007 3:19 PM, John Tromp <[EMAIL PROTECTED]> wrote:
> > > On Nov 14, 2007 2:00 PM, John Tromp <[EMAIL PROTECTED]> wrote:
> > >
> > > > My solution doesn't make use of that, and satisfies the stronger
> > > > property:
> > >
> > > > 0 <= a_i <= 4 and sum a_i * n_i is in 1*nums union 2*nums union 3*nums
> > > > union 4*nums
> > > > => only one a_i is nonzero.
> > >
> > > that was not quite correct. it should say:
> > >
> > > let a_i be the number of adjacencies to a liberty at point i.
> > >
> > > if sum a_i <= 4, and sum (a_i * n_i) is in {1,2,3,4} * nums,
> > > then only one a_i is nonzero.
> >
> > I'm really lost now. a_i is the number of stones we have adjacent to a
> > liberty at intersection i? Do we need to know the location of our
> > liberties to update sum a_i? How is this easier than just remembering
>
> For every string, you can keep track of this sum incrementally.
> When the string establishes a new adjacency to an empty point i,
> you add code[i] into the sum.
>
> > the locations of all real liberties you saw? How do we know that the
> > stones around i are from the same group? What are the n_i in
>
> n_i was the name that Tom gave to my code[i].
>
> > sum(a_i*n_i)? is {1,2,3,4}*nums supposed to be a cartesian product of
>
> no, it's just my shorthand for the union of the 4 sets nums, 2*nums,
> 3*nums and 4*nums.
>
> regards,
> -John
> _______________________________________________
> computer-go mailing list
> [email protected]
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
