Wordle Solver

[christosangelopoulos]

Now anyone can boast they are great in Wordle:
https://gitlab.com/christosangel/wordle-solver
If you prefer using just one line in terminal:

Code: Select all

FGE1="grep -E \"^.....$\"";for try in {1..6};do F1="$FGE1""$FGVE1""$CR1""$MSPL1""$AB1";db="c";while [[ $db = "c" ]];do w=$(look .| eval $F1|grep -v "'"|shuf|head -1);echo "Enter word: "\"$w\";read -p "Or press c for another word:" db;done; for i in {0..4};do GE1[$i]="";for ii in {0..4};do if [ $ii -eq $i ];then X="${w:i:1}";else X=".";fi;GE1[$i]=${GE1[$i]}"$X";done;echo -e "${w:i:1} is \n 1.Correct \n 2.Misplaced\n 3.Absent\n 4.Quit ";read -p "Select : " l[$i];case ${l[$i]} in 1) CR+=("${w:i:1}");WORD[$i]=${w:i:1};GE1[$i]="grep -E \"${GE1[$i]}\"";FGE1+=\|${GE1[$i]};;2) MSPL+=("${w:i:1}");GVE1[$i]="grep -vE \"${GE1[$i]}\"";FGVE1+=\|${GVE1[$i]};;3) AB+=("${w:i:1}");;4)exit;;esac;done;for c in "${CR[@]}";do CR1=$CR1"|grep "$c;done;for m in "${MSPL[@]}";do MSPL1=$MSPL1"|grep "$m;done;for a in "${AB[@]}";do AB1=$AB1"|grep -v "$a;done;done

Have fun!

[rene]

Your GitLab link is to a project settings page...

[christosangelopoulos]

Your GitLab link is to a project settings page...

Thank you for the correction, I have posted the right link to the script.
https://gitlab.com/christosangel/wordle-solver

[rene]

Just in case you'd like feedback...

Given that I needed to first find out what "a wordle" was even I'll not comment too thoroughly but I did just notice that I was in the sequence DELIS, DEMUR, DECAY, DEPTH every turn re-asked if the D and E were correct/misplaced etc even though I already indicated they were correct in the first turn. Maybe it's a fun suggestion to expand the script so that it remembers what it has asked and doesn't ask the same question again.

It's otherwise probably a strategy to have the script suggest 5 letter words with as many as of yet unused letters as possible, or even better, with on the as of yet unconfirmed places a/the word with the most often used letters from the set of words that still fit. This sounds like it would probably be non-trivial to implement...

As said; just in case you appreciate the feedback

[christosangelopoulos]

It goes without saying that I do appreciate the feedback.
It seems that we more ore less share the same experience with the term "wordle". I had no idea what it was a few days ago, however it seems like a legit concept of a riddle.
I appreciate the feedback of the repeating question of correct letters. I will try to implement this feedback to the script, it should't be this hard. If I do, I will update the gitlab script, and post in this forum, to let you know.
The other two points you made (about using the most frequent letters, and using as many as unused letters as possible) are also legit, and the script could use some fine tuning accordingly.
There is also another issue that has to do with duplicate letters. If the first occurence of a letter is correct, the user should not mark the second occurence as absent, that would lead to an error. This is also an issue to address.
Other useful issues to address would be an option to present the list of alternative words, to let you when you have reached the final solution etc.
However, even with the issues described above, the script can be trusted to solve the riddle. The inspiration was a one-liner as described in this tweet:
https://twitter.com/climagic/status/1496137368075743242
And to be frank, my goal was not only to create a script to solve the riddle, but also, like the author of the above tweet, to create a respective one line command that does the same thing. This is why not only I did not include many things, but also, I tried to keep everything at a minimum, while keeping the one-liner fuctioning at the same time.
Again, many thanks for the feedback, it is most certainly appreciated !

[christosangelopoulos]

... I did just notice that I was in the sequence DELIS, DEMUR, DECAY, DEPTH every turn re-asked if the D and E were correct/misplaced etc even though I already indicated they were correct in the first turn. Maybe it's a fun suggestion to expand the script so that it remembers what it has asked and doesn't ask the same question again.

This issue is now fixed, and the script updated: Once a letter is declared correct, the player will not be asked again.

[christosangelopoulos]

It's otherwise probably a strategy to have the script suggest 5 letter words with as many as of yet unused letters as possible, or even better, with on the as of yet unconfirmed places a/the word with the most often used letters from the set of words that still fit. This sounds like it would probably be non-trivial to implement...

