Author Topic: Rosetta Code Word Search Challenge  (Read 579 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Forum Resident
  • Posts: 5947
  • B+ Knot again!
Rosetta Code Word Search Challenge
« on: March 13, 2020, 09:25:36 PM »
I think this meets all the criteria
Code: QB64: [Select]
  1. _TITLE "Puzzle Builder for Rosetta" 'by B+ started 2018-10-31
  2. ' 2018-11-02 Now that puzzle is working with basic and plus starters remove them and make sure puzzle works as well.
  3. ' Added Direction legend to printout.
  4. ' OverHauled LengthLimit()
  5. ' Reorgnize this to try a couple of times at given Randomize number
  6. ' TODO create alphabetical copy of word list and check grid for all words embedded in it.
  7. ' LoadWords makes a copy of word list in alpha order
  8. ' FindAllWords finds all the items from the dictionary
  9. ' OK it all seems to be working OK
  10.  
  11. RANDOMIZE TIMER ' OK getting a good puzzle every time
  12.  
  13. 'overhauled
  14. DIM SHARED LengthLimit(3 TO 10) AS _BYTE 'reset in Initialize, track and limit longer words
  15.  
  16. 'LoadWords opens file of words and sets
  17. DIM SHARED NWORDS 'set in LoadWords, number of words with length: > 2 and < 11  and just letters
  18.  
  19. ' word file words (shuffled) to be fit into puzzle and index position
  20. DIM SHARED WORDS$(1 TO 24945), CWORDS$(1 TO 24945), WORDSINDEX AS INTEGER 'the file has 24945 words but many are unsuitable
  21.  
  22. 'words placed in Letters grid, word itself (W$) x, y head (WX, WY) and direction (WD), WI is the index to all these
  23. DIM SHARED W$(1 TO 100), WX(1 TO 100) AS _BYTE, WY(1 TO 100) AS _BYTE, WD(1 TO 100) AS _BYTE, WI AS _BYTE
  24.  
  25. ' letters grid and direction arrays
  26. DIM SHARED L$(0 TO 9, 0 TO 9), DX(0 TO 7) AS _BYTE, DY(0 TO 7) AS _BYTE
  27. DX(0) = 1: DY(0) = 0
  28. DX(1) = 1: DY(1) = 1
  29. DX(2) = 0: DY(2) = 1
  30. DX(3) = -1: DY(3) = 1
  31. DX(4) = -1: DY(4) = 0
  32. DX(5) = -1: DY(5) = -1
  33. DX(6) = 0: DY(6) = -1
  34. DX(7) = 1: DY(7) = -1
  35.  
  36. 'to store all the words found embedded in the grid L$()
  37. DIM SHARED ALL$(1 TO 200), AllX(1 TO 200) AS _BYTE, AllY(1 TO 200) AS _BYTE, AllD(1 TO 200) AS _BYTE 'to store all the words found embedded in the grid L$()
  38. DIM SHARED ALLindex AS INTEGER
  39.  
  40. ' signal successful fill of puzzle
  41. DIM SHARED FILLED AS _BIT
  42. FILLED = 0
  43. try = 1
  44. LoadWords 'this sets NWORDS count to work with
  45. WHILE try < 11
  46.     Initialize
  47.     ShowPuzzle
  48.     FOR WORDSINDEX = 1 TO NWORDS
  49.         PlaceWord
  50.         ShowPuzzle
  51.         IF FILLED THEN EXIT FOR
  52.     NEXT
  53.     IF FILLED AND WI > 24 THEN
  54.         FindAllWords
  55.         FilePuzzle
  56.         LOCATE 23, 1: PRINT "On try #"; Trm$(try); " a successful puzzle was built and filed."
  57.         EXIT WHILE
  58.     ELSE
  59.         try = try + 1
  60.     END IF
  61. IF FILLED = 0 THEN LOCATE 23, 1: PRINT "Sorry, 10 tries and no success."
  62.  
  63. SUB LoadWords
  64.     DIM wd$, i AS INTEGER, m AS INTEGER, ok AS _BIT
  65.     OPEN "unixdict.txt" FOR INPUT AS #1
  66.     WHILE EOF(1) = 0
  67.         INPUT #1, wd$
  68.         IF LEN(wd$) > 2 AND LEN(wd$) < 11 THEN
  69.             ok = -1
  70.             FOR m = 1 TO LEN(wd$)
  71.                 IF ASC(wd$, m) < 97 OR ASC(wd$, m) > 122 THEN ok = 0: EXIT FOR
  72.             NEXT
  73.             IF ok THEN i = i + 1: WORDS$(i) = wd$: CWORDS$(i) = wd$
  74.         END IF
  75.     WEND
  76.     CLOSE #1
  77.     NWORDS = i
  78.  
  79. SUB Shuffle
  80.     DIM i AS INTEGER, r AS INTEGER
  81.     FOR i = NWORDS TO 2 STEP -1
  82.         r = INT(RND * i) + 1
  83.         SWAP WORDS$(i), WORDS$(r)
  84.     NEXT
  85.  
  86. SUB Initialize
  87.     DIM r AS _BYTE, c AS _BYTE, x AS _BYTE, y AS _BYTE, d AS _BYTE, wd$
  88.     FOR r = 0 TO 9
  89.         FOR c = 0 TO 9
  90.             L$(c, r) = " "
  91.         NEXT
  92.     NEXT
  93.  
  94.     'reset word arrays by resetting the word index back to zero
  95.     WI = 0
  96.  
  97.     'fun stuff for me but doubt others would like that much fun!
  98.     'pluggin "basic", 0, 0, 2
  99.     'pluggin "plus", 1, 0, 0
  100.  
  101.     'to assure the spreading of ROSETTA CODE
  102.     L$(INT(RND * 5) + 5, 0) = "R": L$(INT(RND * 9) + 1, 1) = "O"
  103.     L$(INT(RND * 9) + 1, 2) = "S": L$(INT(RND * 9) + 1, 3) = "E"
  104.     L$(1, 4) = "T": L$(9, 4) = "T": L$(INT(10 * RND), 5) = "A"
  105.     L$(INT(10 * RND), 6) = "C": L$(INT(10 * RND), 7) = "O"
  106.     L$(INT(10 * RND), 8) = "D": L$(INT(10 * RND), 9) = "E"
  107.  
  108.     'reset limits
  109.     LengthLimit(3) = 200
  110.     LengthLimit(4) = 6
  111.     LengthLimit(5) = 3
  112.     LengthLimit(6) = 2
  113.     LengthLimit(7) = 1
  114.     LengthLimit(8) = 0
  115.     LengthLimit(9) = 0
  116.     LengthLimit(10) = 0
  117.  
  118.     'reset word order
  119.     Shuffle
  120.  
  121. 'for fun plug-in of words
  122. SUB pluggin (wd$, x AS INTEGER, y AS INTEGER, d AS INTEGER)
  123.     DIM i AS _BYTE
  124.     FOR i = 0 TO LEN(wd$) - 1
  125.         L$(x + i * DX(d), y + i * DY(d)) = MID$(wd$, i + 1, 1)
  126.     NEXT
  127.     WI = WI + 1
  128.     W$(WI) = wd$: WX(WI) = x: WY(WI) = y: WD(WI) = d
  129.  
  130.     Trm$ = RTRIM$(LTRIM$(STR$(n)))
  131.  
  132. SUB ShowPuzzle
  133.     DIM i AS _BYTE, x AS _BYTE, y AS _BYTE, wate$
  134.     CLS
  135.     PRINT "    0 1 2 3 4 5 6 7 8 9"
  136.     LOCATE 3, 1
  137.     FOR i = 0 TO 9
  138.         PRINT Trm$(i)
  139.     NEXT
  140.     FOR y = 0 TO 9
  141.         FOR x = 0 TO 9
  142.             LOCATE y + 3, 2 * x + 5: PRINT L$(x, y)
  143.         NEXT
  144.     NEXT
  145.     FOR i = 1 TO WI
  146.         IF i < 20 THEN
  147.             LOCATE i + 1, 30: PRINT Trm$(i); " "; W$(i)
  148.         ELSEIF i < 40 THEN
  149.             LOCATE i - 20 + 1, 45: PRINT Trm$(i); " "; W$(i)
  150.         ELSEIF i < 60 THEN
  151.             LOCATE i - 40 + 1, 60: PRINT Trm$(i); " "; W$(i)
  152.         END IF
  153.     NEXT
  154.     LOCATE 18, 1: PRINT "Spaces left:"; CountSpaces%
  155.     LOCATE 19, 1: PRINT NWORDS
  156.     LOCATE 20, 1: PRINT SPACE$(16)
  157.     IF WORDSINDEX THEN LOCATE 20, 1: PRINT Trm$(WORDSINDEX); " "; WORDS$(WORDSINDEX)
  158.     'LOCATE 15, 1: INPUT "OK, press enter... "; wate$
  159.  
  160. 'used in PlaceWord
  161. FUNCTION CountSpaces% ()
  162.     DIM x AS _BYTE, y AS _BYTE, count AS INTEGER
  163.     FOR y = 0 TO 9
  164.         FOR x = 0 TO 9
  165.             IF L$(x, y) = " " THEN count = count + 1
  166.         NEXT
  167.     NEXT
  168.     CountSpaces% = count
  169.  
  170. 'used in PlaceWord
  171. FUNCTION Match% (word AS STRING, template AS STRING)
  172.     DIM i AS INTEGER, c AS STRING
  173.     Match% = 0
  174.     IF LEN(word) <> LEN(template) THEN EXIT FUNCTION
  175.     FOR i = 1 TO LEN(template)
  176.         IF ASC(template, i) <> 32 AND (ASC(word, i) <> ASC(template, i)) THEN EXIT FUNCTION
  177.     NEXT
  178.     Match% = -1
  179.  
  180. 'heart of puzzle builder
  181. SUB PlaceWord
  182.     ' place the words randomly in the grid
  183.     ' start at random spot and work forward or back 100 times = all the squares
  184.     ' for each open square try the 8 directions for placing the word
  185.     ' even if word fits Rossetta Challenge task requires leaving 11 openings to insert ROSETTA CODE,
  186.     ' exactly 11 spaces needs to be left, if/when this occurs FILLED will be set true to signal finished to main loop
  187.     ' if place a word update L$, WI, W$(WI), WX(WI), WY(WI), WD(WI)
  188.  
  189.     DIM wd$, wLen AS _BYTE, spot AS _BYTE, testNum AS _BYTE, rdir AS _BYTE
  190.     DIM x AS _BYTE, y AS _BYTE, d AS _BYTE, dNum AS _BYTE, rdd AS _BYTE
  191.     DIM template$, b1 AS _BIT, b2 AS _BIT
  192.     DIM i AS _BYTE, j AS _BYTE, wate$
  193.  
  194.     wd$ = WORDS$(WORDSINDEX) 'the right side is all shared
  195.     'skip too many long words
  196.     IF LengthLimit(LEN(wd$)) THEN LengthLimit(LEN(wd$)) = LengthLimit(LEN(wd$)) - 1 ELSE EXIT SUB 'skip long ones
  197.     wLen = LEN(wd$) - 1 '     from the spot there are this many letters to check
  198.     spot = INT(RND * 100) '   a random spot on grid
  199.     testNum = 1 '             when this hits 100 we've tested all possible spots on grid
  200.     IF RND < .5 THEN rdir = -1 ELSE rdir = 1 ' go forward or back from spot for next test
  201.     WHILE testNum < 101
  202.         y = INT(spot / 10)
  203.         x = spot MOD 10
  204.         IF L$(x, y) = MID$(wd$, 1, 1) OR L$(x, y) = " " THEN
  205.             d = INT(8 * RND)
  206.             IF RND < .5 THEN rdd = -1 ELSE rdd = 1
  207.             dNum = 1
  208.             WHILE dNum < 9
  209.                 'will wd$ fit? from  at x, y
  210.                 template$ = ""
  211.                 b1 = wLen * DX(d) + x >= 0 AND wLen * DX(d) + x <= 9
  212.                 b2 = wLen * DY(d) + y >= 0 AND wLen * DY(d) + y <= 9
  213.                 IF b1 AND b2 THEN 'build the template of letters and spaces from Letter grid
  214.                     FOR i = 0 TO wLen
  215.                         template$ = template$ + L$(x + i * DX(d), y + i * DY(d))
  216.                     NEXT
  217.                     IF Match%(wd$, template$) THEN 'the word will fit but does it fill anything?
  218.                         FOR j = 1 TO LEN(template$)
  219.                             IF ASC(template$, j) = 32 THEN 'yes a space to fill
  220.                                 FOR i = 0 TO wLen
  221.                                     L$(x + i * DX(d), y + i * DY(d)) = MID$(wd$, i + 1, 1)
  222.                                 NEXT
  223.                                 WI = WI + 1
  224.                                 W$(WI) = wd$: WX(WI) = x: WY(WI) = y: WD(WI) = d
  225.                                 IF CountSpaces% = 0 THEN FILLED = -1
  226.                                 EXIT SUB 'get out now that word is loaded
  227.                             END IF
  228.                         NEXT
  229.                         'if still here keep looking
  230.                     END IF
  231.                 END IF
  232.                 d = (d + 8 + rdd) MOD 8
  233.                 dNum = dNum + 1
  234.             WEND
  235.         END IF
  236.         spot = (spot + 100 + rdir) MOD 100
  237.         testNum = testNum + 1
  238.     WEND
  239.  
  240. SUB FindAllWords
  241.     DIM wd$, wLen AS _BYTE, i AS INTEGER, x AS _BYTE, y AS _BYTE, d AS _BYTE
  242.     DIM template$, b1 AS _BIT, b2 AS _BIT, j AS _BYTE, wate$
  243.  
  244.     FOR i = 1 TO NWORDS
  245.         wd$ = CWORDS$(i)
  246.         wLen = LEN(wd$) - 1
  247.         FOR y = 0 TO 9
  248.             FOR x = 0 TO 9
  249.                 IF L$(x, y) = MID$(wd$, 1, 1) THEN
  250.                     FOR d = 0 TO 7
  251.                         b1 = wLen * DX(d) + x >= 0 AND wLen * DX(d) + x <= 9
  252.                         b2 = wLen * DY(d) + y >= 0 AND wLen * DY(d) + y <= 9
  253.                         IF b1 AND b2 THEN 'build the template of letters and spaces from Letter grid
  254.                             template$ = ""
  255.                             FOR j = 0 TO wLen
  256.                                 template$ = template$ + L$(x + j * DX(d), y + j * DY(d))
  257.                             NEXT
  258.                             IF template$ = wd$ THEN 'founda word
  259.                                 'store it
  260.                                 ALLindex = ALLindex + 1
  261.                                 ALL$(ALLindex) = wd$: AllX(ALLindex) = x: AllY(ALLindex) = y: AllD(ALLindex) = d
  262.                                 'report it
  263.                                 LOCATE 22, 1: PRINT SPACE$(50)
  264.                                 LOCATE 22, 1: PRINT "Found: "; wd$; " ("; Trm$(x); ", "; Trm$(y); ") >>>---> "; Trm$(d);
  265.                                 INPUT " Press enter...", wate$
  266.                             END IF
  267.                         END IF
  268.                     NEXT d
  269.                 END IF
  270.             NEXT x
  271.         NEXT y
  272.     NEXT i
  273.  
  274. SUB FilePuzzle
  275.     DIM i AS _BYTE, r AS _BYTE, c AS _BYTE, b$
  276.     OPEN "WS Puzzle.txt" FOR OUTPUT AS #1
  277.     PRINT #1, "    0 1 2 3 4 5 6 7 8 9"
  278.     PRINT #1, ""
  279.     FOR r = 0 TO 9
  280.         b$ = Trm$(r) + "   "
  281.         FOR c = 0 TO 9
  282.             b$ = b$ + L$(c, r) + " "
  283.         NEXT
  284.         PRINT #1, b$
  285.     NEXT
  286.     PRINT #1, ""
  287.     PRINT #1, "Directions >>>---> 0 = East, 1 = SE, 2 = South, 3 = SW, 4 = West, 5 = NW, 6 = North, 7 = NE"
  288.     PRINT #1, ""
  289.     PRINT #1, "              These are the items from unixdict.txt used to build the puzzle:"
  290.     PRINT #1, ""
  291.     FOR i = 1 TO WI STEP 2
  292.         PRINT #1, RIGHT$(SPACE$(7) + Trm$(i), 7); ") "; RIGHT$(SPACE$(7) + W$(i), 10); " ("; Trm$(WX(i)); ", "; Trm$(WY(i)); ") >>>---> "; Trm$(WD(i));
  293.         IF i + 1 <= WI THEN
  294.             PRINT #1, RIGHT$(SPACE$(7) + Trm$(i + 1), 7); ") "; RIGHT$(SPACE$(7) + W$(i + 1), 10); " ("; Trm$(WX(i + 1)); ", "; Trm$(WY(i + 1)); ") >>>---> "; Trm$(WD(i + 1))
  295.         ELSE
  296.             PRINT #1, ""
  297.         END IF
  298.     NEXT
  299.     PRINT #1, ""
  300.     PRINT #1, "            These are the items from unixdict.txt found embedded in the puzzle:"
  301.     PRINT #1, ""
  302.     FOR i = 1 TO ALLindex STEP 2
  303.         PRINT #1, RIGHT$(SPACE$(7) + Trm$(i), 7); ") "; RIGHT$(SPACE$(7) + ALL$(i), 10); " ("; Trm$(AllX(i)); ", "; Trm$(AllY(i)); ") >>>---> "; Trm$(AllD(i));
  304.         IF i + 1 <= ALLindex THEN
  305.             PRINT #1, RIGHT$(SPACE$(7) + Trm$(i + 1), 7); ") "; RIGHT$(SPACE$(7) + ALL$(i + 1), 10); " ("; Trm$(AllX(i + 1)); ", "; Trm$(AllY(i + 1)); ") >>>---> "; Trm$(AllD(i + 1))
  306.         ELSE
  307.             PRINT #1, ""
  308.         END IF
  309.     NEXT
  310.     CLOSE #1
  311.  
  312.  

Sample Outout txt file:
Quote
    0 1 2 3 4 5 6 7 8 9

0   t g a m m R l b a r
1   o e O k y u i l u b
2   l S e e n n i o a t
3   s a g d E u i d e w
4   k T c t e h g s a T
5   s e n o j b o A e r
6   C l g n c o a p g r
7   l i o d i u m u e O
8   k a e r f D d y c t
9   t j E a i d r a p h

Directions >>>---> 0 = East, 1 = SE, 2 = South, 3 = SW, 4 = West, 5 = NW, 6 = North, 7 = NE

              These are the items from unixdict.txt used to build the puzzle:

      1)      odium (2, 7) >>>---> 0      2)     resiny (9, 6) >>>---> 5
      3)    debauch (3, 3) >>>---> 1      4)      freak (4, 8) >>>---> 4
      5)      jones (4, 5) >>>---> 4      6)     radium (9, 5) >>>---> 5
      7)       hope (5, 4) >>>---> 1      8)       coca (4, 6) >>>---> 5
      9)       slot (0, 3) >>>---> 6     10)        aid (3, 9) >>>---> 0
     11)       gunk (6, 4) >>>---> 5     12)        keg (0, 4) >>>---> 1
     13)       aile (1, 8) >>>---> 6     14)        set (7, 4) >>>---> 7
     15)       wall (9, 3) >>>---> 5     16)        rye (6, 9) >>>---> 7
     17)        our (7, 2) >>>---> 7     18)        bar (7, 0) >>>---> 0
     19)        par (8, 9) >>>---> 4     20)        gam (1, 0) >>>---> 0
     21)        dee (3, 3) >>>---> 5     22)        ton (3, 4) >>>---> 2
     23)        dab (7, 3) >>>---> 7     24)        jed (1, 9) >>>---> 7
     25)        bin (7, 0) >>>---> 3     26)        pet (7, 6) >>>---> 1
     27)        sag (0, 3) >>>---> 0     28)        nco (3, 6) >>>---> 0
     29)        dug (6, 8) >>>---> 7     30)        oat (2, 7) >>>---> 3
     31)        oil (2, 7) >>>---> 4     32)        nee (4, 2) >>>---> 4

            These are the items from unixdict.txt found embedded in the puzzle:

      1)        abe (6, 6) >>>---> 5      2)       abed (6, 6) >>>---> 5
      3)        aid (3, 9) >>>---> 0      4)        ail (1, 8) >>>---> 6
      5)       aile (1, 8) >>>---> 6      6)        ali (8, 0) >>>---> 3
      7)        all (8, 2) >>>---> 5      8)        bad (9, 1) >>>---> 3
      9)        bar (7, 0) >>>---> 0     10)        bed (5, 5) >>>---> 5
     11)        bin (7, 0) >>>---> 3     12)        but (7, 0) >>>---> 1
     13)        cal (2, 4) >>>---> 5     14)       coca (4, 6) >>>---> 5
     15)        cud (4, 6) >>>---> 1     16)        dab (7, 3) >>>---> 7
     17)        dar (7, 3) >>>---> 1     18)    debauch (3, 3) >>>---> 1
     19)        dee (3, 3) >>>---> 5     20)        dew (7, 3) >>>---> 0
     21)        dug (6, 8) >>>---> 7     22)        edt (3, 2) >>>---> 2
     23)        eli (1, 5) >>>---> 2     24)        etc (4, 4) >>>---> 4
     25)      freak (4, 8) >>>---> 4     26)        gam (1, 0) >>>---> 0
     27)        gas (2, 3) >>>---> 4     28)        goa (6, 4) >>>---> 2
     29)        gsa (6, 4) >>>---> 0     30)        gun (6, 4) >>>---> 5
     31)       gunk (6, 4) >>>---> 5     32)        hop (5, 4) >>>---> 1
     33)       hope (5, 4) >>>---> 1     34)        hun (5, 4) >>>---> 6
     35)        ida (6, 2) >>>---> 1     36)        iii (6, 1) >>>---> 2
     37)        iii (6, 3) >>>---> 6     38)        inn (6, 2) >>>---> 4
     39)        inn (4, 7) >>>---> 5     40)       jail (1, 9) >>>---> 6
     41)        jed (1, 9) >>>---> 7     42)        jon (4, 5) >>>---> 4
     43)      jones (4, 5) >>>---> 4     44)        keg (0, 4) >>>---> 1
     45)        lac (0, 2) >>>---> 1     46)        law (7, 1) >>>---> 1
     47)        lea (0, 2) >>>---> 7     48)        lot (0, 2) >>>---> 6
     49)       lund (6, 0) >>>---> 3     50)        mao (6, 7) >>>---> 6
     51)        nco (3, 6) >>>---> 0     52)        nee (4, 2) >>>---> 4
     53)        nib (5, 2) >>>---> 7     54)        nne (5, 2) >>>---> 4
     55)        not (3, 6) >>>---> 6     56)        oat (7, 2) >>>---> 0
     57)        oat (2, 7) >>>---> 3     58)      odium (2, 7) >>>---> 0
     59)        oil (2, 7) >>>---> 4     60)        one (3, 5) >>>---> 4
     61)        our (7, 2) >>>---> 7     62)        par (8, 9) >>>---> 4
     63)        pet (7, 6) >>>---> 1     64)     radium (9, 5) >>>---> 5
     65)        rap (6, 9) >>>---> 0     66)      resin (9, 6) >>>---> 5
     67)     resiny (9, 6) >>>---> 5     68)        rio (3, 8) >>>---> 7
     69)        rye (6, 9) >>>---> 7     70)        sag (0, 3) >>>---> 0
     71)        sen (0, 5) >>>---> 0     72)        set (7, 4) >>>---> 7
     73)        sin (7, 4) >>>---> 5     74)       slot (0, 3) >>>---> 6
     75)        tao (9, 2) >>>---> 4     76)        tao (0, 9) >>>---> 7
     77)        tee (0, 0) >>>---> 1     78)        ton (3, 4) >>>---> 2
     79)        tub (9, 2) >>>---> 5     80)       wall (9, 3) >>>---> 5
     81)        wed (9, 3) >>>---> 4


Attached in zip is needed Unix dictionary and a QB64 words mod for fun! and some samples.

 


« Last Edit: March 13, 2020, 09:31:23 PM by bplus »

Offline bplus

  • Forum Resident
  • Posts: 5947
  • B+ Knot again!
Re: Rosetta Code Word Search Challenge
« Reply #1 on: March 13, 2020, 10:16:22 PM »
Hey still time to be first real Basic in Word Search Challenge:
http://rosettacode.org/wiki/Word_search

Offline CBTJD

  • Newbie
  • Posts: 80
  • You're only as old as you feel. ...I'm screwed.
Re: Rosetta Code Word Search Challenge
« Reply #2 on: March 13, 2020, 10:24:04 PM »
Ha! Exactly. 'Cuz VB .NOT don't count!
:@)
CBTJD: Coding BASIC Takes Judicious Dedication