Back to the Project Euler puzzles

By: Blog by Bogumił Kamiński

Re-posted from: https://bkamins.github.io/julialang/2023/10/20/pe.html

Introduction

After several technical posts today I decided to switch back to puzzle-solving mode.
My readers probably know that I like and promote the Project Euler project.

This time I picked a relatively easy puzzle 205 as it nicely shows several
functionalities of Julia that are worth learning.

The post was written under Julia 1.9.2 and StatsBase.jl v0.34.2.

The problem

The problem 205 is stated as follows:

Peter has nine four-sided dice, each with faces numbered from 1 to 4.
Colin has six six-sided dice, each with faces numbered from 1 to 6.
Peter and Colin roll their dice and compare totals: the highest total wins.
The result is a draw if the totals are equal.
What is the probability that Peter beats Colin?

Simulation approach

To get some intuition for our problem let us first try simulating the distribution of the results.
We will draw one million times from Peter’s and Colin’s dice:

julia> using Random

julia> using StatsBase

julia> Random.seed!(1234);

julia> sim_p = [sum(rand(1:4) for _ in 1:9) for _ in 1:10^6]
1000000-element Vector{Int64}:
 24
 23
 20
 26
 23
  ⋮
 20
 27
 22
 24
 23

julia> sim_c = [sum(rand(1:6) for _ in 1:6) for _ in 1:10^6]
1000000-element Vector{Int64}:
 21
 23
 23
 24
 24
  ⋮
 16
 30
 15
 20
 25

Now let us compare the results:

julia> describe(sim_p)
Summary Stats:
Length:         1000000
Missing Count:  0
Mean:           22.498804
Std. Deviation: 3.355036
Minimum:        9.000000
1st Quartile:   20.000000
Median:         22.000000
3rd Quartile:   25.000000
Maximum:        36.000000
Type:           Int64

julia> describe(sim_c)
Summary Stats:
Length:         1000000
Missing Count:  0
Mean:           20.996381
Std. Deviation: 4.186906
Minimum:        6.000000
1st Quartile:   18.000000
Median:         21.000000
3rd Quartile:   24.000000
Maximum:        36.000000
Type:           Int64

julia> mean(sim_p .> sim_c)
0.5728

We see that Peter’s chances of winning are around 57%.
We also see that both the mean and the median of Peter’s dice are better than Colin’s.

However, the simulation results are only approximate. Let us thus compute the exact result.

Exact approach

To compute the exact probability of Peter’s win first calculate the distribution of
Peter’s and Colin’s dice. With StatsBase.jl it is easy to do using the countmap function:

julia> ex_p = countmap(map(sum, Iterators.product((1:4 for _ in 1:9)...)))
Dict{Int64, Int64} with 28 entries:
  16 => 4950
  20 => 23607
  35 => 9
  12 => 165
  24 => 27876
  28 => 8451
  30 => 2598
  17 => 8451
  23 => 30276
  19 => 18351
  22 => 30276
  32 => 486
  11 => 45
  36 => 1
  9  => 1
  31 => 1206
  ⋮  => ⋮

julia> ex_c = countmap(map(sum, Iterators.product((1:6 for _ in 1:6)...)))
Dict{Int64, Int64} with 31 entries:
  16 => 2247
  20 => 4221
  35 => 6
  12 => 456
  24 => 3431
  28 => 1161
  8  => 21
  17 => 2856
  30 => 456
  23 => 3906
  19 => 3906
  22 => 4221
  32 => 126
  6  => 1
  11 => 252
  36 => 1
  ⋮  => ⋮

As a result we get the number of times out of the total possible outcomes that a given sum on a dice occurs.
Let us check that the total counts of the outcomes are correct. We can do it as we know that on Peter’s dice
we can get 4^9 outcomes and on Colin’s dice 6^6:

julia> sum(values(ex_p)), 4^9
(262144, 262144)

julia> sum(values(ex_c)), 6^6
(46656, 46656)

Indeed the results match.

Using distributions stored in ex_p and ex_c variables we can count the number of times Peter wins with Collin
using the Cartesian product of the distributions (the tosses of the dice are independent) and, in consequence compute the
exact probability that Peter wins:

julia> p_win = sum(pk > ck ? pv*cv : 0 for
                   (pk, pv) in pairs(ex_p),
                   (ck, cv) in pairs(ex_c))
7009890480

julia> total = 4^9 * 6^6
12230590464

