The Drunken Bishop

In public-key cryptography, a public key fingerprint is a short sequence of bytes used to identify a longer public key.

In SSH in particular they can be used to verify that a server is in fact the server I'm expecting to communicate with and I'm not targeted by a man-in-the-middle attack.

They are usually represented as a string of hexadecimal digits, so it can be rather boring and tedious to compare it with the fingerprint I would expect:

37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e


To make it a little easier, OpenSSH has introduced a method to visualize fingerprints as ASCII art, that would look like the following:

+-----------------+
|                 |
|                 |
|          .      |
|     .   o       |
|o . o . S +      |
|.+ + = . B .     |
|o + + o B o E    |
| o .   + . o     |
|         .o      |
+-----------------+


With this, I could try to remember the rough shape of the ASCII art and would then (theoretically) recognize it when the fingerprint of the server changed and the image looks different.

How it works

Taken from Dirk Loss, Tobias Limmer, Alexander von Gernler. 2009. The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm.

The grid has a width of 17 characters and a height of 9 characters. The "bishop" starts at row 4/column 8 (the center). Each position can be denoted as [x,y], i.e. [8,4] for the starting position of the bishop.

            1111111
01234567890123456
+-----------------+
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
+-----------------+


The bishop uses the fingerprint to move around. It reads it byte-wise from left to right and from the least significant bit to the most significant bit:

Fingerprint      37      :       e4      :       6a      :  ...  :       5e
Bits        00 11 01 11  :  11 10 01 00  :  01 10 10 10  :  ...  :  01 01 11 10
|  |  |  |      |  |  |  |      |  |  |  |              |  |  |  |
Step         4  3  2  1      8  7  6  5     12 11 10  9             64 63 62 61


The bishop will move by the following plan:

Bits   Direction
-----------------
00     Up/Left
01     Up/Right
10     Down/Left
11     Down/Right


Special cases:

• If the bishop is in a corner and would move into the corner again, he doesn't move at all. i.e: The bishop is at [0,0] and his next step would be 00. He remains at [0,0]
• If the bishop is in a corner or at a wall and would move into one of the walls, he moves horizontally or vertically only. i.e: The bishop is at [0,5] and his next step would be 01. He cannot go left, so he just moves up, to [0,4].

Each position holds a value of how often the bishop has visited this field:

Value      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
Character  |   | . | o | + | = | * | B | O | X | @ | % | & | # | / | ^ | S | E |


The values 15 (S) and 16 (E) are special in that they mark the start and end position of the bishop respectively and overwrite the real value of the respecting position.

Goal

Create a program, that takes an alphanumeric fingerprint as input and produces its ASCII art representation as shown in the examples.

Examples

Input:
16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48

Output:
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+

Input:
b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b

Output:
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

Input:
05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47

Output:
+-----------------+
|       o=.       |
|    o  o++E      |
|   + . Ooo.      |
|    + O B..      |
|     = *S.       |
|      o          |
|                 |
|                 |
|                 |
+-----------------+


Rules

• This is . The code in the fewest bytes wins.
• You can not use an existing library that produces the image.
• Use whichever language you prefer!
• Your submission has to be a complete program
• Can we assume that no cell will be visited more than 14 times? – Martin Ender Oct 5 '15 at 5:21
• There are a few corner cases of minimal coverage that would result in a few fields being visited more than 14 times. 33:33:33:...:33, cc:cc:cc:...:cc would be examples for this. The fingerprint is usually a MD5 hash, so it's highly unlikely you get such a result. I haven't found any reliable sources on how to deal with these, so for now I'd say: Assume no cell will be visited more than 14 times. – Padarom Oct 5 '15 at 5:51

Pyth, 125 bytes

Jj*17\-"++"JVc9XXsm@"^ .o+=*BOX@%&#/"hdrS+*U9U17K.u.e@S[0b*8hk)1.b+tNyYNYsm_c4.[08jxsM^.HM16 2d2cz\:,4 8 8ieK17\E76\SjN"||")J


Try it online: Demonstration or Test-Suite

I wrote a few days ago, but didn't post it, because I wasn't really happy about it.

Explanation:

The basic idea is the following. I start with the pair (4, 8). In each move (m1,m2) I go from the (x, y) to (x-1+2*m1, y-1+2*m2). To make sure, that these coordinates don't go outside the boarders, I'll make some lists, sort them and return the middle element: (sorted(0,8,newx)[1], sorted(0,16,newy)[1]).

