------ art_149725_27862236.1165831166113 Content-Type: multipart/alternative; boundary --- art_149726_28512089.1165831166113" ------ art_149726_28512089.1165831166113 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Hi, I am new to the quizzes and also more or less new to ruby. I would appreciate any comments on my "unrubyness", and thanks in advance. I prefer 1<<n to 2**n although I guess they are implemented similarly. I am attaching my solution. Let n be the number of participants and k be the power of 2 following n (or n if it is a power of 2). Let p g2(k). The tournament (in my code) is understood as a binary tree *of "expected" matches* starting with the final (expected to be [1,2] the best against the second-best). Assume we have computed all the matches up to level i-1 (i are the semi-finals, i0quarter-finals...), which are r *(i-1) matches: m_1, ..., m_r (notice I start counting at 1). Let us compute the i-level matches, which are 2**i, call them n_1,...,n_2r . The algorithm is: Let l l_1,...,l_2r) m_11, m_12, m_21, m_22, ..., m_r2) the list of players at level i-1 ordered as the matches say (i.e., in the semi-finals: (1,4,2,5) Let INDEX **(i)+1 Let j STEP: Match n_j l_j, OP_j] where l_j + OP_j NDEX j++ GOTO STEP unless j > 2r return (n_1,...,n2r) Actually, one can do a better ordering (which puts 1 at the top and 2 at the bottom of every tree), which is what I have implemented. In my code, the complete tournament is kept in memory as a list of 1 + 2 +... +2**p matches. Different levels (i) can be distinguished by starting to count at 2**(i-1)-1 As you will see, the code looks somewhat hackish because there are too many 2** and off-by-one counts. However, I think this preserves the "natural" structure of the data without using strong stuff like nested lists of different lengths, etc... (And it is obviously more challenging to program this way :) If you create a Tournament with a number, you get the numbers as the labels. If you create it with a list, it is understood as an ordered (according to rank) list of the participants. Labels (and emptpy spaces) are then given the maximum length of the names. Example: one| |-----| four| | |----- three| | |-----| two| (notice the "nice" 1-at the top 2-at the bottom ordering). -- Pedro Fortuny Ayuso C/Capuchinos 14, 1. 47006 Valladolid. SPAIN http://pfortuny.sdf-eu.org ------ art_149726_28512089.1165831166113 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline Hi,<br><br>I am new to the quizzes and also more or less new to ruby. I would appreciate any comments on my "unrubyness", and thanks in advance. I prefer 1<<n to 2**n although I guess they are implemented similarly. <br><br>I am attaching my solution.<br>Let n be the number of participants and k be the power of 2 following n (or n if it is a power of 2). Let p g2(k).<br>The tournament (in my code) is understood as a binary tree *of "expected" matches* starting with the final (expected to be [1,2] the best against the second-best). Assume we have computed all the matches up to level i-1 (i are the semi-finals, i0quarter-finals...), which are r *(i-1) matches: m_1, ..., m_r (notice I start counting at 1). Let us compute the i-level matches, which are 2**i, call them n_1,...,n_2r . The algorithm is: <br>Let l l_1,...,l_2r) m_11, m_12, m_21, m_22, ..., m_r2) the list of players at level i-1 ordered as the matches say (i.e., in the semi-finals: (1,4,2,5)<br><br>Let INDEX **(i)+1<br>Let j <br>STEP:<br> Match n_j l_j, OP_j] where l_j + OP_j NDEX <br> j++<br> GOTO STEP unless j > 2r<br>return (n_1,...,n2r)<br><br>Actually, one can do a better ordering (which puts 1 at the top and 2 at the bottom of every tree), which is what I have implemented.<br>In my code, the complete tournament is kept in memory as a list of <br>1 + 2 +... +2**p<br>matches. Different levels (i) can be distinguished by starting to count at 2**(i-1)-1<br><br>As you will see, the code looks somewhat hackish because there are too many 2** and off-by-one counts. However, I think this preserves the "natural" structure of the data without using strong stuff like nested lists of different lengths, etc... (And it is obviously more challenging to program this way <br>:)<br><br>If you create a Tournament with a number, you get the numbers as the labels. If you create it with a list, it is understood as an ordered (according to rank) list of the participants. Labels (and emptpy spaces) are then given the maximum length of the names. <br><br>Example:<br> one| <br> |-----|<br> four| |<br> |-----<br>three| |<br> |-----|<br> two| <br><br>(notice the "nice" 1-at the top 2-at the bottom ordering).<br><br><br> -- <br>Pedro Fortuny Ayuso<br>C/Capuchinos 14, 1. 47006 Valladolid. SPAIN<br><a href ttp://pfortuny.sdf-eu.org">http://pfortuny.sdf-eu.org</a> ------ art_149726_28512089.1165831166113-- ------ art_149725_27862236.1165831166113 Content-Type: application/octet-stream; name=tournament_matchups.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_evkprlnn Content-Disposition: attachment; filename="tournament_matchups.rb" aW5jbHVkZSBNYXRoCnJlcXVpcmUgJ3JhdGlvbmFsJwoKY2xhc3MgVG91cm5hbWVudAogIAogIGF0 dHJfcmVhZGVyIDpwYXJ0aWNpcGFudHMsIDpsZXZlbHMsIDp0b3RhbF9tYXRjaHVwcywgOnRyZWUs IDpzdHJpbmdlZCwgOnN0cmluZwogCiAgZGVmIGluaXRpYWxpemUoaCkgIAogICAgIyBwYXJhbWV0 ZXIgY2hlY2tpbmc6CiAgICBjYXNlIGgKICAgIHdoZW4gRml4bnVtCiAgICAgIHJhaXNlIFR5cGVF cnJvciwgIlRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzIG11c3QgYmUgPiAxIiB1bmxlc3MgaD4x CiAgICAgIEBwYXJ0aWNpcGFudHMgPSAoIiN7MX0iLi4iI3tofSIpLnRvX2EKICAgIHdoZW4gQXJy YXkKICAgICAgcmFpc2UgVHlwZUVycm9yLCAiVGhlIG51bWJlciBvZiBwYXJ0aWNpcGFudHMgbXVz dCBiZSA+IDEiIHVubGVzcyBoLmxlbmd0aCA+IDEKICAgICAgQHBhcnRpY2lwYW50cyA9IGgubWFw IHt8eHwgeC50b19zfQogICAgZWxzZQogICAgICByYWlzZSBUeXBlRXJyb3IsICJQYXJhbWV0ZXIg bXVzdCBiZSBhbiBBcnJheSBvciBhIEZpeG51bSIKICAgIGVuZCAKICAgIAogICAgIyBiYXNpYyBp bml0aWFsaXphdGlvbgogICAgQHBfbnVtYmVyID0gQHBhcnRpY2lwYW50cy5sZW5ndGgKICAgIEBs ZXZlbHMgPSBAcF9udW1iZXIubG9nMgogICAgQGxldmVscyA9ICgxPDwoQGxldmVscykgPT0gQHBf bnVtYmVyKSA/IEBsZXZlbHMgLTEgOiBAbGV2ZWxzCiAgICBAdG90YWxfbWF0Y2h1cHMgPSAxPDwo QGxldmVscykKICAgIChAcF9udW1iZXIuLigyKkB0b3RhbF9tYXRjaHVwcyAtIDEpKS5lYWNoIGRv IHx4fCBAcGFydGljaXBhbnRzPDxuaWwgZW5kCiAgICAKICAgICMgc2V0dXAgdGhlIHdob2xlIHZh bHVhdGlvbiB0cmVlOiBXZSBhbHJlYWR5IGtub3cgdGhlcmUgaXMgT05FIG1hdGNoIGF0IGxlYXN0 CiAgICBAdHJlZSA9IFtbMSwyXV0KICAgICgwLi5AbGV2ZWxzKS5lYWNoIGRvIHxsZXZlbHwKICAg ICAgayA9ICgxPDxsZXZlbCkgLSAxCiAgICAgIG5vZGVzID0gQHRyZWVbLShrKzEpLzIsKGsrMSkv Ml0uaW5qZWN0KFtdKSB7fHMsZXwgcytlfQogICAgICAjIHRoaXMgY291bnRlciBpcyBwcm9iYWJs eSBzcHVyaW91cyBpbiBSdWJ5PwogICAgICBpID0gMAogICAgICBub2Rlcy5lYWNoIGRvIHxpbmRl eHwKICAgICAgICBvcHBvbmVudCA9ICgoMiooaysxKS1pbmRleCsxKSA+IEBwX251bWJlcikgPyBu aWwgOiAoMiooaysxKSAtIGluZGV4KzEpCiAgICAgICAgIyBoYWNrIHRvIGdldCB0aGUgdHJlZSBs b29rICJzeW1tZXRyaWNhbCIgaW4gdGhlIDFzdCBhbmQgMm5kIHBsYXllcnMKICAgICAgICBpZiBp IDwgawogICAgICAgICAgQHRyZWU8PCBbaW5kZXgsIG9wcG9uZW50XQogICAgICAgIGVsc2UgIAog ICAgICAgICAgQHRyZWUgPDwgW29wcG9uZW50LCBpbmRleF0KICAgICAgICBlbmQgCiAgICAgICAg aSArPSAxCiAgICAgIGVuZCAKICAgIGVuZCAKICBlbmQgCiAgCiAgIyBwYWlyaW5ncyAoaS5lLiB3 aXRoIE5VTUJFUlMpIChwb3NzaWJseSB3aXRoIG5pbCBvcHBvbmVudCkgKiphZnRlcioqIGsgcm91 bmRzCiAgZGVmIHBhaXJpbmdzKGsgPSAwKQogICAgcmV0dXJuIFtdIHVubGVzcyBrIDwgKEBsZXZl bHMgKyAxKQogICAgQHRyZWVbKCAoKDE8PChAbGV2ZWxzIC0gaykpIC0gMSkuLigoMTw8KEBsZXZl bHMgLSBrKzEpKSAtIDIpICldCiAgZW5kIAogICAgCiAgIyAqKmV4cGVjdGVkKiogdHJ1ZSAqKm1h dGNoZXMqKiAoaS5lLiB3aXRoIG5hbWVzKSAqKmFmdGVyKiogayByb3VuZHMuCiAgIyBJZiB0aGVy ZSBhcmUgdGFpbHMsIHBhcmluaW5ncyBbMSxuaWxdIGdpdmUgTk8gbWF0Y2hlcy4gVGhpcyBpcyAi cmVhbGl0eSIKICBkZWYgbWF0Y2hlcyhrID0gMCkKICAgIHJldHVybiBbXSB1bmxlc3MgayA8IChA bGV2ZWxzICsgMSkKICAgIHBhaXJpbmdzKGspLmZpbmRfYWxsIHt8eHwgbm90KHgubWVtYmVyPyhu aWwpKX0uaW5qZWN0KFtdKSBkbyB8cyxlfAogICAgICBwYWlyID0gW10KICAgICAgZS5lYWNoIGRv IHx0ZWFtfAogICAgICAgIGlmIHRlYW0ubmlsPyB0aGVuIHBhaXI8PG5pbCBlbHNlIHBhaXI8PEBw YXJ0aWNpcGFudHNbdGVhbS0xXSBlbmQKICAgICAgZW5kIAogICAgICBzPDxwYWlyCiAgICBlbmQg CiAgZW5kIAogIAogICMgdG9fczogYnVpbGQgdXAgYSBxdWl0ZSBuaWNlIHN0cmluZyBkZXRhaWxp bmcgdGhlIHRvdXJuYW1lbnQgbWF0Y2hlcwogICMgZXh0cmVtZWx5IGhhY2tpc2ghCiAgZGVmIHRv X3MKICAgIHJldHVybiBAc3RyaW5nIHVubGVzcyBAc3RyaW5nLm5pbD8KICAgIEBzdHJpbmcgPSAi IgogICAgaGVpZ2h0ID0gNCAqIEB0b3RhbF9tYXRjaHVwcwogICAgbGFiZWwgPSAiLSIgKiAoQHBh cnRpY2lwYW50cy5tYXAge3x4fCAoeC5uaWw/ICYmIDApIHx8IHgubGVuZ3RofSkuaW5qZWN0KDEp IHt8cyxlfCBzID4gZSA/IHMgOiBlfQogICAgd2lkdGggPSAobGFiZWwubGVuZ3RoKSooQGxldmVs cyArIDEpICsgMipAbGV2ZWxzCiAgICBAc3RyaW5nZWQgPSBBcnJheS5uZXcoaGVpZ2h0KSB7IEFy cmF5Lm5ldyh3aWR0aCkuZmlsbCgiICIpIH0KICAgICMgc3RlcCAwIGlzIHNwZWNpYWw6IHB1dCBh bGwgdGhlIGxhYmVscwogICAgKDAuLihAdG90YWxfbWF0Y2h1cHMtMSkpLmVhY2ggZG8gfGl0ZW18 CiAgICAgIHB1dF9sYWJlbCgwLDQqaXRlbSxAcGFydGljaXBhbnRzWyhwYWlyaW5ncygpW2l0ZW1d WzBdfHwwKSAtIDFdLnRvX3MsbGFiZWwubGVuZ3RoKQogICAgICBwdXRfbGFiZWwoMCw0KihpdGVt KSsyLEBwYXJ0aWNpcGFudHNbKHBhaXJpbmdzKClbaXRlbV1bMV18fDApIC0gMV0udG9fcyxsYWJl bC5sZW5ndGgpCiAgICBlbmQKICAgICMgaXRlcmF0aXZlIHN0ZXBzCiAgICAoMC4uKEBsZXZlbHMr MSkpLmVhY2ggZG8gfGxldmVsfAogICAgICBzdGVwID0gKDE8PGxldmVsKSAtIDEKICAgICAgKDAu LiggKDE8PChAbGV2ZWxzIC0gbGV2ZWwpKSAtIDEpICkuZWFjaCBkbyB8cGFpcnwgCiAgICAgICAg am9pbl9wYWlyKGxldmVsLHBhaXIsc3RlcCxsYWJlbC5sZW5ndGgpCiAgICAgICAgcHV0X2xhYmVs KChsZXZlbCsxKSoobGFiZWwubGVuZ3RoKzEpLDIucnBvd2VyKGxldmVsKSArIDIucnBvd2VyKGxl dmVsKzIpKnBhaXIrc3RlcCxsYWJlbCkKICAgICAgZW5kIAogICAgZW5kIAogICAgQHN0cmluZ2Vk LmVhY2gge3x4fCBAc3RyaW5nICs9ICh4LmpvaW4oIiIpICsgIlxuIikgfQogICAgcmV0dXJuIEBz dHJpbmcKICBlbmQgCgogICMgcHJpdmF0ZSBtZXRob2RzLiBVc2VkIGJ5IHRvX3MsIG1haW5seQog IHByaXZhdGUgIAogIAogIGRlZiBqb2luX3BhaXIobGV2ZWwscGFpcixzdGVwLHdpZHRoKQogICAg aG9yaXpvbnRhbCA9ICgobGV2ZWwrMSkgKiAod2lkdGggKyAxKSkKICAgIHN0YXJ0ID0gNCpwYWly KigxPDxsZXZlbCkrc3RlcAogICAgZW5kXyA9IHN0YXJ0ICsgKDE8PChsZXZlbCsxKSkKICAgIChz dGFydC4uZW5kXykuZWFjaCBkbyB8eXwKICAgICAgQHN0cmluZ2VkW3ldW2hvcml6b250YWwtMV09 ICJ8IgogICAgZW5kIAogIGVuZCAKCiAgZGVmIHB1dF9sYWJlbCh4LHksbGFiZWwsbWF4X2xlbmd0 aCA9IGxhYmVsLmxlbmd0aCkKICAgICgwLi4obGFiZWwubGVuZ3RoLTEpKS5lYWNoIGRvIHxpfAog ICAgICBAc3RyaW5nZWRbeV1bbWF4X2xlbmd0aCAtIGxhYmVsLmxlbmd0aCArIHggKyBpXSA9IGxh YmVsW2ldLmNociAKICAgIGVuZCAKICBlbmQgCiAgCmVuZCAKICAKCmNsYXNzIEZpeG51bQogIAog ICMgVG9vIHVzZWQgbm90IHRvIGhhdmUgaXQKICBkZWYgbG9nMgogICAgaSA9IDAKICAgIHZhbHVl ID0gc2VsZgogICAgd2hpbGUodmFsdWUgPiAxKSAKICAgICAgdmFsdWUgPj49IDEKICAgICAgaSAr PSAxCiAgICBlbmQgCiAgICBpCiAgZW5kIAogIAplbmQgCg ------ art_149725_27862236.1165831166113--