Day 3 2019

diff --git a/day3/input.txt b/day3/input.txt
new file mode 100644 (file)
index 0000000..2d19f96
--- /dev/null
+++ b/day3/input.txt
@@ -0,0 +1,2 @@
+R997,U849,R349,U641,R581,D39,R285,U139,R455,D346,L965,D707,R393,D302,L263,U58,R950,U731,R858,D748,R302,U211,R588,D441,L153,D417,R861,U775,R777,U204,R929,U868,L62,U163,R841,D214,L648,U626,R501,D751,L641,D961,L23,D430,L73,D692,R49,U334,L601,U996,R444,D658,R633,D30,L861,D811,R10,D394,R9,U227,L848,U420,L378,D622,L501,U397,R855,U369,R615,U591,L674,D166,L181,U61,L224,U463,L203,U594,R93,U614,L959,U198,L689,D229,L674,U255,R843,D382,R538,U923,L960,D775,L879,U97,R137,U665,L340,D941,L775,D57,R852,D167,R980,U704,L843,U989,L611,D32,L724,D790,L32,U984,L39,U671,L994,U399,R475,D85,L322,D936,R117,D261,R705,D696,L523,D433,L239,U477,L247,D465,R560,D902,L589,U682,R645,U376,L989,D121,L215,U514,R519,U407,L218,D444,R704,D436,L680,U759,R937,U400,R533,D860,R782,D233,R840,D549,L508,U380,L992,U406,L213,D403,L413,D532,L429,U186,R262,U313,L913,U873,L838,D882,R851,U70,R185,D131,R945,D595,L330,U446,R88,D243,L561,D952,R982,D395,L708,U459,L82,D885,L996,U955,L406,U697,L183,U266,L878,D839,R843,D891,R118,U772,R590,D376,L500,U370,R607,D12,L310,D436,L602,D365,R886,U239,L471,D418,L122,U18,R879,D693,R856,U848,L657,D911,L63,U431,R41,U752,R919,U323,L61,D263,L370,D85,R929,D213,R350,U818,R458,D912,R509,U394,L734,U49,R810,D87,L870,U658,R499,U550,L402,U244,L112,U859,R836,U951,R222,D944,L691,D731,R742,D52,R984,D453,L514,U692,R812,U35,L844,D177,L110,D22,R61,U253,R618,D51,R163,U835,R704,U148,R766,U297,R457,D170,L104,D441,R330,D330,R989,D538,R668,D811,R62,D67,L470,D526,R788,U376,R708,U3,R961
+L1009,D381,R970,U429,L230,D909,R516,D957,R981,U609,L480,D139,L861,U168,L48,U620,R531,D466,L726,D380,R977,D454,L318,D397,R994,U402,L77,U93,L359,D72,R968,D956,L174,D22,R218,U619,R593,U32,L154,U55,L169,U415,L171,U666,R617,U109,L265,U773,R541,D808,L797,U478,R731,U379,R311,D137,L806,U298,R362,D458,L254,D539,R700,U853,R246,D588,L28,U203,L432,U946,R663,D408,R974,U59,L683,D36,L139,U738,L780,U414,L401,D93,R212,D973,L710,U892,L357,D177,R823,D4,R46,D924,L235,D898,R67,U220,L592,U87,R94,U584,R979,D843,L299,D648,L491,U360,R824,D245,L944,D24,R616,U975,L4,U42,L984,U181,R902,D835,L687,D413,L767,U632,L754,U270,R413,U51,L825,D377,L596,U960,L378,U706,L859,D708,L156,D991,L814,U351,R923,D749,L16,D651,R20,D86,R801,U811,L228,U161,L871,U129,R215,U235,L784,U896,R94,U145,R822,U494,R248,D98,R494,U156,L495,U311,R66,D873,L294,D620,L885,U395,R778,D227,R966,U756,L694,D707,R983,D950,R706,D730,R415,U886,L465,D622,L13,D938,R324,D464,R723,U804,R942,D635,L729,D317,L522,U469,R550,D141,R302,U999,L642,U509,R431,D380,R18,D676,R449,D759,L495,U901,R1,D745,L655,U449,L439,D818,R55,D541,R420,U764,L426,D176,L520,U3,L663,D221,L80,D449,L987,U349,L71,U632,L887,D231,R655,D208,R698,D639,R804,U616,R532,U846,R363,D141,R659,U470,L798,U144,L675,U483,L944,U380,L329,U72,L894,D130,R53,U109,R610,U770,R778,U493,R972,D340,L866,U980,L305,D812,R130,D954,R253,D33,L912,U950,L438,D680,R891,U725,R171,D587,R549,D367,L4,U313,R522,D128,L711,D405,L769,D496,L527,U373,R725,D261,L268,D939,L902,D58,L858,D190,L442

