Thanks @CapelliC … that’s kind of you. @Boris, I note the LOC when I code stuff and then try to improve on it as a heuristic for how well I’ve used the language. How exactly you count things doesn’t matter for that purpose. Compare for example my github repo with @BarrensZeppelin – he literally solves the same things in half the LOC and if you compare the code it means what you expect: more direct solutions and/or a wider vocabulary of standard predicates.
1 Like
Is anyone else still working on day 21 part 2? I’m working on a simpler sub-problem. Rather than working on the infinite grid straight away, I’m consider how I’d handle a grid copied just once to the left, and then copied twice. I think the gist is there.
It looks to me like the whole calculation has to be repeated for 1 copy, but I suspect that for the 2nd copy, it will be entirely determined by the first. Then it is easy to extend it for any number of copies, and hopefully in all directions.
I expect the final answer to be something on the same order of 3751 * 26501365/131 ~ 7.6e8, so it should be feasible to count all the cells in the worse case scenario. The fastest solution for part 1 of this problem was 1m24sec, but for both parts it was 14m35. I suspect that’s because the solution has some calculation time involved so something like the above might be the ticket 
Presumably this is because: if we can only move up, down, left or right, then a position which is reachable in N moves cannot be reachable in N-1 or N+1 moves (or +/- 3,5,7, etc.). Because diagonal moves are not allowed.
With up, down, left or right, each move either:
- Takes 1 step towards the position
- Takes 1 step away from the position
… and it would take another step (totalling 2 steps) to get back on track.
Shockingly 1m24 refers to the time it took someone to read the question, solve it and post the answer as opposed to the run time of their code. I don’t even know how that’s possible but alas it is …
would you mind explaining a bit about how your solution works? I haven’t had time to look into part 2 any more until now. gonna put in an hour or so to see if i can progress a bit.
i’ll spend some time trying to understand why your part 1 solution is so efficient – it is much faster than mine.
I’ve cracked part 2; empirically again unfortunately rather than through computer science. Say you have a function link(X-Y, S) which is true iff a coordinate X-Y connects with the starting point in S steps, and you run this:
between(0,10,S), X is 1+(11*S), link(X-1,50).
Here 11 is the width of the sample grid. What you’ll see is that link/2 will alternate between true/false. I.e. the point 1-1 in the original grid is true, in the grid next to it its false, and in the grid next to that its true, and so on.
Easy peasy. I still don’t know why its true, but that’s a story for another day. I’ll edit this post to add a Github link as soon as I have a chance to finish the code.
Here is an answer to your question and a curiosity. The sum of the first n odd numbers is n^2
E.g. 1+3+5+7+9 = 5^2 = 25
What I’m still struggling with on Part 2 is how to scale a calculation to the whole area. I can calculate the number of times any given cell in the original map will occur in its column for the whole area, but not how it spreads out to columns in adjacent maps. For example, for 40 steps, cell 6,6 will scale across the maps in this pattern:
1 2 3 2 1
for a total occurrence in the whole area of 1+2+3+2+1 = 12, whilst cell 1,1 will scale like this:
1 2 3 3 2 1
I can’t figure out what decides which it will be for any given cell.
Here is a 33 LOC solution to day 22. Straightforward; a nice change from working on day 21 part 2 Solution is naive and inefficient but conceptually simple.
Try it if you have time 
Its super fiddly. This is basically where I’m at but using another method. I’m calculating a whole column (for the whole area) and then trying to work out what the other columns should be from it.
EDIT:
Oh wait, I think I’ve understood. I’ll give it a shot now. If it works I suspect it will be amongst the simplest solutions around.
Its a weird solution since it doesn’t work for just any numbers. I’ve no idea why it works for 11 and 5 in the sample, and for 65 for the whole data.
EDIT:
@anon95304481 at what value did 65 steps converge for you with the input data?
Just want to say thank you @anon95304481 for your thoughts on this thread. It has at least taught me how/where/why to use mode directed tabling and how to code from inside out by writing predicates as if they were generators rather than functions. This latter learning especially is reshaping how I think in Prolog drastically at the moment and causing me to refactor everything. Very grateful!
Sorry to dwell on part 1 day 21 @anon95304481, which by now has been solved 5 different ways on this thread, but I think that the fastest possible solution would be the following which takes advantage of the odd even counting:
- Dijkstra’s algorithm to find the shortest path between S and all other points with early stopping at 64 steps.
- Count cells reached at an even steps as it goes.
I think everything we’ve discussed so far will have higher time complexity than that for part 1.
EDIT: Technically it doesn’t even have to be shortest paths – it can be any path at all between S and the rest of the nodes.
I tried the above on the whole input – seems to take ages and then blow up on account of memory. Did you get it working?
Also this 15 LOC solution completes in about 1.3M inferences for the 64 step problem which I think might be faster than the min based tabling solution above, even though it doesn’t use any optimisation. It suggests that maybe a bit too much is happening behind the scenes.
Thanks, but the credits should mostly go to @friguzzi
@anon95304481 I did a quick hard-coded to 64 steps solution on this basis to see what I’d get. Would you mind comparing it to your min tabling solution for time (not inferences, they seem to completely not correspond to time when comparing tabled solutions) ?
With the 15 LOC implementation I get 0.7-1.5 sec to calculate for 64 steps on the whole input. With this walk + odd/even I get 0.16-0.26 sec: a massive improvement even in the worse case scenario.
grid(_,_,[]) --> [].
grid(X0,_,Xs) --> "\n", {X is X0+1}, !, grid(X,1,Xs).
grid(X0,Y0,[p(X0-Y0,V)|Xs]) --> [V],{Y is Y0+1}, !, grid(X0,Y,Xs).
grid(X0,Y0,Xs) --> `.`, {Y is Y0+1}, !, grid(X0,Y,Xs).
next(X0-Y, X-Y) :- X is 1+X0, p(X-Y,_).
next(X0-Y, X-Y) :- X is -1+X0, p(X-Y,_).
next(X-Y0, X-Y) :- Y is 1+Y0, p(X-Y,_).
next(X-Y0, X-Y) :- Y is -1+Y0, p(X-Y,_).
tourist(_,[],Acc,Acc) :- !.
tourist(Vs,[_-N|T],A,C) :- N > 64, !, tourist(Vs,T,A,C).
tourist(Vs,[H-_|T],A,C) :- ht_get(Vs, H, _), !, tourist(Vs,T,A,C).
tourist(Vs,[H-N0|T],A,C) :-
(N0 mod 2 =:= 0-> A1 is A+1; A1=A),
ht_put(Vs, H, N0), N is N0+1,
findall(X-N, (next(H,X), \+ ht_get(Vs,X,_)), Next),
append(T,Next,Stack),
!, tourist(Vs, Stack,A1,C).
solve(File, Part1) :-
phrase_from_file(grid(1, 1, Ps0), File),
include([p(_,V)]>>(V\=0'#), Ps0, Ps),
retractall(p(_,_)), maplist(asserta, Ps),
ht_new(Vs), tourist(Vs, [66-66-0], 0, Part1).
Day 23 was straightforward, here is an implementation in 46 LOC. I feel these later day problems are getting a bit too “just-so”. I feel like I learned more transferable things from the earlier problems.
Here is day 24 in 29 LOC. Part1 was easy using either the simplex or clpq library. Part 2 is easy with Python (due to sympy or z3) but hard in Prolog.
The problem: you have objects in 3D space defined by their positions X and their velocity V – both given as 3D vectors. Define a new object given by \bar{X},\bar{V}, which collides with all other objects at some time. I.e. X_i + V_iT_i = \bar{X} + \bar{V}T_i where i indexes all the other objects.
For languages with a symbolic or SMT solver, you can just transcribe this and get a solution.
In Prolog, under clpq, the non-linear constraints remain passive, so it produces no solutions. It so happens that the position and velocity are specified to be integers, but under clpfd, the problem requires domains to be specified. All the numbers in the question have massive ranges other than velocity, which I only know because I solved the problem by other means, so in my answer I specify is the domain for velocity: deeply unsatisfying.
Then there are the idiosyncrasies of clpfd. The domain for velocity is -900 to 900, but if I change it to -1000 to 1000, I get “variables are uninstantiated” related errors. It was surprising that the range of a domain could cause errors like those in the first place!
@BarrensZeppelin, am I right in saying you had the same issues?
Is there a neat way to tackle this in Prolog?
1 Like
I experienced the same issues, yes. I used an even smaller domain for the velocities.
It turns out that you can turn the problem into solving a system of linear equations. See here. But I didn’t explore that idea.
1 Like
This is an excellent observation – I’ll look to refactor into it, but I still feel there is a SMT solver shaped hole in the Prolog toolbox