22
\$\begingroup\$

Introduction

I have a room full of magic mirrors. They are mysterious artifacts that can duplicate any item, except another magic mirror. More explicitly, a duplicate version of the item will appear on the other side of the mirror, at the same distance. However, if there is another magic mirror in the way on either side, between the duplicating mirror and either item (original or duplicate), the duplicate is not formed. The original item can be either left or right of the mirror, and the duplicate will appear on the other side. Also, the duplicate item can itself be duplicated by another mirror. Items never block the duplication of other items (except by being directly on the position of the would-be duplicate).

Input

Your input is a string consisting of the characters .#|, which represent empty space, items, and magic mirrors. There will always be at least one magic mirror in the input.

Output

Your output shall be another string where each magic mirror has duplicated every item it can, according to the rules above. You can assume that there will always be an empty space on the spot where a duplicate item appears (so they will no go out of bounds).

Examples

Consider the input string

.#.|.....|......#
 A B     C      D

where we have marked some positions for clarity. The mirror B duplicates item A, which ends up to its right:

.#.|.#...|......#
 A B     C      D

Mirror C then duplicates the new item:

.#.|.#...|...#..#
 A B     C      D

Mirror C cannot duplicate item A, since mirror B is in the way. It also cannot duplicate item D, since mirror B is in the way on the other side. Likewise, mirror B cannot duplicate item D or the duplicate next to it, since mirror C is in the way, so this is the correct output.

For another example, consider the input

.##..#...|#..##...|..##....#.
 AB  C   DE  FG   H  IJ    K

Mirror D can duplicate A and B to the right, and E and G to the left. C and F are already duplicates of each other. The string becomes

.##.##..#|#..##.##|..##....#.
 AB  C   DE  FG   H  IJ    K

Mirror H can duplicate E, F, and the duplicates of A and B to the right, and I to the left. G and J are already duplicates of each other, and mirror D is in the way of K. Now we have

.##.##..#|#..#####|#####..##.
 AB  C   DE  FG   H  IJ    K

Finally, mirror D can duplicate the duplicate of I to the left. We end up with

.#####..#|#..#####|#####..##.
 AB  C   DE  FG   H  IJ    K

Rules and scoring

You can write either a full program or a function. The lowest byte count wins. Submissions that don't use regex engines compete separately from those that do, and may be marked with (no regex).

Test cases

"|" -> "|"
"..|.." -> "..|.."
".#.|..." -> ".#.|.#."
"..#|.#." -> ".##|##."
".#..|....|.." -> ".#..|..#.|.#"
".|..|.#....." -> "#|#.|.#....."
"...|.#...|....#" -> ".##|##...|...##"
"......#|......." -> "......#|#......"
".#.|.....|......#" -> ".#.|.#...|...#..#"
".......|...#.##|...." -> "##.#...|...#.##|##.#"
"...#..||.......#..#...#" -> "...#..||.......#..#...#"
".##|.#....||#||......#|.#" -> ".##|##....||#||.....##|##"
".##..#...|#..##...|..##....#." -> ".#####..#|#..#####|#####..##."
".#|...||...|#...|..##...|#...." -> ".#|#..||.##|##..|..##..#|#..##"
"....#.|...#.|..|.|.....|..#......" -> "..#.#.|.#.#.|.#|#|#.#..|..#.#...."
"..|....|.....#.|.....|...|.#.|..|.|...#......" -> ".#|#...|...#.#.|.#.#.|.#.|.#.|.#|#|#..#......"
\$\endgroup\$
  • \$\begingroup\$ Can we take an array of characters as input and/or output? \$\endgroup\$ – Conor O'Brien Nov 16 '16 at 12:13
  • \$\begingroup\$ @ConorO'Brien No, unless that's the natural representation of a string in your language. \$\endgroup\$ – Zgarb Nov 16 '16 at 12:14
10
\$\begingroup\$

Retina, 50 bytes