I keep track of all positions. To this list of positions I add a list of all possible positions, sort them and run-length-encode them. Which gives me a number for each position. With this number I can choose the coorect char, and at the end overwrite the chars of the start and end position.

Dyalog APL (178)

{⎕ML←3⋄F←9 17⍴0⋄5 9{(⍺⌷F)+←1⋄×⍴⍵:(1 1⌈9 17⌊⍺-1 1-2×↑⍵)∇1↓⍵⋄(⍺⌷F)←16⋄F[5;9]←15⋄K⍪(M,' .o+=*BOX@%&#/^SE'[1+F],M←'|')⍪K←'+','+',⍨17⍴'-'}⊃,/{↓⊖4 2⍴⍉(4/2)⊤¯1+⍵⍳⍨⎕D,'abcdef'}¨⍵⊂⍨':'≠⍵}


This is a function that takes the string as its right argument, and returns a character matrix containing the ASCII art representation, e.g.:

      F←{⎕ML←3⋄F←9 17⍴0⋄5 9{(⍺⌷F)+←1⋄×⍴⍵:(1 1⌈9 17⌊⍺-1 1-2×↑⍵)∇1↓⍵⋄(⍺⌷F)←16⋄F[5;9]←15⋄K⍪(M,' .o+=*BOX@%&#/^SE'[1+F],M←'|')⍪K←'+','+',⍨17⍴'-'}⊃,/{↓⊖4 2⍴⍉(4/2)⊤¯1+⍵⍳⍨⎕D,'abcdef'}¨⍵⊂⍨':'≠⍵}

F '16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48'
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+
F 'b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b'
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+


Explanation:

• ⎕ML←3: set ⎕ML to 3. This makes ⊂ more useful for splitting strings.

• F←9 17⍴0: make a 17-by-9 matrix of zeroes. F represents how many times each position has been visited.

• ⍵⊂⍨':'≠⍵: split ⍵ on : characters.

• {...}¨: for each group:
• ¯1+⍵⍳⍨⎕D,'abcdef': find the index of each character in the string '01234567890abcdef'. Subtract 1, because APL is 1-indexed by default.
• (4/2)⊤: convert the values to their 4-bit representations (there should now be 2-by-4 matrix).
• ↓⊖4 2⍴⍉: rotate the matrix, use the elements to fill a 2-by-4 matrix instead, mirror that matrix horizontally, and then get each line separately. This gives us the 4 2-bit values we need.
• ⊃,/: join the resulting lists together, giving a list of 2-bit steps.
• 5 9{...}: given the list of steps, and starting at position [9,5]:
• (⍺⌷F)+←1: increment the current position in F.
• ×⍴⍵:: if the list of steps is not empty:
• ↑⍵: take the first step from the list
• ⍺-1 1-2×: get the delta for that step, and subtract it from the current position
• 1 1⌈9 17⌊: restrict movement to within the field
• (...)∇1↓⍵: continue with the new position and the rest of the steps
• If it is empty:
• (⍺⌷F)←16: set F to 16 at the final position
• F[5;9]←15: set F to 15 at the start position
• ' .o+=*BOX@%&#/^SE'[1+F]: map each position to the corresponding character
• K⍪(M,...,M←'|')⍪K←'+','+',⍨17⍴'-': wrap the result in lines

Perl, 300 + 1 (-n) = 301 bytes

perl -ne 'sub b{$b=$_[0]+$_[1];$_[0]=$b<0?0:$b>$_[2]?$_[2]:$b}$v=pack"(H2)*",/\w\w/g;($x,$y)=(8,4);$a[b($y,($_&2)-1,8)*17+b($x,($_&1)*2-1,16)]++for map{vec$v,$_,2}0..63;@a[76,$y*17+$x]=(15,16);$c=" .o+=*BOX@%&#/^SE";print$d="+".("-"x17)."+\n",(map{+"|",(map{substr$c,$_,1}@a[$_*17..($_+1)*17-1]),"|\n"}0..8),$d'


This answer is disgusting, but it's also the first one for this puzzle, so it'll do for now.

-n to take a line of input on STDIN and fill $_. # b($v, -1 or 1, max) modifies $v within 0..max sub b{$b=$_[0]+$_[1];$_[0]=$b<0?0:$b>$_[2]?$_[2]:$b}

