Courses/CS 460/Fall 2005/Homework/Cynthia York/Nov 5

From CSWiki

[edit] Let There Be Light

• This program uses constraint programming to determine the numeric values of the letters in the phrase "LET THERE BE LIGHT" such that LET + THERE + BE = LIGHT.

local
   proc {Light Solution}
      B E G H I L R T
      Vars = [B E G H I L R T]
   in
      Solution = [L E T]#[T H E R E]#[B E]#[L I G H T]
      Vars ::: 0#9                                      
      {FD.distinct Vars} 

      % Note: by adding the following contraints the runtime is reduced to instantaneous from 2.54 seconds                         
      B \=: 0                                          
      L \=: 0
      T \=: 0
                            100*L + 10*E + T           
      +  10000*T + 1000*H + 100*E + 10*R + E
                                  + 10*B + E           
      =: 10000*L + 1000*I + 100*G + 10*H + T
      {FD.distribute ff Vars}
   end
in
   {Browse {SearchAll Light}}
   {ExploreAll Light}
end

[edit] Rotating Digits

• This program uses constraint programming to determine the numeric values of the letters A through F such that when the numbers assigned to A through F are concatenated into an integer and multiplied by an integer between 1 and 6 they produce the following patterns:

1. [A...F] * 1 = [A...F]
2. [A...F] * 3 = [B C D E F A]
3. [A...F] * 2 = [C D E F A B]
4. [A...F] * 6 = [D E F A B C]
5. [A...F] * 4 = [E F A B C D]
6. [A...F] * 5 = [F A B C D E]

   local
      proc {RotateDigits Solution}
         % finds the values of A thru F such that multiplying them by 1 thru 6
         % produces the constrained list pattern shown below
         A B C D E F 
         Vars = [A B C D E F]
      in
         Solution = [a#A b#B c#C d#D e#E f#F]
         Vars ::: 1#8                                      
         {FD.distinct Vars}
         {FD.distribute ff Vars}
   
         % constrained list pattern desired
         {Mult [A B C D E F] 1 [A B C D E F]}
         {Mult [A B C D E F] 3 [B C D E F A]}
         {Mult [A B C D E F] 2 [C D E F A B]}
         {Mult [A B C D E F] 6 [D E F A B C]}
         {Mult [A B C D E F] 4 [E F A B C D]}
         {Mult [A B C D E F] 5 [F A B C D E]}
      end
   
      proc {Mult L1 X L2}
         % constrains L1 to L2 when multiplied by X
         {ListToInt L1} * X  =: {ListToInt L2}
      end
   
      proc {ListToInt Xs ?I}
         % concatenates the list of integers Xs into a single integer
         Len = {List.length Xs}       % get length of list Xs
         MagLst = {List.mapInd Xs     % assign magnitudes to elements in list Xs
   		proc {$ I N ?Mag} Mag={AssignMagnitude N I Len} end}
      in
         I = {List.foldL MagLst       % sum the magnified list MagLst to get Int
   	   proc {$ A B ?C} C = A + B end 0}
      end
   
      proc {AssignMagnitude N I Len ?M}
         % assigns the magnitude of N based on its position I
         % in a list of length Len
         M = N * {Number.pow 10 Len - I}
      end
      
   in
      {Browse {SearchAll RotateDigits}}
      {ExploreAll RotateDigits}
   end
   
   

   
   

   [edit] Divisible Digits

   • This program uses constraint programming to determine all the permutations of numeric values for the letters A through J such that when the numbers assigned to A through J are concatenated into an integer, that integer is evenly divisible by any integer between 1 and 9.

   local
      proc {DivDigits Solution}
         % finds all permutations of a 10 digit integer consisting of the distinct
         % digits 0 through 9 that is divisible by all digits 1 through 9
         A B C D E F G H I J
         Vars = [A B C D E F G H I J]
      in
         Solution = [a#A b#B c#C d#D e#E f#F g#G h#H i#I j#J]
         Vars ::: 0#9
         
   %     Since the sum of the digits is 45, any permutation of the digits gives a
   %     multiple of 9.  To get a multiple of both 2 and 5, the last digit must
   %     be 0, and thus to get a multiple of 8 (and 4), the tens digit must be
   %     even, 
         J =: 0
         I :: [2 4 6 8]
         
         {FD.distinct Vars}
         {FD.distribute ff Vars}
         
   %     and the hundreds digit must be odd if the tens digit is 2 or 6,
   %     and even otherwise.
         if I == 2 orelse I == 6
         then
   	 H :: [1 3 5 7 9]
         else
   	 H :: [2 4 6 8]
         end
   
   %     constrain concatenated list to be evenly divisible by 1 thru 9
         {Mod [A B C D E F G H I J] 1}
         {Mod [A B C D E F G H I J] 2}
         {Mod [A B C D E F G H I J] 3}
         {Mod [A B C D E F G H I J] 4}
         {Mod [A B C D E F G H I J] 5}
         {Mod [A B C D E F G H I J] 6}
         {Mod [A B C D E F G H I J] 7}
         {Mod [A B C D E F G H I J] 8}
         {Mod [A B C D E F G H I J] 9}
      end
   
      proc {Mod L1 X }
         % constrains L1 to evenly divisible by X
         {Int.'mod' {ListToInt L1} X}  =: 0
      end
   
      proc {ListToInt Xs ?I}
         % concatenates the list of integers Xs into a single integer
         Len = {List.length Xs}       % get length of list Xs
         MagLst = {List.mapInd Xs     % assign magnitudes to elements in list Xs
   		proc {$ I N ?Mag} Mag={AssignMagnitude N I Len} end}
      in
         I = {List.foldL MagLst       % sum the magnified list MagLst to get Int
   	   proc {$ A B ?C} C = A + B end 0}
      end
   
      proc {AssignMagnitude N I Len ?M}
         % assigns the magnitude of N based on its position I
         % in a list of length Len
         M = N * {Number.pow 10 Len - I}
      end
      
   in
      {Browse {SearchAll DivDigits}}
      {ExploreOne DivDigits}
   end