Courses/CS 460/Fall 2005/Homework/Brian Smith/Nov 5
From CSWiki
Contents |
[edit] LET + THERE + BE = LIGHT
This one was just like SEND + MORE = MONEY. The Num procedure makes it easy to convert a list into a number. R and B are interchangeable so there are two possible solutions.
- 857 + 79525 + 15 = 80397
- 857 + 79515 + 25 = 80397
local
fun {Num L}
{FoldL L fun {$ I J} {FD.plus {FD.times I 10} J} end 0}
end
proc {Light Solution}
B L E G H I T R
Vars = [B L E G H I T R]
in
Solution = [L E T]#[T H E R E]#[B E]#[L I G H T]
Vars ::: 0#9
{FD.distinct Vars}
L \=: 0
T \=: 0
B \=: 0
{Num [L E T]} + {Num [T H E R E]} + {Num [B E]}
=: {Num [L I G H T]}
{FD.distribute ff Vars}
end
in
{Browse {SearchAll Light}}
{ExploreAll Light}
end
[edit] Rotating Digits
Due to the constraints created by using the Mult procedure this solution does not have to search at all. There is only one solution left: 142857.
local
fun {Num L}
{FoldL L fun {$ I J} {FD.plus {FD.times I 10} J} end 0}
end
proc {Mult L1 X L2}
{Num L1} * X =: {Num L2}
end
proc {RotatingDigits Solution}
A B C D E F
Vars = [A B C D E F]
in
Solution = Vars
Vars ::: 1#9
{FD.distinct Vars}
{Mult Vars 1 [A B C D E F]}
{Mult Vars 3 [B C D E F A]}
{Mult Vars 2 [C D E F A B]}
{Mult Vars 6 [D E F A B C]}
{Mult Vars 4 [E F A B C D]}
{Mult Vars 5 [F A B C D E]}
{FD.distribute ff Vars}
end
in
{Browse {SearchAll RotatingDigits}}
{ExploreAll RotatingDigits}
end
[edit] Divisible Permutations
The problem is to find all permutations of the digits 0-9 that as a number are each divisible by each digit (other than 0). This solution uses divisibility tests for some of the digits 1-9. Some of the tests are redundant so they are left out. Others (like 3 and 9) aren't needed because the sum of all digits is always the same.
All permutations of length 10 of 10 digits with no repetitions is 10!, or 3,628,800. We don't want to search that many possibilities, so we create restraints to narrow them before searching. This tables shows the numbers after adding each constraint to the program.
| Starting with no divisibility constraints (This is n!) | 3,628,800 |
| Add Rule 5: Last digit must be 0 or 5 | 725,760 |
| Add Rule 2: Last digit must be even | 362,880 |
| Add Rule 8: Number made from last 3 digits must be divisible by 8 | 80,640 |
| Add Rule 7: Break into 6-digit chunks, whose sum must be divisible by 7 | 11,460 |
[edit] Notes
A few things I learned about FD in Oz. If any of these are wrong please let me know.
- The infix operators =:, \=:, <:, >:, =<:, and >=: absorb the arithmetic operators +, -, *, and ~, and no others. This means that mod and div won't work in a constraint; you have to use FD.modI/D and FD.divI/D respectively. The I means interval propagation, and D means domain propagation.
- FD operators require integers to be between FD.inf (0) and FD.sup (134,217,726). For this problem that means that you can't take the modulus of the 10-digit numbers for a constraint, nor can you use FD ops on negative numbers. The Grocery example shows a way of getting around this by declaring a multiplier outside the FD procedure, but I couldn't apply it to this problem.
[edit] Code
I'm sure this can be improved. There are most likely parts of FD that I should be using but are unknown to me. The online documentation for Oz leaves much to be desired, and the book covers the basic theory but not how to use the FD module.
This solution takes about 19 seconds to complete.
local
fun {Num L}
{FoldL L fun {$ X Y} {FD.plus {FD.times X 10} Y} end 0}
end
fun {Sum L}
{FoldL L fun {$ X Y} {FD.plus X Y} end 0}
end
proc {DivisiblePerms Solution}
A9 A8 A7 A6 A5 A4 A3 A2 A1 A0
A = [A9 A8 A7 A6 A5 A4 A3 A2 A1 A0]
in
Solution = A
A ::: 0#9
{FD.distinct A}
% 1. All integers are divisible by 1 so this goes without saying
% 2. The last digit must be divisible by 2
{FD.modI A0 2} =: 0
% 3. The sum of all digits must be divisible by 3
% Not needed because the sum is always 45.
%{FD.modI {Sum A} 3} =: 0
% 4. The number made by the last two digits must be div. by 4.
% Alternately, A0 + 2A1 must be divisible by 4.
% Not needed because anything divisible by 8 is div. by 4
%{FD.modI {Num [A1 A0]} 4} =: 0
% 5. The last digit must be either 5 or 0.
A0 :: [0 5]
% 6. If Rules 2 and 3 are true, then 6 is automatically true
% 7. This one is tricky. I tried Pascal's method with coefficients,
% but FD couldn't work with negative numbers. There were other
% methods that required the user's judgment so they were out.
% This method splits the number into 6-digit chunks and requires
% that their sum is divisible by 7.
{FD.modI
{FD.plus {Num [A9 A8 A7 A6]} {Num [A5 A4 A3 A2 A1 A0]}}
7} =: 0
% 8. The number made by the last three digits must be div. by 8.
% Alternately, A0 + 2A1 + 4A2 must be divisible by 8.
{FD.modI {Num [A2 A1 A0]} 8} =: 0
% 9. The sum of all the digits must be divisible by 9.
% Not needed because the sum is always 45.
%{FD.modI {FDSum A} 9} =: 0
{FD.distribute ff A}
end
RL
in
RL = {SearchAll DivisiblePerms}
{Browse {Length RL}}
{Browse RL}
{ExploreOne DivisiblePerms} % this finds the example 1234759680
end