# turn $_ into a binary string$v=pack"(H2)*",/\w\w/g;

# initialize cursor
($x,$y)=(8,4);

# find an element of single-dimensional buffer @a
$a[ # y += (bitpair & 2) - 1, within 8 b($y,($_&2)-1,8) * 17 # x += (bitpair & 1) * 2 - 1, within 17 + b($x,($_&1)*2-1,16) # and increment it ]++ # for each bit pair (in the right order!) for map{vec$v,$_,2}0..63; # overwrite the starting and ending positions @a[76,$y*17+$x]=(15,16); # ascii art lookup table$c=" .o+=*BOX@%&#/^SE";

# output
print
# the top row, saving it for later
$d="+".("-"x17)."+\n", # each of the eight middle rows (map{+ # converting each character in @a in this row as appropriate "|",(map{substr$c,$_,1}@a[$_*17..($_+1)*17-1]),"|\n" }0..8), # the bottom row$d


R, 465459410393382 357 bytes

f=function(a){s=strsplit;C=matrix(as.integer(sapply(strtoi(el(s(a,":")),16),intToBits)[1:8,]),2);C[!C]=-1;n=c(17,9);R=array(0,n);w=c(9,5);for(i in 1:64){w=w+C[,i];w[w<1]=1;w[w>n]=n[w>n];x=w[1];y=w[2];R[x,y]=R[x,y]+1};R[]=el(s(" .o+=*BOX@%&#/^",""))[R+1];R[9,5]="S";R[x,y]="E";z="+-----------------+\n";cat(z);for(i in 1:9)cat("|",R[,i],"|\n",sep="");cat(z)}


With indentations and newlines:

f=function(a){
s=strsplit
C=matrix(as.integer(sapply(strtoi(el(s(a,":")),16),intToBits)[1:8,]),2)
C[!C]=-1
n=c(17,9)
R=array(0,n)
w=c(9,5)
for(i in 1:64){
w=w+C[,i]
w[w<1]=1
w[w>n]=n[w>n]
x=w[1]
y=w[2]
R[x,y]=R[x,y]+1
}
R[]=el(s(" .o+=*BOX@%&#/^",""))[R+1]
R[9,5]="S"
R[x,y]="E"
z="+-----------------+\n"
cat(z)
for(i in 1:9)cat("|",R[,i],"|\n",sep="")
cat(z)
}


Usage:

> f("16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48")
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+
> f("37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e")
+-----------------+
|                 |
|                 |
|          .      |
|     .   o       |
|o . o . S +      |
|.+ + = . B .     |
|o + + o B o E    |
| o .   + . o     |
|         .o      |
+-----------------+

• Cant you golf the 'matrix' function by defining it once as 'm'? Same for 'function'? – CousinCocaine Oct 5 '15 at 10:18
• I think you do not need 'sep=' in the 'cat' function – CousinCocaine Oct 5 '15 at 10:20
• the default for sep is a space, so i need to override it, but indeed I could alias matrix. – plannapus Oct 5 '15 at 12:00
• Additionnaly, as far as I know, you can't alias function. – plannapus Oct 5 '15 at 12:04

Octave, 277

d=reshape(rot90(dec2bin(hex2dec(strsplit(input('','s'),':'))))>'0',2,[])*2-1;p=[9;5];for m=1:64 p=[max(min(p(:,1)+d(:,m),[17;9]),1) p];end;A=' .o+=*BOX@%&#/^SE';F=A(sparse(p(2,:),p(1,:),1,9,17)+1);F(5,9)='S';F(p(2,1),p(1,1))='E';[a='+-----------------+';b=['|||||||||']' F b;a]


Explanation:

%// convert the input to binary and rearrange it to be
%//   an array of vectors: [x_displacement; y_displacement]
d=reshape(rot90(dec2bin(hex2dec(strsplit(input('','s'),':'))))>'0',2,[])*2-1;

%// start position array with vector for the start position
p=[9;5];
%// for each move, add displacement, clamping to valid values
for m=1:64 p=[max(min(p(:,1)+d(:,m),[17;9]),1) p];end;

%// alphabet for our fingerprint
A=' .o+=*BOX@%&#/^SE';

%// create a sparse matrix, accumulating values for duplicate
%// positions, and replace counts with symbols
F=A(sparse(p(2,:),p(1,:),1,9,17)+1);

%// correct the start and end symbols and construct the final output
F(5,9)='S';F(p(2,1),p(1,1))='E';
[a='+-----------------+';b=['|||||||||']' F b;a]


Sample run:

>> bish
b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b
ans =

+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+


Pyth, 145143 140

Jm*17]09A,4K8FYcz\:V4AmhtS[0^2d+@,HGdtyv@+_.BiY16*7\0+-4dyN),3 4 X@JGHh@@JGH; X@J4K15 X@JGH16
=Y++\+*17\-\+VJ++\|s@L" .o+=*BOX@%&#/^SE"N\|)Y


Try it online.

Pyth isn't really good at challenges with iteration. I'm expecting CJam to beat it easily.

JavaScript (ES6) 249 208

Test running the snippet below in any EcmaScript 6 compliant browser

B=f=>f.replace(/\w+/g,b=>{for(b=0x1${b};b-1;b>>=2)++g[p=(q=(p=(q=p+~-(b&2)*18)>0&q<162?q:p)+b%2*2-1)%18?q:p]},p=81,z=+${'-'.repeat(17)}+,g=Array(162).fill(0))&&g.map((v,q)=>q?q-81?q-p?q%18?' .o+=*BOX@%&#/^'[v]:|
|:'E':'S':z+
|).join+|
+z

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;['37:e4:6a:2d:48:38:1a:0a:f3:72:6d:d9:17:6b:bd:5e'
,'16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48'
,'b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b'
,'05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47'
].forEach(t=>console.log(t+'\n'+B(t)+'\n'))

// Less golfed

BB=f=>(
p = 81,
g = Array(162).fill(0),
f.replace(/\w+/g, b => {
for(b = 0x1\${b};b != 1; b >>= 2)
q = p+~-(b&2)*18,
p = q>0&q<162?q:p,
p = (q=p+b%2*2-1)%18?q:p,
++g[p]
}),
g.map((v,q) => q-81?q-p?q%18?' .o+=*BOX@%&#/^'[v]:'\n':'E':'S')
.join
)
pre { font-family: menlo,consolas; font-size:13px }
<pre id=O></pre>

• Your golfed code itself should be capable to print the borders too. Currently only your test case prints the upper and lower borders in the forEach, the vertical borders are still missing. – Padarom Oct 9 '15 at 14:36
• @Padarom I misunderstood your "be reasonable" comment, thinking that the border was not requested – edc65 Oct 9 '15 at 14:49
• I meant be reasonable as to which method of input and output you use. My apologies if that was misleading, I'll edit it out – Padarom Oct 9 '15 at 15:08

Python, 381328

-51 thanks to @JonathanFrech

def h(f):
s=[f'{int(o,16)>>s&3:02b}'for o in f.split(':')for s in(0,2,4,6)];r=[0]*153;p=76;w=17
for d in s:r[p]+=1;p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]
r[76]=15;r[p]=16;b='+'+'-'*w+'+';print(b);i=0
while i<153:print(f"|{''.join(' .o+=*BOX@%&#/^SE'[c]for c in r[i:i+w])}|");i+=w
print(b)


