brhfl.com

Aztec diamonds: Testing the reversed Aztec numbers

My initial test of x=ceil(sqrt(2y)/2) to determine the size of a square given a value in A046092 corresponding to how many line segments would remain if the grid formed internally at every unit of height and width of the square was broken at every intersection was tested and shown to be valid for the first 1000 numbers in the sequence. I did this haphazardly in Excel, just to make sure it wasn’t going to fail quickly.

I have since scripted a test in python, which has thus far shown my method viable up to a 50907428697×50907428697 square. The script is called by passing it an argument containing the initial integer for the square’s size (default 2), and it loops infinitely until it either fails or is halted with SIGINT. Upon halting, it returns something like Last success: Square 39033633; azNum 3047249088424644; urNum 39033633.0, where Square is the height/width of the square being tested, azNum is the number of line segments (or squares in the equivalent Aztec diamond), and urNum is the calculation which (hopefully) is equal to Square. Revealing the last success in this way tells me where to start next time. The code:

import signal
import sys
from math import ceil,sqrt
def sigintHdl(signal,f):
    print "Last success: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)
    sys.exit(0)
signal.signal(signal.SIGINT,sigintHdl)
tNum = 2 if len(sys.argv)<2 or int(sys.argv[1])<2 else int(sys.argv[1])
result=0
while result==0:
    azNum=tNum**2+tNum*(tNum-2)
    urNum=ceil(((2*azNum)**.5)/2)
    result=urNum-tNum
    tNum+=1
print "FAILURE: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)

There’s another way of looking at this whole thing. If we consider an isosceles right triangle with hypotenuse h, we know the length of either of the legs is equal to sqrt(h^2/2). Interestingly enough, if we work with a hypotenuse of one unit larger (which should never exist as a halved Aztec diamond), h^2/2 is equal to our A046092 value +0.5.

24 units in diamond 7 2 / 2 = 2 4 . 5

Ultimately, the problem seems to be one of dealing with a not-quite-proper triangle. It’s easy to imagine additional nodes that make the triangle more… triangular. Doing so leads to more funny math, but it all sort of, kind of makes sense. I guarantee there’s an off-the-shelf solution out there, and it’s likely quite straightforward and, in hindsight, obvious. But this sort of math isn’t necessarily my forté, so I’ll just fidget around until I come up with something conclusive. At this point, it’s all for fun – I have far more known-valid values than I could ever imagine needing. My little python test snippet will easily be reused for other things as well, so I’ll call that a win.


Aztec diamonds: How I came to learn of them

A little project I’m working on requires me to suss out the size of a square given the following: Imagine a square of width and height x units. The square is gridded by unit such that x^2 squares are visible inside it. How many of these squares’ perimeter lines exist inside the outer square? Or, put another way, if you then erase the border of the original square and break every line segment at the intersections, how many line segments do you have left?

1 2 3 4 5 6 7 11 12 13 14 18 19 20 21 8 9 10 15 16 17 22 23 24

It seems to work out to x^2+x*(x-2). For a 2×2 square, there are 4 segments left. 3×3 yields 12, 4×4 yields 24, 5×5 yields 40, 6×6 yields 60, and so on. I confirmed this far by manually counting the segments, and everything seemed good. This wasn’t what I needed, however, I needed to be able to do it in reverse – given 24 segments, I needed to come up with my outer square’s width and height of 4. This was not an obvious solution.

I tried searching for things like ‘size of square from inner grid segments’, but I couldn’t really articulate the thing in a way that got me anywhere. Or, perhaps, nobody has ever really needed this version of this problem solved before (though I find that doubtful). I needed a new angle. I searched OEIS for my sequence, 4, 12, 24, 40, 60, and came up with A046092, ‘4 times triangular numbers’. Now, OEIS is great, but it has a way of presenting a lot of information very tersely, which can be overwhelming. So I googled A046092, and nearly every hit came back to one thing – Aztec diamonds.

Further searching revealed that Aztec diamonds are popular because of the Aztec diamond theorem and the Arctic Circle theorem, both related to domino tilings. This is all very fascinating, but unfortunately presented me with a dead end. Fortunately, I did also discover that Aztec Diamond Equestrian is a company that makes leggings with very functional looking pockets, so that was a win. But on the math side of things, I wasn’t coming up with much. I did, at least, realize that if I rotated my grid and treated each of those segments as the diagonal of a square, I was in fact dealing with an Aztec diamond. If nothing else, this allowed me to confirm that A046092 was the sequence I was dealing with, it allowed me to confirm my original equation, and therefore meant I could test any arbitrary case without manually counting.

