From F# to Scala – type inference

It’s a new year, a new job, a new language (Scala) and runtime (JVM) to work with.

After a week of learning about my new surroundings at Space Ape Games and getting up to speed with Scala I have learnt a fair bit. In my own journey (aided by Twitter’s Scala School, Odersky’s Coursera course and Effective Scala) I found the target audience for a lot of online materials is Java developers, or developers who are new to functional programming.

As a proficient F# developer, a lot of the FP concepts translate quite easily to Scala (albeit with a different, more verbose syntax). However, Scala does have a lot of language features that do not exist in F# and many things (such as type inference) work slightly differently and can bite you in subtle ways if caught unaware of these differences.

So, for anyone coming into Scala from F#, I hope I can provide some useful info based on the things that I found interesting in my journey.

One of those things is how type inference differs in the two languages.

 

F# uses a Hindley-Milner type inference system similar to its ML brethren, but Scala’s type inference works slightly differently.

Take the following example for instance, this bit of code works just fine in F#.

but the same doesn’t work in Scala…

unless you explicitly specify the type parameter for toList.

Interestingly, if you rewrite the function in curried form then the Scala compiler is able to infer the type for toList.

but the order of parameters matters somehow..

which I eventually understood thanks to some helpful folks on Twitter.

 

Although less restrictive, this limitation of only being able to unify types from left to right also applies to F#.

For example, a simple example using the backward pipe (<|) is enough to cause the compiler to bark.

I hope this has been useful for you, over the next weeks or months I should be adding more posts to this series as I better familiarise myself with Scala, both in terms of language features as well as the toolchain/ecosystem around it.

See here for the rest of the series (as they become available).

Advent of Code F# – Day 25

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 25

See details of the challenge here.

Today’s input looks like this:

cpy a d
cpy 7 c
cpy 362 b
inc d
dec b
jnz b -2

At last, we’re at the end of this year’s Advent of Code challenges, and today’s challenge is another twist of the assembunny code we’ve seen a few times this year, most recently on Day 23.

Ad before, let’s define the instruction set as a union type and make short work of the parsing the input file.

One notable difference to today’s challenge though is that we’re no longer interested in the value of the registers but the output from executing the program.

So instead of returning the registers we’ll use a sequence comprehension to return the output values as an infinite, and lazy sequence instead.

(ps. I initially wrote the execute function with a nested recursive function, but on second thought the problem feels more concisely expressed as a while loop so I rewrote it as such)

To wrap up today’s challenge (part 2 just requires you to click a link to wrap up your AOC journey for another year) we need to find the first value of n that will yield pairs of [ 0, 1 ] indefinitely. Of course you can’t be sure that the pattern repeats indefinitely without deeper understanding of the pattern of change in the register values (perhaps it’d be a better approach rather than the trial-and-error route I have gone with). I have gone with 1000 values all following that pattern = repeating indefinitely, but turns out the answer is the same even when you use Seq.take 10.

So there it is folks, another year and another set of wonderfully enjoyable challenges. With you all a happy new year and see you soon!

 

Links

Advent of Code F# – Day 24

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 24

See details of the challenge here.

Today’s challenge is a mix of Breadth-First Search (or Level Order Tree Traversal) and the Travelling Salesman Problem.

First, let’s parse the input file into a 2D array to make it easier for us to work with.

My first attempt at solving this challenge with the same BSF approach that has been so useful in this year’s AOC challenges proved unsuccessful. Unlike previous challenges, today’s problem can involve backtracking so we can’t rely on a naive cache of positions we have passed through thus far.

However, we can still use BSF to find out the shortest distance between any two numbered nodes.

From here, we can build up a dictionary of the distance between every pair of numbered nodes and turn this BSF problem into a Travelling Salesman Problem and find the path through all the numbered nodes with the lowest total distance.

Now we can solve part 1 of the challenge with a simple recursive function.

This solution ran in 109ms on my laptop, including the time to build up the distances between pairs of nodes.

 

