Up to Main Index                          Up to Journal for December, 2024

                   JOURNAL FOR SATURDAY 28TH DECEMBER, 2024
______________________________________________________________________________

SUBJECT: Advent of Code and Mote
   DATE: Sat 28 Dec 20:36:53 GMT 2024

During December I've been following the Advent Of Code[1] again. This year I
used Mote, my Mere rewrite, for writing solutions. My objective was to have
fun and maybe find bugs, shortfalls or performance issues in Mote. Previously
I had used Mere to write solutions with great success - lots of performance
issues and bugs.

Over the 25 days of AoC I didn't do too bad. I managed to get 43 out of 50
stars. I'm still working on a few of the problems and the last star I can't
get until I get all of the 49 other stars first.

I think the most interesting problem was day 19. You are given a set of towel
patterns where w=white, u=blue, b=black, r=red and g=green. For example:


    r, wr, b, g, bwu, rb, gb, br


You are then given a list of designs. For example:


    brwrr
    bggr
    gbbr
    rrbgbr
    ubwu
    bwurrg
    brgr
    bbrgwb


For part one you have to determine how many of the designs are possible given
the list of patterns. In the above example 6 are valid designs and 2 are not.

For the actual puzzle there are 447 patterns and 400 designs. The designs are
also a lot longer. For example:


    wrbwgruugbbgwwurggwrgrrrurbgwbgggwbbgwgbrwggwur
    bururbrguwurbguwrubbbbbuburuuuwbgbgrwggbugrwrwurwwbrb
    wgwgwbwuggbbwbrbgrwwgwbrbwbrbggrrgburbubwwur
    wguwuugubwggburwwbbbbwrgwbrwuubgbbrugrbrrbrrugwuwguwrwwwur
    rubwururuggurrgbgrburbrgbuuuuurwgubbbrbuwwbgbwgwrb


This was my complete solution:


    results = [bool] false 0, true 0

    mRE = regexp(`^(` + (input ~s ", " "|") + `)+$`)

    for input; !EOF;
      towel = input
      is towel == ""; break
      results[towel ~m mRE]++
    next

    println "valid: " results[true] " invalid: " results[false]
    println elapsed()["autoMicro"]


I basically take the input patterns and build a large regular expression.
Using the example, the regular expression would be:


    ^(r|wr|b|g|bwu|rb|gb|br)+$


Remember, for the actual puzzle input we have 447 patterns and the designs are
long. Applying the regular expression would involve a lot of alternations. I
didn't have much hope and thought my solution would choke. However, it seems
that Go's RE2 implementation for regular expressions deserves much more credit
than I give it. Here are my actual results:


    >cat 19input.txt | mote ./19.src
    valid: 311 invalid: 89
    179.423ms
    >


Quite impressive! One more gold star gained :)

For the second part of the puzzle, and another gold star, you have to work out
how many different combinations of patterns can be used to make the valid
designs. For the patterns and designs I was given there were 616234236468263
different combinations. Just over six hundred and sixteen trillion! This was
my solution:


    memo = [string]()
    pat  = []regexp

    line = input
    mRE  = regexp `^(` + (line ~s `, ` "|") + `)+$`
    range ; p; line ~c `, `
      pat[] = regexp (`^` + p)
    next

    sum = 0
    for input; !EOF;
      towel = input
      is towel == ""; break
      is towel ~m mRE; sum += @match towel 0
    next

    println "sum: " sum
    println elapsed()["autoMicro"]

    func match towel combo
      is exists $memo[towel]; return combo+$memo[towel]
      range ; p; $pat
        is towel ~v p; continue
        _towel = towel ~s p ""
        if _towel != ""
          m = @match _towel 0
          $memo[_towel] = m
          combo += m
        else
          combo++
        fi
      next
      return combo
    end


How did it fare this time?


  >cat 19input.txt | mote ./19b.src
  sum: 616234236468263
  4.92268s
  >


Just under 5 seconds. Not too shabby for calculating over six hundred and
sixteen trillion combinations. The solution uses a recursive match function
with memoisation.

I also tested my solutions on some Raspberry Pi. An 8Gb RPi4 managed 772.733ms
and 23.525s, an RPi Zero W managed 9.764s - but couldn't run the 2nd part as
616234236468263 does not fit into a 32 bit integer :/

Now why am I bothering to share all this? Well, it proves Mote is very capable
as a programming language. Writing the above code was quick and easy. I've
preferred writing code using Mote a lot more than Go recently…

A few posts ago I said I was working on a little toy adventure using AI to
generate some nice textual descriptions. I don't like the Go code I have
written. It works but seems… wrong. It's bitty, looks ugly and I'm unhappy
with it :( I thought of using Mote for this project. However, I wanted to
release the project on this site and Mote isn't ready for release still.

--
Diddymus

  [1] Advent of Code 2024: https://adventofcode.com


  Up to Main Index                          Up to Journal for December, 2024