# Krypto

In the 2016 Year Game, the task was to generate the numbers 0 to 100 using APL primitives and the digits 2 0 1 6 in that order. For example,

``````   20=16
×2016
2⌊016
2+×016
…
``````

This “puzzle of the year” brings to mind Krypto, a game I played many years ago while in grade school.

## Krypto

Krypto is a mathematical card game. The Krypto deck has 56 cards: 3 each of numbers 1-6, 4 each of the numbers 7-10, 2 each of 11-17, 1 each of 18-25.

``````   ⎕io←0
DECK ← (3/1+⍳6),(4/7+⍳4),(2/11+⍳7),18+⍳8
``````

Six cards are dealt: an objective card and five other cards. A player must use all five of the latter cards’ numbers exactly once, using any combination of arithmetic operations (`+`, `-`, `×`, and `÷`) to form the objective card’s number. The first player to come up with a correct formula is the winner. The stricter “International Rules” specify the use of non-negative integers only; fractional or negative intermediate results are not permitted.

For example, if the objective card were `17` and the other cards were `2`, `8`, `14`, `19`, and `21`, then a Krypto solution can be as follows. Without loss of generality, we use APL notation and syntax.

``````   8 - 19 + 14 - 2 × 21
``````

In this article we present functions to find all solutions to a Krypto hand.

## A Solution

There are a maximum of `!5` permutations of the `5` cards and `4` possibilities in each of the `4` places where an operation can be put, for `(!5)×4*4` or `30720` total possibilities. This number is small enough for an exhaustive approach.

``````deal←{DECK ⌷⍨⊂ 6?≢DECK}

Krypto←{
perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
a←256⌿5 0⍕⍵[perm 5]
a[;6+5×⍳4]←'+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
⊣⌸ a ⌿⍨ ⍺ = ⍎⍤1 ⊢a
}

deal ⍬
17 8 19 14 2 21

⊢ t← 17 Krypto 8 19 14 2 21
8 - 19 + 14 -  2 × 21
8 - 19 + 14 - 21 ×  2
8 - 19 - 21 + 14 ÷  2
8 - 14 + 19 -  2 × 21
...
21 +  8 - 19 - 14 ÷  2
21 - 19 -  8 + 14 ÷  2

⍴ t
24 25
``````

## Intermediate Steps

The function `perm` is from the Dyalog blog post Permutations, 2015-07-20. `perm n` generates the sorted table of all permutations of `⍳n`.

The local variable `a` in `Krypto` is a `30720`-row character matrix computed from the `5` non-objective numbers. It consists of all `!5` permutations of the `5` numbers interspersed with all `4*4` arrangements of the four operations `+ - × ÷`.

Executing the rows of `a` produces a `30720`-element numeric vector. Comparison of this vector with the objective yields a boolean vector that selects the rows of `a` which are correct formulas.

``````   ⍴ a
30720 25

8↑a
8 + 19 + 14 +  2 + 21
8 + 19 + 14 +  2 - 21
8 + 19 + 14 +  2 × 21
8 + 19 + 14 +  2 ÷ 21
8 + 19 + 14 -  2 + 21
8 + 19 + 14 -  2 - 21
8 + 19 + 14 -  2 × 21
8 + 19 + 14 -  2 ÷ 21
¯5↑a
21 ÷  2 ÷ 14 × 19 ÷  8
21 ÷  2 ÷ 14 ÷ 19 +  8
21 ÷  2 ÷ 14 ÷ 19 -  8
21 ÷  2 ÷ 14 ÷ 19 ×  8
21 ÷  2 ÷ 14 ÷ 19 ÷  8

+/ b ← 17 = ⍎⍤1 ⊢a
24

t ≡ b⌿a
1
``````

We note that use of the `@` operator, new to Dyalog version 16.0, obviates the need to name intermediate results for reasons for syntax. Instead, names are only used to break the code down into more comprehensible components.

``````Krypto1←{
perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]⊣@(6+5×⍳4)⍤1 ⊢256⌿5 0⍕⍵[perm 5]
}

Krypto2←{
perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
fns  ← '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
nums ← 256⌿5 0⍕⍵[perm 5]
⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) fns ⊣@(6+5×⍳4)⍤1 ⊢nums
}

17 (Krypto ≡ Krypto1) 8 19 14 2 21
1

17 (Krypto ≡ Krypto2) 8 19 14 2 21
1

``````

## International Rules

The international rules (intermediate results must be non-negative integers) can be enforced readily:

``````irules←{⍵⌿⍨∧/(i=⌊i)∧0≤i←8 13 18{⍎¨⍺↓¨⊂⍵}⍤1⊢⍵}

irules 17 Krypto 8 19 14 2 21
8 +  2 + 14 ÷ 21 - 19
8 + 21 - 19 - 14 ÷  2
19 -  2 ×  8 - 21 - 14
19 -  2 ÷  8 - 21 - 14
19 -  2 × 14 - 21 -  8
19 -  2 ÷ 14 - 21 -  8
2 +  8 + 14 ÷ 21 - 19
21 - 19 -  8 + 14 ÷  2
``````

It is instructive to look at how the local variable `i` in `irules` is formed:

``````   ⊢ t←17 Krypto 8 19 14 2 21
8 - 19 + 14 -  2 × 21
8 - 19 + 14 - 21 ×  2
8 - 19 - 21 + 14 ÷  2
8 - 14 + 19 -  2 × 21
...
21 +  8 - 19 - 14 ÷  2
21 - 19 -  8 + 14 ÷  2

8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
┌─────────────────┬────────────┬───────┐
│19 + 14 -  2 × 21│14 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
│19 + 14 - 21 ×  2│14 - 21 ×  2│21 ×  2│
├─────────────────┼────────────┼───────┤
│19 - 21 + 14 ÷  2│21 + 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│14 + 19 -  2 × 21│19 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
...
├─────────────────┼────────────┼───────┤
│ 8 - 19 - 14 ÷  2│19 - 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│19 -  8 + 14 ÷  2│ 8 + 14 ÷  2│14 ÷  2│
└─────────────────┴────────────┴───────┘

⍎¨ 8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
¯9 ¯28  42
¯9 ¯28  42
¯9  28   7
¯9 ¯23  42
...
¯4  12   7
4  15   7
``````

(An earlier version of the text appeared as the Jwiki essay Krypto, 2013-07-04.)