diff --git a/day3/summary.txt b/day3/summary.txt
new file mode 100644 (file)
index 0000000..061b206
--- /dev/null
+++ b/day3/summary.txt
@@ -0,0 +1,81 @@
+--- Day 3: Crossed Wires ---
+The gravity assist was successful, and you're well on your way to the Venus refuelling station. During the rush back on Earth, the fuel management system wasn't completely installed, so that's next on the priority list.
+
+Opening the front panel reveals a jumble of wires. Specifically, two wires are connected to a central port and extend outward on a grid. You trace the path each wire takes as it leaves the central port, one wire per line of text (your puzzle input).
+
+The wires twist and turn, but the two wires occasionally cross paths. To fix the circuit, you need to find the intersection point closest to the central port. Because the wires are on a grid, use the Manhattan distance for this measurement. While the wires do technically cross right at the central port where they both start, this point does not count, nor does a wire count as crossing with itself.
+
+For example, if the first wire's path is R8,U5,L5,D3, then starting from the central port (o), it goes right 8, up 5, left 5, and finally down 3:
+
+...........
+...........
+...........
+....+----+.
+....|....|.
+....|....|.
+....|....|.
+.........|.
+.o-------+.
+...........
+Then, if the second wire's path is U7,R6,D4,L4, it goes up 7, right 6, down 4, and left 4:
+
+...........
+.+-----+...
+.|.....|...
+.|..+--X-+.
+.|..|..|.|.
+.|.-X--+.|.
+.|..|....|.
+.|.......|.
+.o-------+.
+...........
+These wires cross at two locations (marked X), but the lower-left one is closer to the central port: its distance is 3 + 3 = 6.
+
+Here are a few more examples:
+
+R75,D30,R83,U83,L12,D49,R71,U7,L72
+U62,R66,U55,R34,D71,R55,D58,R83 = distance 159
+R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
+U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = distance 135
+What is the Manhattan distance from the central port to the closest intersection?
+
+Your puzzle answer was 209.
+
+--- Part Two ---
+It turns out that this circuit is very timing-sensitive; you actually need to minimize the signal delay.
+
+To do this, calculate the number of steps each wire takes to reach each intersection; choose the intersection where the sum of both wires' steps is lowest. If a wire visits a position on the grid multiple times, use the steps value from the first time it visits that position when calculating the total value of a specific intersection.
+
+The number of steps a wire takes is the total number of grid squares the wire has entered to get to that location, including the intersection being considered. Again consider the example from above:
+
+...........
+.+-----+...
+.|.....|...
+.|..+--X-+.
+.|..|..|.|.
+.|.-X--+.|.
+.|..|....|.
+.|.......|.
+.o-------+.
+...........
+In the above example, the intersection closest to the central port is reached after 8+5+5+2 = 20 steps by the first wire and 7+6+4+3 = 20 steps by the second wire for a total of 20+20 = 40 steps.
+
+However, the top-right intersection is better: the first wire takes only 8+5+2 = 15 and the second wire takes only 7+6+2 = 15, a total of 15+15 = 30 steps.
+
+Here are the best steps for the extra examples from above:
+
+R75,D30,R83,U83,L12,D49,R71,U7,L72
+U62,R66,U55,R34,D71,R55,D58,R83 = 610 steps
+R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
+U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = 410 steps
+What is the fewest combined steps the wires must take to reach an intersection?
+
+Your puzzle answer was 43258.
+
+Both parts of this puzzle are complete! They provide two gold stars: **
+
+At this point, you should return to your Advent calendar and try another puzzle.
+
+If you still want to see it, you can get your puzzle input.
+
+You can also [Share] this puzzle.

diff --git a/day3/wires.sh b/day3/wires.sh
index a28765a75bc89d118a62790e04b31aa371cf7890..b94ef0b54c7d121c5f0731fd22a1bbb22c9d4be0 100644 (file)
--- a/day3/wires.sh
+++ b/day3/wires.sh
@@ -12,61 +12,19 @@ set -e
 #wire_2=(U62 R66 U55 R34 D71 R55 D58 R83)
 
 # these wires should get 135
 #wire_2=(U62 R66 U55 R34 D71 R55 D58 R83)
 
 # these wires should get 135

