# The art of computer programming

EDIT: I know we are not supposed to edit in new requirements after first posting but as far as I understand it this requirement is implicit in all questions here:

Here is a simple but I hope fun one:

Can you recreate any of the following patterns?

Rules:

1. Integer arithmetic only

2. Strictly local, i.e. only a point's x,y coordinates may be used to compute its color

3. No lookup tables

4. No brute-forcing (that's why the no-computers tag is there in case you were wondering), apart from that you may use computers as you see fit.

(5.) The simpler the better

Notes:

The patterns are all periodic and use colors 0,1,2,3,4.
You needn't use the exact same colors, any five colors will do.
I've deliberately put no text version of the patterns because you are not supposed to brute force it.
I'm still quite new to creating puzzles, any feedback is welcome.

One example with solution:

Possible answer $$f(x,y) = \left [ \lfloor \frac x 3 \rfloor - \lceil \frac {y+2x+1} 6 \rceil - \lceil \frac {y+1} 6 \rceil \right ] \mod 5$$

• I really like this puzzle although I've no idea how to solve for the specific examples. I've set up excel with some conditional formatting so that I can adjust parameters of the formula and play with some functions. So am building up methods for what kind of things should be in the functions but am still a long way off yet. Kinda getting lost just making my own patterns instead :) – MooN TreeS Oct 18 '20 at 21:53
• @MooNTreeS It is rather addictive isn't it? Thanks for the feedback and have fun! – Paul Panzer Oct 18 '20 at 22:17
• I assume the the point (0,0) of the images actually represent (0,0) and not just a random starting point of a snippet? I pretty much have pattern #3, but can't make the it exactly look like the depiction. I guess there's something slightly off with my formula, since small shifts don't seem to work. – Lukas Rotter Oct 19 '20 at 7:35
• @LukasRotter (0,0) is in the bottom left corner, but that shouldn't really matter all that much because it is straightforward to shift coordinates in whatever formula you have come up with. – Paul Panzer Oct 19 '20 at 7:51
• +1 for the sheer audacity of having no-computers and computer-puzzle on the same puzzle! – Steve Oct 19 '20 at 12:22

I believe the first pattern is (with (0,0) at top left)

$$\Biggl\{\left\lfloor\frac{2x+3y-2}8\right\rfloor+\left\lfloor\frac{-3x-2y+3}8\right\rfloor \Biggr\} \mathop{\textrm{mod}}5.$$

And the last is (with (0,0) at top left)

$$\Biggl\{x+y+m(x-y)-\left\lfloor\frac x4\right\rfloor\Biggl\}\mathop{\textrm{mod}}5$$

where

$$m(x)$$ goes $$0, +1, 0, -1$$ depending on $$x$$ mod 4. There are lots of lookup-table-free ways to define $$m$$; for instance $$m(x)=(x \mathop{\textrm{mod}}2)\cdot(-1)^{\lfloor x/2\rfloor}$$.

The question has been updated to include a request to "explain your answer".

I don't have much explanation to offer for the first pattern. I just

thought I should try things of the form $$\lfloor\textrm{linear}(x,y)\rfloor+\lfloor\textrm{linear}(x,y)\rfloor\pmod5$$, with the coefficients of the two linear things matching up so as to give the pattern the right sort of symmetry; the periodicity of the pattern suggested that I probably wanted 8 or 16 in the denominators, a bit of experimentation showed (as should have been obvious from the outset) that the difference between the $$x$$ and $$y$$ coefficients shows up in how many "bands" there are from southwest to northeast, and then there were only a few cases to try to see whether they gave the right pattern. After finding something with the right pattern but an offset in $$x$$ and $$y$$, I replaced $$x,y$$ with $$x-\delta,y-\epsilon$$ where $$\delta,\epsilon$$ was the offset I needed to produce, and simplified. Done.

I can say a little more about the fourth.

First of all, the very obvious banding pattern suggested that inside my "... mod 5" I wanted a term $$\lfloor x/4\rfloor$$. The rest then needed to yield a nice simple periodic "snake" pattern. The snakes run southwest-to-northeast going right, right, up, up, right, right, up, up, right, right, etc. If we just took the contours of $$x+y$$ then we would have plain diagonal lines, which are actually rather similar to those snakes; we can turn diagonal lines into snakes by adding and subtracting 1s in a carefully selected set of places. If you add 1 all down a northwest-to-southeast diagonal line, you effectively push all the contours one unit diagonally inward; if you subtract 1, you effectively push them one unit diagonally outward. Staring at the pattern a bit one sees that what's needed is for half the NW-SE diagonals to stay as they are and the other half to alternate between being pushed in and being pushed out, which means we need to add that function $$m(x,y)$$ before reducing mod 5.

• Well done! Now only the most difficult one is left. – Paul Panzer Oct 19 '20 at 13:41
• Well ,this save me the time of beautifying my solution for the last.. – Retudin Oct 19 '20 at 14:13
• One could argue that any finite lookup table can be made "lookup-table-free" in the way you do it. But I grant you $m$ is simple enough to be acceptable. I'm not sure which answer to accept.@LukasRotter I think both could profit from some kind of explanation, for example, showing the patterns generated by individual terms and how they overlay to create the final result. – Paul Panzer Oct 19 '20 at 14:49
• As you say: any finite lookup table can be de-lookup-ified. I think mine is well within the spirit of the thing. Personally I'd rather call it $\Im(i^x)$ but I don't think that counts as "integer arithmetic" even though it's nice and simple and short. – Gareth McCaughan Oct 19 '20 at 16:03
• (That slightly confusing symbol is how LaTeX likes to write the imaginary-part operator.) – Gareth McCaughan Oct 19 '20 at 16:04

(2 out of 4)

$$(0,0)$$ is bottom left, not top left.

2nd pattern:

$$f(x,y) = \left [ \left\lceil \frac {3x} 8 \right\rceil - \left\lfloor \frac {5x} 8 - \frac {y} 4 \right\rfloor \mod 5 - \left\lfloor -\frac {y} 8 \right\rfloor \mod 5 \right] \mod 5$$

3rd pattern:

$$f(x,y) = \left [ \left\lceil \frac {3x+3} 7 \right\rceil - \left\lfloor \frac {6x-y} 7 \right\rfloor - 7 \right] \mod 5$$

• You may try using LaTeX/MathJax \left and \right modifiers, which make the respective parens to adjust their height to the contents – see e.g. \left\lfloor\frac {\frac 1{0+2}} 3\right\rfloor $\left\lfloor\frac {\frac 1{0+2}} 3\right\rfloor$ vs. \lfloor\frac {\frac 1{0+2}} 3\rfloor $\lfloor\frac {\frac 1{0+2}} 3\rfloor$. – CiaPan Oct 19 '20 at 11:56
• @CiaPan Ah, thanks! Will edit right away, as I have a formula for pattern #2 now also – Lukas Rotter Oct 19 '20 at 12:01
• Nice work so far! The third is indeed a bit off, but it is just a matter of tinkering a bit more. – Paul Panzer Oct 19 '20 at 12:16
• @PaulPanzer Wait, I thought I fixed it in my answer. I don't see any difference between your image. Or do you mean the function itself can be expressed way simpler? – Lukas Rotter Oct 19 '20 at 13:42
• Going by the picture there are minor glitches, for example, in the bottom left corner you have red-blue-red where it shoulf be cycling through all five colors before coming back – Paul Panzer Oct 19 '20 at 13:47