Author Archives: perfectionatic

Exploring Wordle with Julia: Part I

Re-posted from: https://perfectionatic.org/?p=753

Wordle is a fun and easy game that has shot to fame recently. It is completely minimalistic, no-fills and highly addictive. We will explore here how to write as simple solver for Wordle with Julia and then adding layers of complexity and sophistication as we go along.

In Wordle we are successively guessing five-letter words. After each guess the game tells us which of our letters occur in the secret word and whether they are in the correct position. As explained in their website.

So after each guess we narrow the set of possible words to choose from till we arrive at the secret word, and we only have six tries.

Our Dictionary

Wordle only deals with a valid five-letter English words. So we need to start grabbing such words. A good place to start is the Standford GraphBase data set.

	julia> words = readlines(download("https://www-cs-faculty.stanford.edu/~knuth/sgb-words.txt"))
	5757–element Vector{String}:
	"which"
	"there"
	⋮
	"biffy"
	"pupal"

view raw

word_dict.jl

hosted with ❤ by GitHub

Constraints

The next step is the try narrow down the set of feasible words as we are getting clues. Towards that end, we construct a Dict to map letters that are in the word at the correct spot to their location, another Dict to maps letter in the word that are in the wrong spot, and finally a Set of letters that are not in the word:

	let_in_pos = Dict{Int,Char}()
	let_not_in_pos = Dict{Char,Vector{Int}}()
	let_not_in_word = Set{Char}()

view raw

constraint_definition.jl

hosted with ❤ by GitHub

Now we can encode the the response we get the game as String of numbers, where 0 means that the character is not in the word, 1 means the that character is the word but not in the right spot, and 2 means that the character is in the word at the correct spot. For example

Secret Word:    perky
Candidate Word: ebony
Response:       10002

We can update our set of constraint for any response by the following function:

	function update_constraints_by_response!(word, response, let_in_pos, let_not_in_pos, let_not_in_word)
	for i in eachindex(response)
	c = response[i]
	if c=='2'
	let_in_pos[i]=word[i]
	elseif c=='1'
	let_not_in_pos[word[i]] = push!(get(let_not_in_pos,word[i],Int[]),i)
	else
	push!(let_not_in_word,word[i])
	end
	end
	end

view raw

update_constraints_by_response.jl

hosted with ❤ by GitHub

Shrinking the feasible set of words

The constraints will reduce the feasible set of possible words. This can be done by applying filters that make use of constraints as in the following function:

	function word_set_reduction!(word_set, let_in_pos, let_not_in_pos, let_not_in_word)
	filter!(w->all(w[r[1]]==r[2] for r in let_in_pos), word_set)
	filter!(w->all(occursin(s[1],w) && all(w[p]!=s[1] for p in s[2]) for s in let_not_in_pos), word_set)
	filter!(w->all(!occursin(c,w[setdiff(1:5,keys(let_in_pos))]) for c in setdiff(let_not_in_word,keys(let_not_in_pos))), word_set)
	end

view raw

word_set_reduction.jl

hosted with ❤ by GitHub

Putting it all together

So all what we have to do now is to apply the following step

Guess a candidate first word
Get response from the Game
Use that response to update the set of constraints
Use the constraints to reduce the set of possible words
Guess the new candidate word
Repeat step 2 until a word is found or the game is over

In the steps 1 and 5 above, the simplest approach is just to pick a word at random. Below is Julia repl session showing how we go about applying the above. The secret word here is “super”

	julia> let_in_pos = Dict{Int,Char}();
	julia> let_not_in_pos = Dict{Char,Vector{Int}}();
	julia> let_not_in_word = Set{Char}();
	julia> word_set = copy(words);
	julia> word=rand(word_set)
	"excel"

	julia> update_constraints_by_response!(word, "00020", let_in_pos, let_not_in_pos, let_not_in_word)
	julia> word_set_reduction!(word_set, let_in_pos, let_not_in_pos, let_not_in_word)
	698–element Vector{String}:
	"other"
	"water"
	⋮
	"assed"
	"osier"

	julia> word=rand(word_set)
	"buyer"

	julia> update_constraints_by_response!(word, "02022", let_in_pos, let_not_in_pos, let_not_in_word)
	julia> word_set_reduction!(word_set, let_in_pos, let_not_in_pos, let_not_in_word)
	13–element Vector{String}:
	"outer"
	"super"
	⋮
	"fumer"
	"muter"

	julia> word=rand(word_set)
	"fumer"

	julia> update_constraints_by_response!(word, "02022", let_in_pos, let_not_in_pos, let_not_in_word)
	julia> word_set_reduction!(word_set, let_in_pos, let_not_in_pos, let_not_in_word)
	10–element Vector{String}:
	"outer"
	"super"
	⋮
	"duper"
	"nuder"

	julia> word=rand(word_set)
	"purer"

	julia> update_constraints_by_response!(word, "12022", let_in_pos, let_not_in_pos, let_not_in_word)
	julia> word_set_reduction!(word_set, let_in_pos, let_not_in_pos, let_not_in_word)
	2–element Vector{String}:
	"super"
	"duper"

	julia> word=rand(word_set)
	"super"

view raw

blog_julia_wordle_repl_session1.jl

hosted with ❤ by GitHub

We see that we arrived at the correct word after guessing

excel
buyer
fumer
purer
super

That is a 5/6 score. Not too bad! But we could do better. How? We explore that in the next part.

