Author Archives: OpenSourcES

Table logging in Julia

This is kinda part of the constraint solver series => Building a constraint solver in Julia but is useful for more than this and might be its own package (yeah I say that often :D)

There were some changes to the constraint solver which still need a post and I’m not satisfied yet to write a post about it but I should…

What is this topic about?

When I started with Julia and Juniper.jl I needed to write a table logger to display the current status of the solver.
By status I mean information like best solution found so far (incumbent) and best bound as well as how long did it run so far.

Basically the table from this:

Logging of Juniper.jl

Now I of course also need this for the constraint solver project but I didn’t like the code that much and spoiler alert: I’m not completely satisfied with the current implementation now but I think I should put it out here and maybe some others have ideas on how to improve it.

What I want

I want to easily define the table by giving the header information which includes the type, the width and some other information.

In the solver I want to push something to the table and given some criteria the table should decide whether this is a new row or whether there it’s not worth it i.e in the constraint solver there can be a lot of backtracking steps but they can be quite fast for example in the case of solving sudokus. I don’t want a line for each step in the backtrack! function. Normally the user wants to get updates to see that it’s running or if a new solution was found. Therefore I use the rule that a new line should be added every five seconds or if there is a new solution.

Additionally the type of the column should define some formatting rules which the developer should be able to change.

Some problems

Not too sure how to make it as extensible as possible so this is my try of doing it and I welcome your comments/issues/PRs.

Current implementation

TableLogger.jl

mutable struct TableCol
    id                  :: Symbol
    name                :: String
    type                :: DataType
    width               :: Int
    alignment           :: Symbol # :left, :center, :right
    b_format            :: Bool
end

mutable struct TableEntry{T}
    col_id              :: Symbol
    value               :: T
end

mutable struct TableSetup
    cols                :: Vector{TableCol}
    col_idx             :: Dict{Symbol,Int}
    new_row_criteria    :: Bool
    diff_criteria       :: Dict{Symbol, Any}
    last_row            :: Vector{TableEntry}
end

The table is defined by the columns cols might have some criteria to check if a new row should be added or now which depends on last_row and diff_criteria will be passed to the function of deciding whether a new row will be added.
I need the col_idx to know which column is at which position. Maybe that can be done in a different fashion.

TableCol has a type which defines whether some formatting should be used.
Each row is a vector of TableEntry which defines the column…

Building an Enigma emulator and a Bombe

I got a bit distracted on my work of building a constraint solver which is a series of 17 posts now. Check it out if you’re interested in solving sudokus, graph coloring, JuMP or well generally contraint solving. This time I want to show you what I’ve done the last couple of days.

YouTube suggested me this video from Code Bullet about building an Enigma Machine. It was somehow on my imaginary list of things I wanted to code like a sudoku solver some years ago.

Additionally I want to code a chess computer but that’s something for another day.

Alright let’s start with the Enigma. First of all I will shortly explain what it is about then I’ll start with creating the Enigma package in Julia with starting which functions we need to encrypt and decrypt messages.

In the second part you can read more about the flaws of the Enigma machine and how they can be used to crack the code so decrypt messages without knowing the setting.

A bit of a story

The Enigma was used in the World War II by the Germans to have a secure communication in their military. They thought that their machine is sooo good that it is unbreakable. Well they weren’t the first to think that about a new cryptographic technique and probably not the last. The code was famously cracked by Alan Turing and others at Bletchley Park during the war. Which means that they were able to save a lot of lives and end the war earlier.

Maybe you have seen the movie The Imitation Game with Benedict Cumberbatch about that story. Even though it is simplified as always it is a good movie.

Because we dive into the actual Enigma Machine we might want to have a very short look at previous methods of decrypting and I’m not an expert on this so it’s just a short overview of simple methods that I find interesting.

First part of every cryptography section should be the Caesar method where one only replaces a letter with a different letter and even simpler just moving the alphabet by a number of steps like this.

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 
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 

Things that come to mind if cracking such codes are:

  • Is it safe even if they know the method but not the settings?
  • How many possibilities are there?

In this case there are only 26 setting and one of them is the plain text so it is obviously not good if you know the method.

What if we just randomly set the letters instead of shifting?

A B C D E F G H I J K L M N O P Q R S T...

Kaggle Santa 2019: Final wrap up

Well guys and girls I’m happy to announce that I’m probably the last person telling you something about the last Kaggle Santa challenge. The reason is I’m late like super late but hopefully some of you are still interested in my thoughts. The reason I write this blog now: I haven’t found the optimal solution during the challenge and I wanted to find it before I write this and after I found it I got sick so here we are.

If you’re interested in building a constraint solver which is my current project on this blog you might want to check out the dozen of posts about it and consider subscribing on patreon to get post 48 hours earlier (This one is a special one ;))

Special limited offer only for X days… I either just lost your attention or I have it now 😀
I decided to offer a 1:1 (binary) talk where you can ask me about my work and just chat with me if you’re willing to join the Patron 4$ club. 😉 This offer exists until the 10th of February.

My final steps during the competition

Before I go over the optimal solution which I only found because I read what other teams did after the competition ended I want to go briefly over the things I didn’t talk about in my last two posts about the challenge:

There is not much more to add to the swapping part from the last post besides some things I encountered. In the following a,b,c are family ids and A,B,C are the days they currently visit the workshop.

  • Swaps of the form a->B, b->C, c->A didn’t work as well as a->B, b->C, c->D
    • this is normal as the last c->A normally destroys it
  • How did I choose a,b,c? + d,e,… for longer swap patterns?
    • a is chosen from randomly from the 5000 families
    • b is chosen by choosing B as a day of the choices from a
    • and then b is chosen randomly
    • this continues til the end
    • I reject the current set if I chosen the same family more than once
  • For performance reasons:
    • I precompute the days and choices for each family and update the assigned day after I make a change. (Probably everyone does that)
    • Only compute the resulting change in costs
    • Easy for preference cost
    • Bit harder for preference costs
    • => In the end I had about 1 million swaps per second on my machine.
  • In general I experimented a lot with the temperature in simulated annealing and with falling back to previous solutions when stuck which were quite helpful but I explained the interesting stuff in the last post.

Let’s move from swapping to the MIP approach. Last time I mentioned a way to find the optimal arrangement if we know how many people visit the workshop per day.

Which we normally don’t know 😀 Therefore that was quite pointless.
We want…