11
\$\begingroup\$

Adam7 is an interlacing algorithm for raster images, such as PNG. It is called the "Adam7" algorithm because it was invented by Adam M. Costello, and it is generated by following a certain pattern 7 times. One of the cool things about the Adam7 algorithm that makes it really fun for code golf, is that the pattern can be repeated an arbitrary number of times, as long as it's odd. Back when 1996 when the PNG standard was developed, using only 7 iterations was seen as sufficient, since the 9 iterations was too complex, and 5 iterations is not as efficient.

Here is the first iteration of the tile:

a

Pretty simple. This is an "Adam1" tile. Here's how we get to the next iteration, the "Adam3" tile.

Since our last tile was 1x1, we double the height and width, and the next one will be 2x2. First, we start with an 'a' in the upper left corner.

a-
--

Step 2, copy this pattern to the right, and increase the letter we're on by one.

ab
--

Step 3, same as step 2, but copy down instead of right.

ab
cc

Boom. The "Adam3" tile. Let's do the "Adam5" also, so you can actually see how the algorithm works. This tile will, again, be twice as large, so 4x4. Again, we start with a a in the upper left corner:

a---
----
----
----

Double this pattern, increase the letter, and move it to the right:

a-b-
----
----
----

Again, this time down.

a-b-
----
c-c-
----

Again, this time to the right.

adbd
----
cdcd
----

Again, this time down.

adbd
eeee
cdcd
eeee

This is the "Adam5" tile. Here is the ASCII representation of the Adam7 tile:

afdfbfdf
gggggggg
efefefef
gggggggg
cfdfcfdf
gggggggg
efefefef
gggggggg

And while we're at it, here is a fun animation of each step of the Adam7 tile (although it does several tiles side by side):

enter image description here

The challenge

Given a positive odd number N, output the "AdamN" tile. You can use any default method of IO. Since we're using the alphabet in lieu of numbers, you only need to handle inputs up to 25. You can choose to output lower-case or upper-case characters as long as you specify and it's consistent.

Sample IO

1:

a

3:

ab
cc

5:

adbd
eeee
cdcd
eeee

7:

afdfbfdf
gggggggg
efefefef
gggggggg
cfdfcfdf
gggggggg
efefefef
gggggggg

9:

ahfhdhfhbhfhdhfh
iiiiiiiiiiiiiiii
ghghghghghghghgh
iiiiiiiiiiiiiiii
ehfhehfhehfhehfh
iiiiiiiiiiiiiiii
ghghghghghghghgh
iiiiiiiiiiiiiiii
chfhdhfhchfhdhfh
iiiiiiiiiiiiiiii
ghghghghghghghgh
iiiiiiiiiiiiiiii
ehfhehfhehfhehfh
iiiiiiiiiiiiiiii
ghghghghghghghgh
iiiiiiiiiiiiiiii

As usual, this is code-golf, so standard loopholes apply, and shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Where's the c in the testcase for 9? \$\endgroup\$ – Leaky Nun May 15 '16 at 6:56
  • \$\begingroup\$ @KennyLau Sorry, It's fixed now. \$\endgroup\$ – James May 15 '16 at 7:00
8
\$\begingroup\$

CJam, 20 bytes

Laq~{'a+_@f*\f+z}/N*

Try it online.

La                      Push [[]]
  q~                    Push input n
    {           }/      For i in 0..n-1 ...
     'a+                  Add to char 'a to give current char
        _@f*              Join each row by char
            \f+           Add char to the end of each row as well
               z          Zip to transpose
                  N*    Join result by newlines

20/21-byte alternatives:

Laaq~{'a+aff+:sz}/N*
Laaq~{'a+\Laf+f*z}/N*
Laq~{'a+f{_@*\+}z}/N*
|improve this answer|||||
\$\endgroup\$
6
\$\begingroup\$

MATL, 23 bytes

97tiq:+"TFX*tXa~@wZ(!]c

Try it online!

This uses repeated Kronecker tensor product for extending the array, followed by transposition. At each iteration, new columns containing zeros are interleaved with the old; those zeros are then replaced by the appropriate new value (which increases at each iteration); and the matrix is transposed.

(One byte wasted because Octave's Kronecker product doesn't allow char input. This will be fixed for next release).

EXplanation

97       % Push 97 (ASCII for 'a')
t        % Duplicate
iq:      % Take input n. Range [1 2 ... n-1]
+        % Add. Gives [98 99 ... 97+n-1] (letters to be filled)
"        % For each
  TFX*   %   Kronecker product with [1 0]. This interleaves new columns with zeros
  tXa~   %   Duplicate. Logical index for the new columns
  @wZ(   %   Assign letter to those columns
  !      %   Transpose (zip)
]        % End if
c        % Convert to chat. Implicitly display
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Perl, 110 104 100 99 91 89 87 + 1 (-p flag) = 88 bytes

#!perl -p
$==$_/2;$_=a.$/;$"=b;s/\w/$&.$"/ge,$"++,s/\n/$&.$"x2**$%.$&/ge,$"++until$=<++$%;$\=$_}{

Using:

> echo 5 | perl -pe '$==$_/2;$_=a.$/;$"=b;s/\w/$&.$"/ge,$"++,s/\n/$&.$"x2**$%.$&/ge,$"++until$=<++$%;$\=$_}{'

Ungolfed:

while (<>) {
# code above added by -p
    # $_ has input value
    # $/ = "\n" by default
    # $% = 0 by default
    my $n = $_ / 2;   # input
    my $s = "a" . $/; # "a\n"
    my $c = "b";      # "b"
    my $i = $%;       # 0
    while (++$i <= $n) {
        $s =~ s/(\w)/$1 . $c/ge;
        $c++;
        $s =~ s/(\n)/$1 . ($с x 2**$i) . $1/ge;
        $c++;
    }
    $\ = $s;
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Ideone.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Goodness.... what does such a long flag mean? \$\endgroup\$ – Conor O'Brien May 16 '16 at 0:24
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ The -l flag assigns $\ variable to have the value with octal code 0141 (ASCII character a). And l141 is shorter than $\="a";. \$\endgroup\$ – Denis Ibaev May 16 '16 at 6:41
  • \$\begingroup\$ Oh, how interesting! \$\endgroup\$ – Conor O'Brien May 16 '16 at 14:00
1
\$\begingroup\$

Pyth, 38 bytes

u:+r:jK@;tyHGb++b*^2H@;yHb6b+bKbh/Q2"a

Try it here!

I would expect this to be easily golfable.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 114 bytes

f=n=>n<2?`a
`:f(n-2).replace(/./g,`$&`+(n+8).toString(36)).replace(/\n/g,`
${(n+9).toString(36).repeat(1<<n/2)}
`)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ oo, recursive. Nice! \$\endgroup\$ – Conor O'Brien May 16 '16 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.