Discussion on: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

View post

Back to Prolog today but rather than battle with reading the input file in Prolog and turning it into relations, which I have no idea where to begin with, I used a Perl one-liner to turn it into Prolog source code. That's not cheating is it?

perl -n -e '/^([A-Za-z0-9]+)\)([A-Za-z0-9]+)/ && print "orbits(object_$1, object_$2).\n"' <input.txt >rules.pl

Part 1 boiled down to finding all possible paths in the graph and counting them.

indirect(C, A) :- 
      orbits(C, A)
    ; orbits(C, B), indirect(B, A).

total(N) :- 
    setof([X, Y], indirect(X, Y), S),
    length(S, N).

Part 2 was more involved but is ultimately a similar algorithm in Prolog, filtering the possible solutions down to a single path between the start and end which does not visit any location twice.

can_jump(X, Y) :-
      orbits(X, Y)
    ; orbits(Y, X). 

part2(Length) :-
    findall(L, (
        orbits(SAN, object_SAN)
      , orbits(YOU, object_YOU)
      , path_to(YOU, SAN, P)
      , length(P, L)
    ), Length).

path_to(X, Y, P) :-
    path_to_impl(X, Y, [X], P).

path_to_impl(X, Y, _, [Y]) :-
    can_jump(X, Y).

path_to_impl(X, Y, L, [Z|Path]) :-
      can_jump(X, Z)
    , \+(member(Z, L))
    , \+(member(Y, L))
    , path_to_impl(Z, Y, [Z|L], Path).

Shortest code for the day?

Jon Bristow • Dec 6 '19 • Edited

Since I solved one based on the Josephus Problem by hand once because I had just seen a numberphile video based upon it, it's only cheating (in my book) if someone else figured it out for you.

I don't think it's even cheating looking at someone else's solution, as long as you write your own version instead of copying it. (renaming doesn't count!)