Problem 43

Projekt Euler w Ruby
1

Problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1-st digit, d2 be the 2-nd digit, and so on. In this way, we note the following:

* d2d3d4=406 is divisible by 2
* d3d4d5=063 is divisible by 3
* d4d5d6=635 is divisible by 5
* d5d6d7=357 is divisible by 7
* d6d7d8=572 is divisible by 11
* d7d8d9=728 is divisible by 13
* d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

2

[code=ruby]Combo = %w(0 1 2 3 4 5 6 7 8 9).permutation
pandigitals = []
loop do
e = Combo.next
next if e.first == ‘0’
STDOUT.print “#{e}\r”
STDOUT.flush
pandigitals << e.join if (e[1]+e[2]+e[3]).to_i % 2 == 0 &&
(e[2]+e[3]+e[4]).to_i % 3 == 0 &&
(e[3]+e[4]+e[5]).to_i % 5 == 0 &&
(e[4]+e[5]+e[6]).to_i % 7 == 0 &&
(e[5]+e[6]+e[7]).to_i % 11 == 0 &&
(e[6]+e[7]+e[8]).to_i % 13 == 0 &&
(e[7]+e[8]+e[9]).to_i % 17 == 0
end

puts " "
p pandigitals
puts pandigitals.map(&:to_i).inject(:+)[/code]

3

A może tak:

#!/usr/bin/env ruby P = [1, 2, 3, 5, 7, 11, 13, 17] sum = 0 ("0".."9").to_a.permutation do |t| if (0..7).all? { |i| t[i..i+2].join.to_i%P[i] == 0 } puts "pan=#{t.join}" sum += t.join.to_i end end puts sum

4

tutaj rozwiązanie “oszczędzające” ilość iteracji - (trochę mniej “brute force” :slight_smile: ).
Warto zauważyć że “dziedzina” to liczby w których znaki ułożone z trzech ostatnich cyfr są podzielne przez 17 (div_by_17). Oczywiście nie trzeba tu robić wszystkich 3-elementowych kombinacji - wystarczy wielokrotności 17 między 100 i 999 gdzie poszczególne cyfry występują tylko raz. Potem elegancko dodajemy po jednej z przodu i sprawdzamy czy jest podzielna przez kolejną zadaną wartość.
Na koniec dodajemy na początku pozostającą cyferkę i sumujemy (0,15 sec na dość leciwej już maszynie)

ALL_DIGITS = [0,1,2,3,4,5,6,7,8,9]
div_by_17 = []

ALL_DIGITS.permutation(3).to_a.each do |aa1|
  div_by_17 << aa1.join if aa1.join.to_i.%(17).zero?
end

def c_f_d(results_so_far, divider)
  new_results = []
  results_so_far.each do |aa|
    two_new_last_digits = aa[0..1]
    remains = ALL_DIGITS - aa.split(//).map {|chr| chr.to_i}
    remains.each do |b|
      new_results << b.to_s + aa if (b.to_s + two_new_last_digits).to_i.%(divider).zero?
    end
  end
  new_results
end

neww = c_f_d(c_f_d(c_f_d(c_f_d(c_f_d((c_f_d(div_by_17, 13)), 11), 7), 5), 3), 2)
neww.collect! {|r| ("1234567890".delete(r) + r).to_i}
p neww.inject(:+)