Courses/CS 460/Fall 2005/Homework/Brian Smith/Nov 12

From CSWiki

[edit] Int from list of digits

I think Cynthia's second method is a good one, I'd use it over the # method. It uses foldRInd to pass the index of the list elements as the first argument of the folding function. If we determine the length of the list beforehand, we can find the power of 10 to use for each element of the list.

local
   fun {IntR L}
      Len = {Length L} in
      {List.foldRInd L fun {$ I X Y} X*{Pow 10 Len-I} + Y end 0}
   end
in
   {Browse {IntR [4 8 2 4 5 9 0]}}
end

[edit] Int from list of digits, base 2 to 36

The previous procedure works for decimal numbers because we put 10 into the folding code. I generalized it to create integers from lists that represent any number from base 2 to 36. For numbers from base 2 to 10, we can just pass the base in place of 10. For bases higher than 10 we need to use letters in place of numbers--this means that we have to convert the letters to the number they represent before doing the math. I created a couple of functions to find the index of an element of a list (which also use folding).

I did this out of curiosity, I'm not sure if it would be useful to anyone.

local
   fun {IndexOf X L}
      {List.foldRInd L fun {$ I M N} if X == M then I else N end end 0}
   end

   fun {LastIndexOf X L}
      {List.foldLInd L fun {$ I M N} if X == N then I else M end end 0}
   end
  
   fun {IntFromBase L Base}
      Len = {Length L}
      Alphabet = [1 2 3 4 5 6 7 8 9 a b c d e f g h
		  i j k l m n o p q r s t u v w x y z]
   in
      {List.foldRInd L fun {$ I X Y} {IndexOf X Alphabet}*{Pow Base Len-I} + Y end 0}
   end
in
   {Browse first#{IndexOf 0 [4 6 0 2 3 8 9 0]}}
   {Browse last#{LastIndexOf 0 [4 6 0 2 3 8 9 0]}}
   {Browse missing#{IndexOf 7 [4 6 0 2 3 8 9 0]}}
   {Browse base2#{IntFromBase [1 0 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0] 2}}
   {Browse base3#{IntFromBase [1 0 0 0 0 2 0 1 0 0 0 2 1 1 2] 3}}
   {Browse base5#{IntFromBase [2 2 1 3 3 4 1 3 3 0] 5}}
   {Browse base8#{IntFromBase [2 2 3 1 7 0 1 6] 8}}
   {Browse base10#{IntFromBase [4 8 2 4 5 9 0] 10}}
   {Browse base16#{IntFromBase [4 9 9 e 0 e] 16}}
   {Browse base36#{IntFromBase [2 v e o e] 36}}
end

[edit] Free Puzzles

% Math 035
% Fill in the boxes with 1, 2, 3, 4, 5, 6, 7, 8, and 9 to make the
% multiplication equation work. 

%   ####
% x    #
% ------
%   ####

% (This one is simple, it uses the same pieces as our previous work.)

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 {GuessAllMult Solution}
      A1 A2 A3 A4
      B1 B2 B3 B4
      N
      All = [A1 A2 A3 A4 N B1 B2 B3 B4]
   in
      Solution = [[A1 A2 A3 A4] N [B1 B2 B3 B4]]
      All ::: 1#9
      {FD.distinct All}
      
      {Mult [A1 A2 A3 A4] N [B1 B2 B3 B4]}

      {FD.distribute ff All}
   end
   RL
in
   RL = {SearchAll GuessAllMult}
   {Browse {Length RL}}
   {Browse RL}
end

% Math 083
% Can you arrange the digits 0 through 9 so that they will
% make the equation 1/2 + 1/2 = 1? 

% ##     ###
% --  +  ---  =  1
% ##     ###

local
   fun {Int L}
      {FoldL L fun {$ I J} {FD.plus {FD.times I 10} J} end 0}
   end

   proc {Fractions Solution}
      A1 A2
      B1 B2
      C1 C2 C3
      D1 D2 D3
      All = [A1 A2 B1 B2 C1 C2 C3 D1 D2 D3]
   in
      Solution = [[A1 A2] [B1 B2] [C1 C2 C3] [D1 D2 D3]]
      All ::: 0#9
      {FD.distinct All}

      % Numerators are twice the size of denominators
      {Int [A1 A2]}*2 =: {Int [B1 B2]}
      {Int [C1 C2 C3]}*2 =: {Int [D1 D2 D3]}

      % Sum of numerators (after cross-multiplying to make denominators
      % equal) equals the product of the denominators
      {Int [A1 A2]}*{Int [D1 D2 D3]} + {Int [C1 C2 C3]}*{Int [B1 B2]}
      =: {Int [B1 B2]}*{Int [D1 D2 D3]}

      {FD.distribute ff All}
   end
   RL
in
   RL = {SearchAll Fractions}
   {Browse {Length RL}}
   {Browse RL}
end