Puzzle Hunt with Racer

Note: The main content is first written in Chinese, with the English translation (by AI) following below.

Chinese Version

我编写商业软件到现在有10年的时间.

使用过的编程语言(按掌握程度排序): C/C++, Python, Python(machine learn), F#, Golang, Scala, Clojure, JavaScript

使用过的编程范式: Object-Oriented (OO), Functional Programming (FP)

实现过的软件项目: 低延迟TCP/UDP Server side Framework, 高并发订单系统, 利用machine learning实现的高性能预测系统等等

我计划在这篇文章里记录一下我对编程的一些思考, 而且这些想法随着我解决更复杂问题, 积累更多的经验后也会有些变化, 因此我会不断更新这篇文章.

1. 自顶向下编程

有两种编程理念, 一种是自底向上, 一种是自顶向下.

自低向上: 先实现很多小的函数, 然后使用这些小函数组成很复杂的功能. 在很多讲lisp的书里, 经常会讲如何实践自底向上的编程思想.

自顶向下: 从使用者的角度, 先写完框架/函数API, 最后才是具体代码实现.

我赞同使用很多小的函数组成很复杂的功能这个编程思路, 但是在我的编程实践里, 我认为自顶向下才更容易写出高质量的代码.

举个例子: 假如我们要写一个网站,用来展示在不同的网站上,同一款汽车的最新销售信息, 方便用户选择最优的网站去购买汽车

如果使用自底向上的思路, 我们会依次实现这些代码

For every input, there is only one or zero solution, so that is not a coding question, it checks if you know basic math. :D

type Day13(lines: string[]) =
    let lines =
        String.Join("", lines)
        |> split2Int64ByReg @"(\d+)"
        |> Array.concat
        |> fun nums -> nums |> Array.splitInto (nums.Length / 6)

    let getMinCost (ai, aj) (bi, bj) (ti, tj) =
        // a * ai + b * bi = ti
        // a * aj + b * bj = tj
        // solve a, b
        // because for every a, b, t only have one or zero int solution
        let d = ai * bj - aj * bi
        let a = (ti * bj - tj * bi) / d
        let b = (tj * ai - ti * aj) / d

        if a * ai + b * bi = ti && a * aj + b * bj = tj then
            Some(a * 3L + b)
        else
            None

    member this.Q1() =
        lines
        |> Array.toList
        |> List.choose (fun nums -> getMinCost (nums[0], nums[1]) (nums[2], nums[3]) (nums[4], nums[5]))
        |> List.sum

    member this.Q2() =
        lines
        |> Array.toList
        |> List.choose (fun nums ->
            getMinCost (nums[0], nums[1]) (nums[2], nums[3]) (10000000000000L + nums[4], 10000000000000L + nums[5]))
        |> List.sum

You can find the source code at https://github.com/zangruizhe/AoC

AoC 2024 Day9 F# solution #AdventOfCode #fsharp

Today, my solution takes 5 seconds to get the result, which means my algorithm is not good enough because AoC questions usually only take 1 second to get the result.

let me know if you have some good ideas. :D

type Day9(lines: string[]) =
    member this.Q1() =
        let transform (l: string) =
            l
            |> Seq.mapi (fun i c ->
                let n = char2Int c

                if i % 2 = 0 then
                    Array.init n (fun _ -> $"{i / 2}")
                else
                    Array.init n (fun _ -> "."))
            |> Seq.concat
            |> Seq.toArray

        let lines = String.Join("", lines) |> transform

        let rec shift i j =
            if i < j then
                match lines[i] = ".", lines[j] <> "." with
                | true, true ->
                    lines[i] <- lines[j]
                    lines[j] <- "."
                    shift (i + 1) (j - 1)
                | true, false -> shift i (j - 1)
                | false, true -> shift (i + 1) j
                | false, false -> shift (i + 1) (j - 1)

        shift 0 (lines.Length - 1)

        lines
        |> Array.mapi (fun i c -> if c <> "." then int64 i * (int64 c) else 0L)
        |> Array.sum

    member this.Q2() =
        let transform (l: string) =
            l
            |> Seq.mapi (fun i c ->
                let n = char2Int c

                if i % 2 = 0 then
                    Array.init n (fun idx -> (idx + 1, $"{i / 2}"))
                else
                    Array.init n (fun idx -> (n - idx, ".")))
            |> Seq.concat
            |> Seq.toArray

        let lines = String.Join("", lines) |> transform

        let rec shift i j =
            let ni, ci = lines[i]
            let nj, cj = lines[j]

            if i < j then
                match ci = ".", cj <> ".", ni >= nj with
                | true, true, true ->
                    for n in 0 .. nj - 1 do
                        lines[i + nj - n - 1] <- lines[j - n]
                        lines[j - n] <- (fst lines[j - n], ".")

                    shift 0 (j - nj)
                | true, true, false -> shift (i + ni) j
                | false, true, _ -> shift (i + 1) j
                | true, false, _ -> shift i (j - 1)
                | false, false, _ -> shift (i + 1) (j - 1)
            elif cj <> "." && j - nj > 0 then
                shift 0 (j - nj)

        shift 0 (lines.Length - 1)

        lines
        |> Array.mapi (fun i (_, c) -> if c <> "." then int64 i * (int64 c) else 0L)
        |> Array.sum

