From: William James Date: 2005-12-04T05:47:33+09:00 Subject: Re: Programming Newbie: Ruby or Java? mekly wrote: > > """the reality is that the real world and universities don't always > > match up.""" > > > > I'm a current CS student at ASU (arizona, US) and this statement is SO true. :/ > > Besides learning Java, C, & C++... I've had to learn Lisp/Scheme and Prolog. > > I mean who uses Prolog?? It's basically dead. > > School teaches theory mostly. > > Experience teaches you the rest I guess. > > Many problems in "the real world" (planning, scheduling, etc.) are not > so easy to handle in the "living" languages like Java or C++. > So, universities are trying to prepare you for "the real world." > In many cases a "dead" language like Prolog might be of great > help. Of course, it's difficult to give here a non-trivial, industry- > specific example (need background). So, below is a five star puzzle > solved in GNU Prolog/CLP(FD). I'd love to see how to solve it in any of > those practical languages. > > Best Regards, > Leon > --------------------------------------------------------------- > > % 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 } } } } }