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 at 16:52
  • 4
    \$\begingroup\$ Are /, + and # guaranteed never to appear in topic parts? \$\endgroup\$ – Jonathan Allan Jul 15 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 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 at 18:22
  • 2
    \$\begingroup\$ @NickKennedy - nice digging, but we really shouldn't need to. \$\endgroup\$ – Jonathan Allan Jul 15 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\$ – Nic Hartley Jul 16 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 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\$ – Nic Hartley Jul 16 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 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 at 20:53
  • \$\begingroup\$ ...like f('myhome/ground$floor/livingroom/temperature', 'myhome/ground$floor/+/temperature') which fails \$\endgroup\$ – Jonathan Allan Jul 15 at 21:10
  • \$\begingroup\$ As Value Ink says, +/kei$ha/+ does not match music/kei$ha/latest. \$\endgroup\$ – Chas Brown Jul 15 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 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 at 22:09
  • \$\begingroup\$ Oh weird rule given the problem context! \$\endgroup\$ – Jonathan Allan Jul 15 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 at 7:23
  • \$\begingroup\$ @cole: yes, that works. Thanks a lot! \$\endgroup\$ – nimi Jul 16 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 at 17:28
  • \$\begingroup\$ @JonathanAllan, indeed, except + and # do not appear in subject topic strings :) \$\endgroup\$ – Patrick Jul 15 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 at 23:40
  • \$\begingroup\$ @ChasBrown, correct, and with ^ instead of $; thanks. \$\endgroup\$ – Patrick Jul 15 at 23:50
  • 1
    \$\begingroup\$ Try with '\Q' before and '\E' after the pattern prior to the replace - source \$\endgroup\$ – Jonathan Allan Jul 15 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 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 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 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 at 0:09
  • \$\begingroup\$ Try it online is always recommended! \$\endgroup\$ – Chas Brown Jul 16 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 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.