[Community Puzzle] DAWG

Puzzles
#22

thx - there i get 75 instead of 86 - but I’ll take this to think about the task again

what my algorithm does is this:

NodesNeeded starts with 1 for the ‘End’-node

then i put the words in a 2D-Matrix and for each column i add to NodesNeeded the number of different letters in that column.

works for the example only - and if it was that easy, it wouldn’t be ratet as ‘hard’ - but as i understand it my result leads to a complete graph for all words.

#23

alright - i thought about it more and - nothing . . .

I’ll need some more thorough description of the task itself to see what i am understanding wrong.

#24

See if the breakdown below may help you some more. It shows how many nodes in total are required with each additional word in the custom case, with the final figure being the same as the expected output:

against       9
always       13
anyone       17
baby         20
budget       23
by           23
charge       27
degree       31
eight        34
energy       37
everyone     39
finger       44
generation   53
get          53
hang         56
history      60
legal        64
light        64
long         64
military     69
myself       73
party        76
tough        80
type         81
worry        83
yeah         85
year         86
yet          86

I’ve also drawn a graph, but it may be too confusing to see anyway… I’ll just show part of it:

d
d1918×980 188 KB

#25

Thanks a ton for your time - at least now i understand, that the letters do not correspond to the Nodes - but to the Links - but still . . .

When I watch the wikipedia-example which is linked in the description:

wikiexample

then I see two things:

  • a node can have multiple letter-links to the same target-node

  • a node can have letter-links and also at the same time a link to the end-node

then I watched your graphic and wanted to ask, why my changed version would not be right (blue arrows):

myway
myway1035×528 252 KB

then I made up an example to ask if this would not also follow from it:

myexample1
myexample1800×243 20.8 KB

then i took the next step - which leads back to what my algorithm does:

myexample2
myexample2800×373 37.7 KB

I you could tell me, what is wrong here - i might get the idea . . .

#27

The blue arrows added to my original graph would mean these words appeared in the list:

agains (because you have a link labelled “END” after the link labelled “s”)
alwa?st (the unlabelled link “?”)
alwa?s (the unlabelled link “?” + new “END” link)
budge (because you have a link labelled “END” after the link labelled “e”)
etc.

But these words were not in the list.

Essentially every path must result in a word in the list.