Word break problem: Difference between revisions

{{trans|D}}

 

String val

[String] parsed

 

d = [‘abc’, ‘a’, ‘ac’, ‘b’, ‘c’, ‘cb’, ‘d’]

 

{{out}}

 

=={{header|Aime}}==

wordbreak(record dict, text phrase, integer p, list words)

{

 

return 0;

{{Out}}

<pre>abcd: a b cd

acdbc: a cd bc

abcdd: can't break</pre>

 

=={{header|C++}}==

{{trans|Rust}}

#include <iostream>

#include <optional>

return 0;

}

 

{{out}}

=={{header|D}}==

{{trans|Java}}

import std.range;

import std.stdio;

parsed = p;

}

{{out}}

<pre>String = aab, Dictionary = ["a", "aa", "b", "ab", "aab"]. Solutions = 4

{{libheader| System.Generics.Collections}}

{{Trans|Go}}

program Word_break_problem;

 

 

Readln;

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

=={{header|Haskell}}==

{{Trans|Javascript}}

import Data.Tree (Tree(..))

 

 

main :: IO ()

{{Out}}

<pre>abcd:

With such short sentences we can find the partition sets, then check that all are words.

 

all_partitions=: <@(<;.1)"1 _~ (1,.[:#:[:i.2^<:@:#) NB. all_partitions 'abcd'

word_break=: ([ #~ 0 = [: #&>@:] -.L:_1 _)~ all_partitions

main=: (] , (;:inv L:_1@:word_break >))"_ 0 boxopen

 

<pre>

=={{header|Java}}==

Accept string to be parsed, and dictionary of words, as method arguments.

import java.util.ArrayList;

import java.util.Arrays;

 

}

{{out}}

<pre>

Composing a solution from generic functions.

{{Trans|Python}}

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>abcd:

used to determine the number of possible parses of the string "totalreturn".

 

def words: ["a", "bc", "abc", "cd", "b"];

def strings: ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"];

demo1, " ", demo2, "", demo3

 

{{out}}

<pre>

 

=={{header|Julia}}==

words = ["a", "bc", "abc", "cd", "b"]

strings = ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]

end

 

{{output}}<pre>

1 Solution(s) for abcd:

=={{header|Kotlin}}==

I've downloaded the free dictionary at http://www.puzzlers.org/pub/wordlists/unixdict.txt for this task. All single letters from 'a' to 'z' are considered to be words by this dictionary but 'bc' and 'cd' which I'd have expected to be present are not.

 

import java.io.File

println()

}

 

{{out}}

 

=={{header|Lua}}==

-- possible candidates for this particalur problem

function genDict(ws)

for i=1,#test do

print(test[i],wordbreak(test[i]))

{{out}}

<pre>abcd a b cd

We provide two ways to initialize the dictionary: either explicitly by providing the list of words or by providing a file name from which extract the words. In the second case, it is possible to specify the minimal length of the words to keep. This is useful mainly to eliminate all the one letter words we get with “unixdict.txt”.

 

 

type

dict = initDict("unixdict.txt", 2)

dict.breakWord("because")

 

{{out}}

 

=={{header|Perl}}==

use warnings;

 

@matches = $word =~ /^ ($one_of) ($one_of)? ($one_of)? ($one_of)? $/x; # sub-optimal: limited number of matches

return join(' ', grep {$_} @matches) || "(not possible)";

{{out}}

<pre>a: a

=={{header|Phix}}==

The distributed version also contains a few experiments with applying a real dictionary, largely unsuccessful.

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\Word_break_problem.exw

<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

===Non-determinism using member/2===

<code>s/2</code> checks all possible combinations. It uses <code>member/2</code> to select some element from Dict and backtracks if no solution is found.