Slightly ungolfed for the sake of explanation:

def h_(f):
#Alias 17 because it gets used enough times for this to save bytes
w=17

#Input parsing
s=[f'{int(o,16)>>s&3:02b}'for o in f.split(':')for s in(0,2,4,6)]

#Room setup
r=[0]*153
p=76

#Apply movements
for d in s:
r[p]+=1
p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]
r[76]=15 #Set start position
r[p]=16 #Set end position

#Display result
b='+'+'-'*w+'+'
print(b)
i=0
while i<153:
print(f"|{''.join(' .o+=*BOX@%&#/^SE'[c]for c in r[i:i+w])}|")
i+=w
print(b)


This mess of a line:

r[p]+=1;p+=(-(p%w!=0),p%w!=16)[int(d[1])]+(-w*(p//w!=0),w*(p//w!=8))[int(d[0])]


​ is functionally equivalent to this:

if int(d[0]): #Down, Y+
if p//17!=8:
p+=17
else: #Up, Y-
if p//17!=0:
p-=17
​
if int(d[1]): #Right, X+
if p%17!=16:
p+=1
else: #Left, X-
if p%17!=0:
p-=1


but nests all of the conditionals in this style of golf shortcut: (false_value,true_value)[condition] Hopefully the rest is fairly self-explanatory

Tests

h('16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48')
+-----------------+
|        .        |
|       + .       |
|      . B .      |
|     o * +       |
|    X * S        |
|   + O o . .     |
|    .   E . o    |
|       . . o     |
|        . .      |
+-----------------+

h("b6:dd:b7:1f:bc:25:31:d3:12:f4:92:1c:0b:93:5f:4b")
+-----------------+
|            o.o  |
|            .= E.|
|             .B.o|
|              .= |
|        S     = .|
|       . o .  .= |
|        . . . oo.|
|             . o+|
|              .o.|
+-----------------+

h("05:1e:1e:c1:ac:b9:d1:1c:6a:60:ce:0f:77:6c:78:47")
+-----------------+
|       o=.       |
|    o  o++E      |
|   + . Ooo.      |
|    + O B..      |
|     = *S.       |
|      o          |
|                 |
|                 |
|                 |
+-----------------+
$$$$

• Hello and welcome to PPCG. You can golf your code by using one-letter variable names and putting a single-line-for-loop into one line. (1,0)[p%17==16] is +(p%17!=16), or possibly even p%17!=16. – Jonathan Frech Feb 21 at 19:02
• Furthermore, there is a superfluous space in ] for. – Jonathan Frech Feb 21 at 20:29
• I think fp should be f. – Jonathan Frech Feb 21 at 20:30
• – Jonathan Frech Feb 21 at 20:34
• Why did I use ~16? A bit of obfuscation can never hurt your golf! – Jonathan Frech Feb 21 at 23:43

Ruby 288

->k{w=17
r=[z=?++?-*w+?+]
(0...w*9).each_slice(w).map{|o|r<<?|+o.map{|x|c=76
q=0
k.split(?:).flat_map{|b|(0..7).map{|i|b.to_i(16)[i]}}.each_slice(2){|h,v|v<1?(c>w&&c-=w):c<w*8&&c+=w
c+=h<1?c%w>0?-1:0:c%w<16?1:0
c==x&&q+=1}
x==76?'S':c==x ?'E':' .o+=*BOX@%&#/^'[q]}.join+?|}
(r+[z]).join'
'}


Try it online: http://ideone.com/QOHAnM

The readable version (the one I started golfing from) is here: http://ideone.com/XR64km

C - 488

There must be a way to make this smaller....

#include<stdio.h>
#define H ++p;h[i]|=(*p-(*p>58?87:48))<<
#define B ((h[j]>>n*2)&3)
#define L puts("+-----------------+")
#define F(m,s)for(m=0;m<s;m++)
int h[16],m[17][9],i,j,n,x=8,y=4;main(w,v)char**v;{char*p=v[1]-1,c[17]={32,46,111,43,61,42,66,79,88,64,37,38,35,47,94,83,69};for(;*p;p++,i++){H 4;H 0;}F(j,16)F(n,4){if(B&1)x+=!(x==16);else x-=!(x==0);if(B&2)y+=!(y==8);else y-=!(y==0);m[x][y]++;}m[8][4]=15;m[x][y]=16;L;F(i,9){printf("|");F(j,17)printf("%c",c[m[j][i]]);puts("|");}L;}


Rust - 509 bytes

fn b(s:&str)->String{let(mut v,mut b)=([[0;11];20],[9,5]);v[19]=[19;11];for i in 0..16{let mut c=usize::from_str_radix(&s[i*3..i*3+2],16).unwrap();for k in 0..4{for j in 0..2{v[j*18][i%9+1]=18;v[i+k][j*10]=[17,3][(i+k+17)%18/17];b[j]=match(if c&(j+1)==j+1{b[j]+1}else{b[j]-1},j,){(0,_)=>1,(18,0)=>17,(10,1)=>9,x@_=>x.0 as usize,}}v[b[0]][b[1]]+=1;c>>=2;}}v[9][5]=15;v[b[0]][b[1]]=16;(0..220).fold("\n".to_string(),|s,i|{format!("{}{}",s," .o+=*BOX@%&#/^SE-|\n".chars().nth(v[i%20][i/20] as usize).unwrap())})}
`

Large but... almost close to C. As usual there are many bytes used up due to the way Rust does not automagically cast types into each other. But there is also probably room for improvement.... could probably use some ideas from other solutions.

ungolfed version is on the Rust Playground online