I started noticing other patterns, too. The problem is complicated because it’s like a square, but it’s missing the corners. This is where the narrative begins to fall apart. All these thoughts of squares and right triangles, hypotenuses… I established a formula that I have tested for the first 1000 integers in A046092, they all pass. But I cannot come up with a proof that explains it. Furthermore, I am not confident that it actually holds up despite the first 1000 integers validating. The next step is scripting the formulae out to test well beyond 1000.

Now, for my project, I don’t need anywhere near 1000, so the equation is Good Enough. Hell, I could probably hardcode the sequence as far as I need it, and a lookup table would likely be faster than a bunch of math. But now I’m really curious. So for a square x by x units, and y as the xth integer in A046092, I’d love to prove that x=ceil(sqrt(2y)/2). I don’t know that I can, but I would really like to. Ultimately I know I’m looking at a hypotenuse, or an approximation of a hypotenuse, with the Pythagorean theorem being beautifully simple given the area of a square.

I guess, in the end, I have an equation that more than meets my needs. I learned about Aztec diamonds, and I figured out why this problem is not as simple as it originally seems. I also learned about some pretty bangin’ equestrian leggings. I’m going to keep at this, though, because it fascinates me, and I haven’t found a solution in the wild. I’ll report back, but before I do, there will likely be a game-in-a-post to explain why I was trying to solve it in the first place.


Golfing in Eukleides

Eukleides is decidedly not a golfing language, but when a geometry-related question came up on PPCG, I had to give it a shot. Eukleides can be quite rigid; for starters it is very strongly typed. Functions are declared by what they intend to return, so while set would be the shortest way to declare a function, it can’t really be exploited (unless returning a set is, in fact, desired). Speaking of sets, one thing that is potentially golfable is ‘casting’ a point to a set. Given a point, p, attempting a setwise operation on p will fail because a point does not automatically cast to a set (strict typing). p=set(p) will overwrite point p with a single-item set containing the point that was p. If, however, it is okay to have two copies of the point in the set, p=p.p is three bytes shorter.

If user input is required, the command number("prompt") reads a number from STDIN. The string for the prompt is required, though it can be empty (""). Thus, if more than four such inputs (or empty strings for other purposes) are required, it saves bytes to assign a variable with a one-letter name to an empty string.

Whitespace is generally unavoidable, but I did come to realize that boolean operators do not need to be preceded by whitespace if preceded by a number. So, if a==7or a==6 is perfectly valid. aor a, 7ora, 7 or6 are all invalid, however. This may be an interpreter bug, but for the time being it is an exploitable byte.

Finally, loci. Loci are akin to for-loops that automagically make sets. Unfortunately, they don’t seem to care much for referencing themselves mid-loop, which meant that I couldn’t exploit how short of a construction they are compared to manually creating a set in a for-loop.

This was a fun exercise, and just goes to show that if you poke around at any language enough, you’ll find various quirks that may prove useful given some ridiculous situation or another.


Fight our administration's hate, now. (external)

Link goes to Lambda Legal’s donate page. So many people need you to do it, if you’re here and you have a spare buck or two. I’m really tired of making these posts, but our administration wants to eliminate trans people, one way or another. Frankly, I believe they want to eliminate all queer people, but trans folks are the low-hanging fruit right now. I’m not here to contribute to the infighting, but trans men, trans women, trans enbies… isolated in the fight. And the administration knows that. They know that it’s a weakness. Fuck Jeff Sessions and his fucking memo. Fight.

Fight.


Tetris has been implemented in Conway's Game of Life (external)

Over four years ago, a challenge was posed on the Programming Puzzles & Code Golf Stack Exchange: Build a working game of Tetris in Conway’s Game of Life (GoL). Yesterday, an incredibly dedicated team of seven posted a working solution that is just fantastic to read about. I am flabbergasted by the work that went into this, and what these folks achieved. Starting with the concept of a metapixel – essentially a giant block of GoL tiles that can be programmed to behave like a single GoL cell, but with any ruleset – they developed wiring, logic gates, an ALU, a RISC architecture, an assembly language, a higher-level language, and finally (for now) a working game of Tetris. Not the first example of advanced computation in GoL (Wireworld is well known), but almost certainly the largest in scope and likely the best-documented as well. I linked to the Stack Exchange page, and if you have any knowledge of GoL, logic gates, or low-level computing, the multiple write-ups are incredibly clear and fascinating.