From: mekly Date: 2005-12-04T09:47:33+09:00 Subject: Re: Programming Newbie: Ruby or Java? Excellent! Great job! You deserve more stars for doing it in Ruby, and it's quite educational. Thank you! Actually, I wanted to see how ugly it'd be done in a "public static void" language. (IMHO, Java and C++ are on the dark side of CS). BTW, that answer was provided by the author of the logic problem on his web site, so you might ask him for a reward. My Prolog solution provided the same answers, and therefore, it's not "wrong." It's a constraint satisfaction problem with very little logic involved (it's for humans with no computers). Your conclusion: "Evidently Prolog isn't well suited for logic problems" is far from being evident. Also, you can ask the experts at comp.lang.prolog, if you "wonder what it is good for." Any way, below is a more demanding problem. It's been used as an official benchmark in the field. You have an opportunity to push the recognition of the Ruby language to the top. (I think the optimal span was proved to be 930 time units -- need to google that). Best Regards, Leon ------------------------------------------------------------ % MT10 Scheduling Problem % J. F. Muth and G. L. Thompson. Industrial Scheduling. % Prentice Hall, Englewood Cliffs, NJ, USA, 1963. % % MT10 was considered as an especially hard problem for several years. % It took more than 25 years that the optimality of a found makespan % was proven. % J. Carlier and E. Pinson. An algorithm for solving the job-shop problem. % Management Science, 35(2):164-176, 1989. % Ten jobs (a-j), with ten tasks (1-10) each run on ten machines (m1-m10) % for N time units after completion of a specified list of tasks. % E.g., t(b5,69,[b4],m4) -- job B task 5 needs 69 time units on machine % m4 after task b4. Only one task can use a machine... mt10([ t(a1,29,[],m1), t(a2,78 ,[a1],m2), t(a3, 9,[a2],m3), t(a4,36 ,[a3],m4), t(a5,49,[a4],m5), t(a6,11 ,[a5],m6), t(a7,62,[a6],m7), t(a8,56 ,[a7],m8), t(a9,44,[a8],m9), t(a10,21,[a9],m10), t(b1,43,[],m1), t(b2,90 ,[b1],m3), t(b3,75,[b2],m5), t(b4,11 ,[b3],m10), t(b5,69,[b4],m4), t(b6,28 ,[b5],m2), t(b7,46,[b6],m7), t(b8,46 ,[b7],m6), t(b9,72,[b8],m8), t(b10,30,[b9],m9), t(c1,91,[],m2), t(c2,85 ,[c1],m1), t(c3,39,[c2],m4), t(c4,74 ,[c3],m3), t(c5,90,[c4],m9), t(c6,10 ,[c5],m6), t(c7,12,[c6],m8), t(c8,89 ,[c7],m7), t(c9,45,[c8],m10), t(c10,33,[c9],m5), t(d1,81,[],m2), t(d2,95 ,[d1],m3), t(d3,71,[d2],m1), t(d4,99 ,[d3],m5), t(d5, 9,[d4],m7), t(d6,52 ,[d5],m9), t(d7,85,[d6],m8), t(d8,98 ,[d7],m4), t(d9,22,[d8],m10), t(d10,43,[d9],m6), t(e1,14,[],m3), t(e2, 6 ,[e1],m1), t(e3,22,[e2],m2), t(e4,61 ,[e3],m6), t(e5,26,[e4],m4), t(e6,69 ,[e5],m5), t(e7,21,[e6],m9), t(e8,49 ,[e7],m8), t(e9,72,[e8],m10), t(e10,53,[e9],m7), t(f1,84,[],m3), t(f2, 2 ,[f1],m2), t(f3,52,[f2],m6), t(f4,95 ,[f3],m4), t(f5,48,[f4],m9), t(f6,72 ,[f5],m10), t(f7,47,[f6],m1), t(f8,65 ,[f7],m7), t(f9, 6,[f8],m5), t(f10,25,[f9],m8), t(g1,46,[],m2), t(g2,37 ,[g1],m1), t(g3,61,[g2],m4), t(g4,13 ,[g3],m3), t(g5,32,[g4],m7), t(g6,21 ,[g5],m6), t(g7,32,[g6],m10), t(g8,89 ,[g7],m9), t(g9,30,[g8],m8), t(g10,55,[g9],m5), t(h1,31,[],m3), t(h2,86 ,[h1],m1), t(h3,46,[h2],m2), t(h4,74 ,[h3],m6), t(h5,32,[h4],m5), t(h6,88 ,[h5],m7), t(h7,19,[h6],m9), t(h8,48 ,[h7],m10), t(h9,36,[h8],m8), t(h10,79,[h9],m4), t(i1,76,[],m1), t(i2,69 ,[i1],m2), t(i3,76,[i2],m4), t(i4,51 ,[i3],m6), t(i5,85,[i4],m3), t(i6,11 ,[i5],m10), t(i7,40,[i6],m7), t(i8,89 ,[i7],m8), t(i9,26,[i8],m5), t(i10,74,[i9],m9), t(j1,85,[],m2), t(j2,13 ,[j1],m1), t(j3,61,[j2],m3), t(j4, 7 ,[j3],m7), t(j5,64,[j4],m9), t(j6,76 ,[j5],m10), t(j7,47,[j6],m6), t(j8,52 ,[j7],m4), t(j9,90,[j8],m5), t(j10,45,[j9],m8) ]). ------------------------------------------------------------------------ On Sat, 03 Dec 2005 12:44:35 -0800, William James wrote: >> --------------------------------------------------------------- >> >> % Chess Tournament Logic Problem >> % http://www.geocities.com/Heartland/Plains/4484/lp9705.htm >> % Copyright � 1997 William T. Pelletier >> % Stars: 5 >> % During the final round of Georgia's All-State Chess Tournament, >> % the eventual top 4 finishers in the tournament played their final >> % game against 4 different opponents. The tournament boards were >> % numbered from 1 to 50 to facilitate location and identification >> % of games. Each of the top 4 finishers played a different opening >> % in this last game. Use the clues below to determine the first and last >> % names of the first through fourth place winners of the tournament, >> % the chess opening each used in his last game, and the number of the >> % chess board on which he played his final game. >> % 1. Mr. Hart played the King's Indian Defence. >> % 2. Steve placed ahead of the one who used the Ruy Lopez opening. >> % 3. The top 4 players were Larry, Mr. Korn, the contestant who opened >> % with Queen's Gambit, and a player who played on an even-numbered board. >> % 4. Mr. Rose finished exactly 2 places ahead of the player on board 31. >> % 5. The number of the 3rd place winner's board is at least 10 higher or >> % at least 10 lower than that of Mr. Baird. >> % 6. The number of the board of the contestant who placed immediately >> % after Bert is exactly 15 higher than the number of the board played >> % by the one who placed immediately before Tom. >> % 7. The lowest board number of the top 4 finishers was exactly half the >> % number of the board played by the one who placed immediately after >> % the one who played the Giuoco Piano opening. >> % 8. The highest board number was exactly 8 higher than the board number >> % of the man who finished exactly two places after Bert. >> % Answer: >> % PLACE 1ST NAME SURNAME OPENING BOARD >> % First Steve Rose Queen's Gambit #40 >> % Second Bert Baird Ruy Lopez #16 >> % Third Tom Korn Giuoco Piano #31 >> % Fourth Larry Hart King's Indian #32 >> % ----------------------------------------------------------------------- > > I think that your answer is wrong. There are 3 solutions: > > 1. Steve Baird Giuoco Piano 12 > 2. Bert Rose Queen's Gambit 24 > 3. Tom Korn Ruy Lopez 39 > 4. Larry Hart King's Indian 31 > > 1. Steve Rose Giuoco Piano 8 > 2. Bert Baird Queen's Gambit 16 > 3. Tom Korn Ruy Lopez 31 > 4. Larry Hart King's Indian 23 > > 1. Steve Rose Queen's Gambit 40 > 2. Bert Baird Ruy Lopez 16 > 3. Tom Korn Giuoco Piano 31 > 4. Larry Hart King's Indian 32 > > Evidently Prolog isn't well suited for logic problems. I wonder > what it is good for. > > Here's a Ruby program. > > > NAME, SURNAME, OPENING, BOARD = *(0..3) > Names = %w(Steve Larry Tom Bert) > Surnames = %w(Baird Hart Korn Rose) > Openings = %w(Ruy\ Lopez King's\ Indian Giuoco\ Piano > Queen's\ Gambit) > > > class Array > def permute(prefixed=[]) > if (length < 2) > yield(prefixed + self) > else > each_with_index { |e, i| > (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) {|a| > yield a } > } > end > end > > def find_row( column, string ) > self[column].index(string) > end > def get( column_a, string, column_b ) > self[ column_b][ self.find_row( column_a, string) ] > end > end > > module Combine > def Combine.pick(pick, items, &block) > combine([], 0, pick, items, &block) > end > > private > > def Combine.combine(set, index, pick, items, &block) > if pick == 0 or index == items.length > yield set > else > set.push(items[index]) > combine(set, index + 1, pick - 1, items, &block) > set.pop > combine(set, index + 1, pick, items, &block) if > pick < items.length - index > end > end > end > > > Names.permute{|names| > Surnames.permute{|surnames| > Openings.permute{|openings| > > boards = [ names, surnames, openings, [] ] > > > # 1. Mr. Hart played the King's Indian Defence. > > next unless "King's Indian"==boards.get(SURNAME,'Hart',OPENING) > > # 2. Steve placed ahead of the one who used the Ruy Lopez opening. > > next unless boards.find_row(NAME,'Steve') < > boards.find_row(OPENING, 'Ruy Lopez' ) > > > # 3. The top 4 players were Larry, Mr. Korn, the contestant who > # opened with Queen's Gambit, and a player who played on an > # even-numbered board. > > remaining = Array(0..3) - [ boards.find_row(NAME,'Larry'), > boards.find_row(SURNAME, 'Korn'), > boards.find_row(OPENING, "Queen's Gambit" ) ] > next if remaining.size != 1 > ## ... to be continued ... > > > # Combine.pick( 4, Array(1..50) ){ |board_nums| > ## I reduced the range for speed's sake. > Combine.pick( 4, Array(8..40) ){ |board_nums| > > ## Skip board-number combination if it obviously > ## isn't up to snuff. > next if !board_nums.index(31) > max, min = board_nums.last, board_nums.first > next if max - min < 15 or max/min < 2 > next if not board_nums.index( min * 2 ) > diffs = [] > (board_nums.size-1).times{|i| > (i.succ ... board_nums.size).each{|j| > diffs << board_nums[j] - board_nums[i] > } > } > next if !diffs.index(15) or !diffs.index(8) > > > board_nums.permute{ |board_nums_perm| > > boards[-1] = board_nums_perm > > > ## ... continued from above. > next if boards[BOARD][ remaining.first ] % 2 > 0 > > # 4. Mr. Rose finished exactly 2 places ahead of the player > # on board 31. > > next unless boards[BOARD].index(31) > next unless -2 == boards.find_row(SURNAME,'Rose') - > boards.find_row(BOARD,31) > > # 5. The number of the 3rd place winner's board is at least 10 higher > # or at least 10 lower than that of Mr. Baird. > > next unless 10 <= (boards[BOARD][2] - > boards.get(SURNAME,'Baird',BOARD)).abs > > # 6. The number of the board of the contestant who placed > # immediately after Bert is exactly 15 higher than the number of > # the board played by the one who placed immediately before Tom. > > num1 = boards[BOARD][ boards.find_row(NAME,'Bert') + 1] > num2 = boards[BOARD][ boards.find_row(NAME,'Tom') - 1] > next if !num1 or !num2 or 15 != num1 - num2 > > > # 7. The lowest board number of the top 4 finishers was exactly > # half the number of the board played by the one who placed > # immediately after the one who played the Giuoco Piano opening. > > num = boards[BOARD][ boards.find_row(OPENING, > "Giuoco Piano") + 1 ] > next unless num and boards[BOARD].min == num / 2 > > > # 8. The highest board number was exactly 8 higher than the board > # number of the man who finished exactly two places after Bert. > > num = boards[BOARD][boards.find_row(NAME,"Bert") + 2] > next unless num and boards[BOARD].max == 8 + num > > # ---- Print the answer. ---- > > boards.first.size.times {|i| > puts "%d. %-7s%-7s%-15s%3d" % > boards.inject([i+1]){|a,x| a << x[i] } > } > puts > > } } } } }