Word ladder - Rosetta Code

[Jaze]

Where can I find the "unixdict.txt" file?

[bplus]

It is attached to the first post in this thread.

[Jaze]

I skipped by it twice. Finally found it

[david_uwi]

I've removed the duplicates in each list. I have a feeling that I could be accidentally filtering out some genuine ones - I need to check this!
anyway job-->fun 0.33 sec (found 8 solutions - seems to have missed fun, bun,bub,bob, job)
girl-->lady 4.9 sec and the word list goes up as follows 2,18,71,278,756,1394,1716 and comes up with the same sequence as you got. So I'm getting there!

[bplus]

@david_uwi

girl > lady in 4.9 is looking really good, roughly .1 * my time @46.5 secs.
Could you get from alien > drool?

I've exhausted variations on code from first thread, I am going to try a different approach.

[david_uwi]

Yes I got alien --> drool in 49 sec. I'm not sure I've done anything clever, maybe I just hit on a good approach.

At the moment I am trying to work out how to prove that child-->adult is not possible.
I was thinking that the chain of words, when it gets long enough, must start to repeat and I've attempted to write a routine that will look for that. Problem is that I'm up to chains 100 words long and there still seems to be 1000 word chains without repeats.
Maybe I've programmed it wrong!

[bplus]

Yes I got alien --> drool in 49 sec. I'm not sure I've done anything clever, maybe I just hit on a good approach.

At the moment I am trying to work out how to prove that child-->adult is not possible.
I was thinking that the chain of words, when it gets long enough, must start to repeat and I've attempted to write a routine that will look for that. Problem is that I'm up to chains 100 words long and there still seems to be 1000 word chains without repeats.
Maybe I've programmed it wrong!

alien to drool in 49 secs is great! You've certainly programmed something right!

My code is done eg for child to adult when it runs out of connections in my TheList array which is not so different from a stack except I work it off from the front end instead of the back. TheList() array only grows but TheList position index only goes up in looking for connections.

[david_uwi]

The solution just suddenly came to me last evening (while taking a beer!).

Once a word has been used it can be eliminated from all future consideration.
With that insight alien-->drool takes 6 seconds and no path child-->adult is also found in 6 seconds.

Here's the code (it's a bit messy and I've only bothered with the 5 letter words).

Code: QB64: [Select]

1. OPEN "c:\cw1\unixdict.txt" FOR INPUT AS #1
2. 'OPEN "c:\cw1\english3.txt" FOR INPUT AS #1 'bigger dictionary
3. DIM w(10000) AS STRING * 5 'make sure we have enough storage!!
4. DIM q4(10000, 100) AS STRING * 5
5. DIM k1(100)
6. DIM z4(10000, 100) AS STRING
7. tt = TIMER 'include time taken to load to RAM
8.  
9. q1$ = "alien": q2$ = "drool"
10. 'q1$ = "child": q2$ = "adult"
11.  
12. DO UNTIL EOF(1)
13.     INPUT #1, a$
14.     IF LEN(a$) = 5 THEN
15.         k = k + 1
16.         w(k) = a$
17.         IF a$ = q1$ THEN w(k) = "*****"
18.     END IF
19. LOOP
20. CLOSE #1
21. 'tt = TIMER
22. jk = 1
23. k1(jk) = 1
24. q4(1, 1) = q1$
25. DO
26.     FOR i = 1 TO k
27.         cnt = 0
28.         FOR kk = 1 TO k1(jk)
29.             cnt = 0
30.             FOR j = 1 TO 5
31.                 IF MID$(w(i), j, 1) = MID$(q4(kk, jk), j, 1) THEN cnt = cnt + 1 ELSE zz = j
32.             NEXT j
33.             IF cnt = 4 THEN
34.                 k1(jk + 1) = k1(jk + 1) + 1
35.                 q4(k1(jk + 1), jk + 1) = w(i)
36.                 z4(k1(jk + 1), jk + 1) = z4(kk, jk) + MID$(w(i), zz, 1) + CHR$(zz + 48) + " "
37.                 w(i) = "*****"
38.             END IF
39.        20 NEXT kk
40.     NEXT i
41.     kflag = 0
42.     FOR i = 1 TO k1(jk + 1)
43.         IF q4(i, jk + 1) = q2$ THEN kflag = 99: final$ = z4(i, jk + 1)
44.     NEXT i
45.     PRINT
46.     PRINT jk; k1(jk + 1)
47.     IF k1(jk + 1) = 0 THEN kflag = 99
48.     jk = jk + 1
49.     IF kflag = 99 THEN EXIT DO
50. LOOP
51. IF k1(jk) = 0 THEN PRINT: PRINT "No path found!"
52. IF k1(jk) > 0 THEN
53.     xlen = LEN(final$)
54.     PRINT: PRINT q1$; " ";
55.     FOR i = 1 TO xlen STEP 3
56.         c1$ = MID$(final$, i, 1)
57.         c2$ = MID$(final$, i + 1, 1)
58.         MID$(q1$, VAL(c2$), 1) = c1$
59.         PRINT q1$; " ";
60.     NEXT i
61. END IF
62. PRINT: PRINT "time taken = "; TIMER - tt; " seconds"

