Fork me on GitHub
#clojure-losangeles
<
2020-09-10
>
nate03:09:46

hammered my head against it a bit more, and I got it to work. both functions return lists, so one of them needs to flatten so that it doesn't endlessly keep making nested lists. I pushed a branch called working-code to the github repo if anyone is interested @dorab @jts

nate03:09:01

I added the flatten to line 15, and changed match to [match] on line 17.

nate03:09:35

then it was just a matter of handling the case in cleave of filtering out all the non results and defaulting to the "not found" string if nothing was found

nate03:09:58

very curious if you found other solutions in your tinkering

alandipert14:09:20

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

Javier Trevino Saldana15:09:14

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

alandipert15:09:22

thanks thats enough to go on :thumbsup:

dorab21:09:10

@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 🙂

alandipert21:09:20

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

dorab21:09:37

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.

dorab21:09:49

@U04VC31U8 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.

alandipert21:09:22

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

nate21:09:34

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

dorab21:09:37

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.

dorab21:09:49

This was a surprisingly good challenge.

dorab21:09:10

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.

alandipert21:09:39

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

alandipert21:09:32

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

alandipert21:09:08

this is a chance for me to redeem myself simple_smile

dorab22:09:50

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

🙌 6
😄 3
Javier Trevino Saldana23:09:14

haha anytime. Looking forward to the next one

Mario C.18:09:16

Seems to work on the 3 examples on the site

Mario C.18:09:17

does not work

Mario C.18:09:30

Just found the tests on the github

Mario C.19:09:18

After some tweaking I ended up with this

Mario C.19:09:20

(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 [])

Mario C.19:09:47

this passed all the tests

Mario C.19:09:53

fun problem

nate22:09:07

oh man, I always forget about trampoline!

nate22:09:20

it's like recur, but for mutual recursion

Mario C.23:09:42

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.

Mario C.23:09:29

"[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]"