julia> p_win / total
0.5731440767829801

julia> p_win // total
48679795//84934656

Note that in Julia we can nicely compute both approximate solution (using Float64) and exact solution using rational numbers.

One important aspect that we should have checked when solving this puzzle is if we do not have an integer overflow issue when
computing the result. On 64-bit machine the overflow happens for the value:

julia> typemax(Int)
9223372036854775807

which is much larger than 12230590464. But how can we be sure that we do not get an overflow when computing 4^9 * 6^6?
The easiest check is to take the logarithms of both expressions:

julia> log(typemax(Int))
43.66827237527655

julia> 9 * log(4) + 6 * log(6)
23.227206065447348

Indeed we see that we have a wide safety margin.

Note, however, that on 32-bit machine Julia would use Int32 type to represent integers by default, and hen we have:

julia> typemax(Int32)
2147483647

julia> log(typemax(Int32))
21.487562596892644

And in this case we would have an integer overflow issue, so some care is needed.

Conclusions

I hope you enjoyed the puzzle, the solution, and the code examples I have presented!

Understanding the Julia Type System

By: Justyn Nissly

Re-posted from: https://glcs.hashnode.dev/julia-type-system

In the programming landscape, type systems traditionally fall into two categories: static and dynamic.In static languages such as C, C++, Rust, and Go,computations are performed before run time to determine types and the values of those types.

Pearl, Ruby, PHP, Python, and JavaScript are languages that use a dynamic type system.In these languages, nothing is known until runtime.Now you may be thinking, where does Julia fit on this landscape? orhow does Julias type system work?That is exactly what we will cover in this post!

Julias Type System

Where exactly does Julia fall along the type system landscape?Is it static? Is it dynamic? Is it some strange amalgam of both?According to Julia’s documentation,it is dynamic, nominative, and parametric.So, what does that mean?

It means Julia is a dynamic language but with a powerful twist.You get all the features of a dynamic type system while also gaining some of the advantages of static type systems.Julia does this by allowing you to indicate that certain values are of specific types.

By default, Julia will allow values to be of any type if the type is not explicitly stated.This allows you to write functions without ever explicitly using types; however, explicitly declared types can be added as needed to help improve human readability and to help catch errors.

Now that we have the introduction out of the way, lets get our hands dirty and see how we use types in Julia.

Type Declarations

The first thing to get familiar with is how to declare types in Julia.To declare a type (also called type annotations), we use the :: operator on a variable or expression in a program.When the :: operator is applied to a variable, it is read as is an instance of.For example, if you were to type var::Integer you would read this as var is an instance of Integer.

Lets look at an example in the REPL:

julia> test = (1+1)::Integer2julia> typeof(test)Int64

You can see in the example above thatwe declared the result of the expression (1+1) to be an instance of Integerbut when we checked the type using the typeof() function, it returns Int64.The reason we see the type as Int64 rather than Integer is because Julia chooses a default primitive type (more on this later) for that value.For integers, Julia will choose Int64 on a 64-bit computer or Int32 on a 32-bit computer.Furthermore,typeof(variable_name) will always return what is called a concrete type.A concrete type is a type where values can be created by the compiler.Variables can’t be an abstract type so any time you check the type of a variable you will get some concrete type.In our example, Integer is an abstract type (we will cover these types later) that is a supertype of the concrete type Int64.If you go to the REPL you will see that test isa Integer returns true even though using typeof(test) returns Int64.This is because of the hierarchy of types in Julia. We will cover this later.

Adding types also works on function declarations:

julia> function multiply_two_numbers(x,y)::Float64           return x*y       endmultiply_two_numbers (generic function with 1 method)

Now let’s run this function with two integer values and see what gets returned:

julia> x = multiply_two_numbers(2,4)8.0julia> typeof(x)Float64

You notice it returns a Float64 even though we passed it two integers?This is because we have told Julia that the function should ALWAYS return a Float64 regardless of what the values in the function are.

One thing that we should note is that type annotations are generally not used much.Using type annotations does not improve performance unless there is a “type-unstable” function, but we won’t cover that in this article. You can learn more about type-stability here and here.

Abstract Types

Abstract types function differently than primitive types. (More on those later.)They function as placeholders for groups of related types.They can’t be used to create objects,but they are essential for organizing different types into a hierarchy.Think of them as labels that help Julia understand which types are related to each other.

Lets look at an example from the Julia documentation.

