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\$
2
  • \$\begingroup\$ Where's the c in the testcase for 9? \$\endgroup\$
    – Leaky Nun
    May 15, 2016 at 6:56
  • \$\begingroup\$ @KennyLau Sorry, It's fixed now. \$\endgroup\$
    – DJMcMayhem
    May 15, 2016 at 7:00

5 Answers 5

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*
\$\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
\$\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.

\$\endgroup\$
3
  • \$\begingroup\$ Goodness.... what does such a long flag mean? \$\endgroup\$ May 16, 2016 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\$ May 16, 2016 at 6:41
  • \$\begingroup\$ Oh, how interesting! \$\endgroup\$ May 16, 2016 at 14:00
2
\$\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)}
`)
\$\endgroup\$
1
  • \$\begingroup\$ oo, recursive. Nice! \$\endgroup\$ May 16, 2016 at 0:22
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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