Clojurians Log v2

i missed the meetup but this looks interesting, do you hvae the problem description handy?

yep, this is it https://edabit.com/challenge/y7xoBP9bgHRNTcELK the test cases were converted to clojure in the repo link above if you want em

thanks thats enough to go on :thumbsup:

@nate Your solution is likely better than mine. I, too, banged on it last night and realized what you did. However, my solution is hackier than yours. In any case, it passes all the tests, so it MUST be correct 🙂

the tests don't suggest it but i can imagine inputs that would produce multiple solutions, which suggest a solution that backtracks

I should mention that I pushed my solution under the dorab-working-code branch. I attempted to put that branch off of the la-meetup-september-2020.

@alandipert When we worked on it together, we did envision multiple solutions. In fact, my solution generates all possible solutions and then takes the first one. Did not add tests to see if it worked.

oh awesome. i'll try not to look at it before making my own 😄

Yes, definitely need a solution that backtracks. The last test case has a dead end that needs to be backed out of.

One alley we went down was to use a backtracking regex. But eventually stopped pursuing that path because we could not quite figure out the regex.

This was a surprisingly good challenge.

The first solution we tried was a greedy longest-match-first solution without backtracking. When it failed on a test we realized we'd need a backtracking solution.

nice! yeah i enjoy this puzzle, i think i'll warm up with it before work tomorrow

about 10 yrs ago i was presented a similar problem as part of an interview at Twitter and i totally blew it

this is a chance for me to redeem myself :simple_smile:

Thanks to @jts for making it an international virtual meetup and contributing to the discussion and solution.

haha anytime. Looking forward to the next one

Seems to work on the 3 examples on the site

does not work

Just found the tests on the github

After some tweaking I ended up with this

(defn first-matches [sentence words]
    (-> (filter (fn [word]
                  (let [reg    (re-pattern word)
                        result (str/split sentence reg)
                        match  (first result)]
                    (zero? (count match))))
                words)))

  (defn match-validator [sentence fms]
    (->> fms
         (remove (fn [ms]
                   (-> (str/split sentence (re-pattern ms) 2)
                       last
                       (first-matches words)
                       empty?)))
         first))

  (defn clean-string [sentence words ms]
    (let [fms (first-matches sentence words)
          fm (match-validator sentence fms)]
      (if (nil? fm)
        "Cleaving stalled: Word not found"
        (let [cs (last (str/split sentence (re-pattern fm) 2))]
          (if (or (empty? cs) (nil? cs))
            (str/join " " (conj ms fm))
            #(clean-string cs words (conj ms fm)))))
      ))

  (trampoline clean-string s7 words [])

this passed all the tests

fun problem

oh man, I always forget about trampoline!

it's like recur, but for mutual recursion

I was thinking about this and figured out a way to simplify it. You could sort the word bank and reverse it. Then "wrap" all the matches starting with the biggest word. Leaving you with something like [[[a]n]d] . All the words in valid sentences will be insides the brackets. If any letters are dangling outside of that, then it is stalled sentence. Then you split the sentence by ][ . Then remove all the brackets.

"[f[or]][a][moment][noth[i]ng][[h[a]ppen]ed][[the]n][[a]fter][a][second][or][so][noth[i]ng][cont[i]nued][to][h[a]ppen]"