Map Coloring

Another fun challenge from Decision Management Community. A canonical example of the constraint programming (over finite domains) paradigm leads to a simple and elegant SQL solution.

The task is to color a map of six European countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands in such a way that no neighboring countries use the same color. You need to use no more than 4 colors: blue, red, green, or yellow.

Starting with two sets: country and color; who borders whom, and the rule.

country {BE, DK, FR, DE, LU, NL}
color   {B, R, G, Y}

BE borders {FR, LU, DE, NL}
DK borders {DE}
FR borders {BE, LU, DE}
DE borders {FR, LU, BE, NL, DK}
LU borders {FR, DE, BE}
NL borders {BE, DE}

Neighboring countries can not use the same color.

Reasoning

There are six countries, each one can have one of four colors, so in total there is a maximum of 4^6 = 4096 combinations to examine. The strategy is simple:

  1. Create a set of all possible combinations.
  2. Apply constraints.
  3. Present all results that satisfy given constraints.

The SQL code is straightforward and easy to follow. Try it, there are 144 possible solutions.

Variation

In a variation of the problem rules are changed a bit. Only three colors are allowed and some neighboring countries are allowed to have the same color, but there is a penalty cost assigned. The task is to find solutions with minimum penalty cost.

country {BE, DK, FR, DE, LU, NL}
color   {R, G, B}

These neighboring countries can use the same color,
with assigned cost:

LU-FR  $257
LU-DE  $904
LU-BE  $568

Reasoning v2

This time there are 3^6 = 729 combinations to examine. The strategy:

  1. Create a set of all possible combinations.
  2. Apply mandatory constraints.
  3. Calculate the cost for all tuples satisfying mandatory constraints.
  4. Find the minimum cost.
  5. Present all results that have the minimum cost.

Again, SQL code is easy to follow, this time there are 12 possible solutions.

Home Network DNS Resolver

Raspberry Pi Kit
Scott Helme has a detailed procedure of how to configure Raspberry PI to act as a DNS resolver with DNS-level “content-blocking” for a network. It is a great weekend project, fun and useful. The hardware cost is around 100 CAD on Amazon.

Benefits

  • Content filter on DNS level, including ads and known nasty sites.
  • Reduced web traffic. Depends on sites you visit, but 40% is a reasonable expectation.
  • Upstream DNS queries are directed over https, so you get some extra privacy.
  • Pages load faster, take a look at the example.
  • Pi-Hole has a nice admin interface, so you get insight into DNS chatter on the network.

Here are network requests for a home page of a popular news site using default (no filtering) DNS resolver. In total it took 395 requests, 5.3 MB and six minutes to load.
Default DNS

Now if I switch to the DNS resolver on Raspberry PI:
DNS via pi-hole
Total of 143 request, 2.7MB to load, and 20.75 seconds. Take a look at all the lines in red with failed status, this is where the domain got blocked by the pi-hole on the Raspberry.

That’s ~ 50% less data and 17 times faster.

Continue reading “Home Network DNS Resolver”

Monkey Business

A challenge by Decision Management Community.

A zoo has four monkeys, during the monkey lunchtime each one ate a different fruit in their favourite resting place. Sam, who doesn’t like bananas, likes sitting on the grass. The monkey who sat on the rock ate the apple. The monkey who ate the pear didn’t sit on the tree branch. Anna sat by the stream but she didn’t eat the pear. Harriet didn’t sit on the tree branch. Mike doesn’t like oranges.

  1. What kind of fruit each monkey ate?
  2. Where their favourite resting place was?

So, how to solve this in SQL? It is easy to identify domains, predicates and rules; after that it is straightforward. Continue reading “Monkey Business”

Cyber Security Incident Scenario

This scenario has been designed to engage the entire cyber security incident response (IR) team and evolve the IR plan and capabilities as quickly as possible. It includes technical, managerial, financial, regulatory, legal, and public relation challenges.

Dante's Inferno

Take a look at your current IR plan and see if it stands up to this test. An organisation that does not have a cyber security IR plan, or a program, must act as if it has already been breached. If you do not have an IR plan get one; NIST SP 800-61 r2 is a good start. Continue reading “Cyber Security Incident Scenario”