search

PleasingFungus / Silicon-Zeroes

Issue repository for Silicon Zeroes. (Contains no actual code.)
12 stars 0 forks source link

Tick limit on "Odds" #101

Closed andersk closed 7 years ago

andersk commented 7 years ago

The tick limit on the puzzle "Odds" seems to be computed as the sum of the absolute values of the numbers, but the number of ticks required by the most straightforward solution is the sum of one more than the absolute values of the numbers. Is that intentional?

PleasingFungus commented 7 years ago

It's not intentional, but I'm not sure it's a problem. What is the "most straightforward solution"?

andersk commented 7 years ago

(Feel free to delete spoilers.)

Keep a pointer to the current memory location, a counter that runs 0, 1, 2, 3, ..., and an alternating parity bit. On each tick, compare both the counter and its negative with the value at the current location; if either are equal, store the parity bit at the current location, then reset the counter and the parity bit and move the pointer to the next location.

If the values in memory are, say, 3, 0, -4, 1, then the counter needs to run 0, 1, 2, 3, 0, 0, 1, 2, 3, 4, 0, 1 for a total of 4 + 1 + 5 + 2 ticks.

Obviously there are many possible solutions, but none of them can get around the fact that it certainly takes a nonzero amount of time to process a 0 in memory. No solution can skip over an arbitrary number of 0s in constant time.

PleasingFungus commented 7 years ago

True! You can run quite a lot faster than your solution, but I do like your solution, so I'll double the time limit for the puzzle in f726c361. (Will be in the next release, on Monday.)

Thanks for reporting!

andersk commented 7 years ago

I’m running 1.1.1.1-gffa46c9a, and the tick limit for test 001 (3, 2, -1, 10, -9, 21, -30) is still 74 ticks; the above solution needs 83. It looks like you only increased the limit for tests after 001.

PleasingFungus commented 7 years ago

Ah, oops, good catch! Fixed again in 240ccc96, for the next next release.