See also below an interactive session where the secret word is “wrung”

Expanding WordPress Julia’s GeSHi Syntax Highlighting

By: perfectionatic

Re-posted from: https://perfectionatic.org/?p=778

In your WordPress installation you want to modify the wp-content/plugins/wp-geshi-highlight/geshi/geshi/julia.php file.

/*
** builtins
*/
2 => array(
    'Array', 'String', 'Bool', 'Number', 'Int', 'Integer', 'Real', 'Complex',
    'FloatingPoint', 'Float64', 'Float32', 'Int8', 'Int16', 'Int32', 'Int64',
    'Rational', 'AbstractArray', 'Unsigned', 'Signed', 'Uint', 'Uint8', 'Uint16',
    'Uint32', 'Uint64', 'Vector', 'AbstractVector', 'Matrix', 'AbstractMatrix',
    'Type', 'IO',....

You are trying to expand the list of those builtins. In Julia, you extract that list by running

julia> [names(Core);names(Base)] .|> String |> x->filter(z->occursin(r"^[A-Za-z]+[A-Za-z0-9]+",z),x) |> x->join(["'$y'" for y in x],", ") |> x-> replace(x,r"(.{30,75},)\s"=>SubstitutionString(" "^12*"\\1\\n"))|> clipboard

You take the output in the clipboard and replace the contents of the aforementioned array.

Evaluating Arbitrary Precision Integer Expressions in Julia using Metaprogramming

While watching the Mathologer masterclass on power sums

I came across a challenge to evaluate the following sum
$1^{10}+2^{10}+\cdots+1000^{10}$

This can be easily evaluated via brute force in Julia to yield

function power_cal(n)
  a=big(0)
  for i=1:n
    a+=big(i)^10
  end
  a 
end
 
julia&gt; power_cal(1000)
91409924241424243424241924242500

Note the I had to use big to makes sure we are using BigInt in the computation. Without that, we would be quickly running in into an overflow issue and we will get a very wrong number.

In the comment section of the video I found a very elegant solution to the above sum, expressed as

(1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 – 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000 = 91409924241424243424241924242500

If I try to plug this into the Julia, I get

julia&gt; (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + r1000^5-(1/2) * 1000^3 + (5/66) * 1000
-6.740310541071357e18

This negative answer is not surprising at all, because we obviously ran into an overflow. We can, of course, go through that expression and modify all instances of Int64 with BigInt by wrapping it in the big function. But that would be cumbersome to do by hand.

The power of Metaprogramming

In Julia, metaprogramming allows you to write code that creates code, the idea here to manipulate the abstract syntax tree (AST) of a Julia expression. We start to by “quoting” our original mathematical expressing into a Julia expression. In the at form it is not evaluated yet, however we can always evaluate it via eval.

julia&gt; ex1=:((1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000)
:((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000)
 
julia&gt; dump(ex1)
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol +
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol -
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol +
            2: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol -
                2: Expr
                3: Expr
            3: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol ^
                2: Int64 1000
                3: Int64 5
        3: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol *
            2: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol /
                2: Int64 1
                3: Int64 2
            3: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol ^
                2: Int64 1000
                3: Int64 3
    3: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol *
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol /
            2: Int64 5
            3: Int64 66
        3: Int64 1000
 
julia&gt; eval(ex1)
-6.740310541071357e18

The output of dump show the follow AST in all its glory (…well almost the depth is a bit truncated). Notice that here all our numbers are interpreted as Int64.
Now we walk through the is AST and change all occurrences of Int64 with BigInt by using the big function.

function makeIntBig!(ex::Expr)
  args=ex.args
  for i in eachindex(args)
       if args[i] isa Int64
          args[i]=big(args[i])
       end
       if args[i] isa Expr
          makeIntBig!(args[i])
       end
   end
end
 
julia&gt; ex2=copy(ex1)
:((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000)
 
julia&gt; makeIntBig!(ex2)
 
julia&gt; eval(ex2)
9.14099242414242434242419242425000000000000000000000000000000000000000000000014e+31

We see an improvement here, but the results are not very satisfactory. The divisions yield BigFloat results, which had a tiny bit of floating point errors. Can we do better?
Julia has support for Rational expressions baked in. We can use that improve the results. We just need to search for call expressions the / symbol and replace it by the // symbol. For safety we just have to makes sure the operands are as subtype of Integer.

function makeIntBig!(ex::Expr)
    args=ex.args
    if ex.head == :call && args[1]==:/ && 
              length(args)==3 && 
              all(x->typeof(x) <: Integer,args[2:end]) 
        args[1]=://
        args[2]=big(args[2])
        args[3]=big(args[3])
    else 
        for i in eachindex(args)
           if args[i] isa Int64
              args[i]=big(args[i])
           end
           if args[i] isa Expr
              makeIntBig!(args[i])
           end
        end
    end
end
 
julia> ex2=copy(ex1);
 
julia> makeIntBig!(ex2)
 
julia> eval(ex2)
91409924241424243424241924242500//1

Now that is much better! We have not lost any precision and we ended us with a Rational expression.

Finally, we can build a macro so the if we run into such expressions in the future and we want to evaluate them, we could just conveniently call it.

macro eval_bigInt(ex)
   makeIntBig!(ex)
   ex
end

and we can now simply evaluate our original expression as

julia> @eval_bigInt (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000
91409924241424243424241924242500//1

juliabloggers.com

A Julia Language Blog Aggregator