-wire_1=(R98 U47 R26 D63 R33 U87 L62 D20 R33 U53 R51)
-wire_2=(U98 R91 D20 R16 D67 R40 U7 R15 U6 R7)
+#wire_1=(R98 U47 R26 D63 R33 U87 L62 D20 R33 U53 R51)
+#wire_2=(U98 R91 D20 R16 D67 R40 U7 R15 U6 R7)

 
 # read in data from file instead
 
 # read in data from file instead

-#exec 3<input.txt
-#IFS="," read -u 3 -a wire_1
-#IFS="," read -u 3 -a wire_2
-
-get_min_max() {
-    local -n wire=$1
-    horz_min=0
-    horz_max=0
-    vert_min=0
-    vert_max=0
-    cur_horz=0
-    cur_vert=0
-    for instruction in "${wire[@]}"; do
-        direction=${instruction:0:1}
-        amount=${instruction:1}
-        case $direction in
-            U)
-                cur_vert=$((cur_vert+$amount))
-                if [ $cur_vert -gt $vert_max ]; then
-                    vert_max=$cur_vert
-                fi
-                ;;
-            D)
-                cur_vert=$((cur_vert-$amount))
-                if [ $cur_vert -lt $vert_min ]; then
-                    vert_min=$cur_vert
-                fi
-                ;;
-            R)
-                cur_horz=$((cur_horz+$amount))
-                if [ $cur_horz -gt $horz_max ]; then
-                    horz_max=$cur_horz
-                fi
-                ;;
-            L)
-                cur_horz=$((cur_horz-$amount))
-                if [ $cur_horz -lt $horz_min ]; then
-                    horz_min=$cur_horz
-                fi
-                ;;
-        esac
-    done
-
-    echo "$horz_min,$horz_max,$vert_min,$vert_max"
-}
+exec 3<input.txt
+IFS="," read -u 3 -a wire_1
+IFS="," read -u 3 -a wire_2

 
 trace_wire() {
     local -n w=$1
     local -n b=$2
     local -n c=$3
 
 trace_wire() {
     local -n w=$1
     local -n b=$2
     local -n c=$3

-    min_left=$4
+    wire_number=$4

     cur_vert=0
     cur_horz=0
     moved=0
     cur_vert=0
     cur_horz=0
     moved=0


@@ -92,131 +50,41 @@ trace_wire() {
 
         case $direction in
             U|D)
 
         case $direction in
             U|D)

-                last_replace_char="|"
-                offset=$((0-$min_left))
-                offset=$((offset+$cur_horz))

                 for (( moved=1; moved <= $amount; moved++ )); do
                     cur_vert=$((cur_vert${operator}1))
                 for (( moved=1; moved <= $amount; moved++ )); do
                     cur_vert=$((cur_vert${operator}1))

-                    cur_line=${b[$cur_vert]}
-                    cur_char=${cur_line:$offset:1}
-                    replace_char="|"
-                    if [ $cur_char = "-" ] || [ $cur_char = "|" ]; then
-                        replace_char="X"
-                        c+=($cur_horz,$cur_vert)
-                    fi
-                    if [ $moved -eq $amount ]; then
-                        replace_char="+"
+                    if [ ${b[$cur_horz,$cur_vert]+a} ] && [ $wire_number -eq 2 ]; then
+                        if [ ${b[$cur_horz,$cur_vert]} -eq 1 ]; then
+                            c+=($cur_horz,$cur_vert)
+                            b[$cur_horz,$cur_vert]=3
+                        fi
+                        continue

                     fi
                     fi

-                    if [ $cur_vert -eq 0 ] && [ $cur_horz -eq 0 ]; then
-                        replace_char='o'
-                    fi
-                    new_line="${cur_line:0:$((offset))}${replace_char}${cur_line:$((offset+1))}"
-                    b[$cur_vert]=$new_line
+                    b[$cur_horz,$cur_vert]=$wire_number

                 done
                 ;;
             L|R)
                 done
                 ;;
             L|R)