Part 2

Of course, if you leave the cleaning robot somewhere weird, someone is bound to notice.

What is the fewest number of steps required to start at 0, visit every non-0 number marked on the map at least once, and then return to 0?

A slight twist on part 1, but we can use the same approach as before but simply stipulate that when all numbered nodes have been traversed we also take into account the distance from the last node back to number 0.

This ran in 113ms on my laptop, including the time to build up the distance between pairs of nodes (or, 14ms if reusing the existing pairDistances)

 

Links

Advent of Code F# – Day 23

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 23

See details of the challenge here.

Today’s input looks like this:

cpy a b
dec b
cpy a d
cpy 0 a
cpy b c
inc a

..

Today’s challenge is an extension to Day 12, where we have introduced a new instruction for toggle (tgl). To make toggling logic simpler let’s introduce a union type to represent the different instructions we can receive and write a function parse them.

Next, let’s add a toggle function to toggle a given instruction and modify the execute function from Day 12 to work with the union type and support the new tgl instruction as well.

Now we can solve part 1.

let part1 = (execute [ “a”, 7 ] inputs).[“a”]

 

Part 2

The safe doesn’t open, but it does make several angry noises to express its frustration.

You’re quite sure your logic is working correctly, so the only other thing is… you check the painting again. As it turns out, colored eggs are still eggs. Now you count 12.

As you run the program with this new input, the prototype computer begins to overheat. You wonder what’s taking so long, and whether the lack of any instruction more powerful than “add one” has anything to do with it. Don’t bunnies usually multiply?

Anyway, what value should actually be sent to the safe?

As the description eludes to, if we use 12 as initial input it might take a while to run.. and the naive approach of just executing the logic as before, ie

let part2 = (execute [ “a”, 12 ] inputs).[“a”]

took a good 4 minutes to run on my 2015 MBP.

If you add a few printfn statements and you’ll a few blocks of instructions that repeat for many cycles, eg.

cpy b c
inc a
dec c
jnz c -2
dec d
jnz d -5

you can add a short-circuit when you see this happen and replace it with the equivalent of a = b * d (as the description eluded to).

 

Links

Advent of Code F# – Day 22

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 22

See details of the challenge here.

Today’s input looks like this:

root@ebhq-gridcenter# df -h
Filesystem                           Size    Used     Avail    Use%
/dev/grid/node-x0-y0     87T     71T     16T       81%
/dev/grid/node-x0-y1     93T     72T      21T       77%
/dev/grid/node-x0-y2     87T     67T      20T       77%
/dev/grid/node-x0-y3     89T     65T      24T       73%
/dev/grid/node-x0-y4     93T     67T      26T       72%

Of the information presented to us we only need the x & y position of the node, its size and amount of space used. Everything else can either be derived from these or are not needed for this challenge.

For part 1 of the challenge, if we sort the array of nodes by the amount of available space in descending order, then for each of the elements we only need to iterate through the sorted array for as long as the available space is >= the used space of the current node. Hence reducing the average time complexity from O(n2) to O(n * log n).

 

Part 2

Now that you have a better understanding of the grid, it’s time to get to work.

Your goal is to gain access to the data which begins in the node with y=0 and the highest x (that is, the node in the top-right corner).

For example, suppose you have the following grid:

Filesystem            Size  Used  Avail  Use%
/dev/grid/node-x0-y0   10T    8T     2T   80%
/dev/grid/node-x0-y1   11T    6T     5T   54%
/dev/grid/node-x0-y2   32T   28T     4T   87%
/dev/grid/node-x1-y0    9T    7T     2T   77%
/dev/grid/node-x1-y1    8T    0T     8T    0%
/dev/grid/node-x1-y2   11T    7T     4T   63%
/dev/grid/node-x2-y0   10T    6T     4T   60%
/dev/grid/node-x2-y1    9T    8T     1T   88%
/dev/grid/node-x2-y2    9T    6T     3T   66%