[bplus]

@david_uwi Really nice time:
 

Why is the _Title I gave it not showing???

Code: QB64: [Select]

1. _Title "Word ladder - RC v david_uwi"
2. ' 2021-09-10 ref https://www.qb64.org/forum/index.php?topic=4157.msg135285#msg135285
3. Open "unixdict.txt" For Input As #1 ' bplus mod path
4. 'OPEN "c:\cw1\english3.txt" FOR INPUT AS #1 'bigger dictionary
5. Dim w(10000) As String * 5 'make sure we have enough storage!!
6. Dim q4(10000, 100) As String * 5
7. Dim k1(100)
8. Dim z4(10000, 100) As String
9. tt = Timer 'include time taken to load to RAM
10.  
11. q1$ = "alien": q2$ = "drool" '  6.70.. secs on bplus system
12. 'q1$ = "child": q2$ = "adult" ' 6.89.. secs on bplus system
13.  
14. Do Until EOF(1)
15.     Input #1, a$
16.     If Len(a$) = 5 Then
17.         k = k + 1
18.         w(k) = a$
19.         If a$ = q1$ Then w(k) = "*****"
20.     End If
21. Loop
22. Close #1
23. 'tt = TIMER
24. jk = 1
25. k1(jk) = 1
26. q4(1, 1) = q1$
27. Do
28.     For i = 1 To k
29.         cnt = 0
30.         For kk = 1 To k1(jk)
31.             cnt = 0
32.             For j = 1 To 5
33.                 If Mid$(w(i), j, 1) = Mid$(q4(kk, jk), j, 1) Then cnt = cnt + 1 Else zz = j
34.             Next j
35.             If cnt = 4 Then
36.                 k1(jk + 1) = k1(jk + 1) + 1
37.                 q4(k1(jk + 1), jk + 1) = w(i)
38.                 z4(k1(jk + 1), jk + 1) = z4(kk, jk) + Mid$(w(i), zz, 1) + Chr$(zz + 48) + " "
39.                 w(i) = "*****"
40.             End If
41.        20 Next kk
42.     Next i
43.     kflag = 0
44.     For i = 1 To k1(jk + 1)
45.         If q4(i, jk + 1) = q2$ Then kflag = 99: final$ = z4(i, jk + 1)
46.     Next i
47.     Print
48.     Print jk; k1(jk + 1)
49.     If k1(jk + 1) = 0 Then kflag = 99
50.     jk = jk + 1
51.     If kflag = 99 Then Exit Do
52. Loop
53. If k1(jk) = 0 Then Print: Print "No path found!"
54. If k1(jk) > 0 Then
55.     xlen = Len(final$)
56.     Print: Print q1$; " ";
57.     For i = 1 To xlen Step 3
58.         c1$ = Mid$(final$, i, 1)
59.         c2$ = Mid$(final$, i + 1, 1)
60.         Mid$(q1$, Val(c2$), 1) = c1$
61.         Print q1$; " ";
62.     Next i
63. End If
64. Print: Print "time taken = "; Timer - tt; " seconds"
65.  
66.  

[bplus]

Weird! Is anyone getting a title for above code?

I was wondering if Windows changed it's rules but _Title is still working in my other Word ladder codes.

[FellippeHeitor]

Setting _TITLE may fail if the command is run before the window has time to be created. As per the wiki, add this to the beginning of your program:

Code: QB64: [Select]

1. DO UNTIL _SCREENEXISTS: LOOP

[bplus]

Thanks @FellippeHeitor  so another race condition with screen load like moving it to _Middle.

[david_uwi]

Should you want to do shorter words here is a bodge.
I've also shaved about a second off the time and as a bit of variety I am searching from Z to A.
I notice that on the "Rosetta Code page" there are no execution times given.
As always it is about the algorithm being efficient and nothing to do with the programming language (despite what the C++ bores would like you to believe).

