Sorry folks, no Hexagony this time...
Byte count assumes ISO 8859-1 encoding.
.+¶
$.'$*_¶$&
^_¶
¶
((^_|\2_)*)_\1{5}_+
$2_
^_*
$.&$*×_$&$&$.&$*×
M!&m`(?<=(?=×*(_)+)\A.*)(?<-1>.)+(?(1)!)|^.*$
O$`(_)|.(?=.*$)
$1
G-2`
T`d`À-É
m`\A(\D*)(?(_)\D*¶.|(.)\D*¶\2)((.)(?<=(?<4>_)\D+)?((?<=(?<1>\1.)\4\D*)|(?<=(?<1>\D*)\4(?<=\1)\D*)|(?<=\1(.(.)*¶\D*))((?<=(?<1>\D*)\4(?>(?<-7>.)*)¶.*\6)|(?<=(?<1>\D*)(?=\4)(?>(?<-7>.)+)¶.*\6))|(?<=(×)*¶.*)((?<=(?<1>\1.(?>(?<-9>¶.*)*))^\4\D*)|(?<=(?<1>\D*)\4(?>(?<-9>¶.*)*)(?<=\1)^\D*)|(?<=(?<1>\1\b.*(?(9)!)(?<-9>¶.*)*)\4×*¶\D*)|(?<=(?<1>\D*\b)\4.*(?(9)!)(?<-9>¶.*)*(?<=\1.)\b\D*))|(?<=(?<1>\1.(?>(?<-11>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1(?>(?<-12>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1.(?>(?<-13>.)*¶\D*))\4(\w)*\W+.+)|(?<=(?<1>.*)\4(?>(?<-14>.)*¶\D*)(?<=\1.)(\w)*\W+.+))(?<=\1(\D*).+)(?<!\1\15.*(?<-1>.)+))*\Z
Expects the target string on the first line and the hexagon on the second line of the input. Prints 0 or 1 accordingly.
Try it online! (The first line enables a test suite, where each line is a test case, using ¦ for separation instead of a linefeed.)
The proper way to solve this challenge is with a regex of course. ;) And if it wasn't for the fact that this challenge also involves the unfolding procedure of the hexagon, this answer would actually consist of nothing but a single ~600-byte long regex.
This isn't quite optimally golfed yet, but I'm quite happy with the result (my first working version, after removing named groups and other stuff required for sanity, was around 1000 bytes). I think I could save about 10 bytes by swapping the order of the string and the hexagon but it would require a complete rewrite of the regex at the end, which I'm not feeling up to right now. There's also a 2-byte saving by omitting the G stage, but it slows down the solution considerably, so I'll wait with making that change until I'm sure I've golfed this as well as I can.
Explanation
The main part of this solution makes extensive use of balancing groups, so I recommend reading up on them, if you want to understand how this works in detail (I won't blame you if you don't...).
The first part of the solution (i.e. everything except the last two lines) is a modified version of my answer to Unfolding the Hexagony source code. It constructs the hexagon, while leaving the target string untouched (and it actually constructs the hexagon before the target string). I've made some changes to the previous code to save bytes:
- The background character is
× instead of a space so that it doesn't conflict with potential spaces in the input.
- The no-op/wildcard character is
_ instead ., so that grid cells can be reliably identified as word characters.
- I don't insert any spaces or indentation after the hexagon is first constructed. That gives me a slanted hexagon, but that is actually much more convenient to work with and the adjacency rules are fairly simple.
Here is an example. For the following test case:
ja
abcdefghij
We get:
××abc
×defg
hij__
____×
___××
ja
Compare this with the usual layout of the hexagon:
a b c
d e f g
h i j _ _
_ _ _ _
_ _ _
We can see that the neighbours are now all of the usual 8 Moore-neighbours, except the north-west and south-east neighbours. So we need to check horizontal, vertical and south-west/north-east adjacency (well and then there are the wrapping edges). Using this more compact layout also has the bonus that we'll be able to use those ×× at the end to determine the size of the hexagon on the fly when we need it.
After this form has been constructed, we make one more change to the entire string:
T`d`À-É
This replaces the digits with the extended ASCII letters
ÀÁÂÃÄÅÆÇÈÉ
Since they are replaced both in the hexagon and in the target string this won't affect whether the string is matched or not. Also, since they are letters \w and \b still identify them as hexagon cells. The benefit of doing this substitution is that we can now use \D in the upcoming regex to match any character (specifically, linefeeds as well as non-linefeed characters). We can't use the s option to accomplish that, because we'll need . to match non-linefeed characters in several places.
Now the last bit: determining whether any path matches our given string. This is done with a single monstrous regex. You might ask yourself why?!?! Well, this is fundamentally a backtracking problem: you start somewhere and attempt a path as long as it matches the string, and once it doesn't you backtrack and try a different neighbour from the last character that worked. The one thing that you get for free when working with regex is backtracking. That's literally the only thing the regex engine does. So if we just find a way to describe a valid path (which is tricky enough for this kind of problem, but definitely possible with balancing groups), then the regex engine will sort out finding that path among all possible ones for us. It would certainly be possible to implement the search manually with multiple stages (and I've done so in the past), but I doubt it would be shorter in this particular case.
One issue with implementing this with a regex is that we can't arbitrarily weave the regex engine's cursor back and forth through the string during backtracking (which we'd need since the path might go up or down). So instead, we keep track of our own "cursor" in a capturing group and update that at every step (we can move to the position of the cursor temporarily with a lookaround). This also enables us to store all past positions which we'll use to check that we haven't visited the current position before.
So let's get to it. Here is a slightly saner version of the regex, with named groups, indentation, less random order of neighbours and some comments:
\A
# Store initial cursor position in <pos>
(?<pos>\D*)
(?(_)
# If we start on a wildcard, just skip to the first character of the target.
\D*¶.
|
# Otherwise, make sure that the target starts with this character.
(?<first>.)\D*¶\k<first>
)
(?:
# Match 0 or more subsequent characters by moving the cursor along the path.
# First, we store the character to be matched in <next>.
(?<next>.)
# Now we optionally push an underscore on top (if one exists in the string).
# Depending on whether this done or not (both of which are attempted by
# the engine's backtracking), either the exact character, or an underscore
# will respond to the match. So when we now use the backreference \k<next>
# further down, it will automatically handle wildcards correctly.
(?<=(?<next>_)\D+)?
# This alternation now simply covers all 6 possible neighbours as well as
# all 6 possible wrapped edges.
# Each option needs to go into a separate lookbehind, because otherwise
# the engine would not backtrack through all possible neighbours once it
# has found a valid one (lookarounds are atomic).
# In any case, if the new character is found in the given direction, <pos>
# will have been updated with the new cursor position.
(?:
# Try moving east.
(?<=(?<pos>\k<pos>.)\k<next>\D*)
|
# Try moving west.
(?<=(?<pos>\D*)\k<next>(?<=\k<pos>)\D*)
|
# Store the horizontal position of the cursor in <x> and remember where
# it is (because we'll need this for the next two options).
(?<=\k<pos>(?<skip>.(?<x>.)*¶\D*))
(?:
# Try moving north.
(?<=(?<pos>\D*)\k<next>(?>(?<-x>.)*)¶.*\k<skip>)
|
# Try moving north-east.
(?<=(?<pos>\D*)(?=\k<next>)(?>(?<-x>.)+)¶.*\k<skip>)
)
|
# Try moving south.
(?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
|
# Try moving south-east.
(?<=(?<pos>\k<pos>(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
|
# Store the number of '×' at the end in <w>, which is one less than the
# the side-length of the hexagon. This happens to be the number of lines
# we need to skip when wrapping around certain edges.
(?<=(?<w>×)*¶.*)
(?:
# Try wrapping around the east edge.
(?<=(?<pos>\k<pos>.(?>(?<-w>¶.*)*))^\k<next>\D*)
|
# Try wrapping around the west edge.
(?<=(?<pos>\D*)\k<next>(?>(?<-w>¶.*)*)(?<=\k<pos>)^\D*)
|
# Try wrapping around the south-east edge.
(?<=(?<pos>\k<pos>\b.*(?(w)!)(?<-w>¶.*)*)\k<next>×*¶\D*)
|
# Try wrapping around the north-west edge.
(?<=(?<pos>\D*\b)\k<next>.*(?(w)!)(?<-w>¶.*)*(?<=\k<pos>.)\b\D*)
)
|
# Try wrapping around the south edge.
(?<=(?<pos>\k<pos>.(?>(?<-x>.)*¶\D*))\k<next>(?<x>\w)*\W+.+)
|
# Try wrapping around the north edge.
(?<=(?<pos>.*)\k<next>(?>(?<-x>.)*¶\D*)(?<=\k<pos>.)(?<x>\w)*\W+.+)
)
# Copy the current cursor position into <current>.
(?<=\k<pos>(?<current>\D*).+)
# Make sure that no matter how many strings we pop from our stack of previous
# cursor positions, none are equal to the current one (to ensure that we use
# each cell at most once).
(?<!\k<pos>\k<current>.*(?<-pos>.)+)
)*
# Finally make sure that we've reached the end of the string, so that we've
# successfully matched all characters in the target string.
\Z
I hope that the general idea is roughly clear from this. As an example for how one of those movements along the path works, let's look at the bit that moves the cursor south:
(?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
Remember that lookbehinds should be read from right to left (or bottom to top), because that's the order they are executed in:
(?<=
(?<pos>
\k<pos> # Check that this is the old cursor position.
. # Match the character directly on top of the new one.
(?>(?<-x>.)*) # Match the same amount of characters as before.
¶.* # Skip to the next line (the line, the old cursor is on).
) # We will store everything left of here as the new
# cursor position.
\k<next> # ...up to a match of our current target character.
(?<x>.)* # Count how many characters there are...
¶\D* # Skip to the end of some line (this will be the line below
# the current cursor, which the regex engine's backtracking
# will determine for us).
)
Note that it's not necessary to put an anchor in front of the \k<pos> to ensure that this actually reaches the beginning of the string. <pos> always starts with an amount of × that can't be found anywhere else, so this acts as an implicit anchor already.
I don't want to bloat this post more than necessary, so I won't go into the other 11 cases in detail, but in principle they all work similarly. We check that <next> can be found in some specific (admissible) direction from the old cursor position with the help of balancing groups, and then we store the string up to that match as the new cursor position in <pos>.
21Somebody should do this in Hexagony. :D – James – 2016-08-02T23:52:26.467
hexAGONY xD have fun – Rohan Jhunjhunwala – 2016-08-02T23:57:34.413
@DrGreenEggsandIronMan I was going to suggest Retina also, but that's probably pretty trivial. :P – Rɪᴋᴇʀ – 2016-08-03T00:01:33.393
2
Related: http://codegolf.stackexchange.com/q/66708/29750
– NinjaBearMonkey – 2016-08-03T00:05:29.9079I was initially very confused by the truthy examples until I realized that the hexagon is the source of the regex(es), so to speak, not the second string. Which is still mind-bending... :P – El'endia Starman – 2016-08-03T01:40:00.700
Apparently, I made this challenge too difficult, as I haven't gotten any answers yet (and to think that I was considering allowing any regex symbol in the hexagon) – Nathan Merrill – 2016-08-03T12:41:58.797
5@DrGreenEggsandIronMan I'll offer a 500-rep bounty if someone does do this in Hexagony. – AdmBorkBork – 2016-08-03T13:21:55.397
('abcdefghijklm', 'h%a'):
honly connects to the bottom right corner, which doesn't connect toa. ('abcdefghijklmno', 'ja') :jis completely entrapped. – Nathan Merrill – 2016-08-29T15:29:04.207As for
kgfeia, I already had it in the truthy, but forgot to change it. You were correct about side-to-side wrapping. When I initially wrote the spec, I thought they wrapped. – Nathan Merrill – 2016-08-29T15:36:44.400You don't need to use
horj, there are.s at the bottom you can get toafrom – Blue – 2016-08-29T15:38:57.757oooh, I didn't think about that. Good catch. – Nathan Merrill – 2016-08-29T15:40:05.193
I guess you should also change your example to a hexagon that's completely filled in as well (it has dots that make the path valid) – Blue – 2016-08-29T16:11:48.447
2@Blue An example of an unfilled hexagon is important. More importantly, I've made the distinction between a "path" and a "regex". – Nathan Merrill – 2016-08-29T16:13:42.200