Julias hierarchy for numeric values is actually built off of abstract types:

abstract type Number endabstract type Real          <: Number endabstract type AbstractFloat <: Real endabstract type Integer       <: Real endabstract type Signed        <: Integer endabstract type Unsigned      <: Integer end

You can see that Number is an abstract type (a direct descendant of the Any type). Then Real is a subtype of Number,Integer is a subtype of Real,and Signed is a subtype of Integer.That means the hierarchy looks like this:

Abstract Types Graphs

We can write a function to see the hierarchy of any type:

function show_type_tree(T, level=0)    println("\t" ^ level, T)    for t in subtypes(T)        show_type_tree(t, level+1)    endend

Now you know that there is a hierarchy,you might want to know what the point of it is.Let’s look at our earlier example of the multiply_two_numbers() function:

julia> function multiply_two_numbers(x,y)::Float64           return x*y       endmultiply_two_numbers (generic function with 1 method)

Lets see what happens when with give the function two Integers:

julia> multiply_two_numbers(2::Int,2::Int)4.0

Now lets try an integer and a float:

julia> multiply_two_numbers(2::Int,2.3::Float64)4.6

One more example, we will do one as a float and one without asserting a type:

julia> multiply_two_numbers(1.6::Float64,54)86.4

Notice how these examples still work without errors?That is because of abstract types!Because we created multiply_two_numbers() without declaring a type for the parameters,Julia will default them to the Any type and that means we can assign any of the number types that are in the hierarchy as subtypes of Any

Let’s look at the hierarchy again to see how this worksBig Type Graph

Since we didnt explicitly define the type of the parameters for the function,we can send it any type of numeric value and the function can work on it.We are not limited to sending only Int64 or a Float64.That is the real power of abstract types!It allows us to create very generic code that works on various types within a categorywithout having to create a function for each type.

Primitive Types

Primitive types are similar to Abstract types in that they are part of a hierarchy of types,but they are different in that they are concrete types.The data contained in a primitive type is simply the bits in memory.One interesting thing about primitive types in Julia is that Julia will let you define your own.

primitive type name bits endprimitive type name <: supertype bits end

Interestingly enough, Julias own default primitive types are all defined in Julia itself using the syntax above.

primitive type Float16 <: AbstractFloat 16 endprimitive type Float32 <: AbstractFloat 32 endprimitive type Float64 <: AbstractFloat 64 endprimitive type Bool <: Integer 8 endprimitive type Char <: AbstractChar 32 endprimitive type Int8    <: Signed 8 endprimitive type Int16   <: Signed 16 endprimitive type Int32   <: Signed 32 endprimitive type Int64   <: Signed 64 endprimitive type Int128  <: Signed 128 endprimitive type UInt8   <: Unsigned 8 endprimitive type UInt16  <: Unsigned 16 endprimitive type UInt32  <: Unsigned 32 endprimitive type UInt64  <: Unsigned 64 endprimitive type UInt128 <: Unsigned 128 end

Just like Abstract types, if you leave off a supertype when you declare the primitive,the primitive will have Any as its direct supertype.One thing to note when declaring your own primitive types, according to Julias documentation,it is usually preferred that you wrap an existing primitive type in a new composite type rather than creating your own primitive.Fortunately for us, this is a great segue into our next topic: Composite Types!

Composite Types

Composite types are Julia’s implementation of what other languages call structs, records, or objects.Interestingly enough, composite types are declared very similar to structs in C

julia> struct Foo           bar           baz::Int           qux::Float64       end

Just like we saw earlier, if you leave the type annotation off of a field in your composite type, it will be defaulted to the Any type.

Just like structs in C or Objects in Java, composite types are a very powerful part of the language. We will have a more detailed post on composite types later, but if you would like to know more in the meantime, check out the official Julia documentation

Type of Types

In the last few sections we covered abstract types, primitive types, and we touched on composite types.Let’s see what happens when we check the type of some of these types

julia> typeof(Number)DataTypejulia> typeof(Int64)DataTypejulia> typeof(AbstractFloat)DataTypejulia> typeof(Char)DataType

You will notice that they all return the same thing, DataType.The reason for this is the shared properties that these types have.Abstract, primitive, and composite types all have names.They have a supertype that is explicitly declared.All those types are explicitly declared.Since these properties are shared amongst the different types we covered,Julia represents each instance of these types as the same concept internally.

Summary