Code: QB64: [Select]

1. OPEN "c:\cw1\unixdict.txt" FOR INPUT AS #1
2. 'OPEN "c:\cw1\english3.txt" FOR INPUT AS #1 'bigger dictionary
3. DIM w(10000) AS STRING * 5 'make sure we have enough storage!!
4. DIM q4(10000, 100) AS STRING * 5
5. DIM k1(100)
6. DIM z4(10000, 100) AS STRING
7. tt = TIMER 'include time taken to load to RAM
8.  
9. q1$ = "alien": q2$ = "drool"
10. 'q1$ = "child": q2$ = "adult"
11. 'q1$ = "girl": q2$ = "lady"
12. 'q1$ = "john": q2$ = "jane"
13. 'q1$ = "play": q2$ = "ball"
14. n = LEN(q1$)
15. IF n < 5 THEN q1$ = q1$ + SPACE$(5 - n): q2$ = q2$ + SPACE$(5 - n)
16. DO UNTIL EOF(1)
17.     INPUT #1, a$
18.     IF LEN(a$) = n THEN
19.         k = k + 1
20.         w(k) = a$
21.         IF a$ = q1$ THEN w(k) = "*****"
22.     END IF
23. LOOP
24. CLOSE #1
25. 'tt = TIMER
26. jk = 1
27. k1(jk) = 1
28. q4(1, 1) = q1$
29. DO
30.     FOR i = k TO 1 STEP -1
31.         IF w(i) = "*****" THEN 500
32.         cnt = 0
33.         FOR kk = 1 TO k1(jk)
34.             cnt = 0
35.  
36.             FOR j = 1 TO n
37.                 IF MID$(w(i), j, 1) = MID$(q4(kk, jk), j, 1) THEN cnt = cnt + 1 ELSE zz = j
38.             NEXT j
39.             IF cnt = n - 1 THEN
40.                 k1(jk + 1) = k1(jk + 1) + 1
41.                 q4(k1(jk + 1), jk + 1) = w(i)
42.                 z4(k1(jk + 1), jk + 1) = z4(kk, jk) + MID$(w(i), zz, 1) + CHR$(zz + 48) + " "
43.                 w(i) = "*****"
44.             END IF
45.        20 NEXT kk
46.    500 NEXT i
47.     kflag = 0
48.     FOR i = 1 TO k1(jk + 1)
49.         IF q4(i, jk + 1) = q2$ THEN kflag = 99: final$ = z4(i, jk + 1)
50.     NEXT i
51.     PRINT
52.     PRINT jk; k1(jk + 1)
53.     IF k1(jk + 1) = 0 THEN kflag = 99
54.     jk = jk + 1
55.     IF kflag = 99 THEN EXIT DO
56. LOOP
57. IF k1(jk) = 0 THEN PRINT: PRINT "No path found!"
58. IF k1(jk) > 0 THEN
59.     xlen = LEN(final$)
60.     PRINT: PRINT q1$; " ";
61.     FOR i = 1 TO xlen STEP 3
62.         c1$ = MID$(final$, i, 1)
63.         c2$ = MID$(final$, i + 1, 1)
64.         MID$(q1$, VAL(c2$), 1) = c1$
65.         PRINT q1$; " ";
66.     NEXT i
67. END IF
68. PRINT: PRINT "time taken = "; TIMER - tt; " seconds"

[bplus]

running my tests

'                                                     2nd times with 20 removed from my line 49 here
q1$ = "alien": q2$ = "drool" ' 5.21... bplus system  5.11..
'q1$ = "child": q2$ = "adult" ' 5.21... bplus system  4.94..
'q1$ = "girl": q2$ = "lady" '   2.47... bplus system  2.58..
'q1$ = "john": q2$ = "jane" '   1.48... bplus system  1.42..
'q1$ = "play": q2$ = "ball" '   1.97... bplus system  2.08..

Wow another second + off the longest, that's a huge percent at 6.9 or so to start.

I am still trying to figure out Iterating digits squared now I have another to study:
*The 20 on line 45 is artifact from some other test code.
*500 NEXT i     _Continue does not work for you also (maybe I screwed up when I tried) or just old habit? Oh I can check it here!
*I see 2 arrays used to store hit info the word of course but also the letter place they differ.
Well that's from first read through... got to go but hope to figure it out this afternoon for big aha!

[bplus]

Update: _Continue does work in this line (instead of 500)

Code: QB64: [Select]

1. IF w(i) = "*****" THEN 500
2.