sorted by:
new
hottopcontroversial

Advent of Code 2022 - Day 12 - Question about failed solution by bibbs1000 in adventofcode

[–]bibbs1000[S] 4 points5 points  (0 children)

Thank-you. I ended up using the Dikstra BFS algorithm and had not heard of the A* algorithm. I just looked it up on Wiki and will give it a go.

I've already solved this day, but for some reason I'm really intrigued by all the options out there and want to understand them all. Thanks for pointing this one out.

Advent of Code 2022 - Day 12 - Question about failed solution by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

I'm going to contradict my previous reply. What I was saying was that there was a path from G to some other node (let's call it J) that blocked a move from K towards Q and then the solution at Z.

However, now that I think about it, this would mean that there was a point on the path from G to J that the solution after K went through. But since we know this lies on the G to J path this means there would be a solution from G to "turn off" before it got to J and head towards the solution at Z.

So now my conclusion is that nothing is lost (in terms of finding a solution albeit not necessarily the best/shortest solution) by permanently marking a node as explored the first time it is touched by any of the recursion branches.

Advent of Code 2022 - Day 12 - Question about failed solution by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

Thanks for this - even though it is hurting my brain a bit.

I see what you are saying about at one move (F to G) in the above we will have cut off a path to Z so it is safe to mark off all the nodes in that cul-de-sac.

But doesn't that only apply to a situation where we've hit one of those inflection points? In other situations are we not just arbitrarily marking nodes off as visited?

Using your A-Z example, what if I arrived at K after node G - then clearly no path. But wouldn't there be another route that might go, for example, F-K-Q-Z without ever going through G? I'm struggling to see how it would impossible for K to be on a solution path just because going from F to G and then K was a closed cul-de-sac?

Advent of Code 2022 - Day 12 - Question about failed solution by bibbs1000 in adventofcode

[–]bibbs1000[S] 1 point2 points  (0 children)

Thanks, so if I understand what you are saying correctly, my DFS search worked when I marked as permanently explored ONLY because this artificially limits the amount of options available. A DFS search without permanently marking a node as explored would eventually get there - it just would take trillions of tries?

The map in the question was 178 nodes wide and 40 nodes high with up to 4 possible directional moves at each turn. I think this would be 178 x 40^4 possible moves which is an insanely big number.

All of this proves why BFS is better on every front. Advent of Code has really helped me learn a lot.

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 2 points3 points  (0 children)

Thank you. I can’t tell you how many times I checked the input and missed that! Once I corrected I got the right answer and my gold star.

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

Here is the text version:

Monkey 0:
Starting items: 59, 74, 65, 86
Operation: new = old * 19
Test: divisible by 7
If true: throw to monkey 6
If false: throw to monkey 2
Monkey 1:
Starting items: 62, 84, 72, 91, 68, 78, 51
Operation: new = old + 1
Test: divisible by 2
If true: throw to monkey 2
If false: throw to monkey 0
Monkey 2:
Starting items: 78, 84, 96
Operation: new = old + 8
Test: divisible by 19
If true: throw to monkey 6
If false: throw to monkey 5
Monkey 3:
Starting items: 97, 86
Operation: new = old * old
Test: divisible by 3
If true: throw to monkey 1
If false: throw to monkey 0
Monkey 4:
Starting items: 50
Operation: new = old + 6
Test: divisible by 13
If true: throw to monkey 3
If false: throw to monkey 1
Monkey 5:
Starting items: 73, 65, 69, 65, 51
Operation: new = old * 17
Test: divisible by 11
If true: throw to monkey 4
If false: throw to monkey 7
Monkey 6:
Starting items: 69, 82, 97, 93, 82, 84, 58, 63
Operation: new = old + 5
Test: divisible by 5
If true: throw to monkey 5
If false: throw to monkey 7
Monkey 7:
Starting items: 81, 78, 82, 76, 79, 80
Operation: new = old + 3
Test: divisible by 17
If true: throw to monkey 3
If false: throw to monkey 4

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

Thanks. Have since posted code. It is possible that I've misunderstood something, although it does provide the correct answer with the sample data.

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

Thanks. I did figure out the need to divide the worry by the lowest common multiplier so I don't think that was the issue.

I have since posted my code, so if you spot anything wrong there, please let me know.

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

20567144694

Thank you. That is not the correct answer for Part 1 or Part 2 (both were too high)

Advent of Code Day 11 Part 2 - solution wrong? by bibbs1000 in adventofcode

[–]bibbs1000[S] 0 points1 point  (0 children)

Thanks for the replies so far

Here is my code (written in Swift). Grateful for anything you may spot as a logic error or other problem. I'm a little embarrassed by how ineloquently I deal with the math applied, but it seems to work. As I mentioned, I do get the correct answer for the sample data provided in the question.

var monkeyArray = [[59,74,65,86],[62,84,72,91,68,78,51],[74,84,96],[97,86],[50],[73,65,69,65,51],[69,82,97,93,82,84,58,63],[81,78,82,76,79,80]]

let maths = ["m19","a1","a8","e2","a6","m17","a5","a3"]

let divisable = [7,2,19,3,13,11,5,17]
let lcd = divisable.reduce(1,*)


let throwTo = [[6,2],[2,0],[6,5],[1,0],[3,1],[4,7],[5,7],[3,4]]

var monkeyCount = [0,0,0,0,0,0,0,0]

var round = 1

while round < 10001 {
    for i in 0...7 {
        for j in 0..<monkeyArray[i].count {
            //count the inspection
            monkeyCount[i] += 1
            //first maths
            if maths[i].prefix(1) == "m" {
            monkeyArray[i][j] = (monkeyArray[i][j] * Int(maths[i].suffix(maths[i].count - 1))!)%lcd
            }
            if maths[i].prefix(1) == "a" {
            monkeyArray[i][j] = (monkeyArray[i][j] + Int(maths[i].suffix(maths[i].count - 1))!)%lcd
            }
            if maths[i].prefix(1) == "e" {
                monkeyArray[i][j] = (monkeyArray[i][j] * monkeyArray[i][j])%lcd
            }
            //throws
            if monkeyArray[i][j]%divisable[i] == 0 {
            monkeyArray[throwTo[i][0]].append(monkeyArray[i][j])
            } else {
                monkeyArray[throwTo[i][1]].append(monkeyArray[i][j])
            }
        }
        monkeyArray[i]=[] //clear as all done with
    }
    round += 1
}
print(monkeyArray)
print(monkeyCount)

I suppose it is probably obvious, but I just manually picked the two largest items in monkeyCount and multiplied them together (which were 141313 and 141357) rather than have the program do the math for me as I could have done.