Tests = [["aab", ["a", "aa", "b", "ab", "aab"]],

["abba", ["a", "aa", "b", "ab", "aab"]],

foreach([String,Dict] in Tests)

println([string=String,dict=Dict]),

println(All),

nl

S := S ++ [D]

end,

 

{{out}}

===Non-determinism using member/2 and append/3===

<code>s2/2</code> is more efficient. It uses <code>append/3</code> to extract the found prefix from the string.

String2 = copy_term(String),

S = [],

S := S ++ [D]

end,

 

===Using recursion===

<code>s3/2</code> use the same idea as <code>s2/2</code> but use recursion. Neater and more efficient.

s3(Dict,String,S).

 

member(E,Dict),

append(E,String2,String),

 

===Some tests===

Here is the test engine.

garbage_collect(300_000_000),

_ = random2(),

end,

println(len=All.len),

 

As can be seen by this summary, <code>s3/2</code> is the most efficient of these versions. <code>s/2</code> is too slow but for the simplest examples.

 

=={{header|PicoLisp}}==

(setq *Dict2

(quote

(println (word "samsungandmango" *Dict2))

(println (word "samsungandmangok" *Dict2))

{{out}}

<pre>

 

{{Works with|Python|3.7}}

 

from itertools import (chain)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>abcd:

This returns all the possible splits (and null list if none is possible). Who's to say which is the best?

 

 

(define render-phrases pretty-print)

(render-phrases (word-splits "samsungandmango" dict-2))

(render-phrases (word-splits "samsungandmangok" dict-2))

{{out}}

<pre>'("a b cd")

This implementation does not necessarily find ''every'' combination, it returns the one with the longest matching tokens.

 

my $regex = @words.join('|');

 

put "$_: ", word-break($_) for <abcd abbc abcbcd acdbc abcdd>;

 

{{out}}

<pre>abcd: a b cd

=={{header|REXX}}==

This REXX version allows the words to be tested (and the dictionary words) to be specified on the command line.

parse arg a '/' x; a=space(a); x=space(x) /*get optional args; elide extra blanks*/

if a=='' | a=="," then a= 'abcd abbc abcbcd acdbc abcdd' /*Not specififed? Use default*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Word break problem

 

next

next

Output:

<pre>

abcbcd = abc b cd

acdbc = a cd bc

</pre>

 

=={{header|Rust}}==

===Dynamic programming===

fn create_string(s: &str, v: Vec<Option<usize>>) -> String {

let mut idx = s.len();

set.insert("b");

println!("{:?}", word_break("abcd", set).unwrap());

{{output}}

<pre>"a b cd"</pre>

===First solution===

Finds all possible solutions recursively, using a trie representation of the dictionary:

def add(s: String): TrieNode = s match {

case "" => copy(isWord = true)

def wordBreak(s: String, dict: TrieNode): List[List[String]] = {

wordBreakRec(s, dict, dict, "")

Calling it with some example strings:

val testCases = List("abcd", "abbc", "abcbcd", "acdbc", "abcdd")

for (s <- testCases) {

println("\t" + words.mkString(" "))

}

{{out}}

<pre>abcd has 1 solution(s):

===Combined solution===

{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/49YwsD5/1 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/L47OzgmjSkOnQ5wfrZ5snQ Scastie (remote JVM)].

val dict = buildTrie("a", "bc", "abc", "cd", "b")

lazy val empty = TrieNode(isWord = false, Map.empty) // lazy or in a companion object

})

 

 

=={{header|Seed7}}==

 

const func boolean: wordBreak (in string: stri, in array string: words, in string: resultList) is func

end if;

end for;

 

{{out}}

=={{header|Sidef}}==

{{trans|zkl}}

 

var r = ->(str, arr=[]) {

for str in (strs) {

printf("%11s: %s\n", str, word_break(str, words) \\ '(not possible)')

{{out}}

<pre>

{{trans|Rust}}

 

 

@inlinable

print("\(test):")

print(" \(wordBreak(str: test, dict: words) ?? "did not parse with given words")")

 

{{out}}

=={{header|Tailspin}}==

Does a depth-first search (after generating all possibilities on the current level). We could stop looking further after one is found, just add a condition to do nothing if a done-flag is set.

templates wordBreaks&{dict:}

composer starts&{with:}

'ababab' -> wordBreaks&{dict: ['a', 'ab', 'bab']} -> !OUT::write

'abcbab' -> wordBreaks&{dict: ['a', 'ab', 'bab']} -> !OUT::write

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{trans|Java}}

 

Structure Node

End Sub

 

{{out}}

<pre>String = aab, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 4

{{trans|Go}}

{{libheader|Wren-fmt}}

 

class Prefix {

System.print("can't break")

}

 

{{out}}

 

=={{header|zkl}}==

words=words.split(" "); // to list of words

r:=fcn(str,words,sink){ // recursive search, easy to collect answer

if(False==r) return("not possible");

r.reverse().concat(" ")

println(text,": ",wordBreak(text,"a bc abc cd b"))

{{out}}

<pre>