Advent of Code - adventofcode.com

You are reading a single comment by @wence and its replies. Click here to read the full conversation.

•

Greenbank
Exponential algorithm?!?

Mine runs fine given an input of every number from 1 to 73.

(Most will start to run into trouble given numbers 1 to 30 and it quickly gets uglier from then on.)
```
$ seq 1 73 | time ./10.pl
Part 1: d1=73 d3=1 tot=73
Part 2: 12903063846126135669
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 9264maxresident)k
0inputs+0outputs (0major+618minor)pagefaults 0swaps
```
(Any more than 1..73 and the answer is > 2^64 and I can't be bothered to deal with that right now.)

•

wence in reply to @Greenbank

Exponential algorithm?!?

I first parsed the problem as determining all simple paths in a digraph, so wrote the "obvious" thing (build the graph, call networkx.all_simple_paths). And then after waiting more than 30s I stopped and thought harder and did the next most obvious thing.

[Edit: add what the original "obvious" thing was]

About

@wence started