Courses/CS 460/Fall 2005/Homework/Jeff Bailey/Nov 5

From CSWiki

Contents 1 LET + THERE + BE = LIGHT 2 Rotating Digits 3 Divisible Permutations

[edit] LET + THERE + BE = LIGHT

The solution for this problem are:

• 857 + 79525 + 15 = 80397
• 857 + 79525 + 25 = 80397

declare

% converts a list of numbers into an integer.  Inspired by Brian.
fun {Int Xs}
   {FoldL Xs fun {$ I J} {FD.plus {FD.times 10 I} J} end 0}
end

% solve the problem
local
   proc {Light Answer}
      L E T H R B I G
      Vars = [L E T H R B I G]
   in
      Answer = [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   

      {Int [L E T]} + {Int [T H E R E]} + {Int [B E]} =: {Int [L I G H T]}
      {FD.distribute ff Vars}
   end
in
   {Browse {SearchAll Light}}
end

[edit] Rotating Digits

I decided against using the Mult procedure as suggested and instead wrote a function that converts a list of numbers to a proper integer instead. This both simplified the source code and improved performance.

The solution to this problem is:

• A = 1
• B = 4
• C = 2
• D = 8
• E = 5
• F = 7

declare

% converts a list of numbers into an integer. 
fun {Int Xs}
   {FoldL Xs fun {$ I J} {FD.plus {FD.times 10 I} J} end 0}
end

% solution
local
   proc {Rotate Answer}
      A B C D E F
      Vars = [A B C D E F]
   in
      Answer = Vars
      Vars ::: 1#9
      {FD.distinct Vars}

      {Int Vars} * 3 =: {Int [B C D E F A]}
      {Int Vars} * 2 =: {Int [C D E F A B]}
      {Int Vars} * 6 =: {Int [D E F A B C]}
      {Int Vars} * 4 =: {Int [E F A B C D]}
      {Int Vars} * 5 =: {Int [F A B C D E]}

      {FD.distribute ff Vars}
   end
in
   {Browse {SearchAll Rotate}}
end

[edit] Divisible Permutations

This problem was uninteresting other than solving for divisibility by 7. I tried 4 methods and finally settled on Wells 3

• Wells 3: Take the most significant digit multiplied by 3 added to the next most significant digit. Rinse. Repeat. If the resulting integer is div7, the original integer is also div7.
• Wells 5: Take the least significant digit multiplied by 5 added to the next least significant digit. Recurisve of course. If the resulting integer is div7, the original integer is also div7.
• Matrix method. From the right most digit, multiply and add each digit using the repeated pattern 1 3 2 -1 -3 -2. If the resulting integer is div7, the original integer is also div7.
• Chop & Subtract. Recursively apply (Number/10) - (2 * (Number % 10)). Extremely difficult to code, gave up after a few hours of toying with it :(.

The solution to this problem is:

• Number of Permutations Divisible by 1 thru 9 inclusive = 11460

declare
% converts a list of numbers into an integer. 
fun {Int Xs}
   {FoldL Xs fun {$ I J} {FD.plus {FD.times 10 I} J} end 0}
end

% solution
local
   proc {DivPerms Answer}
      N0 N1 N2 N3 N4 N5 N6 N7 N8 N9
      N = [N0 N1 N2 N3 N4 N5 N6 N7 N8 N9]
   in
      Answer = N
      N ::: 0#9
      {FD.distinct N}

      % div1, div3, div9 are implied
      % div2, div5, occur when N9 = 0
      N9 =: 0

      % div6 occurs when div2 and div3 are true   
      % div4, div8 occur when {Int [N7 N8 N9]} is div8
      {FD.modI {Int [N7 N8 N9]} 8} =: 0

      % div7 using the wells 3 method.
      {FD.modI {FoldL Answer fun {$ I J} {FD.plus {FD.times 3 I} J} end 0} 7} =: 0

      {FD.distribute ff N}
   end
   Results
in
   Results = {SearchAll DivPerms}
   {Browse Results}
   {Browse {Length Results}}
end