-                last_replace_char="-"
-                # this could change multiple characters in the line

                 for (( moved=1; moved <= $amount; moved++ )); do
                     cur_horz=$((cur_horz${operator}1))
                 for (( moved=1; moved <= $amount; moved++ )); do
                     cur_horz=$((cur_horz${operator}1))

-                    offset=$((0-$min_left))
-                    offset=$((offset+$cur_horz))
-                    cur_line=${b[$cur_vert]}
-                    cur_char=${cur_line:$offset:1}
-                    replace_char="-"
-                    if [ $cur_char = "-" ] || [ $cur_char = "|" ]; then
-                        replace_char="X"
-                        c+=($cur_horz,$cur_vert)
-                    fi
-                    if [ $moved -eq $amount ]; then
-                        replace_char="+"
-                    fi
-                    if [ $cur_vert -eq 0 ] && [ $cur_horz -eq 0 ]; then
-                        replace_char='o'
+                    if [ ${b[$cur_horz,$cur_vert]+a} ] && [ $wire_number -eq 2 ]; then
+                        if [ ${b[$cur_horz,$cur_vert]} -eq 1 ]; then
+                            c+=($cur_horz,$cur_vert)
+                            b[$cur_horz,$cur_vert]=3
+                        fi
+                        continue

                     fi
                     fi

-                    new_line="${cur_line:0:$((offset))}${replace_char}${cur_line:$((offset+1))}"
-                    b[$cur_vert]=$new_line
+                    b[$cur_horz,$cur_vert]=$wire_number

                 done
                 ;;
         esac
     done
                 done
                 ;;
         esac
     done

-
-    cur_line=${b[$cur_vert]}
-    offset=$((0-$min_left))
-    offset=$((offset+$cur_horz))
-    if [ ${cur_line:$offset:1} != 'X' ]; then
-        new_line="${cur_line:0:$((offset))}${last_replace_char}${cur_line:$((offset+1))}"
-        b[$cur_vert]=$new_line
-    fi
-    echo

 }
 
 }
 

-make_board() {
-    local -n mm=$1
-    local -n b=$2
-
-    min_horz=${mm[0]}
-    if [ $min_horz -gt 0 ]; then
-        min_horz=0
-    fi
-
-    min_vert=${mm[2]}
-    if [ $min_vert -gt 0 ]; then
-        min_vert=0
-    fi
-
-    max_horz=${mm[1]}
-    total_horz=$(($max_horz - $min_horz))
-
-    max_vert=${mm[3]}
-
-    cur_vert=${min_vert}
-    blank_string=$(printf ".%.0s" $(eval echo '{0..'$total_horz'}'))
-    while [[ $cur_vert -le ${max_vert} ]]; do
-        if [[ $cur_vert -eq 0 ]]; then
-            offset=$((0-${mm[0]}))
-            line="${blank_string:0:$offset}o${blank_string:$((offset+1))}"
-            b[$cur_vert]=$line
-        else
-            b[$cur_vert]=$blank_string
-        fi
-        cur_vert=$((cur_vert+1))
-    done
-}
-
-echo "Getting board boundaries"
-IFS="," read -a min_max < <(get_min_max wire_1)
-IFS="," read -a min_max_2 < <(get_min_max wire_2)
-
-# do the minimums first
-for pos in 0 2; do
-    if [ ${min_max[$pos]} -gt ${min_max_2[$pos]} ]; then
-        min_max[$pos]=${min_max_2[$pos]}
-    fi
-done
-
-# now the maximums
-for pos in 1 3; do
-    if [ ${min_max[$pos]} -lt ${min_max_2[$pos]} ]; then
-        min_max[$pos]=${min_max_2[$pos]}
-    fi
-done
-
-echo "  ${min_max[@]}"
-
-# we now know exactly how big the grid is, which is handy, as we'll use it to do offsets

 declare -A board
 declare -a cross_wires
 declare -A board
 declare -a cross_wires

-echo "Building board"
-make_board min_max board

 echo "Tracing first wire"
 echo "Tracing first wire"

-trace_wire wire_1 board cross_wires ${min_max[0]}
+trace_wire wire_1 board cross_wires 1

 echo "Tracing second wire"
 echo "Tracing second wire"

-trace_wire wire_2 board cross_wires ${min_max[0]}
-
-for (( a=${min_max[3]}; a>=${min_max[2]}; a-- )); do
-    echo ${board[$a]}
-done
+trace_wire wire_2 board cross_wires 2

 
 echo "Wires cross at:"
 min_distance=-1
 
 echo "Wires cross at:"
 min_distance=-1

