9
\$\begingroup\$

Background

MQTT (Message Queuing Telemetry Transport) is an ISO standard publish-subscribe-based messaging protocol (Wikipedia).

Each message has a topic, such as the following examples:

  • myhome/groundfloor/livingroom/temperature
  • USA/California/San Francisco/Silicon Valley
  • 5ff4a2ce-e485-40f4-826c-b1a5d81be9b6/status
  • Germany/Bavaria/car/2382340923453/latitude

MQTT clients may subscribe to message topics using wildcards:

  • Single level: +
  • All levels onward: #

For example, the subscription myhome/groundfloor/+/temperature would produce these results (non-conformances in bold):

✅ myhome/groundfloor/livingroom/temperature
✅ myhome/groundfloor/kitchen/temperature
❌ myhome/groundfloor/livingroom/brightness
❌ myhome/firstfloor/livingroom/temperature
garage/groundfloor/fridge/temperature

Whereas the subscription +/groundfloor/# would produce these results:

✅ myhome/groundfloor/livingroom/temperature
✅ myhome/groundfloor/kitchen/brightness
✅ garage/groundfloor/fridge/temperature/more/specific/fields
❌ myhome/firstfloor/livingroom/temperature
❌ myhome/basement/corner/temperature

More info here.

The Task

Implement a function/program accepting two strings and returning a boolean. The first string is the subject topic, the second is the criteria topic. The criteria topic uses the subscription syntax detailed above. The function is truthy when the subject matches the criteria.

Rules for this task:

  • Topics are ASCII
  • There are no criteria fields beyond the # wildcard
  • Wildcards do not appear in subject topics
  • Number of subject fields >= number of criteria fields
  • There are no 0-character fields nor leading or tailing forward slashes

Test cases

criteria1 = "myhome/groundfloor/+/temperature"
criteria2 = "+/groundfloor/#"

("abc", "ab") => false
("abc", "abc") => true
("abc/de", "abc") => false
("myhome/groundfloor/livingroom/temperature", criteria1) => true
("myhome/groundfloor/kitchen/temperature", criteria1) => true
("myhome/groundfloor/livingroom/brightness", criteria1) => false
("myhome/firstfloor/livingroom/temperature", criteria1) => false
("garage/groundfloor/fridge/temperature", criteria1) => false
("myhome/groundfloor/livingroom/temperature", criteria2) => true
("myhome/groundfloor/kitchen/brightness", criteria2) => true
("garage/groundfloor/fridge/temperature/more/specific/fields", criteria2) => true
("myhome/firstfloor/livingroom/temperature", criteria2) => false
("myhome/basement/corner/temperature", criteria2) => false
("music/kei$ha/latest", "+/kei$ha/+") => true

\$\endgroup\$
  • \$\begingroup\$ @HyperNeutrino, that's a good question. I'm on the fence. Subject a/b/c would not match criteria a/b, so I'm inclined to say No. \$\endgroup\$ – Patrick Jul 15 '19 at 16:52
  • 4
    \$\begingroup\$ Are /, + and # guaranteed never to appear in topic parts? \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 17:11
  • \$\begingroup\$ I see in the blog linked that "Additionally, the forward slash alone is a valid topic" but no mention of + and #, so I guess these two can be. \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 17:20
  • 1
    \$\begingroup\$ @JonathanAllan From docs.oasis-open.org/mqtt/mqtt/v3.1.1/os/… : The wildcard characters can be used in Topic Filters, but MUST NOT be used within a Topic Name \$\endgroup\$ – Nick Kennedy Jul 15 '19 at 18:22
  • 2
    \$\begingroup\$ @NickKennedy - nice digging, but we really shouldn't need to. \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 18:58

16 Answers 16

3
\$\begingroup\$

Jelly, 20 bytes

ṣ€”/ZṖF”#eƊ¿œiÐḟ”+ZE

A monadic Link accepting a list of lists of characters, [topic, pattern], which returns 1 or 0 for match or no-match respectively.

Try it online! Or see a test-suite.