I have also fixed a bug that crashed the script when there were double entries in the absent letters.
As far as the word selection according to double letters and/or frequent instances of letters is concerned: I think I might permit the selection of words without any double letter instances/with more frequent letters in the first 1? 2? 3? turns. This is doable.
However, I believe the best way to go would be to use the option to reshuffle the word, if it is not admitted by the game, or if it doesn't fit the users criteria.
Criteria that in their turn, are quite subjective. Strategy itself, any user's "style" is after all subjective.
So, if the script proposes a word, and this particular word doesn't feel right to a user, this user can enter c, reshuffle, and select another word.
Feel free to chime in!

[rene]

Not behind a system now so haven't seen the update in action yet, but sounds good.

As to solver-algorith; what I was was sort of thinking of is that you with, say, letters 2 and 4 known construct a list of words with those letters at 2 and 4 and from it as the next suggestion pick that word from the list with N1+N3+N5 highest, in which Nx is the number of times that letter <x> from that word appears in the list as letter <x> in all words from the list.

Hope I said that right. Probably not optimal, but sounds fun. Might also be implementable recursively: once you have 1 letter of a 5-letter "wordle" you're after all just basically starting over on a 4-letter one and so on.

Never mind if that's not the kind of thing you enjoy; don't want to spoil the fun

[christosangelopoulos]

Basically the logic behind the whole thing is to gather each piece of information about the word, and create a pipe of grep commands. So if we know that the trird letter is a "d", that information is transformed in a grep -E "..d..". if we know that there is no "s", we pipe the outcome to grev -v s, and so on and so forth.
on each turn, more info is gathered, and added in a super string that gets evaled. The order of the grep commands in the pipe is not important, but starting from all the words, on each command of the pipe, some get left out, until we have the solution.
I have also found out that strategy is not really an issue : the grep commands are doing their work, no matter the selection of words, one does find the solution in the end.
However, the processing of all this info was/is a bit challenging, and I admit that now that I have somehow taken under consideration the position of the correct letters, through arrays, I feel more comfortable.
Well, I am glad to inform you that I further updated the logic of the script, and I added some more options that hopefully will please the more demanding users: a menu through which the player can enter their preferd word, with protection as far as word length is concerned, an option to print all possible solutions, a word count display of all possible words, that detects when we have solved succesfully the riddle.
The link remains the same, I even threw in a wee png.
I had great fun with this little script.
Always feel free to give your feedback!

[christosangelopoulos]

As to solver-algorith; what I was was sort of thinking of is that you with, say, letters 2 and 4 known construct a list of words with those letters at 2 and 4 and from it as the next suggestion pick that word from the list with N1+N3+N5 highest, in which Nx is the number of times that letter <x> from that word appears in the list as letter <x> in all words from the list.

Towards this idea of most frequent letters, hence more probable words, I was thinking this:

Code: Select all

