RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

Write a script to find the smallest integer x such that x, 2x, 3x, 4x, 5x and 6x are permuted multiples of each other.

Solution

permuted(X, Y):-
    number_chars(X, XChars),
    number_chars(Y, YChars),
    msort(XChars, XCharsSorted),
    msort(YChars, YCharsSorted),
    XCharsSorted == YCharsSorted.

permuted_multiple(Permuted):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(1, MAX_INTEGER, X),
    X2 is 2 * X,
    X3 is 3 * X,
    X4 is 4 * X,
    X5 is 5 * X,
    X6 is 6 * X,
    permuted(X, X2), permuted(X2, X3), 
    permuted(X3, X4), permuted(X4, X5), permuted(X5, X6),
    Permuted = X.

Sample Run

| ?- permuted_multiple(Permuted).

Permuted = 142857 ? 

(2150 ms) yes

Notes

I implemented solutions for this problem in multiple languages and compared side by side on the same system this Prolog solution ran the fastest. I think that's because in Prolog the logic can be (naturally!) expressed very succinctly and so the underlying instructions getting executed are most efficient. Other implementations seem to require a bit more overhead, such as when deconstructing an integer into a list of digits for example.

The task here is for us to generate the smallest integer with this permutable property. Technically the code here will generate all such numbers, however in search of other solutions it seems there is just the one found before we exceed the bounds of MAX_INTEGER.

Part 2

Write a script to find out all Reversible Numbers below 100.

Solution

all_odd([]).
all_odd([H|T]):-
    number_chars(Digit, [H]),
    M is mod(Digit, 2),
    M == 1,
    all_odd(T).

reversible(X):-
    number_chars(X, XChars),
    reverse(XChars, XCharsReversed),
    number_chars(R, XCharsReversed),
    Sum is X + R, 
    number_chars(Sum, SumChars),
    all_odd(SumChars).

reversible_under_n(N, Reversible):-
    between(1, N, X),
    reversible(X),
    Reversible = X.

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- reversible_under_n(100, Reversibles).

Reversibles = 10 ? a

Reversibles = 12

Reversibles = 14

Reversibles = 16

Reversibles = 18

Reversibles = 21

Reversibles = 23

Reversibles = 25

Reversibles = 27

Reversibles = 30

Reversibles = 32

Reversibles = 34

Reversibles = 36

Reversibles = 41

Reversibles = 43

Reversibles = 45

Reversibles = 50

Reversibles = 52

Reversibles = 54

Reversibles = 61

Reversibles = 63

Reversibles = 70

Reversibles = 72

Reversibles = 81

Reversibles = 90

(10 ms) no

Notes

Here we also use Prolog's ability to identify multiple solutions to generate all solutions less than 100, as required.

References

Challenge 176