Just a picture…

# Synacor Virtual Machine.

Just recently I came across the ‘Synacor VM’ challenge. The problem is an interesting exercise in implementing a virtual machine using a supplied architecture definition and then running the VM using the given binary file as input. When run the program is an adventure type game which many people have completed but I have, so far, resisted that temptation. So here’s the spec.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
-- -- == Synacor Challenge == In this challenge, your job is to use this architecture spec to create a virtual machine capable of running the included binary. Along the way, you will find codes; submit these to the challenge website to track your progress. Good luck! == architecture == - three storage regions - memory with 15-bit address space storing 16-bit values - eight registers - an unbounded stack which holds individual 16-bit values - all numbers are unsigned integers 0..32767 (15-bit) - all math is modulo 32768; 32758 + 15 => 5 == binary format == - each number is stored as a 16-bit little-endian pair (low byte, high byte) - numbers 0..32767 mean a literal value - numbers 32768..32775 instead mean registers 0..7 - numbers 32776..65535 are invalid - programs are loaded into memory starting at address 0 - address 0 is the first 16-bit value, address 1 is the second 16-bit value, etc == execution == - After an operation is executed, the next instruction to read is immediately after the last argument of the current operation. If a jump was performed, the next operation is instead the exact destination of the jump. - Encountering a register as an operation argument should be taken as reading from the register or setting into the register as appropriate. == hints == - Start with operations 0, 19, and 21. - Here's a code for the challenge website: mzMXMdUpOZeH - The program "9,32768,32769,4,19,32768" occupies six memory addresses and should: - Store into register 0 the sum of 4 and the value contained in register 1. - Output to the terminal the character with the ascii code contained in register 0. == opcode listing == halt: 0 stop execution and terminate the program set: 1 a b set register <a> to the value of <b> push: 2 a push <a> onto the stack pop: 3 a remove the top element from the stack and write it into <a>; empty stack = error eq: 4 a b c set <a> to 1 if <b> is equal to <c>; set it to 0 otherwise gt: 5 a b c set <a> to 1 if <b> is greater than <c>; set it to 0 otherwise jmp: 6 a jump to <a> jt: 7 a b if <a> is nonzero, jump to <b> jf: 8 a b if <a> is zero, jump to <b> add: 9 a b c assign into <a> the sum of <b> and <c> (modulo 32768) mult: 10 a b c store into <a> the product of <b> and <c> (modulo 32768) mod: 11 a b c store into <a> the remainder of <b> divided by <c> and: 12 a b c stores into <a> the bitwise and of <b> and <c> or: 13 a b c stores into <a> the bitwise or of <b> and <c> not: 14 a b stores 15-bit bitwise inverse of <b> in <a> rmem: 15 a b read memory at address <b> and write it to <a> wmem: 16 a b write the value from <b> into memory at address <a> call: 17 a write the address of the next instruction to the stack and jump to <a> ret: 18 remove the top element from the stack and jump to it; empty stack = halt out: 19 a write the character represented by ascii code <a> to the terminal in: 20 a read a character from the terminal and write its ascii code to <a>; it can be assumed that once input starts, it will continue until a newline is encountered; this means that you can safely read whole lines from the keyboard and trust that they will be fully read noop: 21 no operation |

I had a couple of attempts at this – in Haskell – and the main thing I learnt from this was… Yes, the Haskell type system is very expressive and allows for a sophisticated modelling Read More

# Continued Fractions Continued.

It seems to me that continued fractions (CFs) are perhaps too advanced for ‘A’ levels and too elementary for a degree maths course and are perhaps undervalued or ignored in schools and universities? Since my last post about fractions I’ve looked a little more at CFs and found they have applications ranging from factorising large numbers to gear ratio calculations. And they’re really interesting when their layers are peeled away with a bit of Haskell. So, a bit of playing with numbers and a bit of Haskelling- what’s not to like? Let’s start with a fraction, any fraction – say Read More