t=$(echo $(look .)|sed "s/ //g;s/'//g;s/\(.*\)/\L\1/");tlength=${#t}; echo "length  " $tlength;for i in {a..z}; do echo $i $(tr -dc $i <<<"$t" | wc -c) >>frec.txt;done;awk '{print $2, $1}' frec.txt|sort -nr

The result of this is :
94661 s
91292 e
68740 i
67130 a
59142 r
58947 n
54237 t
50648 o
42488 l
32808 c
29302 d
26929 u
23371 g
23282 m
22758 p
20264 h
16159 b
13058 y
10926 f
8872 k
8228 v
7822 w
3427 z
2185 x
2046 j
1574 q
which can be transformed in an associative array that associates each letter with its frequency of occurence in all words, with s the most and q the least frequent...

[rene]

When I google "wordle solver algorithm" I see this is "a thing" on the internet and that many implementations are available, with a top hit for me being e.g. https://www.youtube.com/watch?v=bVTcQtEnOlk, i.e., an implementation in MATLAB and by a MathWorks employee with "a 99.6% success rate with an average of 3.5 guesses". I'll not personally try and best the algorithms out there already -- since I'm quite sure I wouldn't... -- so will I guess as to algorithm leave it at that.

One thing to still comment on perhaps is that I'm not sure that I'd like those greps. I'd personally likely start of with reading in the word list into an internal array and then work on that only (deleting entries from the array that prove impossible as per the feedback each turn, and from that ever shrinking words-array then select the best guess, such as per suggestions from any of those existing implementations). Just in case you'd agree with / like that, you can read in all 5-letter words consisting of letters only into an array words with

Code: Select all

mapfile -t words < <(sed -n '/^[A-Za-z]\{5\}$/p' /usr/share/dict/words)

I'll as said myself not start trying to best those out there already -- but fun project.

[christosangelopoulos]

When I google "wordle solver algorithm" I see this is "a thing" on the internet and that many implementations are available, with a top hit for me being e.g. https://www.youtube.com/watch?v=bVTcQtEnOlk, i.e., an implementation in MATLAB and by a MathWorks employee with "a 99.6% success rate with an average of 3.5 guesses". I'll not personally try and best the algorithms out there already -- since I'm quite sure I wouldn't... -- so will I guess as to algorithm leave it at that.

Wow, I didn't know this was trully a thing. It seems like I have managed to keep away from the "play wordle" trend, and fallen for the "write a wordle solver routine" meta-trend. I didn't even know what MATLAB was...
I am not sure what my script's stats are. And to be frank I am not sure I want to go down this rabbit hole...I think I am pretty pleased with the way it works.
Especially now that I have added box lines and bold characters, not just the logic!

One thing to still comment on perhaps is that I'm not sure that I'd like those greps. I'd personally likely start of with reading in the word list into an internal array and then work on that only (deleting entries from the array that prove impossible as per the feedback each turn, and from that ever shrinking words-array then select the best guess, such as per suggestions from any of those existing implementations).

That is sort of what I am doing with grep. Greps generated and piped in series. Surely I am not creating an array, I need some time to think on what you are talking about, and how to implement it. Still, I see no particular gain in reinventing the wheel.Grep works just fine, it is there just for that, fast and eficient enough.

Thinking again over the more /less frequent letters in all the words etc, I am not sure one would not shoot themselves in the foot opting for using the more frequent letters. What is a difficult word? I think it is about using fewer letters in the word (teepee perhaps?), combined with using less frequent letters (example "quaff").
So if someone as a question of strategy, opts for more frequent letters, will end up at a later turn to the right conclusion.Also important is I think to know "who" you are playing with, what is the routine that decides which words to put.
Anyway, I would be interested for your feedback after today's changes!
It sure has been great fun so far!

[christosangelopoulos]

... an implementation in MATLAB and by a MathWorks employee with "a 99.6% success rate with an average of 3.5 guesses".

It turns out that I do have statistics about the eficiency of this script.
The page I use to practice the eficiency of the script from the start https://wordlegame.org/
keeps score of my games.
Unfortunately it draws a worse image of my game, because these games were played during the debugging period(the last three days).
Still, I might say,

things don't look bad at all
Especially taking into account that for the last 36 games we had straight success.
Even through the testing period, 97% success, for a 100 line bash script, especially compared to the MATLAB implementation, makes me smile!
I will appreciate anyone who would report any crashing or malfunction!

[rene]

If you are -- as I am -- only interested in something like this from a fundamental algorithmic viewpoint then the issue is that something like grep doesn't legitimately count as just one step; it is itself an involved general-purpose tool using quite a few steps to get you your one result. Now admittedly this forum section is named "Scripts & Bash" and not "Algorithms & Asperger's Syndrome" so your viewpoint may be fair enough -- but for me then it doesn't really work: I'd want to go down to basics.

And, yes, the thing as to shooting oneself in the foot is the reason I must say I've lost interest a bit; that linked YouTube video describes an algorithm where he assigns 0=absent, 1=misplaced, 2=correct and therefore has with 5 letters 3^5=243 possible numerical feedback scores to any given try. He then simply generates a matrix with said feedback score for every word from the list tested against also every word from the list and then in each turn picks that still as per the feedback possible word which has the flattest feedback-score distribution against all other still possible words, i.e., so as to minimize the number of words in each individual feedback score's bucket, i.e., to with highest chance delete as many still possible words per turn as possible.

Details there, but what this is then basically to say that it's a "statistical solution" which for again me tends to equates to non-fundamental or at least non-insightful. At the same time statistical solutions by virtue of auto-adapting to actual reality tend to be extremely hard to beat with smarts, so, wah, blah, yah, fun's over...

Your current version is nice. I'll keep https://www.nytimes.com/games/wordle/index.html bookmarked for a bit -- although to be honest I'm also finding the game to a bit dull in the first place

[christosangelopoulos]

I am glad you find the latest version nice, and many many thanks for the feedback.
The game itself supposedly tests one's vocabulary richness, as well as their ability to work within this vocabulary.
It seemed like a challenge for me to write up something like this.
This script was a fun project, a cheeky way to show off to my friends, and at the same time an opportunity to learn a few things about the powerful grep command. And I hope other people have fun while using it!

[FreedomTruth]

Not a "solver" but (a variation on) the game itself, to be run in terminal window. It's not perfect but I've stopped working on it, it's good enough for me to play on my own system occasionally

Code: Select all

#!/bin/bash

if [ ! -z "$1" ]; then
  # make sure $1 is an integer ...
  ntest=$(expr $1 + 1 >/dev/null 2>&1; echo $?)
  if [ $ntest -ne 0 ]; then
    echo "Invalid: $1"
    wordlength=5
  else
    if [ $1 -lt 5 -o $1 -gt 12 ]; then
      echo "Invalid word length: $1"
      wordlength=5
    fi
    wordlength=$1
  fi
else
  wordlength=5
fi

listfile=$HOME/.config/words.list.$wordlength
statfile=$HOME/.config/words.statistics

if [ ! -f $listfile ]; then
  echo -n "Building word list..."
  case "$wordlength" in
    5)
      grep ^[a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    6)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    7)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    8)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    9)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    10)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    11)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    12)
      grep ^[a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z]$ /usr/share/dict/words > $listfile
      ;;
    *)
      echo "Invalid word length: $wordlength"
      exit 0
      ;;
  esac
  echo " done."
