Make the Stretchy Snakes Kiss

Question

A stretchy snake looks something like this:

<||=|||:)~

Each separate sequence of vertical bars (|) in a stretchy snake, known as a stretchy portion, is individually extendable to twice its width, and is drawn with alternating slashes (/,\) once extended.

The particular snake above has two such stretchy portions, giving it four possible poses:

<||=|||:)~

</\/\=|||:)~

<||=/\/\/\:)~

</\/\=/\/\/\:)~

The general form of a stretchy snake in its least stretched pose is defined by this regex:

<(\|+=)*\|+:\)~

Which can be stated in words as:

<, followed by any number of sequences of |'s joined with = signs, followed by :)~.

So <|:)~ and <||:)~ and <|=|:)~ and <|=|=||=|||||=||:)~ are stretchy snakes, but <=:)~ and <=|:)~ and <||=:)~ and <|==||:)~ are not.

Stretchy snakes can also face left instead of right, e.g. ~(:|||=||>. The forms are the same, just mirrored.

Challenge

Write a program that takes in a single line string of two stretchy snakes facing each other, with some number of spaces in between. Both snakes will be in their least stretched pose (all vertical bars, no slashes). The string will start with the tail of the right-facing snake and end with the tail of the left-facing snake (you may optionally assume there's also a trailing newline).

For example, here's a possible input with five spaces between the snakes:

<|=||:)~.....~(:||||>

^{I'm using periods (.) instead of actual space characters for clarity.}

Zero spaces between snakes is also valid input:

<|=||:)~~(:||||>

We say the snakes are kissing when their tongues are touching like this.

Your program needs to extend some combination of the stretchy portions of both of the snakes such that the snakes have the fewest number of spaces possible between them (without overlapping), i.e. such that the snakes are as close to kissing as possible.

Both the snakes' tails are fixed but their heads and bodies can move - right for the right-facing snake, left for the left-facing snake - according to what stretchy portions have been extended.

The output of your program is the single line string (plus optional trailing newline) that shows the snakes as close to kissing as possible, with alternating slashes drawn in place of vertical bars for stretchy portions that have been extended.

---

For example, the output for <|=||:)~.....~(:||||> (from above) would be:

</\=||:)~~(:/\/\/\/\>

This is the only solution here because with any other combination of the stretchy portions extended, the snakes would either overlap or be farther away from kissing.

---

If there are multiple solutions possible, the output may be any one of them.

For example, if the input were

<|=||:)~.....~(:|||=|>

the output could be

<|=/\/\:)~~(:/\/\/\=|>

or

</\=||:)~~(:/\/\/\=/\>

---

Remember that it won't always be possible to make the snakes kiss, but you still need to get them as close as possible.

For example, if the input were

<||=||||:)~...~(:||>

the output could be

</\/\=||||:)~.~(:||>

or

<||=||||:)~.~(:/\/\>

---

If the snakes are already kissing, the output will be the same as the input. e.g.

<|=||:)~~(:||||>

In general, the output will be the same as the input if the extension of any stretchy portion would make the snakes overlap. e.g.

<|||=|||:)~..~(:||||=|||||=||||||>

---

Notes

• Takes input from stdin or the command line as usual, or write a function that takes a string. Print or return the output.
• You can use periods (.) in the input and output in place of spaces ( ) if you prefer.
• It's only important that slashes alternate within the sequence of vertical bars they replaced. Their ordering in the snake at large or whether a forward or backward slash comes first doesn't matter.
• Stretchy portions cannot extend partway - it's exactly double or no extension at all.

Scoring

This is code-golf. The shortest submission in bytes wins. Tiebreaker is earlier answer.

Answer 1

Retina, 209 107 99 97 92 bytes

.(?=(.+)(?<=(?=<((\|+|(?<-5>\|(?=\1())?)+)[^|]+)+$(?(5)!)).+( )+\S+))\4
/ \
+` (.*~|~.*) 
$1

For counting purposes, each line goes in a separate file, but you can run the code from a single file with the -s flag.

Bringing the best features of .NET regex and Retina together: balancing groups, arbitrary length lookbehinds and repeated regex substitution.

Essentially, the long regex encodes a valid solution and the regex engine's backtracker finds one of the optimal ones for me.

Explanation

First, let's consider how we can find a valid solution (not necessarily producing the correct output) with a regex. We can use .NET's balancing groups to help us count the stretchy parts. Consider the following simpler regex:

\S+( )+.+(?<=(?(1)!)^([^|]+(\|+|(?<-1>\|)*))+>)

We can disect that.

\S+( )+.+

This matches the entire string, pushing one capture onto the group 1 stack for each space in the input. We will use that stack to ensure that the stretchy parts exactly fill the space captured into those groups.

Next is a lookbehind. The catch is that lookbehinds are matched from right to left in .NET (so that's how you should read them). This gives us the opportunity to traverse the string a second time, figuring out whether there's a subset of stretchy part that sums to the number of matched spaces. Going through the lookbehind from right-to-left:

>

This is just ensure that we're actually starting from the end of the string (the snake's tail).

(
  [^|]+
  (
    \|+
  |
    (?<-1>\|)+
  )
)+

For each stretchy part, this either just matches the entire part without doing anything (\|+), or it matches the entire part while popping captures off stack 1 ((?<-1>\|)*). Having this alternation ensures that we can only fully extend a stretchy part or leave it unchanged, and not get stuff like |/\|. Then we move on to the next stretchy part with [^|]+.

(?(1)!)^

Finally, we ensure that we've traverse the entire string (both snakes), and that stack 1 is completely empty. I.e. that we've found a subset of stretchy part that exactly sums to the number of spaces we've captured earlier.

The backtracker will go back and forth through the string trying all combinations of unchanged and extended parts until the subset sum problem is solved. If such a subset doesn't exist, the lookbehind will fail. This will cause the backtracker to go back to the \S+( )+.+ part and try capturing one space less with ( )+ (which will just be cover by .+ instead). Due to the greediness of + we therefore try filling as many spaces as possible.

You can check the validity of this approach with this slightly modified substitution:

\S+(( )+).+(?<=(?(2)!)^([^|]+(\|+|(?<-2>\|)*))+>)
=$1=

Which will give you a string =spaces= with exactly the number of spaces that can be filled with the given snakes.

I've had to add some more trickery to actually expand the correct |s. Basically, I want to replace all |s which were matched using the (?<-1>\|)+ branch. The idea is to match an individual character, put the solver in a lookaround and set a flag if the match happens to be inside that branch. If that flag wasn't set we invalidate the match at the end to avoid replacement of other characters.

To do this, we use a bunch of nested lookarounds. Again, .NET's variable-length lookbehinds are matched from right to left, so if we nest lookaheads and lookbehinds, we can let the regex engine traverse the string several times. For golfing reasons, the solver is reversed in my actual solution (starting at the end, picking up the spaces from right to left, and then solving the subset sum from left to right), but otherwise the structure of the solver is exactly the same. Let's dissect the full regex:

.(?=(.+)...)

We match a single character, then capture the remainder of the string and move the cursor to the end of the string. We will use this group 1 later to check in the solver whether we're at the position of the match.

(?<=....+( )+\S+)

This is like the first part of the simple solver above, except that we pick up the spaces from right to left. The backtracking of the number of spaces works exactly the same as before, except that we're using group 5 now.

(?=<((\|+|(?<-5>\|(?=\1())?)+)[^|]+)+$(?(5)!))

This is the same as before, except we're going from left to right, and whenever we match a | in the expanding branch, we check if it's the one being matched right with

(?=\1())?

This is an optional lookahead. It tries to match group 1 again (which, here, is only possible if we're right after the character being matched), and if we do, we capture an empty string into group 4, which indicates that we did find the current character in one of the expanded bits. If \1 doesn't match, 4 won't capture anything, and the ? ensures that the failing lookahead won't affect the solver at all.

Finally, after all the solving is done, we just check with \4 whether this lookahead was used. If so, we want to replace the current character with /\.

One difficulty remains: removing the right amount of spaces. The shortest way to do this I've found so far is to insert a space along with the /\ and then get rid of one space between the tongues for each of those marker spaces in a separate step:

+` (.*~|~.*) 
$1

Answer 2

CJam, 87 71 70 68 bytes

l:L"|"f&Qa%_,Y\m*\f{.{_,"/\\"*?}L'|%.\s" /"1$fe=:-\a+}${0a>}=~S%\S**

Try it online in the CJam interpreter.

How it works

l:L        e# Read a line from STDIN and save it in L.
"|"f&      e# Intersect each character with the string "|".
           e# This pushes either "|" or "".
Qa%        e# Split the resulting array at runs of "".
_,         e# Compute the length of the resulting array (A).
           e# This yield K, the number of stretchy parts.
Y\m*       e# Push the array of all vectores in {0,1}^K.
\f{        e# For each vector V in {0,1}^K, push V and A; then:
  .{       e#   For each C in V and the corresponding P in A:
    _,     e#     Compute the length of the stretchy part P.
    "/\\"* e#     Repeat "/\" that many times.
    ?      e#     If C, select P; else, select "/\"*length(P).
  }        e#   This modifies A.
  L'|%     e#   Split L at runs of vertical lines.
  .\s      e#   Interleave the chunks of L and the modified A. Sringify.
           e#   In each iteration, this constructs a different modification of L,
           e#   with some stretched out stretchy parts.
  " /"1$   e#   Push " /" and a copy of the modified L.
  fe=      e#   Calculate the number of spaces and slashes in the modifed L.
  :-       e#   Subtract the number of occurrences.
  \a+      e#   Construct the array [difference modified-L].
}          e#
$          e# Sort the array (by final number of spaces).
{0a>}=     e# Find the first element greater than [0].
           e# This skips over too far stretched snakes, where the number of
           e# slashes is less than the number of spaces.
~          e# Dump the difference (D) and modified L on the stack.
S%         e# Split L at runs of spaces.
\S*        e# Construct a string of D spaces.
*          e# Join the split L, delimiting by D spaces.

Answer 3

Ruby 191 187 186 170 162

->t{s=r=t.size
i=m=t[o=/ +/].size
(0...2**t.scan(y=/\|+/).size).map{|n|q=-1
x=t.gsub(y){|r|n[q+=1]<1?r:'\/'*r.size}
d=i+s-x.size
d<0||d<m&&r=x.gsub(o,' '*m=d)}
r}

This is a function that takes a string as a parameter and returns a string.

Online tests: http://ideone.com/uhdfXt

Here's the readable version:

# enumerates the possible states for any string containing snakes
COMBINATIONS =-> snake {
  expandable_fragments = snake.scan /(\|+)/

  (0...2**(expandable_fragments.size)).map{ |i|
    x=-1
    snake.gsub(/\|+/){|r| i[x+=1]>0 ? '\/'*r.size : r}
  }
}

# finds the configuration in which snakes are closest to each other
KISS=
-> input {
  result = input
  s = input.size
  initial_distance = min_distance = input[/ +/].size

  COMBINATIONS[input].map{|c|
    distance = initial_distance + s - c.size
    if distance > -1 && distance < min_distance
      min_distance = distance
      result = c.gsub(/ +/,' '*distance)
    end
  }

  result
}

In the golfed version, the main function is the equivalent of the KISS function above, and the COMBINATIONS function has been inlined.

Answer 4

Python, 205 bytes

from itertools import*
f=lambda s:min([c.replace(".","",c.count("X"))for c in map("".join,product(*map({"|":"|X"}.get,s,s)))if{c.count("X")>c.count("."),"|X"in c,"X|"in c}=={0}],key=len).replace("X","/\\")

Having a single lambda looks neat and all, but I'm almost certain this is not the best way to go. But I'm posting this because it's all I've got so far that looks half decent.

This is a simple brute force over all possible replacements of | with /\, filtering out the invalid configurations. The only neat bit I guess is that we don't actually replace any | with /\ directly - we first replace | with X and drop a . from the middle for every replacement, take the minimum length string over all valid strings, then replace the Xs with /\.

I tried a few other approaches, including recursive ones, but they ended up pretty messy. I also learnt that re.split currently doesn't split on empty strings, which was unfortunate, because one of my ideas involved splitting on \b word boundaries.

Answer 5

Mathematica, 381 bytes

StringReplace[MapAt[StringReplace[#,"|"->"/\\"]&,StringSplit[#<>"="<>#2,"="],#3]~StringRiffle~"=",")="->")~"<>If[#4>0,"."~StringRepeat~#4,""]<>"~"]&[#1,#3,Sequence@@Function[{l,s},{#,#2-Total@Extract[l,#]}&[Flatten[l~Position~#~Take~#2&@@@Tally@#&@@Select[Subsets@l,Total@#<=s&]~MaximalBy~Total,1],s]][StringLength/@StringCases[#1<>#3,"|"..],StringLength@#2]]&@@#~StringSplit~"~"&

Pure function taking the string as its argument. Expects . rather than between the snakes.

I didn't think it would be this bad...Here's what I had before I smashed it together and infixed everything.

f[lhs_, rhs_, 
  spaces_] := {StringLength /@ StringCases[lhs <> rhs, "|" ..], 
  StringLength@spaces}

g[barLens_, 
   spaceLen_] := {#, #2 - Total@Extract[barLens, #]} & @@ {Flatten[
     Take[Position[barLens, #], #2] & @@@ 
      Tally[First[
        MaximalBy[Select[Subsets[barLens], Total@# <= spaceLen &], 
         Total]]], 1], spaceLen};

h[lhs_, rhs_, partspec_, newSpaceLen_] := 
 StringReplace[
  StringRiffle[
   MapAt[StringReplace[#, "|" -> "/\\"] &, 
    StringSplit[lhs <> "=" <> rhs, "="], partspec], "="], 
  ")=" -> ")~" <> 
    If[newSpaceLen > 0, StringRepeat[".", newSpaceLen], ""] <> "~"]

 h[#1, #3, Sequence @@ g @@ f[#1, #3, #2]] & @@ 
     StringSplit[#, "~"] &

Here is an example run-through with explanation:

Input: "<|=||:)~.....~(:||||>"
@Call StringSplit[#, "~"] &, yielding  {"<|=||:)", ".....", "(:||||>"}
@@Apply h[#1, #3, Sequence @@ g @@ f[#1, #3, #2]] &, but first
Set arguments: h["<|=||:)", "(:||||>", Sequence @@ g @@ f["<|=||:)", "(:||||>", "....."]]
@Call f, yielding {{1, 2, 4}, 5} = {# of bars in each segment, # of spaces}
@@Apply g, let's trace from the interior:
Subsets[barLens] = all subsets of {1, 2, 4}
Select those subsets whose sum is less than # of spaces {{},{1},{2},{4},{1,2},{1,4}}
MaximalBy Total, yielding a list of all subsets whose sum is maximal {{1, 4}}
First of these subsets, can be any of them {1, 4}
Tally the subset, yielding frequencies of each {{1, 1}, {4, 1}}
@@@Apply Take[Position[barLens, #], #2] & at the first level, yielding
    {Take[Position[{1, 2, 4}, 1], 1], Take[Position[{1, 2, 4}, 4, 1]]}
    which takes the first 1 positions of 1 and the first 1 positions of 4, yielding
    {{{1}},{{3}}}
Flatten at the first level, yielding {{1}, {3}}
Create a list {{{1}, {3}}, 5}
@@Apply {#, #2 - Total@Extract[barLens, #]} &, inserting arguments:
    {{{1}, {3}}, 5 - Total@Extract[{1, 2, 4}, {{1}, {3}}]} = {{{1}, {3}}, 0}
    where the second element becomes the # of spaces left over.
Done with g, it returned {{{1}, {3}}, 0}
@@Apply Sequence, splicing the return of g into h, yielding the
@Call, h["<|=||:)", "(:||||>", {{1}, {3}}, 0]; let's start from the interior
StringSplit the concatenated "<|=||:)=(:||||>" with delimiter "=", {"<|","||:)","(:||||>"}
MapAt the part specification {{1}, {3}} and StringReplace at those indices any | with /\
    yielding {"</\","||:)","(:/\/\/\/\>"}
StringRiffle together, inserting back the delimiter "=", yielding "</\=||:)=(:/\/\/\/\>"
StringReplace ")=" with ")~", concat the new number of spaces, concat "~"
Yields "</\=||:)~~(:/\/\/\/\>", done.

Answer 6

Prolog (ECLiPSe), 438 bytes

My other answers were solving the wrong problem (sorry for the noise). Here is another attempt in Prolog which actually respects all rules.

:-lib(fd).
a([],[]).
a([H|T],L):-append(H,X,L),a(T,X).
s(E,Z,X,Y,L):-length(E,L),a([[60],M,[58,41,126],T,[126,40,58],W,[62]],E),checklist(=(32),T),length(T,Z),b(M,X-[]),b(W,Y-[]).
b(I,[K:M|R]-E):-(I:K=[47,92|L]:s;I:K=[124|L]:n),M#=N+1,N#>=0,b(L,[K:N|R]-E).
b([61|L],[_:0|R]-E):-b(L,R-E).
b([],[_:0|E]-E).
d(_:N,Y:N):-Y=s;Y=n.
s(W,P):-string_list(W,E),s(E,_,X,Y,L),minimize((maplist(d,X,U),maplist(d,Y,V),s(K,Q,U,V,L)),Q),string_list(P,K).

Tests

(format: input, output, newline)

<===:)~         ~(:>
<===:)~         ~(:>

<|||:)~         ~(:||||=|>
</\/\/\:)~ ~(:/\/\/\/\=/\>

<=|=:)~         ~(:||||=|>
<=/\=:)~   ~(:/\/\/\/\=/\>

<===|:)~         ~(:||=|>
<===/\:)~     ~(:/\/\=/\>

<|=|=|||=|:)~         ~(:=|>
</\=/\=/\/\/\=/\:)~  ~(:=/\>

<||||||:)~         ~(:=|>
</\/\/\/\/\/\:)~  ~(:=/\>

<||||||:)~         ~(:||>
</\/\/\/\/\/\:)~ ~(:/\/\>

<||=||||:)~ ~(:||>
<||=||||:)~ ~(:||>

<||=||||:)~   ~(:||>
</\/\=||||:)~ ~(:||>

<||=||||:)~    ~(:||>
</\/\=||||:)~~(:/\/\>

<||=||||:)~~(:||>
<||=||||:)~~(:||>

Explanations

• The main predicate is s/2, which takes the input as a first argument and unfiy the result with the second argument (both strings). The input is converted to a list of character codes, E.

• Then, s(E,Z,X,Y,L) destructures the list into the following elements:

  • Z number of spaces between snakes

  • X and Y, abstract representation of the left and right bodies

    The format of a body is a list of n:N or s:N expressions, where N is a positive length; n means normal and s means stretched.

  • L total length of the list

What is interesting about s/5 is that it goes both ways, i.e. we can build a snake if other arguments are instanciated:

    s(E,5,[n:3],[s:2,n:7,s:1],_),string_list(S,E).

... unifies `S` with `"<|||:)~     ~(:/\\/\\=|||||||=/\\>"` (backslashes are quoted). This is due to how `b/2` is written, which can parse the character list or generate it.

• We build modified left and right bodies where each part is either normal or stretched, while minimizing the space Q that separates the new snakes. The total length of the computed string is bounded so that the search terminates.

Answer 7

Python 2.7.3 427 421 400 371 Bytes

import re,itertools as K
g,o,k='\|+',len,raw_input()
d=k.count(' ')
if d==0:exit(k)
p,x,y,s=re.sub,0,0,map(o,re.findall(g,k))
for e in [A for w in range(o(s)+1)for A in K.combinations(s,w)]:
 v=sum(e)
 if v==d or x<v<d:x,y=v,list(e)
print p(" +",' '*(d-x),p(g,lambda m:('/\\'*o(m.group(0))if y.remove(o(m.group(0)))or True else 1)if o(m.group(0))in y else m.group(0),k))

Non-golfed code here -

#!/usr/bin/env python
import sys
import re

def find_dist_combo(li, d):
    #Listing all combinations
    from itertools import combinations as c
    max_dist = -1
    max_dist_combo = []
    for p_len in xrange(1,len(li)+1):
        for e in c(li, p_len):
            e_sum = sum(e)
            cond1 = e_sum == d
            cond2 = max_dist < e_sum < d
            if cond1 or cond2:
                max_dist = e_sum
                max_dist_combo = list(e)
                if cond1:
                    return (max_dist, max_dist_combo)
    return (max_dist, max_dist_combo)

def snakes_foreplay(snakes):
    #find distance
    distance = snakes.count(" ")

    #already kissing
    if distance == 0:
        return snakes

    #find num_stretches
    stretch = map(len, re.findall("\|+", snakes))

    #find lowest combination of numbers
    (e_dist, res_stretch) = find_dist_combo(stretch, distance)

    def sub_callback(m):
        s = m.group(0)
        l = len(s) 
        if l in res_stretch:
            res_stretch.remove(l)
            return '/\\'*l
        return s

    #Resultant substitution
    res_snakes = re.sub("\s+", " "*(distance - e_dist), re.sub("\|+", sub_callback, snakes))

    return res_snakes

if __name__ == "__main__":
    for s in [ip.strip() for ip in sys.stdin]:
        print snakes_foreplay(s)

Testing the golfed solution -

$ python stretchy_snakes.py
[In]  <=  <|=||:)~     ~(:||||>
[Out] =>  </\=||:)~~(:/\/\/\/\>

$ python stretchy_snakes.py
[In]  <=  <|=||:)~             ~(:||||>
[Out] =>  </\=/\/\:)~      ~(:/\/\/\/\>

$ python stretchy_snakes.py
[In]  <=  <|=||:)~     ~(:|||=|>
[Out] =>  </\=||:)~~(:/\/\/\=/\>

$ python stretchy_snakes.py
[In]  <=  <||=||||:)~   ~(:||>
[Out] =>  </\/\=||||:)~ ~(:||>

$ python stretchy_snakes.py
[In]  <=  <|=||:)~~(:||||>
[Out] =>  <|=||:)~~(:||||>

Surely this can be done better(I can't figure out how :)).
Let me know if I've missed anything obvious while golfing (It's my first codegolf, I may be doing something stupid :P)

Answer 8

05AB1E, 93 bytes

#õKDεγʒ'|å]©ε€gxøDgU`XG‘]`âDε˜ODI„| Ãg>‹*}ZQÏε˜ε®˜NèDgyÊi„/\y∍]н©J'/¢Ið¢αð×ý'|¡õK®.ιJIðå≠iI

Way too long.. >.>

Try it online or verify all test cases or verify all possible results for all test cases.

Explanation:

#õK                   # Split the (implicit) input by one or multiple adjacent spaces
                      # (we now have both snakes as separated items
                      #  - if any spaces were in the input-string)
   D                  # Duplicate this list
    ε                 # Map both snakes to:
     γ                #  Split the snake into chunks of the same character-type
      ʒ'|å]          '#  And only leave the chunks of "|" characters
    ©                 #  Store this list in variable `r` (without popping)
     ε                #  Map the "|" chunks of both snakes again:
      €g              #  Get the length of each chunk of "|"
        xø            #  Pair each length with double itself
          DgU`XG‘   #  Create all possible combinations for the current snake
     ]`â              # After the map: create all possible combinations for both snakes
        ε             # Map over each possible combination
         ˜O           #  Get the flattened sum
            I„| Ãg    #  Count the amount of "|" and spaces in the input
                  >‹  #  Check if it's smaller than or equal to this sum
                      #  (1 if truthy; 0 if falsey)
           D        * #  And multiply it by the sum
        }ZQ           # After the map, get the positions of the largest flattened sum,
                      # still below (or equal to) the amount of "|" and spaces combined
       D   Ï          # And only keep those combinations
ε                     # Then map over the remaining combinations
 ˜ε                   #  Flatten it, and map over each value `y`
   ®˜Nè               #   Get the `N`'th part of the snakes
                      #   (where `N` is the index of the map for the current combination)
       D              #   Duplicate this "|"-part
        gyÊi          #   If the length of this "|"-part is not equal to the map-value:
            „/\       #    Push the string "/\"
               y∍     #    Extended to a size equal to the map-value
                      #   (implicit else:
                      #    use the duplicated value)
]н                    # After the map: only leave the first (since we don't have
                      # to output all possibilities)
 ©                    # Store it in variable `r` (without popping)
  J'/¢               '# Count the amount of "/" in it
      Ið¢             # Count the amount of spaces in the input
         α            # Get the difference between those
          ð×ý         # And join the list of snakes by that many spaces
'|¡õK                '# Then split by one or multiple adjacent "|"
     ®.ι              # Interleave it with the modified parts of variable` r`
        J             # And join everything together to a single string
Iðå≠i                 # If the input didn't contain any spaces:
     I                #  Output the input instead
                      # (implicit else:
                      #  output the top of the stack before this if)