alphametics: Fast example solution?

[Insti]

Does anyone have a super-fast alphamentics solution?

We need an example solution that can solve this test:

ruby/exercises/alphametics/alphametics_test.rb

Line 76 in 83bf92a

def test_puzzle_with_ten_letters_and_199_addends

in a reasonable amount of time.

TODO:

Update the example solution: https://github.com/exercism/ruby/blob/master/exercises/alphametics/.meta/solutions/alphametics.rb
With a faster one.

[Insti]

From a Travis CI run:

running tests for: alphametics
/home/travis/.rvm/rubies/ruby-2.1.2/bin/ruby -I lib -r disable_skip.rb /tmp/alphametics20180827-4172-n6z3u4/alphametics_test.rb 
Run options: --seed 14874
# Running:
.........
Finished in 582.287082s, 0.0155 runs/s, 0.0155 assertions/s.
9 runs, 9 assertions, 0 failures, 0 errors, 0 skips

[petertseng]

I can say that https://travis-ci.org/petertseng/exercism-problem-specifications/builds/421220966 tells me that https://github.com/petertseng/exercism-problem-specifications/blob/verify/exercises/alphametics/verify.rb solves alphametics in 2.5 seconds on travis (the line 2.51user 0.00system 0:02.52elapsed)

Sorry I don't really have time to make a PR soon, so I don't object if someone else takes a better solution.

I can describe my solution in words:

I found that working from right-to-left was too slow and doesn't eliminate any possibilities at all. Every single digit is in the rightmost column, so even if you pre-assign 0 to its only possible digit, you will still examine all 9! permutations in the worst case, which is not acceptable for performance.

Work left-to-right instead; the leftmost columns are sparsely populated.

Working from right-to-left took 15 seconds on my computer, whereas working left-to-right took 1.9 seconds.

[petertseng]

Performance discussion in exercism/problem-specifications#1024 (comment) and all subsequent comments.

Can cut the runtime down from 2.5 seconds (on Travis) to 0.5 seconds (on an unspecified computer, did not test myself) by stopping immediately when you find ONE solution rather than finding them all.

Stopping at one solution is against the purpose of my code (this is verification code, it needs to make sure the solution is unique) therefore I cannot do it within the context of the problem-specifications repo. If you want that speedup you will have to do it yourself, or experiment with a port of exercism/python#1119 to see whether it does the claimed speedup.

[Insti]

Great! thanks @petertseng
Hopefully someone else will be able to make a Ruby PR. for this.

[n8chz]

I guess 53.421492s is not a reasonable amount of time.

[Insti]

It's better than 582.287082s (although it will also depend on how much faster your machine is than the Travis CI machine)

[n8chz]

14.894647s, still an order of magnitude slower than @petertseng, on a Dell Inspiron 580 (about 2010 vintage?)

class Alphametics
  def self.solve(input)
    input.upcase!
    keys = input.gsub(/[^A-Z]/,"").chars.to_a.uniq
    words = input.scan(/[A-Z]+/)
    final_letters = words.map {|x| x.slice(-1)}
    first_letters = words.map {|x| x.slice(0)}

    uniqlast = final_letters.uniq
    uniqfirst = first_letters.uniq
    firstnotlast = uniqfirst-uniqlast
    uniqrest = (keys - final_letters - first_letters).uniq
    sum_last_letter = final_letters.pop

    (0..9).to_a.permutation(uniqlast.length) do |lasts|
      table = Hash[[uniqlast, lasts].transpose]
      next if uniqfirst.any? {|first| table[first] == 0}
      next if (final_letters.map {|x| table[x]}).sum % 10 != table[sum_last_letter]
      ((1..9).to_a-table.values).permutation(firstnotlast.length) do |firsts|
        table2 = table.merge(Hash[[firstnotlast, firsts].transpose])
        ((0..9).to_a-table2.values).permutation(uniqrest.length) do |rest|
          table3 = table2.merge(Hash[[uniqrest, rest].transpose])
          expression = input.tr table3.keys.join, table3.values.map(&:to_s).join
          return table3 if eval(expression)
        end
      end
    end
    {}
  end
end

[Insti]

@n8chz If you want to make that a pull request to update https://github.com/exercism/ruby/blob/master/exercises/alphametics/.meta/solutions/alphametics.rb that would be great.

[petertseng]

Note that although #883 created https://github.com/exercism/ruby/blob/master/exercises/alphametics/.meta/solutions/alphametics_compact.rb, it's my belief that the Ruby track doesn't support multiple examples. This belief is rooted in the code https://github.com/exercism/ruby/blob/master/lib/tasks/exercise.rb#L26 . Therefore the https://github.com/exercism/ruby/blob/master/exercises/alphametics/.meta/solutions/alphametics.rb is still the solution that is being run in Travis CI.

A person who wants to close this issue would want to rectify this. It cannot fairly be recommended that this issue be closed until then.

[guygastineau]

Is this still slowing down the builds? (as it should according to @petertseng's comment above)???

[guygastineau]

According to the Travis logs for #964 a faster version of alphametics must be running:

running tests for: alphametics

/home/travis/.rvm/rubies/ruby-2.5.5/bin/ruby -I lib -r disable_skip.rb /tmp/alphametics20190613-6208-1txufb/alphametics_test.rb

Run options: --seed 47251

# Running:

.........

Finished in 3.092617s, 2.9102 runs/s, 2.9102 assertions/s.

9 runs, 9 assertions, 0 failures, 0 errors, 0 skips

Should this issue be closed?

[petertseng]

Everything I said is still true. There are two solutions, and the track doesn't support having two solutions, so it is not possible to predict which solution is being run. I will create a new issue for that.

Since the track doesn't test the 10 letters case anymore because of #853, the fact that the solution remains slow is no longer visible.

[guygastineau]

Thank you for the clarification 😁

[petertseng]

I forgot to answer the question.

Should this issue be closed?

Yes, because

Since the track doesn't test the 10 letters case anymore because of #853, the fact that the solution remains slow is no longer visible.

and because I made the issue I said I was going to make (#986)

[guygastineau]

Cool, well I don't have the permissions to close this issue, but maybe someone will do it.

[emcoding]

🙇

[Insti]

Finished in 3.092617s, 2.9102 runs/s, 2.9102 assertions/s.

3 seconds is still slow.

Edit: but not unreasonable :)