diff --git a/day3/wires_2.sh b/day3/wires_2.sh
new file mode 100644 (file)
index 0000000..1e86e0c
--- /dev/null
+++ b/day3/wires_2.sh
@@ -0,0 +1,114 @@
+#!/bin/bash
+
+set -u
+set -e
+
+# these wires should give 6
+#wire_1=(R8 U5 L5 D3)
+#wire_2=(U7 R6 D4 L4)
+
+# these wires should get 159
+#wire_1=(R75 D30 R83 U83 L12 D49 R71 U7 L72)
+#wire_2=(U62 R66 U55 R34 D71 R55 D58 R83)
+
+# these wires should get 135
+#wire_1=(R98 U47 R26 D63 R33 U87 L62 D20 R33 U53 R51)
+#wire_2=(U98 R91 D20 R16 D67 R40 U7 R15 U6 R7)
+
+# read in data from file instead
+exec 3<input.txt
+IFS="," read -u 3 -a wire_1
+IFS="," read -u 3 -a wire_2
+
+trace_wire() {
+    local -n w=$1
+    local -n b=$2
+    local -n c=$3
+    local -n w1cost=$4
+    wire_number=$5
+    cur_vert=0
+    cur_horz=0
+    moved=0
+    last_replace_char="-"
+    cost=0
+
+    for operation in "${w[@]}"; do
+        direction=${operation:0:1}
+        amount=${operation:1}
+        case $direction in
+            U)
+                operator=+
+                ;;
+            D)
+                operator=-
+                ;;
+            L)
+                operator=-
+                ;;
+            R)
+                operator=+
+                ;;
+        esac
+
+        case $direction in
+            U|D)
+                for (( moved=1; moved <= $amount; moved++ )); do
+                    cur_vert=$((cur_vert${operator}1))
+                    cost=$((cost+1))
+                    if [ $wire_number -eq 1 ]; then
+                        if ! [ ${w1cost[$cur_horz,$cur_vert]+a} ]; then
+                            w1cost[$cur_horz,$cur_vert]=$cost
+                        fi
+                    fi
+                    if [ ${b[$cur_horz,$cur_vert]+a} ] && [ $wire_number -eq 2 ]; then
+                        if [ ${b[$cur_horz,$cur_vert]} -eq 1 ]; then
+                            cross_wires[$cur_horz,$cur_vert]=$((${w1cost[$cur_horz,$cur_vert]}+$cost))
+                            b[$cur_horz,$cur_vert]=3
+                        fi
+                        continue
+                    fi
+                    b[$cur_horz,$cur_vert]=$wire_number
+                done
+                ;;
+            L|R)
+                for (( moved=1; moved <= $amount; moved++ )); do
+                    cur_horz=$((cur_horz${operator}1))
+                    cost=$((cost+1))
+                    if [ $wire_number -eq 1 ]; then
+                        if ! [ ${w1cost[$cur_horz,$cur_vert]+a} ]; then
+                            w1cost[$cur_horz,$cur_vert]=$cost
+                        fi
+                    fi
+                    if [ ${b[$cur_horz,$cur_vert]+a} ] && [ $wire_number -eq 2 ]; then
+                        if [ ${b[$cur_horz,$cur_vert]} -eq 1 ]; then
+                            cross_wires[$cur_horz,$cur_vert]=$((${w1cost[$cur_horz,$cur_vert]}+$cost))
+                            b[$cur_horz,$cur_vert]=3
+                        fi
+                        continue
+                    fi
+                    b[$cur_horz,$cur_vert]=$wire_number
+                done
+                ;;
+        esac
+    done
+}
+
+declare -A board
+declare -A cross_wires
+declare -A wire_1_cost
+echo "Tracing first wire"
+trace_wire wire_1 board cross_wires wire_1_cost 1
+echo "Tracing second wire"
+trace_wire wire_2 board cross_wires wire_1_cost 2
+
+echo "Wires cross at:"
+min_cost=-1
+for cross in "${!cross_wires[@]}"; do
+    echo "  $cross ${cross_wires[$cross]}"
+    cost=${cross_wires[$cross]}
+    if [ $min_cost -lt 0 ] || [ $min_cost -gt $cost ]; then
+        min_cost=$cost
+    fi
+done
+
+echo Min cost: $min_cost