I tried this out, here is a short write-up.
TL;DR: When very large integers are involved, set_prolog_flag(optimise, true) does not seem to help (on my machine). Also, choosing the right algorithm does make a difference.
The original problem statement can be found here:
https://adventofcode.com/2015/day/6
The essence of the problem is to apply a couple of hundred (300 exactly) instructions (set/reset/flip) to a 1_000_000 element bitset. Every instruction is defined as a rectangle in a 1000x1000 bitmap. The question at the end is “how many bits in the bitmap are on”.
At the bottom of this post you can find the full code listings and the running times I measured. The interesting bits:
- Yes, it is perfectly fine to make an integer with 1_000_000 bits and set/reset/flip those.
- In my original solution, most of the time (95% of about a second) went into generating the “rectangular bitmasks”. The time is spend inside is/2!
- Using
set_prolog_flag(optimise, true) increases the runtime slightly.
The original code for preparing the rectangular bitmasks looked like this:
bitmask(X0, Y0, X1, Y1, Mask) :-
Row is (1 << (X1 - X0 + 1)) - 1,
N_cols0 is Y1 - Y0,
rectangle(N_cols0, Row, 1000, Mask0),
Mask is Mask0 << (X0 + 1000 * Y0).
rectangle(N_cols, Row, Shift, Mask) :-
( succ(N_cols0, N_cols)
-> rectangle(N_cols0, Row, Shift, Mask0),
Mask is (Mask0 << Shift) + Row
; Mask = Row
).
This is where the program was spending 95% of its time. The only idea I could come up to improve this was to instead use the “power of associative operation” algorithm for creating the bitmask; the idea is outlined on pages 31-40 of this PDF; obviously, this idea is ancient (like, ancient Egypt) but I think that this is where I originally stole the code from.
Long story short, as expected, this decreases the running time by a factor of 10 (from 11 seconds down to 0.8 seconds for 10 runs), and is/2 no longer dominates when I profile. The power we are raising to is anything between 1 and 1000 (for my input, mean is 266 and median is 207).
If there is interest, I can wrap up inside a module the “raising to power with associative operation” code I have and post it here.
Code listings
Original solution
:- module(d06, [run/2]).
run(Filename, N) :-
phrase_from_file(light_instr(0, Lights), Filename),
N is popcount(Lights).
light_instr(L0, L) -->
instr(A, X0, Y0, X1, Y1), !,
{ do_instr(A, X0, Y0, X1, Y1, L0, L1) },
light_instr(L1, L).
light_instr(L, L) --> [].
do_instr(A, X0, Y0, X1, Y1, L0, L1) :-
bitmask(X0, Y0, X1, Y1, Mask),
apply_mask(A, Mask, L0, L1).
bitmask(X0, Y0, X1, Y1, Mask) :-
Row is (1 << (X1 - X0 + 1)) - 1,
N_cols0 is Y1 - Y0,
rectangle(N_cols0, Row, 1000, Mask0),
Mask is Mask0 << (X0 + 1000 * Y0).
rectangle(N_cols, Row, Shift, Mask) :-
( succ(N_cols0, N_cols)
-> rectangle(N_cols0, Row, Shift, Mask0),
Mask is (Mask0 << Shift) + Row
; Mask = Row
).
apply_mask(set, Mask, L0, L1) :-
L1 is L0 \/ Mask.
apply_mask(reset, Mask, L0, L1) :-
L1 is L0 /\ ((1 << 1_000_000) - Mask - 1).
apply_mask(flip, Mask, L0, L1) :-
L1 is xor(L0, Mask).
:- use_module(library(dcg/basics)).
instr(A, X0, Y0, X1, Y1) -->
action(A), " ",
integer(X0), ",", integer(Y0),
" through ",
integer(X1), ",", integer(Y1),
"\n".
action(set) --> "turn on".
action(reset) --> "turn off".
action(flip) --> "toggle".
Running this on my computer, with my input (you can download it from the “Advent of Code” website I linked above):
?- time( forall(between(1, 10, _), run('d06.input', N)) ).
% 2,605,420 inferences, 11.797 CPU in 11.879 seconds (99% CPU, 220851 Lips)
true.
“Power-semigroup” solution
:- module(d06, [run/2]).
:- use_module(library(dcg/basics), [integer//1]).
run(Filename, N) :-
phrase_from_file(light_instr(0, Lights), Filename),
N is popcount(Lights).
light_instr(L0, L) -->
instr(A, X0, Y0, X1, Y1), !,
{ format(user_error, "~d,", [Y1 - Y0 + 1]) },
{ do_instr(A, X0, Y0, X1, Y1, L0, L1) },
light_instr(L1, L).
light_instr(L, L) --> [].
do_instr(A, X0, Y0, X1, Y1, L0, L1) :-
Row_mask is ((1 << (X1 - X0 + 1)) - 1) << X0,
N is Y1 - Y0 + 1,
power_semigroup(m(Row_mask, 1000), N, append_rows, m(Mask0, _)),
Mask is Mask0 << (1000 * Y0),
apply_mask(A, Mask, L0, L1).
append_rows(m(M_a, N_a), m(M_b, N_b), m(M, N)) :-
M is (M_a << N_b) + M_b,
N is N_a + N_b.
apply_mask(set, Mask, L0, L1) :-
L1 is L0 \/ Mask.
apply_mask(reset, Mask, L0, L1) :-
L1 is L0 /\ ((1 << 1_000_000) - Mask - 1).
apply_mask(flip, Mask, L0, L1) :-
L1 is xor(L0, Mask).
instr(A, X0, Y0, X1, Y1) -->
action(A), " ",
integer(X0), ",", integer(Y0),
" through ",
integer(X1), ",", integer(Y1),
"\n".
action(set) --> "turn on".
action(reset) --> "turn off".
action(flip) --> "toggle".
/* raise to power */
goal_expansion(odd(N), N /\ 0x1 =:= 1).
goal_expansion(half(N, Half), Half is N >> 1).
power_accumulate_semigroup(R, A, N, Op, P) :-
( N == 0
-> P = R
; power_accumulate_semigroup_1(R, A, N, Op, P)
).
power_accumulate_semigroup_1(R, A, N, Op, P) :-
( odd(N)
-> power_accumulate_semigroup_oddn(R, A, N, Op, P)
; power_accumulate_semigroup_anyn(R, A, N, Op, P)
).
power_accumulate_semigroup_oddn(R, A, N, Op, P) :-
call(Op, R, A, R1),
( N == 1
-> P = R1
; power_accumulate_semigroup_anyn(R1, A, N, Op, P)
).
power_accumulate_semigroup_anyn(R, A, N, Op, P) :-
half(N, N1),
call(Op, A, A, A1),
power_accumulate_semigroup_1(R, A1, N1, Op, P).
power_semigroup(A, N, Op, P) :-
must_be(positive_integer, N),
power_semigroup_(A, N, Op, P).
power_semigroup_(A, N, Op, P) :-
power_semigroup_evenn(A, N, Op, A0, N0),
( N0 == 1
-> P = A0
; call(Op, A0, A0, A1),
half(N0 - 1, N1),
power_accumulate_semigroup(A0, A1, N1, Op, P)
).
power_semigroup_evenn(A, N, Op, A1, N1) :-
( odd(N)
-> A = A1,
N = N1
; call(Op, A, A, A0),
half(N, N0),
power_semigroup_evenn(A0, N0, Op, A1, N1)
).
Time:
?- time( forall(between(1, 10, _), run('d06.input', N)) ).
% 414,149 inferences, 0.740 CPU in 0.756 seconds (98% CPU, 559307 Lips)
true.
