Courses/CS 460/Fall 2005/Homework/Kelly Breed/Nov 5

From CSWiki

My main homework page

Contents 1 HW 6 1.1 LET+THERE+BE=LIGHT 1.2 Rotating Digits 1.3 Divisible

[edit] HW 6

[edit] LET+THERE+BE=LIGHT

local
   proc {Light Solution}
      L E T H R B I G
      Vars = [L E T H R B I G]
   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
                            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}}
end

[edit] Rotating Digits

local    
   fun {Num L}
      {FoldL L fun{$ A B} {FD.plus {FD.times A  10} B} end 0 }
   end

   proc {Rotating Solution}
      A B C D E F
      Vars = [A B C D E F]
      in
      Solution = Vars
      Vars ::: 0#9
     {FD.distinct Vars}
      A \=: 0
      {FD.times {Num [A B C D E F]} 2 } =: {Num [C D E F A B]}
      {FD.times {Num [A B C D E F]} 3 } =: {Num [B C D E F A]}
      {FD.times {Num [A B C D E F]} 4 } =: {Num [E F A B C D]}
      %{FD.times {Num [A B C D E F]} 5 } =: {Num [F A B C D E]}
      %{FD.times {Num [A B C D E F]} 6 } =: {Num [D E F A B C]}
      {FD.distribute ff Solution}
   end

   R
in
   R = {SearchAll Rotating}
   {Browse {Length R}}
   {Browse R}
end

[edit] Divisible

OK, after looking at Brian's code I realized how stupid I'd been. I do have something to add, however. Even though the mod 4 step is technically not necessary, without it the execution is about three times as long. I got a time of about 4 seconds with the mod 4 step uncommented and about 15 seconds with it commented out.

Update: This appears not to be giving entirely correct results. Out of the 5496 results returned by this only 701 pass the test of being evenly divisible by the numbers 2-9.

Update 11/7: My test code was incorrect. All results check out but there is still the question of why I got fewer results. Part of the answer is that I incorrectly implemented the mod 7 in that if the result of the algorithm was above 1000 then the algorithm was to be applied again. Also, with this algorithm it is possible to return negative numbers, which is a no-no for constraint, so for Oz this is a bad algorithm.

local

   % Brian's annoyingly clever numberizer, blatantly borrowed.
   fun {Num L}
      {FoldL L fun{$ A B} {FD.plus {FD.times A  10} B} end 0 }
   end
   
   proc {Divisible S}
      A0 A1 A2 A3 A4 A5 A6 A7 A8 A9
      A = [A0 A1 A2 A3 A4 A5 A6 A7 A8 A9]
   in
      S = A
      A ::: 0#9
      {FD.distinct A}
      A0 \=: 0

      %% Last number divisible by two, then whole number is.
      {FD.modI A9 2} =: 0

      %% mod 3
      %% Sum of digits is divisible by 3 (45)
      %{FD.modI {Sum A} 3} =: 0

      %% mod 4
      {FD.modI {Num [A8 A9]} 4} =: 0

      %% mod 5
      A9 :: [0 5]

      %% mod 6
      %% Covered by mod 2, 3

      %% mod 7
      %% (A7 A8 A9)-(A4 A5 A6)+(A1 A2 A3)-A0
      {FD.modI ({FD.minus {FD.plus{FD.minus {Num [A7 A8 A9]} {Num [A4 A5 A6]}} {Num [A1 A2 A3]}} A0}) 7} =: 0

      %% mod 8
      {FD.modI {Num [A7 A8 A9]} 8} =: 0

      %% mod 9
      %% Sum of digits is divisible by 9 (45)
      {FD.distribute ff A}
      end
in
   {Browse {SearchAll Divisible}}
end

My user page.