Word break problem: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) m (→{{header|11l}}) |
|||
Line 824: | Line 824: | ||
abcdd: |
abcdd: |
||
(Not parseable with these words)</pre> |
(Not parseable with these words)</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The solution offered here does not use regular expressions. |
|||
The function `string2words` is a generator that can produce all |
|||
possible parses of a string but which can be stopped after finding the |
|||
first parse, as in the first demonstration. |
|||
In the second demonstration, the generator is used to count the number |
|||
of possible parses using the same toy dictionary as used in the |
|||
first demonstration. |
|||
In the third demonstration, the well-known dictionary unixdict.txt is |
|||
used to determine the number of possible parses of the string "totalreturn". |
|||
<lang jq> |
|||
def words: ["a", "bc", "abc", "cd", "b"]; |
|||
def strings: ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]; |
|||
# input: an array of allowed words |
|||
# output: a stream giving all possible parses of the given string into |
|||
# the allowed words; each output is an array showing how the string |
|||
# has been parsed. |
|||
def string2words(string): |
|||
. as $dict |
|||
# Input: array of words |
|||
# Output: augmented array |
|||
| def s2w(s): |
|||
if s=="" then . |
|||
else $dict[] as $word |
|||
| (s|startswith($word)) as $ix |
|||
| if $ix |
|||
then s[$word|length:] as $rest |
|||
| (. + [$word]) | s2w($rest) |
|||
else empty |
|||
end |
|||
end; |
|||
[] | s2w(string); |
|||
def count(s): reduce s as $x (0; .+1) ; |
|||
def demo1: |
|||
strings[] as $s |
|||
| words |
|||
| (first(string2words($s)) // []) as $parsed |
|||
| "\($s) => \($parsed|join(" "))" ; |
|||
def demo2: |
|||
strings[] as $s |
|||
| words |
|||
| count(string2words($s)) |
|||
| "\($s) has \(.) parse\(if . == 1 then "" else "s" end)." ; |
|||
# demo3 assumes an invocation along the lines of: |
|||
# jq -Rrn -f program.jq unixdict.txt |
|||
def demo3: |
|||
"returntotal" as $s |
|||
| "\($s) has \([inputs] | count(string2words($s)) parses." |
|||
demo1, " ", demo2, "", demo3 |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
abcd => a b cd |
|||
abbc => a b bc |
|||
abcbcd => a bc b cd |
|||
acdbc => a cd bc |
|||
abcdd => |
|||
abcd has 1 parse. |
|||
abbc has 1 parse. |
|||
abcbcd has 2 parses. |
|||
acdbc has 1 parse. |
|||
abcdd has 0 parses. |
|||
"returntotal" has 99 parses. |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |