Intel's Ronler Acres Plant

Silicon Forest

Saturday, August 13, 2016

Fractal Carpet

I started working on this puzzle from Coding Game a couple of weeks ago. It's not a terribly hard puzzle, but I haven't been sleeping well, which makes thinking a little difficult. There seem to be several levels of conciousness I go through. There's sleeping, when I am actually unconcious, which is great. Then there is eyes closed but awake, which can be restful when I get tired and / or sleepy during the day, or it can be horrid when I wake up in middle of the night and I can't go back to sleep but I don't have enough energy to do anything else but lie there and wait.
     Then there is shuffling awake, which is me when I first get up and I haven't had any coffee. Give me a few minutes and I am ready to go for a hike. Thinking at this stage is an iffy proposition. If I have gotten a good nights sleep (about one in ten these days), I'm good. Otherwise it depends on the problem. If it is something I have tackled before, then we might be able to handle it. Something new and different will probably stump me.
    I like to think that I am worth a $1,000 an hour when I am at the top of my game. Problem is that I am only good for that a few hours a week.

Anyway, back to the puzzle. We have a carpet with a pattern represented by two characters. Carpets come in various sizes, represented by a 'Level':

Level 0:
0

Level 1:
000
0+0
000

Level 2:
000000000
0+00+00+0
000000000
000+++000
0+0+++0+0
000+++000
000000000
0+00+00+0
000000000

Level 3:
000000000000000000000000000
0+00+00+00+00+00+00+00+00+0
000000000000000000000000000
000+++000000+++000000+++000
0+0+++0+00+0+++0+00+0+++0+0
000+++000000+++000000+++000
000000000000000000000000000
0+00+00+00+00+00+00+00+00+0
000000000000000000000000000
000000000+++++++++000000000
0+00+00+0+++++++++0+00+00+0
000000000+++++++++000000000
000+++000+++++++++000+++000
0+0+++0+0+++++++++0+0+++0+0
000+++000+++++++++000+++000
000000000+++++++++000000000
0+00+00+0+++++++++0+00+00+0
000000000+++++++++000000000
000000000000000000000000000
0+00+00+00+00+00+00+00+00+0
000000000000000000000000000
000+++000000+++000000+++000
0+0+++0+00+0+++0+00+0+++0+0
000+++000000+++000000+++000
000000000000000000000000000
0+00+00+00+00+00+00+00+00+0
000000000000000000000000000

Studying this pattern I observe that the length and width of a carpet are the same and that they are equivalent to three raised to the power of the corresponding level, i.e.:

  • Level 0 has a length and width of 1
  • Level 1 has a length and width of 3
  • Level 2 has a length and width of 9
  • Level 3 has a length and width of 27


    Simple enough, but now is there is the matter of the pattern. It's obvious enough looking at it: the center of each block is filled with plus signs and everything else is filled with zeros, but how do you explain that to the computer?
        A problem like this is a natural fit for recursion. For each level, you count to three, and for each number you call yourself. You do this until you run out of levels. This enables you to reach each point in the carpet and to completely cover it, but it doesn't really tell you what character to print. It probably took me (and my sleep deprived brain) a week to come up with a solution.
        When we count to three in Go (the computer language I am using for this problem), we start with zero and quit when we get to three, to wit, zero, one, two. When we get to three, we are done, so we don't actually use it. Anyway, when the row index and the column index for any particular level are both equal to one, then we print a plus sign, otherwise we print a zero.

    Now we have the basic rules for making a carpet and we can move on to the actual problem, which is to generate the pattern for a subsection of the carpet. This is not too difficult, we simple generate a digital image of the carpet and then copy the section we are concerned with.
        But what if it's a really big carpet? A carpet with a zillion threads? If you had some terabytes of diskspace you might be able to do it that way, but we have rules for generating the carpet, could we not just figure out where we need to start and generate from there? Well, sure, we should be able to, but so far I haven't been able to get my mind to concentrate on the problem, hence my writing out this explanation, hoping it will help clear my mind.

    No comments: