# Winter School is Coming

Winter School is a course in cryptography. The course features weekly assignments and review sessions on Mondays.

You can join the Winter School at WellingtonRuby. If you have any questions just comment on the Winter School events there.

## Shuffle Puzzle

Winter School will start in June. Try the Shuffle Puzzle while you wait!

`java.util.Random` generates pseudorandom numbers from a linear congruential generator.

You can implement that generator in Ruby like this:

```## <>
##   @state: Integer
class Generator
A = 0x000000000000000B
F = 0x00000005DEECE66D
M = 0x0000FFFFFFFFFFFF

## Integer -> void
def initialize(seed)
super()
@state = (seed ^ F) & M
return
end

## -> Integer
def __next
return @state = (A + F * @state) & M
end

## Integer -> Integer
def random(n)
unless n > 0
raise ArgumentError.new("n must be positive")
end
if n == n & -n
k = __next >> 17
return (n * k) >> 31
else
while true
k = __next >> 17
r = k % n
if k - r + n - 1 < 0x80000000
return r
end
end
end
end
end
```

Try the generator:

```seed = 0x0000000000000000
g = Generator.new(seed)
8.times do |j|
puts g.random(j + 1)
end
```
```0
1
1
2
0
5
2
0
```

Now use the generator to implement a shuffle with the Fisher–Yates algorithm:

```## <>
module Util
class << self
## <E: ..Object?> Generator, Integer, &{Integer -> E} -> Array<E>
def shuffle(g, n)
a = Array.new(n)
j = 0
while j < n
k = j + 1
i = g.random(k)
if i != j
a[j] = a[i]
end
a[i] = yield(j)
j = k
end
return a
end
end
end
```

Perform a shuffle:

```seed = 0x0000000000000000
g = Generator.new(seed)
a = Util.shuffle(g, 8) { |v| v }
puts a
```
```7
2
6
1
0
5
3
4
```

Implement a class for cards:

```## <>
##   @v: Integer
class Card
RANKS = "A23456789TJQK".chars
SUITS = "♣♦♥♠".chars

## Integer -> void
def initialize(v)
super()
@v = v
return
end

## -> String
def to_s
return RANKS.fetch(@v >> 2) + SUITS.fetch(@v & 3)
end
end
```

Create some cards:

```13.times do |r|
v = r << 2 | 3
c = Card.new(v)
puts c
end
```
```A♠
2♠
3♠
4♠
5♠
6♠
7♠
8♠
9♠
T♠
J♠
Q♠
K♠
```

Implement a class for decks:

```## <>
##   @a: Array<Card>
class Deck
N = Card::RANKS.size * Card::SUITS.size

## Generator -> void
def initialize(g)
super()
@a = Util.shuffle(g, N) { |v| Card.new(v) }
return
end

## -> String
def to_s
return @a.join(" ")
end
end
```

Create a deck:

```seed = 0x0000000000000000
g = Generator.new(seed)
d1 = Deck.new(g)
puts d1
```
```5♠ T♣ J♠ 5♣ 3♦ 9♦ 7♦ 6♥ J♥ A♣ 2♥ 6♠ K♦ ...
```

Create another deck using the same generator:

```# ...

d2 = Deck.new(g)
puts d2
```
```5♦ 5♣ 2♥ Q♠ 7♥ T♣ 3♠ J♠ 3♦ 9♥ 3♣ Q♥ 6♠ ...
```

Now break `java.util.Random`!

Can you determine the second deck given the first deck?

You can do it in three steps:

1. determine the outputs of the generator for the first deck (easy)
2. determine the state of the generator for the first deck (hard)
3. determine the outputs of the generator for the second deck (easy)

## That’s all folks Follow @InfraRuby on Twitter