Architeuthis

joined 2 years ago
[–] Architeuthis@awful.systems 4 points 4 months ago

puzzles unlock at 2PM

Almost exactly at the start of office hours for me.

[–] Architeuthis@awful.systems 2 points 4 months ago (2 children)

10 commentaryYeah basically if you were doing DFS and forgot to check if you'd already visited the next node you were solving for pt2, since the rule about the next node always having a value of +1 compared to the current one was already preventing cyclic paths.

10 CodeHardly a groundbreaking implementation but I hadn't posted actual code in a while so

(* F# - file reading code and other boilerplate omited *)

let mapAllTrails (matrix : int array2d) =
    let rowCount = matrix |> Array2D.length1
    let colCount = matrix |> Array2D.length2

    let rec search (current:int*int) (visited: HashSet<int*int>) (path: (int*int) list) : (int*int) list list= 
        let (row,col) = current
        let currentValue = matrix.[row,col]

        // Remove to solve for 10-2
        visited.Add (row,col) |> ignore

        // If on a 9 return the complete path
        if currentValue = 9 then [List.append path [row,col] ]
        // Otherwise filter for eligible neihboring cells and continue search
        else                    
            [ row-1, col;row, col-1; row, col+1; row+1,col]
            |> List.filter (fun (r,c) -> 
                not (visited.Contains(r,c))
                && r >= 0 && c>=0 && r < rowCount && c < colCount
                && matrix.[r,c]-currentValue = 1 )
            |> List.collect (fun next ->
                [row,col] 
                |> List.append path  
                |> search next visited)

    // Find starting cells, i.e. contain 0
    matrix
    |> Global.matrixIndices
    |> Seq.filter (fun (row,col) -> matrix.[row,col] = 0)
    // Find all trails starting from those cells and flatten the result
    |> Seq.collect (fun trailhead -> search trailhead (HashSet<int*int>()) [])
    

"./input.example"
|> Common.parse 
|> mapAllTrails
|> Seq.length
|> Global.shouldBe 81

"./input.actual"
|> Common.parse 
|> mapAllTrails
|> Seq.length
|> printfn "The sum total of trail rankings is %d"

[–] Architeuthis@awful.systems 2 points 4 months ago* (last edited 4 months ago) (2 children)

Day 9 seemed pretty straightforward, don't really have anything to add.

[–] Architeuthis@awful.systems 2 points 4 months ago* (last edited 4 months ago)

I almost got done in by floating point arithmetic, I think

8-2 commentaryUsed the coordinates of every two same type frequences to create the ilnear equation (y = ax + b) and then fed it all the matrix coordinates to see which belonged to the line. To get the correct number of antinodes I had to check for |y - ax - b| < 0.0001, otherwise I got around 20 too few.

[–] Architeuthis@awful.systems 3 points 4 months ago* (last edited 4 months ago) (1 children)

My graph search solves 7-1 and passes the example cases for 7-2, but gives too low a result for the complete puzzle input, and there's no way I'm manually going through every case to find the false negative. On to day 8 I guess.

7-2 Check case by simple graph search that mostly works

// F#
let isLegit ((total: int64), (calibration : int64 array)) = 

    let rec search (index : int) (acc: int64) =
        let currentValue = calibration.[index]
        
        [Add; Times; Concat] // operators - remove 'Concat' to solve for 7-1
        |> List.exists (fun op -> // List.exists returns true the first time the lambda returns true, so search stops at first true
                match op with // update accumulator
                | Add -> acc + currentValue
                | Times -> acc * currentValue
                | Concat -> int64 (sprintf "%d%d" acc currentValue)
                |> function // stop search on current accumulator value (state) exceeding total, or being just right
                | state when state > total -> false
                | state when state = total && index < (calibration.Length-1) -> false // this was the problem
                | state when state = total && index = (calibration.Length-1) -> true
                | state -> // stop if index exceeds input length, or continue search
                    if index+1 = calibration.Length
                    then false
                    else search (index+1) state
        )
     
    // start search from second element using the first as current sum
    search 1 calibration.[0]

EDIT: total && index < (calibration.Length-1) -> false -- i.e. stop if you reach the total before using all numbers, well, also stops you from checking the next operator, So, removing it worked.

Rubber ducking innocent people on the internets works, who knew.

[–] Architeuthis@awful.systems 2 points 4 months ago* (last edited 4 months ago)

tl;dr: Day 5 was most perfectly fine code thrown out for me, because I ran face first into eliminating imaginary edge cases instead of starting out simple.

5-1 commentaryI went straight into a rabbit hole of doing graph traversal to find all implicit rules (i.e. 1|2, 2|3, 3|4 imply 1|3, 1|4, 2|4) so I could validate updates by making sure all consequent pairs appear in the expanded ruleset. Basically I would depth first search a tree with page numbers for nodes and rules for edges, to get all branches and recombine them to get the full ruleset.

So ideally 1|2, 2|3, 3|4 -> 1|2|3|4 -> 1|2, 2|3, 3|4, 1|3, 1|4, 2|4

Except I forgot the last part and just returned the branch elements pairwise in sequence, which is just the original rules, which I noticed accidentally after the fact since I was getting correct results, because apparently it was completely unnecessary and I was just overthinking myself into several corners at the same time.

5-2 commentary and some codeThe obvious cornerstone was the comparison function to reorder the invalid updates, this is what I came up with:

let comparerFactory (ruleset: (int*int) list) :int -> int -> int = 
    let leftIndex = 
        ruleset 
        |> List.groupBy fst 
        |> List.map (fun (key,grp)-> key, grp |> List.map snd)
        |> Map.ofList

    fun page1 page2 -> 
        match (leftIndex  |> Map.tryFind page1) with
        | Some afterSet when afterSet |> List.contains page2 -> -1
        | _ -> 1

The memoization pattern is for caching an index of rules grouped by the before page, so I can sort according to where each part of the comparison appears. I started out with having a second index where the key was the 'after' page of the rule which I would check if the page didn't appear on the left side of any rule, but it turned out I could just return the opposite case, so again unnecessary.

[–] Architeuthis@awful.systems 2 points 4 months ago* (last edited 4 months ago)

discussionSame, except in 4-1 I used a recursive function to traverse each direction according to the offset decided by the selected direction (like SW is row++,col--) , due to functional programming induced brain damage.

Would have been pretty useful too if 4-2 turned out to be about finding longer patterns, instead of smaller and in half the directions.

4-1Inlined some stuff to fit everything in one function:

let rec isXmas (row:int) (col:int) (dir:int) (depth:int) (arr: char array2d) : bool =
    let value = arr.[row,col]
    if depth = 3
    then value = 'S'
    else if  [|'X';'M';'A';'S'|].[depth] = value
    then
        let (nextRow, nextCol) =
            match dir with
            | 1 -> row + 1, col - 1
            | 2 -> row + 1, col
            | 3 -> row + 1, col + 1
            | 4 -> row, col - 1
            | 6 -> row, col + 1
            | 7 -> row - 1, col - 1
            | 8 -> row - 1, col
            | 9 -> row - 1, col + 1
            | _ -> failwith $"{dir} isn't a numpad direction." 

        let rowCount = arr |> Array2D.length1
        let colCount = arr |> Array2D.length2
       
        if nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount
        then isXmas nextRow nextCol dir (depth+1) arr
        else false
    else false

Then you run this for every appropriately pruned 'X' times every direction and count the trues.

[–] Architeuthis@awful.systems 3 points 4 months ago (1 children)

Nabokov's Lolita really shouldn't be pigeonholed as merely that, but I guess the movies are another story.

[–] Architeuthis@awful.systems 5 points 4 months ago* (last edited 4 months ago) (3 children)

Dolores in Lolita was like twelve though, at least in the book.

edit: also I don't think Yud recommending The Softcore Adventures Of A Six-year-old In A Thirteen-year-old's Body as a Very Normal Book to his considerable audience fits this particular discourse.

[–] Architeuthis@awful.systems 4 points 4 months ago* (last edited 4 months ago)

Got stuck forever on 2-2 because of an edge case that only showed up in 7/1000 reports, ended up just brute forcing it, just ran the fitness function after removing one element at a time sequentially.

Then solved 3.x in like minutes because I could be worse at regex, posting code mostly because no-one else posted F# yet.

edited to fix spoiler header formatting

3-2 in F#

"./input.actual"
|> System.IO.File.ReadAllText
|> fun source -> 
    System.Text.RegularExpressions.Regex.Matches(source, @"don't\(\)|do\(\)|mul\((\d+),(\d+)\)")
    |> Seq.fold
        (fun (acc, enabled) m ->
            match m.Value with
            | "don't()" -> acc, false
            | "do()" -> acc, true
            | mul when enabled && mul.StartsWith("mul") ->
                let (x, y) = int m.Groups.[1].Value, int m.Groups.[2].Value
                acc + x * y, enabled
            | _ -> acc, enabled ) 
        (0, true)
    |> fst
|> printfn "The sum of all valid multiplications with respect to do() and don't() is %A"

commentsNot much to say, the regex grabs all relevant strings and the folding function propagates a flag that flips according to do/don't and an accumulator that is increased when a mul() is encountered and parsed.

[–] Architeuthis@awful.systems 20 points 4 months ago (1 children)

In case anybody skips the article, it's a six year old cybernetically force grown to the body of a horny 13 to 14 year old.

The rare sentence that makes me want to take a shower for having written it.

[–] Architeuthis@awful.systems 6 points 4 months ago

...with a huge chip on his shoulder about how the system caters primarily to normies instead of specifically to him, thinks he has fat-no-matter-what genes and is really into rape play.

view more: ‹ prev next ›