16 votes

Day 5: Hydrothermal Venture

Today's problem description: https://adventofcode.com/2021/day/5

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

28 comments

  1. [2]
    PapaNachos
    Link
    Part B was a bit finicky, but this was pretty entertaining. I feel like Advent of Code has a problem like this every year. I love whenever I can break out regular expressions Day 5 Part A - Python...

    Part B was a bit finicky, but this was pretty entertaining. I feel like Advent of Code has a problem like this every year. I love whenever I can break out regular expressions

    Day 5 Part A - Python

    I used a nested default dict like @spit-evil-olive-tips recommended the other day. It worked great for handling my grid and making it so I could expand it. And I build a regular expression the grabbed the x and y coordinates and walked through them incrementing the values of each coordinate it passes. Then just count up anything with more than vent at a given location

    from collections import defaultdict
    import re
    
    #data = test_data
    data = real_data
    data = data.split('\n')
    
    grid = defaultdict(lambda: defaultdict(int))
    
    pattern = re.compile(r'(\d+),(\d+) -> (\d+),(\d+)')
    
    for vent in data:
        results = re.search(pattern, vent)
        cords = results[0]
        x1, y1, x2, y2 = int(results[1]), int(results[2]), int(results[3]), int(results[4])
        if x1 == x2:
            for i in range(min([y1, y2],), max([y1,y2])+1):
                grid[x1][i] = grid[x1][i] + 1
        elif y1 == y2:
            for i in range(min([x1, x2],), max([x1,x2])+1):
                grid[i][y1] = grid[i][y1] + 1
    count = 0
    for x in grid.keys():
        for y in grid[x].keys():
            if grid[x][y] > 1:
                count = count + 1
                
    print(count)
    
    Day 5 Part B - Python

    My original method worked well enough that I just had to add walking through diagonals. It was pretty simple conceptually, but a bit tedious to get all the x1 vs x2 and y1 vs y2 and +/- and what not in the right order.

    from collections import defaultdict
    import re
    
    #data = test_data
    data = real_data
    data = data.split('\n')
    
    grid = defaultdict(lambda: defaultdict(int))
    
    pattern = re.compile(r'(\d+),(\d+) -> (\d+),(\d+)')
    
    for vent in data:
        #print(vent)
        results = re.search(pattern, vent)
        cords = results[0]
        x1, y1, x2, y2 = int(results[1]), int(results[2]), int(results[3]), int(results[4])
        if x1 == x2:
            for i in range(min([y1, y2],), max([y1,y2])+1):
                #print(x1, i)
                grid[x1][i] = grid[x1][i] + 1
        elif y1 == y2:
            for i in range(min([x1, x2],), max([x1,x2])+1):
                #print(i, y1)
                grid[i][y1] = grid[i][y1] + 1
        else:
            if x2 > x1:
                if y2 > y1:
                    for index, x in enumerate(range(x1, x2+1)):
                        #print(x, y1 + index)
                        grid[x][y1+index] = grid[x][y1+index] + 1 
                else:
                    for index, x in enumerate(range(x1, x2+1)):
                        #print(x, y1 - index)
                        grid[x][y1-index] = grid[x][y1-index] + 1
            else:
                if y2 > y1:
                    for index, x in enumerate(range(x2, x1+1)):
                        #print(x, y2 - index)
                        grid[x][y2-index] = grid[x][y2-index] + 1
                else:
                    for index, x in enumerate(range(x2, x1+1)):
                        grid[x][y2+index] = grid[x][y2+index] + 1
                        #print(x, y2 + index)
    count = 0
    for x in grid.keys():
        for y in grid[x].keys():
            if grid[x][y] > 1:
                count = count + 1
                
    print(count)
    
    Tips
    • The text parsing required here is a bit more sophisticate than what we've been using. If you're not already familiar with them, regular expressions (AKA Regex) are a very handy approach to this

    • Pay special attention in part B. If you run into problems it may help to walk through the path one step at a time and make sure it's travelling at the correct angle

    6 votes
    1. spit-evil-olive-tips
      Link Parent
      we used the exact same regex! I definitely agree that judicious use of regexes is much better than manual string-splitting and parsing. Perl and other languages have given them a bad name by...

      we used the exact same regex! I definitely agree that judicious use of regexes is much better than manual string-splitting and parsing. Perl and other languages have given them a bad name by encouraging their overuse.

      another neat trick, along the lines of the nested defaultdict, is that you can use tuples as dictionary keys because they're immutable:

      >>> d = dict()
      >>> key = [1, 2]
      >>> d[key] = True
      Traceback (most recent call last):
        File "<stdin>", line 1, in <module>
      TypeError: unhashable type: 'list'
      >>> key = (1, 2)
      >>> d[key] = True
      >>> d
      {(1, 2): True}
      

      so in this case it's possible to represent the grid as a single layer dict where the keys are (x, y) tuples, as I did in my "part 3" solution. the possible downside to that is that you can no longer easily iterate a single row of the grid. that doesn't matter for this particular problem but it might in other cases.

      also, a minor Pythonic note, min() and max() both accept an unlimited number of arguments, so min([y1, y2],) can be simplified to min(y1, y2)

      >>> min([69, 420])
      69
      >>> min(69, 420)
      69
      >>> min(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
      1
      
      4 votes
  2. deckard
    Link
    Python golf, day 5. Tips and improvements always appreciated. Part 1 L=[[[int(y)for y in x.split(',')]for x in l.strip().split('->')]for l in open(0)] M=max(sum(sum(L,[]),[]))+1 D=[[0]*M for _ in...

    Python golf, day 5. Tips and improvements always appreciated.

    Part 1
    L=[[[int(y)for y in x.split(',')]for x in l.strip().split('->')]for l in open(0)]
    M=max(sum(sum(L,[]),[]))+1
    D=[[0]*M for _ in range(M)]
    R=lambda a,A:range(min(a,A),max(a,A)+1)
    for l in L:
     s,e=l;x,y=s;X,Y=e
     if x==X:
      for j in R(y,Y):D[j][x]+=1
     elif y==Y:
      for i in R(x,X):D[y][i]+=1
    print(len([c for r in D for c in r if c>1]))
    
    Part 2
    L=[[[int(y)for y in x.split(',')]for x in l.strip().split('->')]for l in open(0)]
    M=max(sum(sum(L,[]),[]))+1
    D=[[0]*M for _ in range(M)]
    R=lambda a,A:range(min(a,A),max(a,A)+1)
    for l in L:
     s,e=l;x,y=s;X,Y=e
     if x==X:
      for j in R(y,Y):D[j][x]+=1
     elif y==Y:
      for i in R(x,X):D[y][i]+=1
     else:
      p=int(X>x)or-1;q=int(Y>y)or-1
      for x,y in zip(range(x,X+p,p),range(y,Y+q,q)):D[y][x]+=1
    print(len([c for r in D for c in r if c>1]))
    
    6 votes
  3. asterisk
    (edited )
    Link
    Python import re, itertools vents = list() with open("input.txt") as file: for line in file: x1, y1, x2, y2 = map(int, re.findall(r"\d+", line)) xo = 1 if x1 <= x2 else -1 yo = 1 if y1 <= y2 else...
    Python
    import re, itertools
    
    vents = list()
    
    with open("input.txt") as file:
        for line in file:
            x1, y1, x2, y2 = map(int, re.findall(r"\d+", line))
            xo = 1 if x1 <= x2 else -1
            yo = 1 if y1 <= y2 else -1
    
            # For Part One
            # if x1 == x2 or y1 == y2:
    
            for x, y in itertools.zip_longest(
                range(x1, x2 + xo, xo),
                range(y1, y2 + yo, yo),
                fillvalue=x1 if x1 == x2 else y1 if y1 == y2 else None,
            ):
                vents.append((x, y))
    
    overlaps = {}
    
    for e in vents:
        overlaps[e] = overlaps.get(e, 0) + 1
    
    points = 0
    
    for _, o in overlaps.items():
        if o > 1:
            points += 1
    
    print("Answer:", points)  # 7436, 21104
    
    6 votes
  4. Crestwave
    Link
    This reminds me a lot of 2019's Crossed Wires. Part 1 #!/usr/bin/awk -f { split($0, line, " -> ") split(line[1], start, ",") split(line[2], end, ",") x = start[1] y = start[2] if (start[1] !=...

    This reminds me a lot of 2019's Crossed Wires.

    Part 1
    #!/usr/bin/awk -f
    {
    	split($0, line, " -> ")
    	split(line[1], start, ",")
    	split(line[2], end, ",")
    
    	x = start[1]
    	y = start[2]
    
    	if (start[1] != end[1] && start[2] != end[2])
    		next
    
    	if (start[1] != end[1])
    		diff = start[1] - end[1]
    	else
    		diff = start[2] - end[2]
    
    	if (diff < 0)
    		diff = diff * -1
    
    	for (i = 0; i <= diff; ++i) {
    		grid[x, y] += 1
    
    		if (start[1] < end[1])
    			x += 1
    		else if (start[1] > end[1])
    			x -= 1
    		else if (start[2] < end[2])
    			y += 1
    		else if (start[2] > end[2])
    			y -= 1
    	}
    }
    
    END {
    	for (i in grid)
    		if (grid[i] >= 2)
    			total += 1
    
    	print total
    }
    
    Part 2
    #!/usr/bin/awk -f
    {
    	split($0, line, " -> ")
    	split(line[1], start, ",")
    	split(line[2], end, ",")
    
    	x = start[1]
    	y = start[2]
    
    	if (start[1] != end[1])
    		diff = start[1] - end[1]
    	else
    		diff = start[2] - end[2]
    
    	if (diff < 0)
    		diff = diff * -1
    
    	for (i = 0; i <= diff; ++i) {
    		grid[x, y] += 1
    
    		if (start[1] < end[1])
    			x += 1
    		if (start[1] > end[1])
    			x -= 1
    		if (start[2] < end[2])
    			y += 1
    		if (start[2] > end[2])
    			y -= 1
    	}
    }
    
    END {
    	for (i in grid)
    		if (grid[i] >= 2)
    			total += 1
    
    	print total
    }
    

    I liked today's challenge overall. I actually had another solution initially, but when part 2 went like this, I decided to rewrite it for fun.

    Old Part 2
    #!/usr/bin/awk -f
    {
    	split($0, line, " -> ")
    	split(line[1], start, ",")
    	split(line[2], end, ",")
    
    	x = start[1]
    	y = start[2]
    
    	if (start[1] < end[1]) {
    		for (x = start[1]; x <= end[1]; ++x) {
    			grid[x, y] += 1
    
    			if (start[2] < end[2]) { 
    				y += 1
    			} else if (start[2] > end[2]) {
    				y -= 1
    			}
    		}
    
    	} else if (start[1] > end[1]) {
    		for (x = start[1]; x >= end[1]; --x) {
    			grid[x, y] += 1
    
    			if (start[2] < end[2]) { 
    				y += 1
    			} else if (start[2] > end[2]) {
    				y -= 1
    			}
    		}
    	} else if (start[2] < end[2]) {
    		for (y = start[2]; y <= end[2]; ++y) {
    			grid[x, y] += 1
    
    			if (start[1] < end[1]) {
    				x ++ 1
    			} else if (start[1] > end[1]) {
    				x -= 1
    			}
    		}
    	} else if (start[2] > end[2]) {
    		for (y = start[2]; y >= end[2]; --y) {
    			grid[x, y] += 1
    
    			if (start[1] < end[1]) {
    				x ++ 1
    			} else if (start[1] > end[1]) {
    				x -= 1
    			}
    		}
    	}
    }
    
    END {
    	for (i in grid) {
    		if (grid[i] >= 2) {
    			total += 1
    		}
    	}
    
    	print total
    
    	# debug visual
    	if (FILENAME == "sample") {
    		for (y = 0; y <= 9; ++y) {
    			for (x = 0; x <= 9; ++x) {
    				if (grid[x, y] == "") {
    					printf("%s", ".")
    				} else {
    					printf("%s", grid[x, y])
    				}
    			}
    
    			print ""
    		}
    	}
    }
    
    5 votes
  5. [7]
    DataWraith
    (edited )
    Link
    Phew. Part 2 took me longer than I would like to admit. Turns out, when you specify a parser that relies on a newline at the end of the input, you'd better include a final newline in your test...

    Phew. Part 2 took me longer than I would like to admit. Turns out, when you
    specify a parser that relies on a newline at the end of the input, you'd better
    include a final newline in your test case...

    As usual for me, the solution is in Rust.

    Setup & Parsing
    #![feature(drain_filter)]
    
    use std::collections::HashMap;
    
    use nom::{
        bytes::complete::tag, character::complete::multispace1, character::complete::space0, IResult,
    };
    
    #[derive(Debug, Eq, PartialEq, Hash, Copy, Clone)]
    struct Coordinate {
        x: i16,
        y: i16,
    }
    
    #[derive(Debug)]
    struct Line {
        start: Coordinate,
        end: Coordinate,
    }
    
    fn parse_position(input: &str) -> IResult<&str, Coordinate> {
        let (input, x) = nom::character::complete::i16(input)?;
        let (input, _) = tag(",")(input)?;
        let (input, y) = nom::character::complete::i16(input)?;
    
        Ok((input, Coordinate { x, y }))
    }
    
    fn parse_arrow(input: &str) -> IResult<&str, ()> {
        let (input, _) = space0(input)?;
        let (input, _) = tag("->")(input)?;
        let (input, _) = space0(input)?;
    
        Ok((input, ()))
    }
    
    fn parse_line(input: &str) -> IResult<&str, Line> {
        let (input, start) = parse_position(input)?;
        let (input, _) = parse_arrow(input)?;
        let (input, end) = parse_position(input)?;
        let (input, _) = multispace1(input)?;
    
        Ok((input, Line { start, end }))
    }
    
    fn parse_input(input: &str) -> Vec<Line> {
        let (_, lines) = nom::multi::many1(parse_line)(input).unwrap();
        return lines;
    }
    

    Writing a parser here is probably overkill, but I wanted to further familiarize myself with nom.

    Helper functions
    fn line_coordinates(l: &Line) -> Vec<Coordinate> {
        let dx = (l.end.x - l.start.x).clamp(-1, 1);
        let dy = (l.end.y - l.start.y).clamp(-1, 1);
    
        let mut cur = Coordinate {
            x: l.start.x,
            y: l.start.y,
        };
    
        let mut result = Vec::new();
    
        loop {
            result.push(cur);
    
            if cur.x == l.end.x && cur.y == l.end.y {
                break;
            };
    
            cur = Coordinate {
                x: cur.x + dx,
                y: cur.y + dy,
            };
        }
    
        result
    }
    

    This returns a vector of all coordinates in a line. I like the use of clamp(-1, 1) here. It's a bit unfortunate that this returns a vector; I should try to convert it into an iterator if I find more time to work on this.

    Edit: Here is what I came up with to return an iterator. I don't quite understand why the trailing + '_ is necessary here. Ah, the mysteries of the borrow checker...

    Iterator version
    fn line_coordinates(l: &Line) -> impl std::iter::Iterator<Item = Coordinate> + '_ {
        let dx = (l.end.x - l.start.x).clamp(-1, 1);
        let dy = (l.end.y - l.start.y).clamp(-1, 1);
    
        let mut cur = Coordinate {
            x: l.start.x,
            y: l.start.y,
        };
    
        std::iter::once(cur).chain(std::iter::from_fn(move || {
            if cur.x == l.end.x && cur.y == l.end.y {
                return None;
            };
    
            cur = Coordinate {
                x: cur.x + dx,
                y: cur.y + dy,
            };
    
            Some(cur)
        }))
    }
    
    Part 1

    This filters out all diagonal lines using drain_filterand then counts the number of times each coordinate appears in the remaining lines using a HashMap.

    fn solve(input: &str) -> u16 {
        let mut lines = parse_input(input);
        lines.drain_filter(|line| line.start.x != line.end.x && line.start.y != line.end.y);
    
        let mut vent_map = HashMap::new();
    
        for line in lines {
            for coord in line_coordinates(&line) {
                let e = vent_map.entry(coord).or_insert(0);
                *e += 1;
            }
        }
    
        let mut overlap_sum = 0;
        for (_, &v) in vent_map.iter() {
            if v > 1 {
                overlap_sum += 1;
            }
        }
    
        overlap_sum
    }
    
    fn main() {
        println!("{}", solve(include_str!("../../input-05.txt")));
    }
    
    Part 2 This is very similar to part 1, except I'm not filtering out diagonal lines.
    fn solve(input: &str) -> i16 {
        let lines = parse_input(input);
    
        let mut vent_map = HashMap::new();
    
        for line in lines {
            for coord in line_coordinates(&line) {
                let e = vent_map.entry(coord).or_insert(0);
                *e += 1;
            }
        }
    
        let mut overlap_sum = 0;
    
        for (_, &v) in vent_map.iter() {
            if v > 1 {
                overlap_sum += 1;
            }
        }
    
        overlap_sum
    }
    
    fn main() {
        println!("{}", solve(include_str!("../../input-05.txt")));
    }
    
    5 votes
    1. Liru
      Link Parent
      I just want to say that I completely forgot about drain_filter, it would've been super useful for me for yesterday's code. Thanks for reminding me of it.

      I just want to say that I completely forgot about drain_filter, it would've been super useful for me for yesterday's code. Thanks for reminding me of it.

      1 vote
    2. [2]
      wycy
      Link Parent
      Our Rust implementations are pretty similar, except I ended up using a Vec to store the final vent map in the end rather than a HashMap. Kind of forgot about HashMaps despite using them for this...

      Our Rust implementations are pretty similar, except I ended up using a Vec to store the final vent map in the end rather than a HashMap. Kind of forgot about HashMaps despite using them for this very purpose in previous years. I think I'll refactor mine to use as HashMap like yours later.

      1 vote
      1. DataWraith
        Link Parent
        Funny, I refactored mine into a Vec (kind of...) because the HashMap was slow... ^_^ Code / Spoilers The idea was to insert all coordinates into a Vec, sort it, and then count the number of...

        Funny, I refactored mine into a Vec (kind of...) because the HashMap was slow... ^_^

        Code / Spoilers

        The idea was to insert all coordinates into a Vec, sort it, and then count the number of duplicates — I was not sure whether sorting or hashing would be faster.

        fn solve(input: &str) -> usize {
            let (_, lines) = parse_input(input).unwrap();
        
            let mut vent_line_coords: Vec<Coordinate> = lines
                .iter()
                .flat_map(|line| line_coordinates(&line))
                .collect();
        
            vent_line_coords.sort_unstable();
        
            vent_line_coords
                .array_windows()
                .filter(|[a, b, c]| c == b && c != a)
                .count()
        }
        

        However, the HashMap ended up being faster, and then I ran out of patience and did not try your approach of nested Vecs...

        I'll have to steal the signum function though. And here I thought I was being clever when using clamp(-1, 1)...

        1 vote
    3. [3]
      Eabryt
      Link Parent
      Quick question, when I try to run through your code for Part I I'm hitting errors for your line 85 | let e = vent_map.entry(coord).or_insert(0); | ^^^^^ the trait `Eq` is not implemented for...

      Quick question, when I try to run through your code for Part I I'm hitting errors for your line

      85 |             let e = vent_map.entry(coord).or_insert(0);
         |                                    ^^^^^ the trait `Eq` is not implemented for `Coordinate`
         |                                    ^^^^^ the trait `Hash` is not implemented for `Coordinate`
      

      As someone who's using this project to learn Rust, I feel like this error message is probably something obvious that I'm missing?

      My initial guess was related to how I'm declaring vent_map, but I'm doing the same thing you are.

      1 vote
      1. [2]
        blitz
        Link Parent
        Are you including the derives on the line above the struct definition? #[derive(Debug, Eq, PartialEq, Hash, Copy, Clone)] struct Coordinate { Those tell the compiler that it can make the standard...

        Are you including the derives on the line above the struct definition?

        #[derive(Debug, Eq, PartialEq, Hash, Copy, Clone)]
        struct Coordinate {
        

        Those tell the compiler that it can make the standard assumptions for hash and eq.

        2 votes
        1. Eabryt
          Link Parent
          Ahh, nope, that was it, thanks! Today was my introduction to derive, so I'm not surprised I missed it. That's cool to learn!

          Ahh, nope, that was it, thanks! Today was my introduction to derive, so I'm not surprised I missed it.

          That's cool to learn!

          1 vote
  6. tomf
    Link
    This is similar to Crossed Wires from a few years back. For those of us working in spreadsheets, its possible -- but not easy. Most people end up with 8000+ formulas. I knew this day would come,...

    This is similar to Crossed Wires from a few years back. For those of us working in spreadsheets, its possible -- but not easy. Most people end up with 8000+ formulas.

    I knew this day would come, but I'm taking my first day off. :)

    4 votes
  7. Gyrfalcon
    Link
    Much like many others, I suspected what part 2 would be after reading part 1. But then I didn't do anything to prepare for it to happen, so I ended up needing to do some modification and a little...

    Much like many others, I suspected what part 2 would be after reading part 1. But then I didn't do anything to prepare for it to happen, so I ended up needing to do some modification and a little debugging because I thought I could swap the points around when making the lines but that was not the case for all diagonal lines if I wanted them to be actually correct. Also learned that you have to define your own hash function if you want to use a custom type as a dictionary key in Nim, which is interesting, but I guess it makes everything more explicit. Looking at the other solutions here it looks like making a Point type and using it for things probably made my solution longer and possibly slower than it really needed to be but it does the job.

    Part 1
    import sugar, std/[strformat, sequtils, strutils, tables, hashes]
    
    type Point = object of RootObj
      x: int
      y: int
    
    func initPoint(x: int, y: int): Point =
      result.x = x
      result.y = y
    
    func hash(x: Point): Hash =
      return !$(hash(x.x) !& hash(x.y))
    
    func generateLine(point1: Point, point2: Point): seq[Point] =
      var line: seq[Point]
      if point1.x == point2.x:
        if point1.y < point2.y:
          for ydx in point1.y .. point2.y:
            line.add(initPoint(point1.x, ydx))
        else:
          for ydx in point2.y .. point1.y:
            line.add(initPoint(point1.x, ydx))
    
      elif point1.y == point2.y:
        if point1.x < point2.x:
          for xdx in point1.x .. point2.x:
            line.add(initPoint(xdx, point1.y))
        else:
          for xdx in point2.x .. point1.x:
            line.add(initPoint(xdx, point1.y))
    
      return line
    
    proc parseInput(inputFile: string): seq[(Point, Point)] =
      var input: seq[string] = collect(newSeq):
        for line in inputFile.lines: line
    
      var points: seq[(Point, Point)]
      for line in input:
        var splitLine: seq[string] = split(line, " -> ")
        var leftSplit: seq[int] = map(split(splitLine[0], ","),
                                      (x: string) => parseInt(x))
        var rightSplit: seq[int] = map(split(splitLine[1], ","),
                                      (x: string) => parseInt(x))
    
        points.add((initPoint(leftSplit[0], leftSplit[1]),
                    initPoint(rightSplit[0], rightSplit[1])))
    
      return points
    
    proc main(inputFile: string) =
      var lines: seq[(Point, Point)] = parseInput(inputFile)
      var points: seq[Point]
    
      for line in lines:
        points = concat(points, generateLine(line[0], line[1]))
    
      var countPoints = toCountTable(points)
      sort(countPoints)
    
      var numDangers: int
      for point, count in pairs(countPoints):
        if count > 1:
          inc numDangers
    
      echo &"The number of dangerous points is {numDangers}"
    
    when is_main_module:
      main("test.txt")
      main("input.txt")
    
    Part 2 diff
    @@ -11,7 +11,9 @@ func initPoint(x: int, y: int): Point =
     func hash(x: Point): Hash =
       return !$(hash(x.x) !& hash(x.y))
     
    -func generateLine(point1: Point, point2: Point): seq[Point] =
    +func generateLine(point1: Point,
    +                  point2: Point,
    +                  diag: bool): seq[Point] =
       var line: seq[Point]
       if point1.x == point2.x:
         if point1.y < point2.y:
    @@ -29,6 +31,29 @@ func generateLine(point1: Point, point2: Point): seq[Point] =
           for xdx in point2.x .. point1.x:
             line.add(initPoint(xdx, point1.y))
     
    +  elif diag:
    +    # bottom left to top right
    +    if point1.x < point2.x and point1.y < point2.y:
    +      for (xdx, ydx) in zip(toSeq(countup(point1.x, point2.x, 1)),
    +                            toSeq(countup(point1.y, point2.y, 1))):
    +        line.add(initPoint(xdx, ydx))
    +    # bottom right to top left
    +    elif point1.x > point2.x and point1.y < point2.y:
    +      for (xdx, ydx) in zip(toSeq(countdown(point1.x, point2.x, 1)),
    +                            toSeq(countup(point1.y, point2.y, 1))):
    +        line.add(initPoint(xdx, ydx))
    +    # top left to bottom right
    +    elif point1.x < point2.x and point1.y > point2.y:
    +      for (xdx, ydx) in zip(toSeq(countup(point1.x, point2.x, 1)),
    +                            toSeq(countdown(point1.y, point2.y, 1))):
    +        line.add(initPoint(xdx, ydx))
    +    # top right to bottom left
    +    elif point1.x > point2.x and point1.y > point2.y:
    +      for (xdx, ydx) in zip(toSeq(countdown(point1.x, point2.x, 1)),
    +                            toSeq(countdown(point1.y, point2.y, 1))):
    +        line.add(initPoint(xdx, ydx))
    +
    +
       return line
     
     proc parseInput(inputFile: string): seq[(Point, Point)] =
    @@ -53,7 +78,7 @@ proc main(inputFile: string) =
       var points: seq[Point]
     
       for line in lines:
    -    points = concat(points, generateLine(line[0], line[1]))
    +    points = concat(points, generateLine(line[0], line[1], false))
     
       var countPoints = toCountTable(points)
       sort(countPoints)
    @@ -65,6 +90,21 @@ proc main(inputFile: string) =
     
       echo &"The number of dangerous points is {numDangers}"
     
    +  points = @[]
    +  numDangers = 0
    +
    +  for line in lines:
    +    points = concat(points, generateLine(line[0], line[1], true))
    +
    +  countPoints = toCountTable(points)
    +  sort(countPoints)
    +
    +  for point, count in pairs(countPoints):
    +    if count > 1:
    +      inc numDangers
    +
    +  echo &"The number of diagonally dangerous points is {numDangers}"
    +
     when is_main_module:
       main("test.txt")
       main("input.txt")
    
    4 votes
  8. [2]
    Bauke
    Link
    Vectors, how fun! Today I also added runtime counters to each day so I've included the days here when ran in release mode (in debug it's about 10 times slower). Runtime amounts Advent of Code 2021...

    Vectors, how fun! Today I also added runtime counters to each day so I've included the days here when ran in release mode (in debug it's about 10 times slower).

    Runtime amounts
    Advent of Code 2021
    
    Day 01 Part 1: 1451
    Day 01 Part 2: 1395
    - Runtime: 146.69µs
    
    Day 02 Part 1: 1727835
    Day 02 Part 2: 1544000595
    - Runtime: 1.91268ms
    
    Day 03 Part 1: 1092896
    Day 03 Part 2: 4672151
    - Runtime: 1.911088ms
    
    Day 04 Part 1: 8580
    Day 04 Part 2: 9576
    - Runtime: 788.298µs
    
    Day 05 Part 1: 6687
    Day 05 Part 2: 19851
    - Runtime: 31.912838ms
    
    Total runtime: 36.671594ms
    
    Imports, setup and creating the Vector
    use std::{collections::HashMap, str::FromStr};
    
    use color_eyre::{
      eyre::{eyre, Error},
      Result,
    };
    
    pub fn solve() -> Result<()> {
      let input_data = include_str!("../../data/day_05.txt").trim();
      println!("Day 05 Part 1: {}", part_1(input_data)?);
      println!("Day 05 Part 2: {}", part_2(input_data)?);
      Ok(())
    }
    
    #[derive(Debug)]
    struct Vector {
      a: (isize, isize),
      b: (isize, isize),
    }
    
    impl FromStr for Vector {
      type Err = Error;
    
      fn from_str(s: &str) -> Result<Self, Self::Err> {
        let numbers = s
          .replace(" -> ", ",")
          .split(",")
          .map(str::parse)
          .collect::<Result<Vec<_>, _>>()?;
    
        if numbers.len() == 4 {
          Ok(Self {
            a: (numbers[0], numbers[1]),
            b: (numbers[2], numbers[3]),
          })
        } else {
          Err(eyre!("Invalid input: {}", s))
        }
      }
    }
    
    Implementing the vector coordinates calculations

    This ended up being quite repetitive, I think if I spent some time thinking about generalizing this it could be much shorter buuut, if it works it works. And it's probably fast enough to not matter.

    impl Vector {
      fn diagonal_coordinates(&self) -> Vec<(isize, isize)> {
        let x_coordinates = {
          let x_amount = (self.a.0 - self.b.0).abs();
          if self.a.0 < self.b.0 {
            (0..=x_amount)
              .into_iter()
              .map(|x| self.a.0 + x)
              .collect::<Vec<_>>()
          } else {
            (0..=x_amount)
              .into_iter()
              .map(|x| self.a.0 - x)
              .collect::<Vec<_>>()
          }
        };
    
        let y_coordinates = {
          let y_amount = (self.a.1 - self.b.1).abs();
          if self.a.1 < self.b.1 {
            (0..=y_amount)
              .into_iter()
              .map(|x| self.a.1 + x)
              .collect::<Vec<_>>()
          } else {
            (0..=y_amount)
              .into_iter()
              .map(|x| self.a.1 - x)
              .collect::<Vec<_>>()
          }
        };
    
        x_coordinates.into_iter().zip(y_coordinates).collect()
      }
    
      fn horizontal_coordinates(&self) -> Vec<(isize, isize)> {
        let y = self.a.1;
    
        let (x1, x2) = if self.a.0 < self.b.0 {
          (self.a.0, self.b.0)
        } else {
          (self.b.0, self.a.0)
        };
    
        (x1..=x2).into_iter().map(|x| (x, y)).collect()
      }
    
      fn vertical_coordinates(&self) -> Vec<(isize, isize)> {
        let x = self.a.0;
    
        let (y1, y2) = if self.a.1 < self.b.1 {
          (self.a.1, self.b.1)
        } else {
          (self.b.1, self.a.1)
        };
    
        (y1..=y2).into_iter().map(|y| (x, y)).collect()
      }
    }
    
    Counting the amount of overlapping coordinates
    fn count_result(coordinates: HashMap<(isize, isize), isize>) -> usize {
      coordinates
        .into_iter()
        .filter(|(_, amount)| amount >= &2)
        .count()
    }
    
    Solving part 1

    Since part 1 doesn't need the diagonals I just throw them away after parsing.

    fn part_1(input: &str) -> Result<usize> {
      let vectors = input
        .lines()
        .filter_map(|line| {
          if let Ok(vector) = Vector::from_str(line) {
            if vector.a.0 == vector.b.0 || vector.a.1 == vector.b.1 {
              return Some(vector);
            }
          }
    
          None
        })
        .collect::<Vec<_>>();
    
      let mut travelled_coordinates = HashMap::<(isize, isize), isize>::new();
      for vector in vectors {
        let coordinates = if vector.a.0 == vector.b.0 {
          vector.vertical_coordinates()
        } else {
          vector.horizontal_coordinates()
        };
    
        for coordinate in coordinates {
          let amount = travelled_coordinates.entry(coordinate).or_default();
          *amount += 1;
        }
      }
    
      Ok(count_result(travelled_coordinates))
    }
    
    Solving part 2
    fn part_2(input: &str) -> Result<usize> {
      let vectors = input
        .lines()
        .map(str::parse)
        .collect::<Result<Vec<Vector>>>()?;
    
      let mut travelled_coordinates = HashMap::<(isize, isize), isize>::new();
      for vector in vectors {
        let coordinates = if vector.a.0 == vector.b.0 {
          vector.vertical_coordinates()
        } else if vector.a.1 == vector.b.1 {
          vector.horizontal_coordinates()
        } else {
          vector.diagonal_coordinates()
        };
    
        for coordinate in coordinates {
          let amount = travelled_coordinates.entry(coordinate).or_default();
          *amount += 1;
        }
      }
    
      Ok(count_result(travelled_coordinates))
    }
    
    3 votes
    1. kari
      Link Parent
      I like how you used SPOILERS a HashMap. I iterated through every single point in every single line to find the maxes and then set up 0-filled vectors for my grid. While it's not super complex to...

      I like how you used

      SPOILERS a HashMap.

      I iterated through every single point in every single line to find the maxes and then set up 0-filled vectors for my grid. While it's not super complex to write (not that the HashMap is either), it's definitely slower than your implementation...

      2 votes
  9. bhrgunatha
    (edited )
    Link
    Racket Notes I guess most of us have a few procedures bundled up into a small library that are useful for AoC problems and take the pain out of having to do really common tasks. Mine are:...

    Racket

    Notes

    I guess most of us have a few procedures bundled up into a small library that are useful for AoC problems and take the pain out of having to do really common tasks.

    Mine are:

    • read-input - convert the input into a list of strings.
    • map-input - same but run a procedure against each line.
    • words - split a string on white-space.
    • numbers - extract only numbers from a string into a list.

    I find it fun to parse complex input, but not today.

    (map-input numbers "day05.input")
    

    vents is a hash-table from co-ordinate (list x y) to count.*

    Part 1 ignores diagonal lines, so I decided to write 2 plot procedures for orthogonal and diagonal lines. To support those I wrote the in-plot sequence which goes either forward or reverse though the range taking care to include the end point.

    (define (orthogonal? line)
      (match-define (list x1 y1 x2 y2) line)
      (xor (= x1 x2) (= y1 y2)))
    
    (define (in-plot start end)
      (if (> start end)
          (in-range start (sub1 end) -1)
          (in-range start (add1 end)  1)))
    

    It feels wrong but since one of the axes won't change for the orthogonal plot - it turns out tidier writing nested iterators (using for*) one of which only iterates once. This meant I didn't have to write any fussy logic to check which axis changes.

    (define (plot-orthogonal line vents)
      (match-define (list x1 y1 x2 y2) line)
      (for*/fold ([vents vents])
                 ([y (in-plot y1 y2)]
                  [x (in-plot x1 x2)])
        (hash-update vents (list x y) add1 0)))
    

    hash-update is nice - you give it a procedure to update an existing key's hash value (add1 here) and either a default value (0 in this case) or another procedure that generates the default value which gets inserted into the table if the key is missing.

    Update:
    * - I was a bit disappointed at the time of each part of my answer. The obvious choice was to change the hash table to a 2d array (using vectors). This wastes a lot of space but is faster. I need to find the maximum co-ordinate from the input to generate the array. At the end I scan the whole array to find the dangerous vents.

    hash table - averaging out over 50 runs:
    Part 1: cpu time: 102.4 real time: 102.4 gc time: 25.4
    Part 2: cpu time: 232.4 real time: 233 gc time: 62.6

    2d array - averaging out over 50 runs:
    Part 1: cpu time: 16.58 real time: 16.58 gc time: 1.74
    Part 2: cpu time: 22.22 real time: 22.3 gc time: 1.72

    lol: more time spent garbage collecting with the hash table than the runtime of the array.

    Part 1
    (define (part-01 input)
      (define vents
        (for/fold ([vents (hash)])
                   ([line input]
                   #:when (orthogonal? line))
          (plot-orthogonal line vents)))
      (dangerous vents))
    
    (define (dangerous vents)
      (count (curry < 1) (hash-values vents)))
    
    Part 2

    The interesting thing about plot-diagonal is that it iterates through both axes in parallel (using for) as opposed to nested (using for*)

    (define (part-02 input)
      (define vents
        (for*/fold ([vents (hash)])
                   ([line input])
          (if (orthogonal? line)
              (plot-orthogonal line vents)
              (plot-diagonal line vents))))
      (dangerous vents))
    
    (define (plot-diagonal line vents)
      (match-define (list x1 y1 x2 y2) line)
      (for/fold ([vents vents])
                ([y (in-plot y1 y2)]
                 [x (in-plot x1 x2)])
        (hash-update vents (list x y) add1 0)))
    
    Inspired by @PapaNachos :)
    Tips

    Anything involving a 2d grid usually has y increasing down the screen.
    For some reason my gut instinct is to iterate x values first. For AoC I generally iterate through increasing y values in the outer loop and then nest the x values. That way any debug output gets output in the same direction as the displayed examples.

    3 votes
  10. wycy
    (edited )
    Link
    Rust Edit: Updated code to use a different approach for storing the map for part 2 just for the novelty. Rust use std::env; use std::io::{self, prelude::*, BufReader}; use std::fs::File; use...

    Rust

    Edit: Updated code to use a different approach for storing the map for part 2 just for the novelty.

    Rust
    use std::env;
    use std::io::{self, prelude::*, BufReader};
    use std::fs::File;
    use std::collections::HashMap;
    
    extern crate regex;
    use regex::Regex;
    
    #[derive(Clone,Hash,PartialEq,Eq)]
    struct Point {
        x: isize,
        y: isize,
    }
    
    #[derive(Clone)]
    struct Line {
        start: Point,
        end: Point,
    }
    impl From<&String> for Line {
        fn from(s: &String) -> Self {
            let re = Regex::new(r"(\d+),(\d+) -> (\d+),(\d+)").unwrap();
            let matches = re.captures(s).unwrap();
            Self {
                start: Point { x: matches[1].parse().unwrap(), y: matches[2].parse().unwrap() },
                end:   Point { x: matches[3].parse().unwrap(), y: matches[4].parse().unwrap() },
             }
        }
    }
    impl Line {
        pub fn points(&self, diagonals: bool) -> Vec<Point> {
            let mut points = Vec::new();
            let dx = self.end.x-self.start.x;
            let dy = self.end.y-self.start.y;
            let delta = if dx != 0 { dx } else { dy };
            if !diagonals && dx != 0 && dy != 0 { return points; } // part1: only vertical or horizontal lines
            let dx = dx.signum();
            let dy = dy.signum();
            for i in 0..delta.abs() + 1 {
                points.push(Point { x: self.start.x + i * dx, y: self.start.y + i * dy });
            }
            points
        }
    }
    
    fn day05(input: &str) -> io::Result<()> {
        let file = File::open(input).expect("Input file not found.");
        let reader = BufReader::new(file);
    
        // Input
        let input: Vec<String> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {}", err),
            Ok(result) => result,
        };
        let lines: Vec<_> = input.iter().map(Line::from).collect();
    
        // Part 1 (using nested Vecs)
        let mut vent_map = vec![vec![0; 1000]; 1000];
        for line in lines.clone() {
            for pt in line.points(false) {
                vent_map[pt.x as usize][pt.y as usize] += 1;
            }
        }
        let part1 = vent_map.iter().flat_map(|x| x.iter().filter(|&x| *x >= 2)).count();    
        println!("Part 1: {}", part1); // 6461
    
        // Part 2 (using HashMap)
        let mut vent_map: HashMap<Point,usize> = HashMap::new();
        for line in lines.clone() {
            for pt in line.points(true) {
                *vent_map.entry(pt).or_insert(0) += 1;
            }
        }
        let part2 = vent_map.iter().filter(|(_,&num)| num >= 2).count();
        println!("Part 2: {}", part2); // 18065
    
        Ok(())
    }
    
    fn main() {
        let args: Vec<String> = env::args().collect();
        let filename = &args[1];
        day05(&filename).unwrap();
    }
    
    3 votes
  11. 3d12
    Link
    Wow, I was definitely expecting fewer people saying part 2 was difficult. The diff between my part 1 and part 2 is literally 2 lines, I just removed the validation check I put on the input step....

    Wow, I was definitely expecting fewer people saying part 2 was difficult. The diff between my part 1 and part 2 is literally 2 lines, I just removed the validation check I put on the input step. Though to be fair, I suspected the twist right away when the puzzle said to ignore certain inputs... ;)

    Part 1
    const fs = require('fs');
    const readline = require('readline');
    
    let inputArr = [];
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		try {
    			inputArr.push(line);
    		} catch(e) {
    			console.error(e);
    		}
    	}
    }
    
    function findMaxDimensions(vectorArray) {
    	let maxX = 0;
    	let maxY = 0;
    	for (const vectorPair of vectorArray) {
    		if (vectorPair.x1 > maxX) {
    			maxX = vectorPair.x1;
    		}
    		if (vectorPair.y1 > maxY) {
    			maxY = vectorPair.y1;
    		}
    		if (vectorPair.x2 > maxX) {
    			maxX = vectorPair.x2;
    		}
    		if (vectorPair.y2 > maxY) {
    			maxY = vectorPair.y2;
    		}
    	}
    	return { maxX: maxX, maxY: maxY };
    }
    
    function initGrid(x, y) {
    	let grid = [];
    	for (let i=0; i<=y; i++) {
    		let currentRow = [];
    		for (let j=0; j<=x; j++) {
    			currentRow.push('.');
    		}
    		grid.push(currentRow);
    	}
    	return grid;
    }
    
    function addLine(grid, vector) {
    	let startX = vector.x1;
    	let startY = vector.y1;
    	let endX = vector.x2;
    	let endY = vector.y2;
    	let cursorX = startX;
    	let cursorY = startY;
    	console.log("DEBUG: startX = " + startX + ", startY = " + startY);
    	console.log("DEBUG: endX = " + endX + ", endY = " + endY);
    	console.log("DEBUG: cursorX != endX is " + (cursorX != endX));
    	console.log("DEBUG: cursorY != endY is " + (cursorY != endY));
    	while (true) {
    		console.log("DEBUG: cursorX = " + cursorX + ", cursorY = " + cursorY);
    		let row = grid[cursorY];
    		let currentValue = row[cursorX];
    		if (currentValue === '.') {
    			grid[cursorY][cursorX] = 1;
    		} else {
    			grid[cursorY][cursorX]++;
    		}
    		if (cursorX === endX && cursorY === endY) {
    			break;
    		}
    		console.log("DEBUG: cursorX != endX is " + (cursorX != endX));
    		if (cursorX != endX && cursorX > endX) {
    			cursorX--;
    		} else if (cursorX != endX && cursorX < endX) {
    			cursorX++;
    		}
    		console.log("DEBUG: cursorY != endY is " + (cursorY != endY));
    		if (cursorY != endY && cursorY > endY) {
    			cursorY--;
    		} else if (cursorY != endY && cursorY < endY) {
    			cursorY++;
    		}
    	}
    }
    
    function getPoints(grid) {
    	let points = 0;
    	for (const row of grid) {
    		for (const value of row) {
    			if (value > 1) {
    				points++;
    			}
    		}
    	}
    	return points;
    }
    
    function isDiagonal(vector) {
    	return ((vector.x1 != vector.x2) && (vector.y1 != vector.y2));
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let vectorArray = inputArr.map(e => {
    		let regex = /(\d+),(\d+) -> (\d+),(\d+)/;
    		let found = e.match(regex);
    		return { x1: parseInt(found[1]), y1: parseInt(found[2]),
    			x2: parseInt(found[3]), y2: parseInt(found[4])
    		};
    	});
    	gridDimensions = findMaxDimensions(vectorArray);
    	let grid = initGrid(gridDimensions.maxX, gridDimensions.maxY);
    	console.log(grid.map(e => e.join('')).join('\n'));
    	for (const vector of vectorArray) {
    		if (!isDiagonal(vector)) {
    			console.log("DEBUG: Operating on vector " + vector.x1 + ","
    				+ vector.y1 + " -> " + vector.x2 + "," + vector.y2);
    			addLine(grid, vector);
    			console.log(grid.map(e => e.join('')).join('\n'));
    		}
    	}
    	console.log("Answer found! " + getPoints(grid));
    })();
    
    Part 2
    const fs = require('fs');
    const readline = require('readline');
    
    let inputArr = [];
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		try {
    			inputArr.push(line);
    		} catch(e) {
    			console.error(e);
    		}
    	}
    }
    
    function findMaxDimensions(vectorArray) {
    	let maxX = 0;
    	let maxY = 0;
    	for (const vectorPair of vectorArray) {
    		if (vectorPair.x1 > maxX) {
    			maxX = vectorPair.x1;
    		}
    		if (vectorPair.y1 > maxY) {
    			maxY = vectorPair.y1;
    		}
    		if (vectorPair.x2 > maxX) {
    			maxX = vectorPair.x2;
    		}
    		if (vectorPair.y2 > maxY) {
    			maxY = vectorPair.y2;
    		}
    	}
    	return { maxX: maxX, maxY: maxY };
    }
    
    function initGrid(x, y) {
    	let grid = [];
    	for (let i=0; i<=y; i++) {
    		let currentRow = [];
    		for (let j=0; j<=x; j++) {
    			currentRow.push('.');
    		}
    		grid.push(currentRow);
    	}
    	return grid;
    }
    
    function addLine(grid, vector) {
    	let startX = vector.x1;
    	let startY = vector.y1;
    	let endX = vector.x2;
    	let endY = vector.y2;
    	let cursorX = startX;
    	let cursorY = startY;
    	console.log("DEBUG: startX = " + startX + ", startY = " + startY);
    	console.log("DEBUG: endX = " + endX + ", endY = " + endY);
    	console.log("DEBUG: cursorX != endX is " + (cursorX != endX));
    	console.log("DEBUG: cursorY != endY is " + (cursorY != endY));
    	while (true) {
    		console.log("DEBUG: cursorX = " + cursorX + ", cursorY = " + cursorY);
    		let row = grid[cursorY];
    		let currentValue = row[cursorX];
    		if (currentValue === '.') {
    			grid[cursorY][cursorX] = 1;
    		} else {
    			grid[cursorY][cursorX]++;
    		}
    		if (cursorX === endX && cursorY === endY) {
    			break;
    		}
    		console.log("DEBUG: cursorX != endX is " + (cursorX != endX));
    		if (cursorX != endX && cursorX > endX) {
    			cursorX--;
    		} else if (cursorX != endX && cursorX < endX) {
    			cursorX++;
    		}
    		console.log("DEBUG: cursorY != endY is " + (cursorY != endY));
    		if (cursorY != endY && cursorY > endY) {
    			cursorY--;
    		} else if (cursorY != endY && cursorY < endY) {
    			cursorY++;
    		}
    	}
    }
    
    function getPoints(grid) {
    	let points = 0;
    	for (const row of grid) {
    		for (const value of row) {
    			if (value > 1) {
    				points++;
    			}
    		}
    	}
    	return points;
    }
    
    function isDiagonal(vector) {
    	return ((vector.x1 != vector.x2) && (vector.y1 != vector.y2));
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let vectorArray = inputArr.map(e => {
    		let regex = /(\d+),(\d+) -> (\d+),(\d+)/;
    		let found = e.match(regex);
    		return { x1: parseInt(found[1]), y1: parseInt(found[2]),
    			x2: parseInt(found[3]), y2: parseInt(found[4])
    		};
    	});
    	gridDimensions = findMaxDimensions(vectorArray);
    	let grid = initGrid(gridDimensions.maxX, gridDimensions.maxY);
    	console.log(grid.map(e => e.join('')).join('\n'));
    	for (const vector of vectorArray) {
    		console.log("DEBUG: Operating on vector " + vector.x1 + ","
    			+ vector.y1 + " -> " + vector.x2 + "," + vector.y2);
    		addLine(grid, vector);
    		console.log(grid.map(e => e.join('')).join('\n'));
    	}
    	console.log("Answer found! " + getPoints(grid));
    })();
    
    3 votes
  12. [3]
    reifyresonance
    (edited )
    Link
    Late to the party. I've been learning Rust for this, as well as getting back into programming, which I haven't really done much of for ~2yrs. Languages I've been good at in the past are python and...

    Late to the party. I've been learning Rust for this, as well as getting back into programming, which I haven't really done much of for ~2yrs. Languages I've been good at in the past are python and go. So I am a little behind, just finished day 5 today. (Also, etiquette Q - should I just blast all the prior threads with my solutions there? I feel like not, but I want people to see them/give feedback on them...)

    Related: Feedback very much appreciated. I kinda hate the way I got the diagonal lines in, but don't know a better way. Rust ranges can't have a negative step, you have to do (1..100).rev() instead of (100..1).step_by(-1), and I don't know how to do this neatly. The python code I want to write is range(start[0], end[0], step_x). A match with 4 separate arms maybe? The vertical/horizontal lines piece is so clean in comparison...

    I originally had each segment represented as a HashSet of points, and then a nested for loop checking the intersection of every combination. This worked but was slowwww. The person mentoring me walked me through figuring out a more performant solution. Another thing that would be neat to hear from other people is: given a working solution, what steps do you take to arrive at a performant solution? What I ended up with was collecting all the points from every segment, sorting them, and then getting ONLY duplicates, then deduping and counting that. I would love to know if there's a functional way to do that - for an iterator, keep a value if it's equal to the prior value. I thought this looks kinda like a fold? That's an operation that keeps state, and I could just set the accumulator to the prior value, but then there's no filter predicate... I could also use the nightly (_, duplicates) = vec.partition_dedup(); and then sort, dedup, filter, but I have been avoiding nightly-only functions because I figure there's probably a better way to do it.

    Other little questions:

    • Is there a way to impl on a type alias, so I can do Segment::new instead of new_segment?
    • Segment also doesn't need to be collected into a vector, right? So it could be some Iterator<Point> or something... what would that look like? Quick search for how to return an iterator seems complicated.
    • Why would one make Point an [i32; 2] vs a (i32, i32) vs a struct Point { x: i32, y: i32}?

    Anyways, here's what I came up with. I will look at other answers in this thread after posting.

    Rust
    use std::fs;
    
    type Point = (i32, i32);
    
    type Segment = Vec<Point>;
    
    fn new_segment(start: Point, end: Point) -> Segment {
        let first_x = start.0.min(end.0);
        let second_x = start.0.max(end.0);
        let first_y = start.1.min(end.1);
        let second_y = start.1.max(end.1);
    
        if start.0 == end.0 {
            // is vertical
            (first_y..=second_y).map(|y| (first_x, y)).collect()
        } else if start.1 == end.1 {
            // is horizontal
            (first_x..=second_x).map(|x| (x, first_y)).collect()
        } else {
            // is diagonal @ 45 degrees
            // replace with Vec::new() for part 1 sln
            let step_x = if end.0 > start.0 { 1 } else { -1 };
            let step_y = if end.1 > start.1 { 1 } else { -1 };
    
            let mut points: Segment = Vec::new();
            let mut cur = start;
            loop {
                points.push(cur);
                if cur == end {
                    break;
                }
                cur = (cur.0 + step_x, cur.1 + step_y);
            }
    
            points
        }
    }
    
    fn main() {
        let contents = fs::read_to_string("src/input.txt").unwrap();
        let lines = contents.lines();
        let parsed: Vec<Vec<Vec<i32>>> = lines
            .map(|l| {
                l.split(" -> ")
                    .map(|coords| coords.split(',').map(|x| x.parse().unwrap()).collect())
                    .collect()
            })
            .collect();
    
        let mut all_points: Vec<Point> = Vec::new();
        for seg in parsed {
            all_points.extend(new_segment((seg[0][0], seg[0][1]), (seg[1][0], seg[1][1])))
        }
    
        all_points.sort();
    
        let mut dupe_points: Vec<Point> = Vec::new();
        let mut last: Point = (-1, -1);
        for point in all_points {
            if point == last {
                dupe_points.push(point);
            }
            last = point;
        }
    
        dupe_points.dedup();
        println!("Answer is: {:?}", dupe_points.len());
    }
    
    3 votes
    1. [2]
      Liru
      Link Parent
      Unfortunately, Rust's ranges are horribly anemic. If you want to do something like that, you'd probably write your own custom iterator for it. One workaround in this case could be...

      Rust ranges can't have a negative step, you have to do (1..100).rev() instead of (100..1).step_by(-1), and I don't know how to do this neatly. The python code I want to write is range(start[0], end[0], step_x).

      Unfortunately, Rust's ranges are horribly anemic. If you want to do something like that, you'd probably write your own custom iterator for it. One workaround in this case could be (1..100).map(|&x| 100-x) or something similar. Still ugly, but it gets you what you want.

      Another thing that would be neat to hear from other people is: given a working solution, what steps do you take to arrive at a performant solution?

      This is a tough question, but it essentially condenses down to "eliminate any factors that are not needed, or group them together". For example, in the lanternfish problem, it's tempting to model the lanternfish as their own object, but you only really want to know one thing about each one.

      What I ended up with was collecting all the points from every segment, sorting them, and then getting ONLY duplicates, then deduping and counting that. I would love to know if there's a functional way to do that - for an iterator, keep a value if it's equal to the prior value.

      Are you restricting yourself to just the Rust stdlib? If not, I'd suggest learning about some common crates that can be useful for development. In this case, I used the itertools crate, which should be kind of familiar if you have experience with Python. In particular, the counts() extension method may be what you wanted (with an additional filter operation).

      If you want to create your own iterator to do that, it would be a good exercise, as well.

      Is there a way to impl on a type alias, so I can do Segment::new instead of new_segment?

      On a type alias, no. You'd have to create a newtype for that.

      Segment also doesn't need to be collected into a vector, right? So it could be some Iterator<Point> or something... what would that look like? Quick search for how to return an iterator seems complicated.

      Here's a sample, at least for this challenge's needs. Note that I'm doing this on my phone, so there may be errors:

      Rust vent point iterator
      use std::cmp::Ordering;
      
      type Point = (i32, i32);
      
      struct VentLine {
          current_point: Point,
          final_point: Point,
          done: bool,
      }
      
      impl VentLine {
          pub fn new(from: Point, to: Point) -> Self {
              Self {
                  current_point: from,
                  final_point: to,
                  done: false,
              }
          }
      }
      
      impl Iterator for VentLine {
          type Item = (i32, i32);
          
          fn next(&mut self) -> Option<Self::Item> {
              if self.done { return None; }
              if self.current_point == self.final_point { self.done = true; return Some(self.current_point); }
          
              let cur = self.current_point;
          
              self.current_point.0 += match self.current_point.0.cmp(&self.final_point.0) {
                  Ordering::Less => 1,
                  Ordering::Equal => 0,
                  Ordering::Greater => -1,
              };
              
              self.current_point.1 += match self.current_point.1.cmp(&self.final_point.1) {
                  Ordering::Less => 1,
                  Ordering::Equal => 0,
                  Ordering::Greater => -1,
              };
      
              Some(cur)
          }
      }
      
      fn main() {
          let a = VentLine::new((1,1), (5,5));
          
          for i in a {
              println!("{:?}", i);
          }
      }
      

      Basically, the iterator returns None when there's nothing left to do, and Some(x) when you want it to return x. Generators are going to be in Rust soon, in case you miss having an explicit yield keyword.

      Why would one make Point an [i32; 2] vs a (i32, i32) vs a struct Point { x: i32, y: i32}?

      • Array for easier iteration/indexing, and communicating a fixed size. Not the ideal choice in this case, as it's more of an optimization to Vec<i32> than an alternative to a tuple in this kind of case, IMO.
      • (i32, i32) for when you just want the point information as a single data structure, and want to make a quick or simple implementation.
      • struct for when you want to implement methods for the data and have nicer access to it. It can also have traits that lets you convert it into the other two forms easily, if needed.

      In this challenge, considering that the points don't need to have any methods on them in this case, I'd either lean towards a tuple, or a struct with a #[derive(PartialEq, Eq, Hash)] on it. (My personal solution when I wanted to get this done was the tuple, but going back and making it a struct is definitely something I might do.)

      4 votes
      1. reifyresonance
        Link Parent
        Hi! Thank you SO much for the detailed reply. Lots to think about, & I will respond properly.. at some point. Work this week is very busy with holiday orders, so I'm not sure when I'll next have...

        Hi! Thank you SO much for the detailed reply. Lots to think about, & I will respond properly.. at some point. Work this week is very busy with holiday orders, so I'm not sure when I'll next have the bandwidth to go through all this but I wanted to say some words to let you know I really appreciate the help.

        2 votes
  13. [2]
    Eabryt
    Link
    Alright I'm working on Part I in Rust and have hit a snag. Right now my plan is to basically build a grid as I go, and for each coordinate I'll update my grid with all the spots it hits. The...

    Alright I'm working on Part I in Rust and have hit a snag.

    Right now my plan is to basically build a grid as I go, and for each coordinate I'll update my grid with all the spots it hits.

    The problem I'm having right now is basic, some coordinates the x/y values increase, some they decrease. I was hoping I could basically do

    for x in start..finish {
    
    }
    

    but it seems like the language doesn't like that when start is bigger than finish. Is there an easy way to do this or will I just need to do some sort of check and reverse them?

    2 votes
    1. Bauke
      Link Parent
      I did the same thing and hit the same snag and yeah, you have to check which is bigger and then make the range ascending. See Rust Playground. Minor hint/spoiler Also unless your finish variable...

      I did the same thing and hit the same snag and yeah, you have to check which is bigger and then make the range ascending. See Rust Playground.

      Minor hint/spoiler

      Also unless your finish variable has +1 you'll want an inclusive range (..=).

      5 votes
  14. kari
    Link
    Today was cool! My implementation is definitely not as efficient as possible but I think I'm finally figuring out how to do things in a way that's a little more idiomatic to Rust (which in turn...

    Today was cool! My implementation is definitely not as efficient as possible but I think I'm finally figuring out how to do things in a way that's a little more idiomatic to Rust (which in turn looks 1000x nicer than some of my earlier days).

    Rust (both days)
    Structs
    pub mod day5;
    
    #[derive(Debug)]
    enum Direction {
        Up,
        Down,
        Left,
        Right,
        UpRight,
        UpLeft,
        DownRight,
        DownLeft,
    }
    
    #[derive(Clone, Copy, Debug)]
    struct Point(u32, u32);
    
    #[derive(Clone, Copy, Debug)]
    struct Line(Point, Point);
    
    #[derive(Clone, Debug)]
    struct Grid {
        grid: Vec<Vec<u32>>,
    }
    
    impl Point {
        fn from(x: u32, y: u32) -> Self {
            Point(x, y)
        }
    }
    
    impl Line {
        fn from(string: String) -> Self {
            let points = string
                .split(" -> ")
                .collect::<Vec<_>>()
                .iter()
                .map(|point| {
                    point
                        .split(",")
                        .collect::<Vec<_>>()
                        .iter()
                        .map(|coord| {
                            coord
                                .parse::<u32>()
                                .expect("Could not parse some coordinate")
                        })
                        .collect::<Vec<_>>()
                })
                .collect::<Vec<_>>();
    
            let p1 = points.get(0).expect("Didn't find point 1!");
            let p2 = points.get(1).expect("Didn't find point 2!");
    
            Line(
                Point::from(
                    *p1.get(0).expect("Didn't find x1"),
                    *p1.get(1).expect("Didn't find y1"),
                ),
                Point::from(
                    *p2.get(0).expect("Didn't find x2"),
                    *p2.get(1).expect("Didn't find y2"),
                ),
            )
        }
    
        fn get_direction(&self) -> Direction {
            // We're assuming lines can only be vertical or horizontal
            if self.0 .0 < self.1 .0 {
                if self.0 .1 < self.1 .1 {
                    Direction::DownRight
                } else if self.0 .1 > self.1 .1 {
                    Direction::UpRight
                } else {
                    Direction::Right
                }
            } else if self.0 .0 > self.1 .0 {
                if self.0 .1 < self.1 .1 {
                    Direction::DownLeft
                } else if self.0 .1 > self.1 .1 {
                    Direction::UpLeft
                } else {
                    Direction::Left
                }
            } else if self.0 .1 < self.1 .1 {
                Direction::Down
            } else if self.0 .1 > self.1 .1 {
                Direction::Up
            } else {
                panic!("Line doesn't have a direction!")
            }
        }
    }
    
    impl Grid {
        fn new(lines: Vec<Line>) -> Self {
            // let grid: Vec<Vec<u32>> = Vec::new();
            let maxes = find_maxes(&lines);
    
            let mut grid = vec![vec![0; maxes.0 as usize + 1]; maxes.1 as usize + 1];
    
            for line in lines {
                match line.get_direction() {
                    Direction::Right => {
                        for i in line.0 .0..=line.1 .0 {
                            grid[line.0 .1 as usize][i as usize] += 1;
                        }
                    }
                    Direction::Left => {
                        for i in line.1 .0..=line.0 .0 {
                            grid[line.0 .1 as usize][i as usize] += 1;
                        }
                    }
                    Direction::Down => {
                        for i in line.0 .1..=line.1 .1 {
                            grid[i as usize][line.0 .0 as usize] += 1;
                        }
                    }
                    Direction::Up => {
                        for i in line.1 .1..=line.0 .1 {
                            grid[i as usize][line.0 .0 as usize] += 1;
                        }
                    }
                    Direction::UpRight => {
                        // "Right" uses - since our loop actually starts at the second coord
                        let mut x_coord = line.1 .0 as i32;
                        for i in line.1 .1..=line.0 .1 {
                            grid[i as usize][x_coord as usize] += 1;
                            x_coord -= 1;
                        }
                    }
                    Direction::UpLeft => {
                        // "Left" uses + since our loop actually starts at the second coord
                        let mut x_coord = line.1 .0 as i32;
                        for i in line.1 .1..=line.0 .1 {
                            grid[i as usize][x_coord as usize] += 1;
                            x_coord += 1;
                        }
                    }
                    Direction::DownRight => {
                        let mut x_coord = line.0 .0 as i32;
                        for i in line.0 .1..=line.1 .1 {
                            grid[i as usize][x_coord as usize] += 1;
                            x_coord += 1;
                        }
                    }
                    Direction::DownLeft => {
                        let mut x_coord = line.0 .0 as i32;
                        for i in line.0 .1..=line.1 .1 {
                            grid[i as usize][x_coord as usize] += 1;
                            x_coord -= 1;
                        }
                    }
                }
            }
    
            Grid { grid }
        }
    
        fn count_dangerous(&self, threshold: u32) -> u32 {
            let mut dangerous = 0;
            for row in &self.grid {
                for column in row {
                    if column >= &threshold {
                        dangerous += 1;
                    }
                }
            }
    
            dangerous
        }
    }
    
    fn find_maxes(lines: &Vec<Line>) -> (u32, u32) {
        let mut max_x = 0;
        let mut max_y = 0;
    
        for line in lines {
            if line.0 .0 > max_x {
                max_x = line.0 .0;
            }
            if line.0 .1 > max_y {
                max_y = line.0 .1;
            }
    
            if line.1 .0 > max_x {
                max_x = line.1 .0;
            }
            if line.1 .1 > max_y {
                max_y = line.1 .1;
            }
        }
    
        (max_x, max_y)
    }
    
    "Main" file
    use crate::day5::Grid;
    use crate::day5::Line;
    use crate::lib::aoc;
    
    pub fn run5() {
        let lines: Vec<Line> = aoc::get_lines("./inputs/day5.in")
            .iter()
            .map(|line| Line::from(line.to_string()))
            .collect();
        let mut lines_p1 = lines.clone();
        lines_p1.retain(|line| line.0 .0 == line.1 .0 || line.0 .1 == line.1 .1);
    
        let grid_p1: Grid = Grid::new(lines_p1);
        let grid_p2: Grid = Grid::new(lines);
    
        aoc::output(
            5,
            "dangerous spots",
            grid_p1.count_dangerous(2) as i32,
            grid_p2.count_dangerous(2) as i32,
        );
    }
    
    2 votes
  15. blitz
    Link
    Today took me a while because I wanted to implement the iter() method on a line and to do it in a way that would be compatible with the rest of the standard library (that is, to have iter() return...

    Today took me a while because I wanted to implement the iter() method on a line and to do it in a way that would be compatible with the rest of the standard library (that is, to have iter() return a struct that implements the Iterator trait) Thankfully I was able to do it! I ended up writing a big utility module called geometry that does most of the heavy lifting; the actual main file is tiny by comparison!

    https://git.sr.ht/~blitz/advent-of-code-2021/tree/master/item/day5

    2 votes
  16. spit-evil-olive-tips
    Link
    Part 1 my initial solution was horribly inefficient, but got the job done. from dataclasses import dataclass import re RIDGE_RE = re.compile('(\d+),(\d+) -> (\d+),(\d+)') @dataclass class Ridge:...
    Part 1

    my initial solution was horribly inefficient, but got the job done.

    from dataclasses import dataclass
    import re
    
    RIDGE_RE = re.compile('(\d+),(\d+) -> (\d+),(\d+)')
    
    @dataclass
    class Ridge:
        x1: int
        y1: int
        x2: int
        y2: int
    
        @classmethod
        def parse(cls, line):
            match = RIDGE_RE.match(line)
            coordinates = [int(value) for value in match.groups()]
            return cls(*coordinates)
    
        def get_points(self):
            if self.x1 == self.x2:
                start = min(self.y1, self.y2)
                end = max(self.y1, self.y2)
                return [(self.x1, y) for y in range(start, end+1)]
            elif self.y1 == self.y2:
                start = min(self.x1, self.x2)
                end = max(self.x1, self.x2)
                return [(x, self.y1) for x in range(start, end+1)]
            else:
                return []
    
        @staticmethod
        def get_overlap(r1, r2):
            points1 = set(r1.get_points())
            points2 = set(r2.get_points())
            if points1 == points2:
                return []
            else:
                overlap = points1.intersection(points2)
                return overlap
    
    def main():
        with open('005.txt') as file:
            lines = file.readlines()
    
        ridges = [Ridge.parse(line) for line in lines]
        all_overlaps = set()
        for ridge1 in ridges:
            for ridge2 in ridges:
                if ridge1 != ridge2:
                    overlap = Ridge.get_overlap(ridge1, ridge2)
                    all_overlaps.update(overlap)
    
        print(sorted(all_overlaps))
        print(len(all_overlaps))
    
    if __name__ == '__main__':
        main()
    

    it takes ~17 seconds to run on my full puzzle input, but I was running on the example input while I was writing it, so it didn't make much of a difference to the overall time.

    Part 2

    biggest stumbling block I had with part 2 was getting this logic to work correctly for diagonal lines of both positive and negative slope.

    @@ -26,7 +26,11 @@
                 end = max(self.x1, self.x2)
                 return [(x, self.y1) for x in range(start, end+1)]
             else:
    -            return []
    +            delta_x = 1 if self.x2 > self.x1 else -1
    +            delta_y = 1 if self.y2 > self.y1 else -1
    +            range_x = range(self.x1, self.x2+delta_x, delta_x)
    +            range_y = range(self.y1, self.y2+delta_y, delta_y)
    +            return [(x, y) for x, y in zip(range_x, range_y)]
     
         @staticmethod
         def get_overlap(r1, r2):
    
    Part 3

    my initial solution worked, but it's much slower than it needs to be, mainly because of the O(n^2) algorithm of looping through every possible pair of ridges and computing their intersection.

    a "not sure why I didn't think of doing it this way initially" refactoring is to just keep counts of the overlapping points:

    @@ -1,3 +1,4 @@
    +from collections import Counter
     from dataclasses import dataclass
     import re
     
    @@ -32,30 +33,21 @@
                 range_y = range(self.y1, self.y2+delta_y, delta_y)
                 return [(x, y) for x, y in zip(range_x, range_y)]
     
    -    @staticmethod
    -    def get_overlap(r1, r2):
    -        points1 = set(r1.get_points())
    -        points2 = set(r2.get_points())
    -        if points1 == points2:
    -            return []
    -        else:
    -            overlap = points1.intersection(points2)
    -            return overlap
     
     def main():
         with open('005.txt') as file:
             lines = file.readlines()
     
         ridges = [Ridge.parse(line) for line in lines]
    -    all_overlaps = set()
    -    for ridge1 in ridges:
    -        for ridge2 in ridges:
    -            if ridge1 != ridge2:
    -                overlap = Ridge.get_overlap(ridge1, ridge2)
    -                all_overlaps.update(overlap)
     
    -    print(sorted(all_overlaps))
    -    print(len(all_overlaps))
    +    points = Counter()
    +    for ridge in ridges:
    +        for point in ridge.get_points():
    +            points[point] += 1
    +
    +    overlap = sum(1 for point, count in points.items() if count > 1)
    +    print(overlap)
    +
    

    run time went from ~30 seconds to ~180 milliseconds.

    2 votes
  17. Crespyl
    Link
    Whoops, I forgot to post my solution to this one on the day, but I'll post it now anyway for posterity. This was another one where the set up in the first part made the second part pretty easy (I...

    Whoops, I forgot to post my solution to this one on the day, but I'll post it now anyway for posterity.

    This was another one where the set up in the first part made the second part pretty easy (I actually got my part 2 answer first by accident, forgetting the "ignore the diagonals" bit).

    Part 1 Ruby
    # utility function to return a list of each point on the line from `a` to `b`
    def line_points(a, b)
      points = [a]
      cur_x, cur_y = a
    
      until cur_x == b[0] && cur_y == b[1]
        cur_x += 1 if a[0] < b[0]
        cur_x -= 1 if a[0] > b[0]
    
        cur_y += 1 if a[1] < b[1]
        cur_y -= 1 if a[1] > b[1]
    
        points << [cur_x, cur_y]
      end
    
      points
    end
    
    def compute_p1(input)
      map = Hash.new(0)
    
      input.lines.each do |line|
        start, finish = line.split(' -> ').map { _1.split(',').map(&:to_i) }
        next unless start[0] == finish[0] || start[1] == finish[1]
    
        line_points(start, finish).each do |point|
          map[point] += 1
        end
      end
    
      map.values.count { _1 > 1 }
    end
    
    Part 2 Ruby Part 2 is identical to the first part, except the statement to skip diagonal lines is commented out.
    def compute_p2(input)
      map = Hash.new(0)
    
      input.lines.each do |line|
        start, finish = line.split(' -> ').map { _1.split(',').map(&:to_i) }
        #next unless start[0] == finish[0] || start[1] == finish[1]
    
        line_points(start, finish).each do |point|
          map[point] += 1
        end
      end
    
      map.values.count { _1 > 1 }
    end
    
    2 votes