In this post, we covered Abstract types, Primitive types, and Composite types.These are the building blocks of the Julia type system.You can see the power of the structure of Julia’s type system.You can create generic code that works on various types within a categorywithout having to create a function for each type.This simplifies your code and makes it easier to understand and maintain long-term.If you want more in-depth information about types you can visit Julia’s official documentation to learn more.

Do you understand the basics of Julia’s type system?Move on to thenext post to learn about basic data structures in Julia!Or,feel free to take a lookat our other Julia tutorial posts!

Additional Links

Understanding the Julia Type System

By: Justyn Nissly

Re-posted from: https://blog.glcs.io/julia-type-system

In the programming landscape, type systems traditionally fall into two categories: static and dynamic.
In static languages such as C, C++, Rust, and Go,
computations are performed before run time to determine types and the values of those types.

Pearl, Ruby, PHP, Python, and JavaScript are languages that use a dynamic type system.
In these languages, nothing is known until runtime.
Now you may be thinking, where does Julia fit on this landscape? or
how does Julias type system work?
That is exactly what we will cover in this post!

Julias Type System

Where exactly does Julia fall along the type system landscape?
Is it static? Is it dynamic? Is it some strange amalgam of both?
According to Julia’s documentation,
it is dynamic, nominative, and parametric.
So, what does that mean?

It means Julia is a dynamic language but with a powerful twist.
You get all the features of a dynamic type system while also gaining some of the advantages of static type systems.
Julia does this by allowing you to indicate that certain values are of specific types.

By default, Julia will allow values to be of any type if the type is not explicitly stated.
This allows you to write functions without ever explicitly using types; however, explicitly declared types can be added as needed to help improve human readability and to help catch errors.

Now that we have the introduction out of the way, lets get our hands dirty and see how we use types in Julia.

Type Declarations

The first thing to get familiar with is how to declare types in Julia.
To declare a type (also called type annotations), we use the :: operator on a variable or expression in a program.
When the :: operator is applied to a variable, it is read as is an instance of.
For example, if you were to type var::Integer you would read this as var is an instance of Integer.

Lets look at an example in the REPL:

julia> test = (1+1)::Integer
2
julia> typeof(test)
Int64

You can see in the example above that
we declared the result of the expression (1+1) to be an instance of Integer
but when we checked the type using the typeof() function, it returns Int64.
The reason we see the type as Int64 rather than Integer is because Julia chooses a default primitive type (more on this later) for that value.
For integers, Julia will choose Int64 on a 64-bit computer or Int32 on a 32-bit computer.
Furthermore,
typeof(variable_name) will always return what is called a concrete type.
A concrete type is a type where values can be created by the compiler.
Variables can’t be an abstract type so any time you check the type of a variable you will get some concrete type.
In our example, Integer is an abstract type (we will cover these types later) that is a supertype of the concrete type Int64.
If you go to the REPL you will see that test isa Integer returns true even though using typeof(test) returns Int64.
This is because of the hierarchy of types in Julia. We will cover this later.

Adding types also works on function declarations:

julia> function multiply_two_numbers(x,y)::Float64
           return x*y
       end
multiply_two_numbers (generic function with 1 method)

Now let’s run this function with two integer values and see what gets returned:

julia> x = multiply_two_numbers(2,4)
8.0

julia> typeof(x)
Float64

You notice it returns a Float64 even though we passed it two integers?
This is because we have told Julia that the function should ALWAYS return a Float64 regardless of what the values in the function are.

One thing that we should note is that type annotations are generally not used much.
Using type annotations does not improve performance unless there is a “type-unstable” function, but we won’t cover that in this article. You can learn more about type-stability here and here.

Abstract Types

Abstract types function differently than primitive types. (More on those later.)
They function as placeholders for groups of related types.
They can’t be used to create objects,
but they are essential for organizing different types into a hierarchy.
Think of them as labels that help Julia understand which types are related to each other.

Lets look at an example from the Julia documentation.

Julias hierarchy for numeric values is actually built off of abstract types:

abstract type Number end
abstract type Real          <: Number end
abstract type AbstractFloat <: Real end
abstract type Integer       <: Real end
abstract type Signed        <: Integer end
abstract type Unsigned      <: Integer end

You can see that Number is an abstract type (a direct descendant of the Any type). Then Real is a subtype of Number,
Integer is a subtype of Real,
and Signed is a subtype of Integer.
That means the hierarchy looks like this:

