Haskell + hgl, 44 bytes
Here we are looking for the subsequence "nice" where all the elements are evenly spaced. So the first things we do to the input are, pair it with it's indexes and get all possible subsequences.
Now that we have these we want to check if any meet the criteria. So we use
ay for any.
ay ... <ss<eu
Now we want to check two separate things here. One is that the values are equal to
nice and the second is that the indexes are evenly spaced. So it would be nice to unzip the two parts e.g.
[(0,'n'),(3,'i'),(4,'c'),(9,'e')] -> ([0,3,4,5],"nice").
Now lets formulate our two tests. One is very easy:
So now we want to determine if the indices are evenly spaced. We use
δ to determine the distances, then to check if the list only contains one value we do
lt2<l<nb, that is we nub the list and check the length is less than 2.
Now we use
bm to map the two functions across our tuple:
Lastly we convert this tuples booleans to a single boolean with
Uc mp, which is and (
mp) uncurried (
With that I'd like to reflect a bit on ways we might improve hgl in light of this. It doesn't score very well here, 44 bytes is pretty long. There are a couple of things that could be improved.
lt2<l<nb is really long to determine if a list is unique. This should probably be 1 function.
- Although it wouldn't help with the size here there probably should be some way to get subsequences of a particular size. We almost had to get all the subsequences and then filter by size. It also would make this much faster.
Haskell + hgl, 47 bytes
Here's it solved with the parsing library
pP$lF bn_(h'*>ʃn*>l<h')$is(rM hd)$p<ʃ<p<"ice"
This is a good deal faster than the previous solution since it doesn't calculate every single subsequence.
Let's start with the string we are looking for:
Now we want to parse these letters with things in between them. It would be nice to use an
is which intersperses elements in a list. So lets turn these into parsers:
This creates a list of parsers each which parses a single letter. Now we want to intersperse it with something that parsers that all parse the same amount of characters.
hd parses a single character so
rM hd takes a number and parses exactly that many of the character.
However this is a function, not a parser so we can't intersperse it with our parsers. We could try to supply the argument first and then intersperse but it's easier to just make our char parsers into functions. They take a single argument, a number, and just ignore it. To do this we just map
p, (short for
const) across the list.
However we can't intersperse yet. Unfortunately the parsers for
rM hd return a string while our other parsers return a character. Even though we don't care about the results we can't put them in a list together. So we have to change one of them. It's fairly easy to just make our char parsers into string parsers:
p turns the char into a string,
ʃ turns the string into a parser
p turns the parser into a parser function. Now we can intersperse:
At this point we have a list of functions to parsers. We would like to supply all these parsers with the same argument since the gaps need to be the same sizes.
There are a couple of ways to do this. The first way that springs to mind is to use a traverse.
sQ will pull all the arguments outside and it's super cheap. But it gets a little messy instead we can use a fold.
bn_ is a sort of chaining operator like
bn_ :: Monad m => m a -> (a -> m b) -> m a
We can use a fold across the list to then chain everything together.
lF bn_ :: (Foldable t, Monad m) => m a -> t (a -> m b) -> m a
So if we apply this to what we have:
ghci> :t F(lF bn_)$is(rM hd)$p<ʃ<p<"nice"
F(lF bn_)$is(rM hd)$p<ʃ<p<"nice"
:: (Integral i, Ord i) =>
Parser (List Prelude.Char) i -> Parser (List Prelude.Char) i
This takes a parser which produces the initial integer and gives us back the parser we want.
Now the question is "How do we figure out which integer?" We could try and have it do something like, guess every size less than the list to see, but the best way seems to be to break the
n off of nice and get the number just as the size of the first gap after the
To parse an
n we can do:
Then after it we want a known number of characters.
h' will parse any number of characters. And
l< will convert that into a length.
And we also have to allow for arbitrary characters before the first
So now we slot that in:
lF bn_(h'*>ʃn*>l<h')$is(rM hd)$p<ʃ<p<"ice"
And we have a full parser. To turn that parser into a function we use
pP, which returns true whenever there is a parse even if it doesn't consume the entire string.
The parsers are very powerful but disappointingly parser based answers are usually a bit shy of the non-parser answer. Here it's 3 bytes, which is the cost to invoke a parser.
- It's probably going to be eventually necessary to add a regex processor. Sometimes we will beat regex, but it would really open up a lot of opportunities.
- I should probably make a parser evaluator that matches the parser anywhere in the input. Would save a
h'*> here and probably in a few other places.
lMy could have been useful here but
l<h' was shorter than
lMy hd. Not sure if this is actionable, even shortening
lMy to one character would leave them tied. But it's of interest to note.