+`([#.])(([#.])*\|(?>(?<-3>[#.])*))(?!\1)[#.]
#$2#

Try it online! (The first line enables a linefeed-separated test suite.)

I guess this is the opposite of a (no regex) submission.

Explanation

This is simply a regex substitution, which is applied repeatedly (+) until the string stops changing. I'm using balancing groups to make sure that the two mirrored positions are the same distance from the given mirror (backreferences won't do, since the exact string on both sides of the | may be different).

([#.])            # Match and capture a non-mirror cell.
(                 # This will match and capture everything up to its corresponding
                  # cell so that we can write it back in the substitution.
  ([#.])*         #   Match zero or more non-mirror cells and push each one onto
                  #   group 3. This counts the distance from our first match to
                  #   the mirror.
  \|              #   Match the mirror.
  (?>             #   Atomic group to prevent backtracking.
    (?<-3>[#.])*  #     Match non-mirror while popping from group 3.
  )               #   There are three reasons why the previous repetition
                  #   might stop:
                  #   - Group 3 was exhausted. That's good, the next position
                  #     corresponds to the first character we matched.
                  #   - We've reached the end of the string. That's fine,
                  #     the last part of the regex will cause the match to fail.
                  #   - We've hit another mirror. That's also fine, because
                  #     the last part of the regex will still fail.
)
(?!\1)            # Make sure that the next character isn't the same as the first
                  # one. We're looking for .|# or #|., not for #|# or .|.
[#.]              # Match the last non-mirror character.

This is replaced with #$2# which simply replaces both the first and last character of the match with a #.

\$\endgroup\$
9
\$\begingroup\$

Perl, 49 bytes

Full credit to @Martin Ender for this one who suggested this regex 15 bytes shorter than mine.

47 bytes of code + -pl flags

s/([.#])(\||[^|](?2)[^|])(?!\1)[^|]/#$2#/&&redo

To run it :

perl -plE 's/([.#])(\||[^|](?2)[^|])(?!\1)[^|]/#$2#/&&redo' <<< ".##..#...|#..##...|..##....#."

The first (([.#])) and last ((?!\1)[^|]) parts are the same as in Retina answer (see the explanation over there).
The middle part ((\||[^|](?2)[^|])) uses perl recursion ((?2)) to match either a mirror (\|) or (|) two not-mirrors-characters ([^|]) separated by the very same pattern ((?2)).


My older (and uglier) version: s/([.#])(([^|]*)\|(??{$3=~s%.%[^|]%gr}))(?!\1)[^|]/#$2#/&&redo

\$\endgroup\$
4
\$\begingroup\$

Haskell (no regex), 117 bytes

r=reverse
s=span(<'|')
m=zipWith min
g a|(b,l:c)<-s a,(d,e)<-s c=b++l:g(m(r b++[l,l..])d++e)|0<1=a
f x=m(g x)$r.g.r$x
\$\endgroup\$
2
\$\begingroup\$

PHP, 123 117 100 bytes

for($t=$argv[1];$t!=$s;)$t=preg_replace("%([.#])(\||[.#](?2)[.#])(?!\g1)[.#]%","#$2#",$s=$t);echo$t;

program takes command line argument, regex taken from @Martin Ender/Dada. Run with -r.

\$\endgroup\$
  • \$\begingroup\$ @Zgarb fixed, thanks \$\endgroup\$ – Titus Nov 16 '16 at 14:05
2
\$\begingroup\$

C, 176 bytes

void t(char*a){int x=0;for(int i=0;a[i];i++)if(a[i]=='|'){for(int j=x;a[j]&&j<=i*2-x;j++){if((a[j]==35)&&(a[2*i-j]==46)){a[2*i-j]=35;i=-1;}if((i-j)&&(a[j]=='|'))break;}x=i+1;}}

Ungolfed

void t(char*a)
{
    int x=0;
    for(int i=0;a[i];i++)
        if(a[i]=='|')
        {
            for(int j=x;a[j]&&j<=i*2-x;j++)
            {
                if((a[j]=='#')&&(a[2*i-j]=='.'))
                {
                    a[2*i-j]='#';
                    i=-1;
                    break;
                }
                if((i!=j)&&(a[j]=='|'))
                    break;
            }
            x=i+1;
        }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can save a couple bytes by replacing '#' and '.' with 35 and 46 respectively. \$\endgroup\$ – artificialnull Nov 17 '16 at 1:25
  • \$\begingroup\$ This code can be golfed..a lot. \$\endgroup\$ – Mukul Kumar Nov 17 '16 at 8:57
  • \$\begingroup\$ thanks artificialNull, that saved 3 byes. '|' is 124, so that doesn't save anything (but maybe I should change that, so it will be consistent; not sure yet). and @Mukul, I don't really see how, without greatly changing the logic flow of it. \$\endgroup\$ – Eyal Lev Nov 17 '16 at 12:56
  • \$\begingroup\$ check if this code runs fine x,i,j;void t(char*a){while(a[i]++)if(a[i]=='|'){for(j=x;a[j++]&&j<=i*2-x;j++){if((a[j]==35)&&(a[2*i-j]==46)){a[2*i-j]=35;i=-1;break;}if((i-j)&&(a[j]=='|'))break;}x=i+1;}} - 170 bytes \$\endgroup\$ – Mukul Kumar Nov 17 '16 at 13:56
  • 1
    \$\begingroup\$ 1more byte replace (i!=j) with (i-j) and if you are going to stick with c++then atleast define all int at one place... \$\endgroup\$ – Mukul Kumar Nov 17 '16 at 16:24
1
\$\begingroup\$

JavaScript (ES6), 170 bytes

s=>s.replace(/#/g,(c,i)=>(g(i,-1),g(i,1)),g=(i,d,j=h(i,d))=>j-h(j=j+j-i,-d)|s[j]!='.'||(s=s.slice(0,j)+'#'+s.slice(j+1),g(j,d)),h=(i,d)=>s[i+=d]=='|'?i:s[i]?h(i,d):-1)&&s

Ungolfed:

function mirror(s) {
    for (var i = 0; i < s.length; i++) {
        // Reflect each # in both directions
        if (s[i] == '#') s = reflect(reflect(s, i, true), i, false);
    }
    return s;
}
function reflect(s, i, d) {
    // Find a mirror
    var j = d ? s.indexOf('|', i) : s.lastIndexOf('|', i);
    if (j < 0) return s;
    // Check that the destination is empty
    var k = j + (j - i);
    if (s[k] != '.') return s;
    // Check for an intervening mirror
    var l = d ? s.lastIndexOf('|', k) : s.indexOf('|', k);
    if (l != j) return s;
    // Magically duplicate the #
    s = s.slice(0, k) + '#' + s.slice(k + 1);
    // Recursively apply to the new #
    return reflect(s, k, d);
}
\$\endgroup\$

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.