From: Bill Dolinar Date: 2006-01-23T10:44:21+09:00 Subject: Re: [QUIZ] Grid Folding (#63) --Apple-Mail-10-759652880 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8; delsp=yes; format=flowed Here's my solution. Looks like it didn't get from google to the =20 mailing list. I used arrays within arrays as well. I wrote my own =20 loops to do the folding. I see now I could have done it much more =20 succinctly. I went for all the extra credit. Can unfold by noticing =20= the last element of the array hasn't been folded over and the first =20 element was previously unfolded. The direction from the first to the =20= last element gives the fold direction. Then just keep cutting off =20 the first half of the array successively gives the array to get the =20 next unfold direction from. Should be quite fast and check_fold. =EF=BF=BC= --Apple-Mail-10-759652880 Content-Type: multipart/mixed; boundary=Apple-Mail-11-759652880 --Apple-Mail-11-759652880 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=ISO-8859-1

Here's my solution. =A0Looks like it didn't get from google to = the mailing list.=A0=A0I used arrays within arrays as well. =A0I wrote = my own loops=A0to do the folding. =A0I see now I could have done it much = more=A0succinctly. =A0I went for all the extra credit. =A0Can unfold by = noticing=A0the last element of the array hasn't been folded over and the = first=A0element was previously unfolded. =A0The direction from the first = to the=A0last element gives the fold direction. =A0Then just keep = cutting off the=A0first half of the array successively gives the array = to get the next unfold direction from.=A0=A0Should=A0be=A0quite=A0fast=A0and=A0check_fold.<= /P>

= --Apple-Mail-11-759652880 Content-Transfer-Encoding: 7bit Content-Type: text/x-ruby-script; x-unix-mode=0755; name="grid_folding.rb" Content-Disposition: attachment; filename=grid_folding.rb #! /usr/bin/env ruby -w =begin Manages the matrix of values for folding: [[1], [2], [3], [4]] left_fold returns new matrix: [[1, 2], [3, 4]] =end class FoldMatrix attr_reader :values def initialize(values, rows, cols) @rows = rows @cols = cols @values = values end # Fold left side of matrix over to right returning new FoldMatrix def left_fold fold(:left) end # Fold right side of matrix over to left returning new FoldMatrix def right_fold fold(:right) end # Fold top of matrix down and return new FoldMatrix def top_fold fold(:top) end # Fold bottom of matrix up and return new FoldMatrix def bottom_fold fold(:bottom) end # Return the result of folding in flattened array def result if (@rows != 1 && @cols != 1) raise ArgumentError, "Paper not completely folded" end @values.flatten end private # Return a matrix element def array_element(i, j) @values[i*@cols + j] end # Iterate through items in array by folded direction where direction # is one of :left, :right, :top, :bottom. Iterates going left to # right then down. Values are already in proper order top to # bottom. # Example: # each_by_fold do |top, bottom| # new_cell_value = top + bottom # end def each_by_fold(fold) # make sure there are enough rows or columns to fold case fold when :left, :right if @cols <= 1 raise ArgumentError, "Attemting to fold to #{fold.to_s} with only 1 column" end when :top, :bottom if @rows <= 1 raise ArgumentError, "Attemting to fold to #{fold.to_s} with only 1 row" end end # setup loop boundaries to loop through unfolded part of page case fold when :left row_start = 0 row_end = @rows - 1 col_start = @cols/2 col_end = @cols - 1 when :right row_start = 0 row_end = @rows - 1 col_start = 0 col_end = @cols/2 - 1 when :top row_start = @rows/2 row_end = @rows - 1 col_start = 0 col_end = @cols - 1 when :bottom row_start = 0 row_end = @rows/2 - 1 col_start = 0 col_end = @cols - 1 end # loop through row by row reversing items folded to top row_start.upto(row_end) do |i| col_start.upto(col_end) do |j| case fold when :left, :right top = array_element(i, @cols - j - 1).reverse bottom = array_element(i, j) when :top, :bottom top = array_element(@rows - i - 1, j).reverse bottom = array_element(i, j) end yield(top, bottom) end end end # Return a new fold matrix by folding in direction where direction # is one of :left, :right, :top, :bottom. def fold(direction) new_values = [] each_by_fold(direction) do |top, bottom| new_values << top + bottom end case direction when :left, :right new_cols = @cols/2 new_rows = @rows when :top, :bottom new_cols = @cols new_rows = @rows/2 end FoldMatrix.new(new_values, new_rows, new_cols) end end # Determine if a number is a power of 2 def is_power_of_2(number) return false if number < 1 # keep on shifting left until number equals one (power of 2) or has # one bit set but isn't one (not power of 2) while number > 1 number >>= 1 return false if ((number & 1) == 1 && number != 1) end true end # Get the direction from an unfolded matrix element to the one # just folded to the top. Both must be in same row or column. def direction_to(unfolded, folded, rows, cols) unfolded -= 1 unfolded_i = unfolded / cols unfolded_j = unfolded % cols folded -= 1 folded_i = folded / cols folded_j = folded % cols case when unfolded_i == folded_i && unfolded_j < folded_j :right when unfolded_i == folded_i && unfolded_j > folded_j :left when unfolded_j == folded_j && unfolded_i < folded_i :bottom when unfolded_j == folded_j && unfolded_i > folded_i :top else raise ArgumentError, "Values not in same row or column: " + "#{unfolded}, #{folded}, #{rows}x#{cols}" end end def check_rows_and_cols(rows, cols) unless is_power_of_2(rows) raise ArgumentError, "Rows must be power of two" end unless is_power_of_2(cols) raise ArgumentError, "Cols must be power of two" end end # Fold up matrix of numbers using given directions where directions # are in a string with T = top, B = bottom, L = left, R = right: # "TLBR". Throws ArgumentError on invalid direction or rows or cols # not a power of 2. def fold(directions, rows=16, cols=16) check_rows_and_cols(rows, cols) # build array of values values = [] 1.upto(rows*cols) do |i| values << [i] end fold_matrix = FoldMatrix.new(values, rows, cols) directions.each_byte do |fold_direction| case fold_direction when ?T fold_matrix = fold_matrix.top_fold when ?B fold_matrix = fold_matrix.bottom_fold when ?L fold_matrix = fold_matrix.left_fold when ?R fold_matrix = fold_matrix.right_fold else raise ArgumentError, "Invalid direction #{fold_direction}" end end fold_matrix.result end # Get the folding directions from a fold array. The item that has # never been folded over is at end of array. The item that wasn't # folded until the last fold and is now at at the first of array. # Therefore... # # while size of array is greater than 1 # get direction in original matrix from last item number # in folded array to first # push direction on front of directions # cut off front half of array # end # # Throws ArgumentError on array not in fold order or rows or cols not # power of 2. def check_fold(folded, rows=16, cols=16) check_rows_and_cols(rows, cols) directions = "" while folded.size > 1 # get direction in original matrix from last to first direction = direction_to(folded.last, folded.first, rows, cols) # and push it on front of directions case direction when :top directions = "T" + directions when :bottom directions = "B" + directions when :left directions = "L" + directions when :right directions = "R" + directions end # cut array in half folded = folded[folded.size/2...folded.size] end directions end if __FILE__ == $0 if (ARGV.size == 1 || ARGV.size == 3) if (ARGV.size == 3) rows = ARGV[1].to_i cols = ARGV[2].to_i else rows = 16 cols = 16 end p fold(ARGV[0], rows, cols) else puts "Usage: #$0 folds [rows cols]" end end --Apple-Mail-11-759652880 Content-Transfer-Encoding: 7bit Content-Type: text/html; charset=US-ASCII

--Apple-Mail-11-759652880-- --Apple-Mail-10-759652880--