How?

ṣ€”/ZṖF”#eƊ¿œiÐḟ”+ZE - Link: list of lists of characters, [topic, pattern]
 €                   - for each:
ṣ                    -   split at occurrences of:
  ”/                 -     '/' character
    Z                - transpose (any excess of topic is kept)
           ¿         - while...
          Ɗ          - ...condition: last three links as a monad:
       ”#            -   '#' character
         e           -   exists in:
      F              -     flatten
     Ṗ               - ...do: pop the tail off
              Ðḟ     - filter discard those for which:
            œi       -   first multi-dimensional index of: ([] if not found, which is falsey)
                ”+   -     '+' character
                  Z  - transpose
                   E - all equal?
\$\endgroup\$
2
\$\begingroup\$

Ruby, 65 bytes

Regex solution. I added Regex.escape in case a criteria name just so happens to be something like com.java/string[]/\n or something silly that would have regex pieces.

->s,c{s=~/^#{Regexp.escape(c).sub('\#','.*').gsub'\+','[^/]*'}$/}

Try it online!

Non-regex solution, 77 bytes

Uses a nice simple split, zip, and match technique. I developed this one first before realizing that even with Regex.escape the regex solution would've been shorter anyways.

->s,c{s.split(?/).zip(c.split ?/).all?{|i,j|i==j||'+#'[j||9]||!j&&c[-1]==?#}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ .*? should work in place of [^/]*. \$\endgroup\$ – Fund Monica's Lawsuit Jul 16 '19 at 17:39
  • \$\begingroup\$ @NicHartley that will trigger a false match for criteria a/+/d with topic a/b/c/d \$\endgroup\$ – Value Ink Jul 16 '19 at 19:22
  • \$\begingroup\$ Ah, so it will. Wrapping that in an atomic group fixes that, but then it's two bytes longer. Oh well. \$\endgroup\$ – Fund Monica's Lawsuit Jul 16 '19 at 19:24
2
\$\begingroup\$

Perl 5 -pl, 50 bytes

$_="\Q$_";s|\\\+|[^/]+|g;s/\\\#/.*/;$_=<>=~m|^$_$|

Try it online!

\$\endgroup\$
  • \$\begingroup\$ small improvement, <>=~/^$_$/ at the end \$\endgroup\$ – Nahuel Fouilleul Jul 17 '19 at 5:51
1
\$\begingroup\$

Python 3, 72 bytes

lambda a,b:bool(re.match(b.translate({43:"[^/]+",35:".+"}),a))
import re

Try it online!

This problem can be trivially simplified to a regex match, though another more interesting method may produce better results.

EDIT I came up with a 107-byte solution not using regex. I don't know if it can get shorter than 72 or maybe I'm just not seeing to correct approach to this. Just the split-zip structure seems to be too large though. Try It Online!

\$\endgroup\$
  • 2
    \$\begingroup\$ If the sequence contains any other regex characters, this might fail. I'd look out for that even though none of the current test cases contain anything remotely regex-like. \$\endgroup\$ – Value Ink Jul 15 '19 at 20:53
  • \$\begingroup\$ ...like f('myhome/ground$floor/livingroom/temperature', 'myhome/ground$floor/+/temperature') which fails \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 21:10
  • \$\begingroup\$ As Value Ink says, +/kei$ha/+ does not match music/kei$ha/latest. \$\endgroup\$ – Chas Brown Jul 15 '19 at 21:18
1
\$\begingroup\$

Python 2, 85 84 80 92 89 bytes

lambda s,c:all(x in('+','#',y)for x,y in zip(c.split('/')+[0]*-c.find('#'),s.split('/')))

Try it online!

Thanks to Jonathan Allan and Value Ink for pointing out bugs.

\$\endgroup\$
  • \$\begingroup\$ Gives the wrong answer on f('ab', 'abc'). \$\endgroup\$ – Value Ink Jul 15 '19 at 21:56
  • \$\begingroup\$ @Jonathan Allan: Actually, rules say 'Number of subject fields >= number of criteria fields'. But other problems needed fixing... \$\endgroup\$ – Chas Brown Jul 15 '19 at 22:09
  • \$\begingroup\$ Oh weird rule given the problem context! \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 22:28
1
\$\begingroup\$

Haskell, 76 73 71 67 bytes

(a:b)#(c:d)=a=='+'&&b#snd(span(/='/')d)||a=='#'||a==c&&b#d
a#b=a==b

Try it online!

Edit: -4 bytes thanks to @cole.

\$\endgroup\$
  • 1
    \$\begingroup\$ a#b=a==b seems to work for a few bytes fewer, unless I’m missing something \$\endgroup\$ – cole Jul 16 '19 at 7:23
  • \$\begingroup\$ @cole: yes, that works. Thanks a lot! \$\endgroup\$ – nimi Jul 16 '19 at 15:09
1
\$\begingroup\$

Clojure, 107 91 76 65 102 bytes

An anonymous function, returns subject topic as truthy and nil as falsey (valid in Clojure).

(defn ?[t c](every? #(#{"#""+"(% 0)}(% 1))(apply #(map vector % %2)(map #(re-seq #"[^/]+" %) [t c]))))

107 102 working
91 76 65 all defeated with regex chars

\$\endgroup\$
  • \$\begingroup\$ ...and my comment under your question becomes pertinent \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 17:28
  • \$\begingroup\$ @JonathanAllan, indeed, except + and # do not appear in subject topic strings :) \$\endgroup\$ – Patrick Jul 15 '19 at 22:03
  • \$\begingroup\$ I think this fails for subject music/kei$ha/latest and criteria +/kei$ha/+ (which should match and is valid ASCII). \$\endgroup\$ – Chas Brown Jul 15 '19 at 23:40
  • \$\begingroup\$ @ChasBrown, correct, and with ^ instead of $; thanks. \$\endgroup\$ – Patrick Jul 15 '19 at 23:50
  • 1
    \$\begingroup\$ Try with '\Q' before and '\E' after the pattern prior to the replace - source \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 23:54
0
\$\begingroup\$

Kotlin, 106 bytes

fun f(s:List<String>)=s[1].split("/").filterIndexed{i,v->v!="+"&&v!="#"&&v!=s[0].split("/")[i]}.count()==0

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 99 88 bytes

Without using a regex. With some help from Jonathan Allan and Chas Brown.

f=lambda s,p:p in(s,'#')or p[:1]in(s[:1],'+')and f(s[1:],p['+'!=p[:1]or(s[:1]in'/')*2:])
\$\endgroup\$
  • \$\begingroup\$ f=lambda s,p:s==p or'#'==p[0]or p[0]in(s[0]+'+')and f(s[1:],p['+'!=p[0]or(s[0]=='/')*2:]) saves 12. However this fails to process some edge cases like f('abc/ijk/x', 'abc/+/xyz') or f('abc/ijk/xyz', 'abc/+/x'), which can be fixed with f=lambda s,p:s==p or'#'==p[:1]or p[:1]in(s[:1]+'+')and f(s[1:],p['+'!=p[:1]or(s[:1]=='/')*2:]) \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 21:07
  • \$\begingroup\$ This fails for f('abc','ab') and f('abc/de','abc') (both should return False, but instead there's an IndexError). \$\endgroup\$ – Chas Brown Jul 15 '19 at 23:33
  • \$\begingroup\$ ...or p[:1]in(s[:1],'+')and... fixes the edge cases @ChasBrown and I pointed out for a cost of 2 bytes. \$\endgroup\$ – Jonathan Allan Jul 15 '19 at 23:35
  • \$\begingroup\$ Fails another edge case of a trailing '+' (e.g. f('a/b', 'a/+')) but fixable in 0 bytes with ...or(s[:1]in'/')*2:]). \$\endgroup\$ – Jonathan Allan Jul 16 '19 at 0:09
  • \$\begingroup\$ Try it online is always recommended! \$\endgroup\$ – Chas Brown Jul 16 '19 at 0:10
0
\$\begingroup\$

Charcoal, 36 bytes

≔⪪S/θ≔⪪S/ηF∧№η#⊟η≔…θLηθF⌕Aη+§≔θι+⁼θη

Try it online! Link is to verbose version of code. Outputs - (Charcoal's implicit output for true) for a match, nothing for no match. Explanation:

≔⪪S/θ

Split the subject on /s.

≔⪪S/η

Split the criteria on /s.

F∧№η#⊟η≔…θLηθ

If the criteria contains (i.e. ends with) a # then remove it and trim the subject to the new length of the criteria.

F⌕Aη+§≔θι+

Where the criteria contains + then replace that element in the subject with +.

⁼θη

Compare the subject with the criteria and implicitly print the result.

\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 42 bytes

%`$
/
+`^([^/]+/)(.*¶)(\1|\+/)
$2
^¶$|¶#/$

Try it online! Explanation:

%`$
/

Suffix a / to both lines.

+`^([^/]+/)(.*¶)(\1|\+/)
$2

Repeatedly remove the first element of both subject and criteria while they equal or the criteria element is a (happy) +.

^¶$|¶#/$

The criteria matches if it's just a # (with the / that was added earlier) otherwise both subject and criteria should be empty by this point.

\$\endgroup\$
0
\$\begingroup\$

Pyth, 22 bytes

:Q::E"[+]""[^/]+"\#".*

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 22 19 bytes

ḟ”+ṣ”/)ZẠƇṖœi”#$¿ZE

Try it online!

A monadic link that takes as its argument [topic], [criterion] and returns 1 for a match and 0 for no match.

\$\endgroup\$
0
\$\begingroup\$

JavaScript, 69 66 bytes

t=>s=>new RegExp(s.split`+`.join`[^/]+`.split`#`.join`.+`).test(t)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This fails for subject music/kei$ha/latest and criteria +/kei$ha/+ (which should match and is valid ASCII). \$\endgroup\$ – Chas Brown Jul 16 '19 at 21:21
0
\$\begingroup\$

Python 3, 149 148 bytes

def f(t,c):t,c=t.split('/'),c.split('/');return all([c[i]=='+'or c[i]==t[i]or c[i]=='#'for i in range(len(c))])and not(len(c)!=len(t)and c[-1]!='#')

Try it online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 21 bytes

ε'/¡}ζʒ'+å≠}˜'#¡н2ôøË

Input as a list in the order [criteria, topic].

Try it online or verify all test cases.

Explanation:

ε                      # Map both strings in the implicit input-list to:
 '/¡                  '#  Split the string on "/"
                       #   i.e. ["+/+/A/B/#","z/y/A/B/x/w/v/u"]
                       #    → [["+","+","A","B","#"],["z","y","A","B","x","w","v","u"]]
    }ζ                 # After the map: zip/transpose the two string-lists,
                       # with space as (default) filler
                       #  → [["+","z"],["+","y"],["A","A"],["B","B"],["#","x"],[" ","w"],
                       #     [" ","v"],[" ","u"]]
      ʒ    }           # Filter each pair by:
       '+å≠           '#  Only keep those which do NOT contain a "+"
                       #   → [["A","A"],["B","B"],["#","x"],[" ","w"],[" ","v"],[" ","u"]]
            ˜          # Flatten the filtered list
                       #  → ["A","A","B","B","#","x"," ","w"," ","v"," ","u"]
             '#¡      '# Split the list by "#"
                       #  → [["A","A","B","B"],["x"," ","w"," ","v"," ","u"]]
                н      # Only keep the first part
                       #  → ["A","A","B","B"]
                 2ô    # Split this back into pairs of two
                       #  → [["A","A"],["B","B"]]
                   ø   # Zip/transpose them back
                       #  → [["A","B"],["A","B"]]
                    Ë  # And check if both inner lists are equal
                       #  → 1 (truthy)
                       # (after which the result is output implicitly)
\$\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.