You can find the source code at https://github.com/zangruizhe/AoC

Today’s question is easy to write in mutable languages, like Python, but hard to write in FP code.

Let me know if you have some ideas to simplify my F# code.

Let’s improve our F# skills together! :D

type Day8(lines: string[]) =
    let R = lines.Length
    let C = lines[0].Length

    let getPoints (lines: string[]) : Map<char, Index array> =
        let points =
            [| for i in 0 .. R - 1 do
                   for j in 0 .. C - 1 do
                       if lines[i][j] <> '.' then
                           (lines[i][j], (i, j)) |]

        points
        |> Array.groupBy fst
        |> Map.ofArray
        |> Map.map (fun _ v -> v |> Array.map snd)


    let inBoard (i, j) : bool = 0 <= i && i < R && 0 <= j && j < C

    let getIdxPair (idx_list: Index array) =
        [ for i in 0 .. idx_list.Length - 2 do
              for j in i + 1 .. idx_list.Length - 1 do
                  (idx_list[i], idx_list[j]) ]

    let getAntinodes op (a: Index) (b: Index) : Index list =
        let ar, ac = a
        let br, bc = b

        let x = abs (ar - br)
        let y = abs (ac - bc)

        match ar < br, ac < bc with
        | true, true -> (-x, -y), (x, y)
        | true, false -> (-x, y), (x, -y)
        | false, true -> (x, -y), (-x, y)
        | false, false -> (x, y), (-x, -y)
        |> fun (d1, d2) -> op a d1 @ op b d2

    member this.Q1() =
        let points_dict = lines |> getPoints
        let getAntIdx (ar, ac) (dr, dc) = [ (ar + dr, ac + dc) ]

        points_dict.Values
        |> Array.ofSeq
        |> Seq.collect (fun idx_list ->
            idx_list
            |> getIdxPair
            |> List.collect (fun (l, r) -> getAntinodes getAntIdx l r))
        |> Seq.filter inBoard
        |> Set.ofSeq
        |> Seq.length

    member this.Q2() =
        let points_dict = lines |> getPoints

        let getAntinodesInLine (ar, ac) (x, y) =
            let rec loop (ar, ac) x y rst =
                if not (inBoard (ar, ac)) then
                    rst
                else
                    loop (ar + x, ac + y) x y ((ar, ac) :: rst)

            loop (ar, ac) x y []

        points_dict.Values
        |> Array.ofSeq
        |> Seq.collect (fun idx_list ->
            idx_list
            |> getIdxPair
            |> List.collect (fun (l, r) -> getAntinodes getAntinodesInLine l r))
        |> Set.ofSeq
        |> Seq.length

You can find the source code at https://github.com/zangruizhe/AoC

Tips for Q2:

If the Guard moving to the same direction at same position twice, that means Guard is in a loop.