fi
wtotal=$(wc -l < $listfile)

# generate "pseudorandom" number
prline=$(xxd -g 0 -l 4 /dev/random | cut -d ' ' -f 2 | tr [a-f] [0-5] | cut -c 2,4,6,7)
if [ $(expr $(date '+%N') % 2) -eq 1 ]; then
  prline=$(expr $prline + 10000)
fi
while [ $prline -gt $wtotal -o $prline -eq 0 ]; do
  prline=$(xxd -g 0 -l 4 /dev/random | cut -d ' ' -f 2 | tr [a-f] [0-5] | cut -c 2,4,6,7)
  if [ $(expr $(date '+%N') % 2) -eq 1 ]; then
    prline=$(expr $prline + 10000)
  fi
done

rword=$(readline $prline $listfile | tr [A-Z] [a-z])
if [ -z "$rword" ]; then
  exec $0 $*
fi

yellow="\033[01;33m"
white="\033[00m"
green="\033[01;32m"
red="\033[01;31m"

att=1
ltab1=(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
ltab2=(a b c d e f g h i j k l m n o p q r s t u v w x y z)

echo "A "$wordlength"-letter word has been selected. Try to guess it!  Enter \"QUIT\" to give up."

# start the timer
tstart=$(date '+%Y 3153600 * %j 1 - 86400 * + %H 3600 * + %M 60 * + %S.%N +')
while [ $att -lt 11 ]; do
  read -p "Guess $att: " tword
  tword="$(echo "$tword"|tr [A-Z] [a-z])"
  if [ ! -z "$tword" -a "$tword" = "quit" ]; then
    exit 0 # don't count this game in statistics; don't show the correct answer, either
  fi
  if [ ! -z "$tword" -a ${#tword} -eq $wordlength -a $(grep -c $tword $listfile) -eq 1 ]; then
    # valid guess; check it
    if [ "$tword" = "$rword" ]; then
      echo -e "Correct! $green$rword$white"
      break;
    else
      # check each letter
      att=$(expr $att + 1)
      tlet=0
      while [ $tlet -lt $wordlength ]; do
        # get offset
        ofs=31
        index=0
        while [ $ofs -eq 31 ]; do
          if [ ${tword:$tlet:1} = ${ltab2[$index]} ]; then
            ofs=$index
          else
            index=$(expr $index + 1)
          fi
        done
        if [ ${tword:$tlet:1} = ${rword:$tlet:1} ]; then
          echo -n -e "$green${tword:$tlet:1}"
          ltab1[$ofs]=3
        elif [ $(echo $rword|grep -c ${tword:$tlet:1}) -eq 1 ]; then
          echo -n -e "$yellow${tword:$tlet:1}"
          if [ ${ltab1[$ofs]} -ne 3 ]; then
            ltab1[$ofs]=2
          fi
        else
          echo -n -e "$white${tword:$tlet:1}"
          ltab1[$ofs]=1
        fi
        tlet=$(expr $tlet + 1)
      done
      echo -en "\t"
      for l in {0..25}; do
        if [ ${ltab1[$l]} -eq 0 ]; then # letter not yet tried
          echo -en "$white${ltab2[$l]}"
        elif [ ${ltab1[$l]} -eq 1 ]; then # letter tried, but not in the answer
          echo -en "$red${ltab2[$l]}"
        elif [ ${ltab1[$l]} -eq 2 ]; then # letter tried, not in correct placement
          echo -en "$yellow${ltab2[$l]}"
        elif [ ${ltab1[$l]} -eq 3 ]; then # letter correct
          echo -en "$green${ltab2[$l]}"
        else # ???
          echo -en "$white${ltab2[$l]}"
        fi
      done
      echo -e "$white"
    fi
  fi
done
# end the timer
tend=$(date '+%Y 3153600 * %j 1 - 86400 * + %H 3600 * + %M 60 * + %S.%N +')

# calculate the time it took from start to finish
tdiff=$(dc -e "8 k $tend $tstart - p q")

# store in statistics file
echo "$wordlength $att $tdiff" >> $statfile

if [ $att -eq 11 ]; then # did not solve; print the correct answer
  echo "The correct word was: $rword"
  echo "This game lost.  Time: $tdiff seconds"
else
  echo "This game won in $att guesses, $tdiff seconds"
fi

# display statistic summary
nplayed=$(grep -c "^$wordlength " $statfile)
grep "^$wordlength " $statfile | awk '
BEGIN { tgames=0; tguess=0; ttime=0; twins=0 }
{ tgames++; tguess+=$2; ttime+=$3; if ($2 < 11) { twins++; } }
END { print "Games Played: "tgames, "Avg Guesses: "tguess/tgames, "Avg Time: "ttime/tgames, "Games won: "twins, "("twins/tgames*100"%)" }'

Updated Sept. 17 2022, fixed a bug with the time calculation (especially noticeable when the hour would change).

[Shiva]

This script was a fun project, a cheeky way to show off to my friends, and at the same time an opportunity to learn a few things about the powerful grep command. And I hope other people have fun while using it!

The 'powerful' grep command has also (known) issues, especially with Extended Regular Expressions (-E) and back references. To check you may try :

Code: Select all

grep -m10 -E '([a-z]*([a-z])\2[a-z]*){2}' /usr/share/dict/words

which is supposed to return the 10 first words of the dic having two sets of doubled characters, but keeps you waiting for some seconds and returns nothing while the PCRE version works immediately :

Code: Select all

grep -m10 -P '([a-z]*([a-z])\2[a-z]*){2}' /usr/share/dict/words

Also :

Code: Select all

grep -E '^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1$' /usr/share/dict/words

is supposed to list all the palindroms of the dic but ends with a stack overflow
while the PCRE version again does the job :

Code: Select all

grep -P '^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1$' /usr/share/dict/words

Bug comes from glibc : https://sourceware.org/bugzilla/show_bug.cgi?id=25322 when used with back references (\ followed by a digit although PCRE also accepts backrefs greater than 9).

Hope some fun has been returned

About your project, I saw the suggestion braid and the solution habit. Is it mandatory that all letters have to be different or are some palindromes like stats or level allowed ? (Keeps you busy thinking about how a suggestion leads if the goal is level or the opposite can be treated )

[antikythera]

Now anyone can boast they are great in Wordle

Nice that you are keeping your own neurons occupied with programming.

Using the solver would be cheating themselves rather than fooling anyone else (family and friends will know straight away if the person concerned is dumb as a box of rocks)

[christosangelopoulos]

Not a "solver" but (a variation on) the game itself, to be run in terminal window. It's not perfect but I've stopped working on it, it's good enough for me to play on my own system occasionally

Hey, thanks for posting, I have tried to run your script but had no success so far, I have just returned from holidays, so it will be a while before I look into it

[christosangelopoulos]

The 'powerful' grep command has also (known) issues, especially with Extended Regular Expressions (-E) and back references. To check you may try :

Thanks, as I mentioned, this script helped me as an introduction to the grep command. As I progress and continue using it, I am certain that I will get acquainted to these issues.

[

About your project, I saw the suggestion braid and the solution habit. Is it mandatory that all letters have to be different or are some palindromes like stats or level allowed ? (Keeps you busy thinking about how a suggestion leads if the goal is level or the opposite can be treated )

I really have no idea!
I will try to look into it though.
I think I had put something in the code about double letters, and how they should be treated.
Let me look into it and I will get back to you.