Abstract Types Graphs

We can write a function to see the hierarchy of any type:

function show_type_tree(T, level=0)
    println("\t" ^ level, T)
    for t in subtypes(T)
        show_type_tree(t, level+1)
    end
end

Now you know that there is a hierarchy,
you might want to know what the point of it is.
Let’s look at our earlier example of the multiply_two_numbers() function:

julia> function multiply_two_numbers(x,y)::Float64
           return x*y
       end
multiply_two_numbers (generic function with 1 method)

Lets see what happens when with give the function two Integers:

julia> multiply_two_numbers(2::Int,2::Int)
4.0

Now lets try an integer and a float:

julia> multiply_two_numbers(2::Int,2.3::Float64)
4.6

One more example, we will do one as a float and one without asserting a type:

julia> multiply_two_numbers(1.6::Float64,54)
86.4

Notice how these examples still work without errors?
That is because of abstract types!
Because we created multiply_two_numbers() without declaring a type for the parameters,
Julia will default them to the Any type and that means we can assign any of the number types that are in the hierarchy as subtypes of Any

Let’s look at the hierarchy again to see how this works
Big Type Graph

Since we didnt explicitly define the type of the parameters for the function,
we can send it any type of numeric value and the function can work on it.
We are not limited to sending only Int64 or a Float64.
That is the real power of abstract types!
It allows us to create very generic code that works on various types within a category
without having to create a function for each type.

Primitive Types

Primitive types are similar to Abstract types in that they are part of a hierarchy of types,
but they are different in that they are concrete types.
The data contained in a primitive type is simply the bits in memory.
One interesting thing about primitive types in Julia is that Julia will let you define your own.

primitive type name bits end
primitive type name <: supertype bits end

Interestingly enough, Julias own default primitive types are all defined in Julia itself using the syntax above.

primitive type Float16 <: AbstractFloat 16 end
primitive type Float32 <: AbstractFloat 32 end
primitive type Float64 <: AbstractFloat 64 end

primitive type Bool <: Integer 8 end
primitive type Char <: AbstractChar 32 end

primitive type Int8    <: Signed 8 end
primitive type Int16   <: Signed 16 end
primitive type Int32   <: Signed 32 end
primitive type Int64   <: Signed 64 end
primitive type Int128  <: Signed 128 end

primitive type UInt8   <: Unsigned 8 end
primitive type UInt16  <: Unsigned 16 end
primitive type UInt32  <: Unsigned 32 end
primitive type UInt64  <: Unsigned 64 end
primitive type UInt128 <: Unsigned 128 end

Just like Abstract types, if you leave off a supertype when you declare the primitive,
the primitive will have Any as its direct supertype.
One thing to note when declaring your own primitive types, according to Julias documentation,
it is usually preferred that you wrap an existing primitive type in a new composite type rather than creating your own primitive.
Fortunately for us, this is a great segway into our next topic: Composite Types!

Composite Types

Composite types are Julia’s implementation of what other languages call structs, records, or objects.
Interestingly enough, composite types are declared very similar to structs in C

julia> struct Foo
           bar
           baz::Int
           qux::Float64
       end

Just like we saw earlier, if you leave the type annotation off of a field in your composite type, it will be defaulted to the Any type.

Just like structs in C or Objects in Java, composite types are a very powerful part of the language. We will have a more detailed post on composite types later, but if you would like to know more in the meantime, check out the official Julia documentation

Type of Types

In the last few sections we covered abstract types, primitive types, and we touched on composite types.
Let’s see what happens when we check the type of some of these types

julia> typeof(Number)
DataType

julia> typeof(Int64)
DataType

julia> typeof(AbstractFloat)
DataType

julia> typeof(Char)
DataType

You will notice that they all return the same thing, DataType.
The reason for this is the shared properties that these types have.
Abstract, primitive, and composite types all have names.
They have a supertype that is explicitly declared.
All those types are explicitly declared.
Since these properties are shared amongst the different types we covered,
Julia represents each instance of these types as the same concept internally.

Summary

In this post, we covered Abstract types, Primitive types, and Composite types.
These are the building blocks of the Julia type system.
You can see the power of the structure of Julia’s type system.
You can create generic code that works on various types within a category
without having to create a function for each type.
This simplifies your code and makes it easier to understand and maintain long-term.
If you want more in-depth information about types you can visit Julia’s official documentation to learn more.

Additional Links