type Day6(lines: string[]) =
    let R = lines.Length
    let C = lines[0].Length

    let getStart (lines: string[]) =
        lines
        |> Array.indexed
        // |> Array.pick (fun (i, s) -> s |> Seq.tryFindIndex ((=) '^') |> Option.map (fun j -> (i, j)))
        |> Array.pick (fun (i, s) ->
            let j = s.IndexOf("^")
            if j <> -1 then Some(i, j) else None)

    let ops = [ (-1, 0); (0, 1); (1, 0); (0, -1) ]

    let rec moving i j op (pos_set: HashSet<Index>) =
        pos_set.Add((i, j)) |> ignore
        let next_i = i + fst ops[op]
        let next_j = j + snd ops[op]

        if next_i < 0 || next_i >= R || next_j < 0 || next_j >= C then
            pos_set
        elif lines[next_i][next_j] = '#' then
            moving i j ((op + 1) % 4) pos_set
        else
            moving next_i next_j op pos_set


    member this.Q1() =
        let start: Index = getStart lines
        let post_set = moving (fst start) (snd start) 0 (HashSet())
        post_set.Count

    member this.Q2() =
        let start: Index = getStart lines
        let pos_set = moving (fst start) (snd start) 0 (HashSet())
        pos_set.Remove(start) |> ignore
        let isInLoop (pos_set: HashSet<int * int * int>) i j op = pos_set.Add((i, j, op)) = false

        let rec checkLoop i j op (pos_set: HashSet<int * int * int>) =

            let next_i = i + fst ops[op]
            let next_j = j + snd ops[op]

            if next_i < 0 || next_i >= R || next_j < 0 || next_j >= C then
                false
            elif lines[next_i][next_j] = '#' then
                if isInLoop pos_set i j op then
                    true
                else
                    checkLoop i j ((op + 1) % 4) pos_set
            else
                checkLoop next_i next_j op pos_set


        pos_set
        |> Seq.filter (fun (i, j) ->
            let old = lines[i]
            let str = old.ToCharArray()
            str[j] <- '#'
            lines[i] <- String(str)
            let rst = checkLoop (fst start) (snd start) 0 (HashSet())
            lines[i] <- old
            rst)
        |> Seq.length

You can find the source code at https://github.com/zangruizhe/AoC

Today’s question should process the whole input together.

If you process input line by line, you can pass Q1, but can not pass Q2

module Day3 =
    let Q1 (lines: string[]) =
        let str = String.Concat(lines)
        str |> split2IntByReg "mul\((\d+),(\d+)\)" |> Array.sumBy (fun n -> n[0] * n[1])

    let Q2 (lines: string[]) =
        let str = String.Concat(lines)

        Regex.Matches(str, @"mul\((\d+),(\d+)\)|don't\(\)|do\(\)")
        |> Seq.fold
            (fun (l, isEnable) m ->
                if m.Value.StartsWith("mul") then
                    if isEnable then
                        l @ [ (int m.Groups[1].Value, int m.Groups[2].Value) ], isEnable
                    else
                        l, isEnable
                elif m.Value = "do()" then
                    l, true
                elif m.Value = "don't()" then
                    l, false
                else
                    failwith $"wrong patten m={m.Value}")
            ([], true)
        |> fst
        |> Seq.sumBy (fun (l, r) -> l * r)

You can find the source code at https://github.com/zangruizhe/AoC

认知疗法

最重要的就是有爱的能力，爱的能力是发挥创造力，和享受生活的关键

在任何情况下，我们都可以为自己和为他人做些有意义的事情

思想实验–“流浪汉”疗法,思考自己是个一无所有的流浪汉，但是仍然能快乐生活，想想是否可以实现。

对生活的事情分级

(-3）worst/worse/bad/normal/good/better/best (3)

(-3）糟透了/很糟/糟/一般/棒/很棒/棒极了 (3)

先想想标尺的两头是什么：

糟透了的事情：死亡，恶性肿瘤

棒极了的事情：孩子出生，结婚

然后用这两头的事情来校准其他事情, 比如：

拿到了心仪的工作机会：很棒

没拿到心仪的工作机会：糟

丢掉了工作：糟

亏了10万：bad-normal(-0.5)

赚了20万：棒

通过这样校准，让我们对事物，尤其是糟糕的事物评价变得具体，从而不会轻易把事情归类到糟透了/很糟这个范围，也就不会这么担忧了

那些坚强、成熟的人，对生活中遇到的大多数事情都会归类到【糟，一般、棒】这个范围内，所以他们的心态也就更加平和

认知练习

事情：发生了什么事
分级：事情的分级
详情：事情的客观详情
结果：过一段时间再回头看这个分级是否合理

Think Programming - Insights from My Coding Journey

Chinese Version

1. 自顶向下编程

Advent of Code 2024 Day13

Advent of Code 2024 Day9

Advent of Code 2024 Day8

Advent of Code 2024 Day6

Advent of Code 2024 Day3

《让人生停止灰暗的艺术》

认知疗法

对生活的事情分级

认知练习