09_Rope.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "type Direction = | Up | Down | Left | Right\n",
    "\n",
    "type Move = \n",
    "    { \n",
    "        Direction : Direction\n",
    "        Steps : int \n",
    "    }\n",
    "\n",
    "type Rope = \n",
    "    {\n",
    "        Head : int*int\n",
    "        Tail : int*int\n",
    "        TailVisited : (int*int) list\n",
    "    }\n",
    "\n",
    "module Rope =\n",
    "    let starting = { Head = (0,0); Tail = (0,0); TailVisited = [(0,0)] }\n",
    "\n",
    "    let moveHead dir rope =\n",
    "        let (x,y) = rope.Head\n",
    "        match dir with\n",
    "        | Up -> { rope with Head = (x, y + 1) }\n",
    "        | Down -> { rope with Head = (x, y - 1) }\n",
    "        | Left -> { rope with Head = (x - 1, y) }\n",
    "        | Right -> { rope with Head = (x + 1, y) }        \n",
    "\n",
    "    let moveTail rope =\n",
    "        let (hx, hy) = rope.Head\n",
    "        let (tx, ty) = rope.Tail\n",
    "        let (dx, dy) = (hx-tx, hy-ty)\n",
    "        if (abs dx <= 1) && (abs dy <= 1) then\n",
    "            rope // ends are next to each other\n",
    "        else\n",
    "            let t' = (tx + sign dx, ty + sign dy) // move one space max\n",
    "            { rope with Tail = t'; TailVisited = t'::rope.TailVisited }\n",
    "\n",
    "    let rec applyMove move rope =\n",
    "        if move.Steps = 0 then\n",
    "            rope\n",
    "        else\n",
    "            rope\n",
    "            |> moveHead move.Direction\n",
    "            |> moveTail\n",
    "            |> applyMove { move with Steps = move.Steps-1 }\n",
    "\n",
    "    let applyMoves moves rope =\n",
    "        moves\n",
    "        |> Seq.fold (fun r m -> applyMove m r) rope\n",
    "\n",
    "    let visitedCount rope =\n",
    "        rope.TailVisited\n",
    "        |> List.distinct\n",
    "        |> List.length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let parseLine (s : string) =\n",
    "    let steps = int (s.Substring(2))\n",
    "    let dir = \n",
    "        match s[0] with\n",
    "        | 'U' -> Up\n",
    "        | 'D' -> Down\n",
    "        | 'L' -> Left\n",
    "        | 'R' -> Right\n",
    "        | _ -> failwith \"Unrecognised direction\"\n",
    "    { Direction = dir; Steps = steps }\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "#r \"nuget: FsUnit\"\n",
    "\n",
    "open FsUnitTyped\n",
    "\n",
    "let testInput = \n",
    "    [|\n",
    "        \"R 4\"\n",
    "        \"U 4\"\n",
    "        \"L 3\"\n",
    "        \"D 1\"\n",
    "        \"R 4\"\n",
    "        \"D 1\"\n",
    "        \"L 5\"\n",
    "        \"R 2\"\n",
    "    |]\n",
    "    |> Array.map parseLine\n",
    "\n",
    "let testResult = Rope.starting |> Rope.applyMoves testInput\n",
    "\n",
    "Rope.visitedCount testResult |> shouldEqual 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "open System.IO\n",
    "\n",
    "let sourcePath = Path.Combine(__SOURCE_DIRECTORY__, \"input_09.txt\")\n",
    "let moves = \n",
    "    File.ReadAllLines(sourcePath)\n",
    "    |> Array.map parseLine\n",
    "\n",
    "let result = \n",
    "    Rope.starting\n",
    "    |> Rope.applyMoves moves\n",
    "    |> Rope.visitedCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "printfn \"Tail visited %d spaces\" result"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "source": [
    "## Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "type Knot = \n",
    "    { \n",
    "        Position : int*int\n",
    "        History : (int*int) list\n",
    "    }\n",
    "\n",
    "type Rope2 = \n",
    "    {\n",
    "        Knots : Knot list\n",
    "    }\n",
    "\n",
    "module Rope2 =\n",
    "    let starting numKnots = \n",
    "        {\n",
    "            Knots = List.init numKnots (fun _ -> { Position = (0,0); History = [(0,0)] })\n",
    "        }\n",
    "\n",
    "    let moveTail ahead behind =\n",
    "        let (hx, hy) = ahead.Position\n",
    "        let (tx, ty) = behind.Position\n",
    "        let (dx, dy) = (hx-tx, hy-ty)\n",
    "        if (abs dx <= 1) && (abs dy <= 1) then\n",
    "            behind // ends are next to each other\n",
    "        else\n",
    "            let t' = (tx + sign dx, ty + sign dy) // move one space max\n",
    "            { Position = t'; History = t' :: behind.History }\n",
    "\n",
    "    let pull dir rope =\n",
    "        match rope.Knots with\n",
    "        | [] -> rope\n",
    "        | h::rest ->\n",
    "            let (x,y) = h.Position\n",
    "            let h' =\n",
    "                match dir with\n",
    "                | Up -> (x, y + 1)\n",
    "                | Down -> (x, y - 1)\n",
    "                | Left -> (x - 1, y)\n",
    "                | Right -> (x + 1, y)\n",
    "            \n",
    "            let movedHead =\n",
    "                { Position = h'; History = h'::h.History }\n",
    "            \n",
    "            let updated=\n",
    "                rest\n",
    "                |> List.scan moveTail movedHead \n",
    "\n",
    "            { rope with Knots = updated }\n",
    "\n",
    "    let rec applyMove move rope =\n",
    "        if move.Steps = 0 then\n",
    "            rope\n",
    "        else\n",
    "            rope\n",
    "            |> pull move.Direction\n",
    "            |> applyMove { move with Steps = move.Steps-1 }\n",
    "\n",
    "    let applyMoves moves rope =\n",
    "        moves\n",
    "        |> Seq.fold (fun r m -> applyMove m r) rope\n",
    "\n",
    "    let lastVisitedCount rope =\n",
    "        (List.last rope.Knots).History\n",
    "        |> List.distinct\n",
    "        |> List.length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let largeTest =\n",
    "    [|\n",
    "        \"R 5\"\n",
    "        \"U 8\"\n",
    "        \"L 8\"\n",
    "        \"D 3\"\n",
    "        \"R 17\"\n",
    "        \"D 10\"\n",
    "        \"L 25\"\n",
    "        \"U 20\"\n",
    "    |]\n",
    "    |> Array.map parseLine\n",
    "\n",
    "let largeTestResult = Rope2.starting 10 |> Rope2.applyMoves largeTest\n",
    "\n",
    "Rope2.lastVisitedCount largeTestResult |> shouldEqual 36"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let result = \n",
    "    Rope2.starting 10\n",
    "    |> Rope2.applyMoves moves\n",
    "    |> Rope2.lastVisitedCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "printfn \"Tail visited %d spaces\" result"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (C#)",
   "language": "C#",
   "name": ".net-csharp"
  },
  "polyglot_notebook": {
   "kernelInfo": {
    "defaultKernelName": "csharp",
    "items": [
     {
      "aliases": [
       "c#",
       "C#"
      ],
      "languageName": "C#",
      "name": "csharp"
     },
     {
      "aliases": [],
      "languageName": "Mermaid",
      "name": "mermaid"
     },
     {
      "aliases": [],
      "languageName": null,
      "name": ".NET"
     },
     {
      "aliases": [
       "f#",
       "F#"
      ],
      "languageName": "F#",
      "name": "fsharp"
     },
     {
      "aliases": [],
      "languageName": "HTML",
      "name": "html"
     },
     {
      "aliases": [],
      "languageName": "KQL",
      "name": "kql"
     },
     {
      "aliases": [
       "powershell"
      ],
      "languageName": "PowerShell",
      "name": "pwsh"
     },
     {
      "aliases": [],
      "languageName": "SQL",
      "name": "sql"
     },
     {
      "aliases": [],
      "languageName": null,
      "name": "value"
     },
     {
      "aliases": [
       "frontend"
      ],
      "languageName": null,
      "name": "vscode"
     }
    ]
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}