Yeah. The re-centering part took me a moment to figure out.
data Trie k a = Value a
| Map (M.Map k (Trie k a))
deriving (Functor, Foldable)The difficulty is all over the place and is nothing compared to the 2019AoC, when the problems were actually interesting, thought-out and well written. This is the laziest AoC shite I've seen and I've been doing them since 2017. It seems as if they completely changed the person responsible for the task - they're weak, mostly unimaginative and confusingly worded. Hell, they even go against the Eric Wastl's own "good practices" on problem descriptions.
I'm genuinely curious as to what your non-clever solution is. I've literally took the solution for the first part, changed a few constants, recompiled and had the answer in a few seconds.
I'm on yesterday's challenge, moving cups around in a million-cup circle ten million times.
Yes, this I understand, but how did you manage to make it so slow? I mean, I can't think of a solution that would be convoluted enough. I'm not being facetious or spiteful - the only brute force solution I can think of (make an array of all the cups and perform deletions, searches and insertions in O(n)) is actually harder to implement than slapping an associative container and copypasta some code on top.
In Haskell, the shortest solution I can think of to part 1 is to use lists, where it's dead easy to match off the next 4 elements, split at the next destination, and append the results together. It definitely doesn't scale to part 2. I was back to unboxed mutable vectors (where an element v at index i means that the cup numbered i is immediately followed by the cup numbered v).
Doing three removals/insertions by hand instead of doing the Right Thing and splicing out/in the relevant part of a linked list (however it's being implemented with - I used an associative array). Because the removals and insertions are always of size 3 I was being lazy. In the general case it could be done in O(1) even if the part to be cut out was in the orders of O(n).
You definitely don't just want a linked list, because then lookup of the destination cup is O(n). That's what I tried first in Haskell, and it wasn't going to work for part 2. I guessed @Kosher Salt had something similar.
I'm potentially interested. I don't know much about that site though.
I'm using hashmap to implement a linked list, so I get expected O(1) per lookup. And even without the implementation-provided hashmap I can create a true linked list myself while storing pointers to cups using an array and have a guaranteed O(1) lookup.
Check out https://onlinejudge.org/. Word of warning though: the supported languages are C, C++, Java, Pascal and Python.
18: Simple recursive-descent parser: recurse on '(', return subexpression value on ')'.
That's not a linked list. A (singly-) linked list is just a head consisting of an element and a pointer to the rest of the linked list. They have specific computational properties, one of which is element lookup being O(n). So it's not the right data structure here. If you shove every node into a hashmap, that's a different data structure.
The cups are numbered contiguously from 1 to 1,000,000, so there's no reason to think of hashmaps at all. Just use a 1d array, where indices are cup numbers, and each element is the number of the next cup.
Ah. I'll have to pass.
For 18, did you write the parser from scratch, or use a library? I'd be interested to read your solution if you're happy to share. Here's my Haskell (without blank lines and type signatures):
import Control.Applicative
import qualified Text.ParserCombinators.ReadP as P
token = (<* P.skipSpaces)
readInt = token (P.readS_to_P reads)
parseAtom expr atom =
P.between (token . P.char $ '(') (token . P.char $ ')') expr <|> atom
parseAdd = token (P.char '+') *> pure (+)
parseMult = token (P.char '*') *> pure (*)
parseExpr1 = P.chainl1 (parseAtom parseExpr1 readInt) (parseAdd <|> parseMult)
parseExpr2 = P.chainl1 (parseAtom parseExpr2 parseAddExpr) parseMult
where parseAddExpr = P.chainl1 (parseAtom parseExpr2 readInt) parseAdd
part1 = sum . fmap (fst . head . P.readP_to_S (parseExpr1 <* P.eof)) . lines
<$> readFile "18.input"
part2 = sum . fmap (fst . head . P.readP_to_S (parseExpr2 <* P.eof)) . lines
<$> readFile "18.input"For day 18 I just wrote a simple parser. First it replaced parenthetical subexpressions with their value, starting from the innermost (so that there were no internal parentheses; this was done recursively but because the subexpressions did not contain subexpressions themselves, the recursion only went 1 level deep). When the expression contains no more parentheses, it replaces the first sum or product with its value, and repeats until it has reduced the expression to a single value. I used regular expressions for all of the replacement matching.
^ and $ symbols so it would only match a complete string, and counted how many of the strings were matched.I really haven't touched C++ since college.
We're in a potatoe/potatoh mode. Pedantically speaking, I did not implement a linked list according to this definition. Logically speaking, I did.
...and this is precisely what I did, except I kept the hashmap for some retarded reason (probably thought it would come in handy in part B and forgot to simplify it later). And yes, I would call such an array storing the number of next element a "linked list". Might be just a case of a mental shortcut I use when describing solutions.
Written from scratch, solution for part B:
long solve(const std::string &s, unsigned &idx)
{
std::vector <long> num;
char op = 0;
while (s[idx] != ')') {
if (s[idx] == ' ') {
++idx;
} else if (s[idx] == '(') {
++idx;
long tmp = solve(s, idx);
if (op == '+')
num.back() += tmp;
else
num.push_back(tmp);
} else if (isdigit(s[idx])) {
long tmp = 0;
while (isdigit(s[idx])) {
tmp = tmp * 10 + s[idx] - '0';
++idx;
}
if (op == '+')
num.back() += tmp;
else
num.push_back(tmp);
} else {
assert(s[idx] == '+' || s[idx] == '*');
op = s[idx];
++idx;
}
}
++idx;
long result = 1;
for (auto n : num)
result *= n;
return result;
}