In this example, you have a storage grid 3 nodes wide and 3 nodes tall. The node you can access directly, node-x0-y0, is almost full. The node containing the data you want to access, node-x2-y0 (because it has y=0 and the highest x value), contains 6 terabytes of data – enough to fit on your node, if only you could make enough space to move it there.

Fortunately, node-x1-y1 looks like it has enough free space to enable you to move some of this data around. In fact, it seems like all of the nodes have enough space to hold any node’s data (except node-x0-y2, which is much larger, very full, and not moving any time soon). So, initially, the grid’s capacities and connections look like this:

( 8T/10T) --  7T/ 9T -- [ 6T/10T]
    |           |           |
  6T/11T  --  0T/ 8T --   8T/ 9T
    |           |           |
 28T/32T  --  7T/11T --   6T/ 9T

The node you can access directly is in parentheses; the data you want starts in the node marked by square brackets.

In this example, most of the nodes are interchangable: they’re full enough that no other node’s data would fit, but small enough that their data could be moved around. Let’s draw these nodes as .. The exceptions are the empty node, which we’ll draw as _, and the very large, very full node, which we’ll draw as #. Let’s also draw the goal data as G. Then, it looks like this:

(.) .  G
 .  _  .
 #  .  .

The goal is to move the data in the top right, G, to the node in parentheses. To do this, we can issue some commands to the grid and rearrange the data:

  • Move data from node-y0-x1 to node-y1-x1, leaving node node-y0-x1empty:
    (.) _  G
     .  .  .
     #  .  .
    
  • Move the goal data from node-y0-x2 to node-y0-x1:
    (.) G  _
     .  .  .
     #  .  .
    
  • At this point, we’re quite close. However, we have no deletion command, so we have to move some more data around. So, next, we move the data from node-y1-x2 to node-y0-x2:
    (.) G  .
     .  .  _
     #  .  .
    
  • Move the data from node-y1-x1 to node-y1-x2:
    (.) G  .
     .  _  .
     #  .  .
    
  • Move the data from node-y1-x0 to node-y1-x1:
    (.) G  .
     _  .  .
     #  .  .
    
  • Next, we can free up space on our node by moving the data from node-y0-x0 to node-y1-x0:
    (_) G  .
     .  .  .
     #  .  .
    
  • Finally, we can access the goal data by moving the it from node-y0-x1to node-y0-x0:
    (G) _  .
     .  .  .
     #  .  .
    

So, after 7 steps, we’ve accessed the data we want. Unfortunately, each of these moves takes time, and we need to be efficient:

What is the fewest number of steps required to move your goal data to node-x0-y0?

If you visualize the grid then the solution becomes pretty clear and one that we can actually work out by hand.

Here, the target node is marked as red, the empty node green (which is initially at position (7, 17)), and the very large, very full nodes are marked as black. We want to move the empty node all the way to (35, 0) so we can start moving the target node at (36, 0) horizontally towards (0, 0).

We can again use the Level Order Tree Traversal approach we have seen so many times this AOC for the first part. First, let’s transform the Node[] into a 2D array first to make our task easier.

The trick for the traversal part of the problem is to avoid passing through the same coordinate more than once, a problem that can be easily rectified with a cache of positions that we have already passed through.

Once the empty node is at (35, 0) we can commence the second part of the problem – to move the data in the target node to (0, 0). Every time we move the data to the empty node on the left, we’ll have to move the empty node in front of it again, which means going down, left, left and then up, so that means a total of 5 moves for every step towards (0, 0). Except, when the data is at (1, 0), which requires only one move.

Which means, there’s a total of 5 * 35 + 1 move left ONCE we have move the empty node to (35, 0).

In case you’re wondering why I left out the “+ 1” on line 33, it’s because the path that’s returned by findPaths includes the starting position (7, 17), so really line 33 should have read let part2 = path.Length – 1 + 35 * 5 + 1

 

Links