On 4/9/07, Raj Sahae <rajsahae / gmail.com> wrote: > Christian Neukirchen wrote: > > =begin > > > >> The quiz, then, is to solve this problem without thinking, instead > >> letting the computer think for you. > >> > > > > I did not intent to seriously submit this solution, but it can be > > helpful as an example of how to use Ruby to solve a problem quickly > > without thinking too much or locating Knuth on the bookshelve. > > Writing this code took maybe ten minutes and happened step-by-step > > with checking the immediate results. > > > > Since there are only 168 solutions (254 if you allow a sign before the > > first digit), brute-forcing is the simplest thing one can do. > > Additional operations can be added by changing the base and mapping > > the digits onto further operations. (Different digit order is not > > that easy to implement and maybe be futile to do with brute-forcing.) > > =end > > > > (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0"). > > tr('012', '-+ ') }. > > find_all { |x| x.count("-") == 2 and x.count("+") == 1 }. > > map { |x| > > t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") > > [eval(t), t] > > }.sort.each { |s, x| > > puts "*****************" if s == 100 > > puts "#{x}: #{s}" > > puts "*****************" if s == 100 > > } > > > > __END__ > > > > 2#787<p4>lilith:~/mess/current$ ruby quiz119.rb |grep -C4 100$ > > 123-456-7+89: -251 > > 123+45-67-89: 12 > > 123-45+67-89: 56 > > ***************** > > 123-45-67+89: 100 > > ***************** > > 12+345-67-89: 201 > > 1-234+567-89: 245 > > 1-23-456+789: 311 > > > > > I'm sorry to be a noob on this, but can someone please explain to me > what this is doing. If it works, it must be genius, and I can't figure > it out. > > Raj Sahae > > Actually I have no idea whatsoever, this is normally a good starting point ;) irb is our friend of course, so let us hack away: irb(main):003:0> (000..'222'.to_i(3)).map{|x|x.to_s(3).rjust(3, "0").tr('012', '-+ ')} => ["---", "--+", "-- ", "-+-", "-++", "-+ ", "- -", "- +", "- ", "+--", "+-+", "+- ", "++-", "+++", "++ ", "+ -", "+ +", "+ ", " --", " -+", " - ", " +-", " ++", " + ", " -", " +", " "] Aha the ternary array is used to create all kind of operator combinations including " ". I do not know exactly what this is good for right now, but I guess we will learn. As a next step I increase 3 to 8 as I think we can understand that now and I will add the next method (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0").tr('012', '-+ ') }.find_all { |x| x.count("-") == 2 and x.count("+") == 1 } => ["--+ ", "-- + ", "-- + ", "-- + ", "-- + ", "-- +", "-+- ", "-+ - ", "-+ - ", "-+ - ", "-+ - ", "-+ -", "- -+ ", "- - + ", "- - + ", "- - + ", "- - +", "- +- ", "- + - ", "- + - ", "- + - ", "- + -", "- -+ ", "- - + ", "- - + ", "- - +", "- +- ", "- + - ", "- + - ", "- + -", "- -+ ", "- - + ", "- - +", "- +- ", "- + - ", "- + -", "- -+ ", "- - +", "- +- ", "- + -", "- -+", "- +-", "+-- ", "+- - ", "+- - ", "+- - ", "+- - ", "+- -", "+ -- ", "+ - - ", "+ - - ", "+ - - ", "+ - -", "+ -- ", "+ - - ", "+ - - ", "+ - -", "+ -- ", "+ - - ", "+ - -", "+ -- ", "+ - -", "+ --", " --+ ", " -- + ", " -- + ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ - ", " -+ - ", " -+ -", " - -+ ", " - - + ", " - - + ", " - - +", " - +- ", " - + - ", " - + - ", " - + -", " - -+ ", " - - + ", " - - +", " - +- ", " - + - ", " - + -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- - ", " +- - ", " +- -", " + -- ", " + - - ", " + - - ", " + - -", " + -- ", " + - - ", " + - -", " + -- ", " + - -", " + --", " --+ ", " -- + ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ - ", " -+ -", " - -+ ", " - - + ", " - - +", " - +- ", " - + - ", " - + -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- - ", " +- -", " + -- ", " + - - ", " + - -", " + -- ", " + - -", " + --", " --+ ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- -", " + -- ", " + - -", " + --", " --+ ", " -- +", " -+- ", " -+ -", " - -+", " - +-", " +-- ", " +- -", " + --", " --+", " -+-", " +--"] It is a little longer but we see already that only 2 minuses and 1 plus is allowed... By storing this into a variable tmp we can continue easily to explore what is happening tmp.map{|x| t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ; [eval(t),t]} => [[456785, "1-2-3+456789"], [56754, "1-2-34+56789"], [6443, "1-2-345+6789"], [-2668, "1-2-3456+789"], [-34479, "1-2-34567+89"], [-345670, "1-2-345678+9"], [-456787, "1-2+3-456789"], [-56756, "1-2+34-56789"], [-6445, "1-2+345-6789"], [2666, "1-2+3456-789"], [34477, "1-2+34567-89"], [345668, "1-2+345678-9"], [56763, "1-23-4+56789"], [6722, "1-23-45+6789"], [311, "1-23-456+789"], [-4500, "1-23-4567+89"], [-45691, "1-23-45678+9"], [-56807, "1-23+4-56789"], [-6766, "1-23+45-6789"], [-355, "1-23+456-789"], [4456, "1-23+4567-89"], [45647, "1-23+45678-9"], [6551, "1-234-5+6789"], [500, "1-234-56+789"], [-711, "1-234-567+89"], [-5902, "1-234-5678+9"], [-7017, "1-234+5-6789"], [-966, "1-234+56-789"], [245, "1-234+567-89"], [5436, "1-234+5678-9"], [-1561, "1-2345-6+789"], [-2322, "1-2345-67+89"], [-3013, "1-2345-678+9"], [-3127, "1-2345+6-789"], [-2366, "1-2345+67-89"], [-1675, "1-2345+678-9"], [-23373, "1-23456-7+89"], [-23524, "1-23456-78+9"], [-23537, "1-23456+7-89"], [-23386, "1-23456+78-9"], [-234565, "1-234567-8+9"], [-234567, "1-234567+8-9"], [-456789, "1+2-3-456789"], [-56820, "1+2-34-56789"], [-7131, "1+2-345-6789"], [-4242, "1+2-3456-789"], [-34653, "1+2-34567-89"], [-345684, "1+2-345678-9"], [-56769, "1+23-4-56789"], [-6810, "1+23-45-6789"], [-1221, "1+23-456-789"], [-4632, "1+23-4567-89"], [-45663, "1+23-45678-9"], [-6559, "1+234-5-6789"], [-610, "1+234-56-789"], [-421, "1+234-567-89"], [-5452, "1+234-5678-9"], [1551, "1+2345-6-789"], [2190, "1+2345-67-89"], [1659, "1+2345-678-9"], [23361, "1+23456-7-89"], [23370, "1+23456-78-9"], [234551, "1+234567-8-9"], [56794, "12-3-4+56789"], [6753, "12-3-45+6789"], [342, "12-3-456+789"], [-4469, "12-3-4567+89"], [-45660, "12-3-45678+9"], [-56776, "12-3+4-56789"], [-6735, "12-3+45-6789"], [-324, "12-3+456-789"], [4487, "12-3+4567-89"], [45678, "12-3+45678-9"], [6762, "12-34-5+6789"], [711, "12-34-56+789"], [-500, "12-34-567+89"], [-5691, "12-34-5678+9"], [-6806, "12-34+5-6789"], [-755, "12-34+56-789"], [456, "12-34+567-89"], [5647, "12-34+5678-9"], [450, "12-345-6+789"], [-311, "12-345-67+89"], [-1002, "12-345-678+9"], [-1116, "12-345+6-789"], [-355, "12-345+67-89"], [336, "12-345+678-9"], [-3362, "12-3456-7+89"], [-3513, "12-3456-78+9"], [-3526, "12-3456+7-89"], [-3375, "12-3456+78-9"], [-34554, "12-34567-8+9"], [-34556, "12-34567+8-9"], [-56778, "12+3-4-56789"], [-6819, "12+3-45-6789"], [-1230, "12+3-456-789"], [-4641, "12+3-4567-89"], [-45672, "12+3-45678-9"], [-6748, "12+34-5-6789"], [-799, "12+34-56-789"], [-610, "12+34-567-89"], [-5641, "12+34-5678-9"], [-438, "12+345-6-789"], [201, "12+345-67-89"], [-330, "12+345-678-9"], [3372, "12+3456-7-89"], [3381, "12+3456-78-9"], [34562, "12+34567-8-9"], [6903, "123-4-5+6789"], [852, "123-4-56+789"], [-359, "123-4-567+89"], [-5550, "123-4-5678+9"], [-6665, "123-4+5-6789"], [-614, "123-4+56-789"], [597, "123-4+567-89"], [5788, "123-4+5678-9"], [861, "123-45-6+789"], [100, "123-45-67+89"], [-591, "123-45-678+9"], [-705, "123-45+6-789"], [56, "123-45+67-89"], [747, "123-45+678-9"], [-251, "123-456-7+89"], [-402, "123-456-78+9"], [-415, "123-456+7-89"], [-264, "123-456+78-9"], [-4443, "123-4567-8+9"], [-4445, "123-4567+8-9"], [-6667, "123+4-5-6789"], [-718, "123+4-56-789"], [-529, "123+4-567-89"], [-5560, "123+4-5678-9"], [-627, "123+45-6-789"], [12, "123+45-67-89"], [-519, "123+45-678-9"], [483, "123+456-7-89"], [492, "123+456-78-9"], [4673, "123+4567-8-9"], [2012, "1234-5-6+789"], [1251, "1234-5-67+89"], [560, "1234-5-678+9"], [446, "1234-5+6-789"], [1207, "1234-5+67-89"], [1898, "1234-5+678-9"], [1260, "1234-56-7+89"], [1109, "1234-56-78+9"], [1096, "1234-56+7-89"], [1247, "1234-56+78-9"], [668, "1234-567-8+9"], [666, "1234-567+8-9"], [444, "1234+5-6-789"], [1083, "1234+5-67-89"], [552, "1234+5-678-9"], [1194, "1234+56-7-89"], [1203, "1234+56-78-9"], [1784, "1234+567-8-9"], [12421, "12345-6-7+89"], [12270, "12345-6-78+9"], [12257, "12345-6+7-89"], [12408, "12345-6+78-9"], [12279, "12345-67-8+9"], [12277, "12345-67+8-9"], [12255, "12345+6-7-89"], [12264, "12345+6-78-9"], [12395, "12345+67-8-9"], [123450, "123456-7-8+9"], [123448, "123456-7+8-9"], [123446, "123456+7-8-9"]] Well this is very impressive as it solves the quiz but I lost him there, I guess we have to look into the block applied to tmp.map {|x| t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ; [eval(t),t]} okay let us take just one x, e.g. x= tmp[32] => "- - +" ## To my great despair tmp[42] is not a very good example :( Now we split x into single characters and zip the digits 2 to 9 into them x.split(//).zip([*2..9]) => [["-", 2], [" ", 3], [" ", 4], [" ", 5], ["-", 6], [" ", 7], [" ", 8], ["+", 9]] and I think I understand what happened now, the rest is basic, add a 1 in the front flatten the array and delete all spaces, and you get the expressions needed for the quiz. I guess that the final sort.each is quite straight forward. HTH BTW I want to have my ball back James, or adjust my handicap please ;). Cheers Robert -- You see things; and you say Why? But I dream things that never were; and I say Why not? -- George Bernard Shaw