# Parsers to Fractions to Square Roots!

The earlier post Fractions to Phi to Fibonacci! showed a simple structure for Continued Fractions (CF) and used a CF representation of the Golden Ratio to derive the terms of the Fibonacci Sequence. It also alluded to a particular notation to express a CF and here we will describe that notation, create a parser for it and calculate the square roots of some integers from their specific CFs and finally derive a general CF that can be used to find the square root of any integer. CF List Notation Essentially the CF is written as a list of ints Read More

# Fractions to Phi to Fibonacci!

Oh no, not another Haskell way of calculating Fibonacci numbers! Well, yes but done perhaps slightly differently. This post brings together The Golden Ratio Fibonacci Numbers Continued Fractions The Golden Ratio (Phi) “…two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities.” This ratio appears often mathematics and in nature, perhaps almost as pervasive as pi. And there is the Golden Rectangle, a 2-D extension of the Golden Ratio, often used in art because of its intrinsically appealing properties. Fibonacci Numbers 0, 1, 1, Read More

# The expressiveness of Haskell – Random Numbers.

Back in the 1940s the mathematician John von Neumann invented the ‘middle square’ method of generating pseudo random numbers. The algorithm starts with a 4 digit number which is then squared. If the resulting number has fewer than 8 digits then it is padded with leading zeros. From this 8 digit number the middle 4 digits are extracted and returned as the result and also as input to repeating the algorithm. This implementation, in Haskell, will manipulate the digits of the number as a list and so in outline we need to take the seed number and ‘square it‘ then Read More

# The Root of the Problem. Part 2.

In the previous post I discussed an algorithm for calculating the square root of a number. This short post will show an implementation in Haskell. I did one implementation using the State Monad but to be quite honest it was an impenetrable mess! I’m sure part of that was down to my embryonic Haskell skills but perhaps the State Monad was a bad fit for this problem? The implementation below uses a fold over a list of digit pairs and the start state for the fold is based on ‘the largest integer squared’ with subsequent calculations using ‘doubling’ – as Read More

# Stateful Folding.

This is not a monad tutorial. These are my notes and code to help me grok monads. 🙂 As part of learning Haskell there is for some, perhaps many – including me, the ascent of Mount Monad! I’m finding the way to ‘get it’ is to keep chipping away at Monads, read, absorb, write some code then rinse and repeat! This creates a familiarity with the symbols, with the do, >>= and >> being different faces of the same coin. As part of this launderette of code I started writing simple Haskell functions and then pulled them apart and rewrote Read More

# The expressiveness of Haskell – Substrings.

Earlier today I was talking with a colleague about extracting a substring of a string given the start and end indices. He showed me an implementation in Javascript and I wrote one in Java and then looked at the Java 8 implementation which I’ve pasted below.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
public String substring(int beginIndex, int endIndex) { if (beginIndex < 0) { throw new StringIndexOutOfBoundsException(beginIndex); } if (endIndex > value.length) { throw new StringIndexOutOfBoundsException(endIndex); } int subLen = endIndex - beginIndex; if (subLen < 0) { throw new StringIndexOutOfBoundsException(subLen); } return ((beginIndex == 0) && (endIndex == value.length)) ? this: new String(value, beginIndex, subLen); } |

If we reformatted this we’d have 6 lines of code. Now for some Haskell… What is it we do when extracting a substring? For me, I think of it as taking the string, dropping the chars up to the start index and then from that getting chars up to the end index and Read More

# The Root of the Problem. Part 1.

I suppose since the advent of cheap calculators the task of working out the square root of a number has become simply a matter of pressing a few buttons and reading off the answer. But there was a time when we didn’t have calculators or slide rules or log tables – like these! Before all of these we used one of several ways to calculate a square root. One technique, which I’ll describe, is a bit like long division and works like this… First off group the numbers in pairs starting from the least significant digit before any decimal point Read More