baweaver/problem_4.rb

## problem_4.rb
def permutation_sorting_n4(my_array)
  my_array
    .map(&:to_s)
    .permutation
    .flat_map { |a|
      a.join.to_i
    }.max
end

def string_sorting_n4(my_array)
  # We make a scoring algorithm for comparing the numbers
  score = -> v {
    # We use the first digit and multiply it by the average of the other digits, such that:
    # 9   -> 81
    # 90  -> 40.5
    # 981 -> 54.0
    # 909 -> 54.0
    #
    # The above failure is compensated for below in the sort.
    v[0].to_i * (v.chars.map(&:to_i).reduce(:+) / v.length.to_f)
  }

  # Now to the solver
  my_array
    # First we want to have all the numbers as strings
    .map(&:to_s)
    # Then we lexigraphically sort it backwards
    .sort { |a,b| b <=> a }
    # and make groups based on the first digit (ie 9 and 90 end up in the same pool)
    # as the first digit being greater will always give priority
    .slice_when { |b, a| b[0] != a[0] }
    # Then we compact the results of the sort
    .flat_map { |xs|
      xs.sort { |a,b|
        # We use our scoring algorithm above
        sa, sb = score[a], score[b]
        # and use it with the comparator
        compare = sb <=> sa

        # If it's 0, we have a potential 981 vs 909 problem, so we compare numerically
        # to compensate
        compare.zero? ? (b.to_i <=> a.to_i) : compare
      }
    }
    .join
    .to_i # and there we have our number
end

my_array        = (1..100).to_a.sample(10)
permutation_way = -> _ { permutation_sorting_n4(my_array) }
string_way      = -> _ { string_sorting_n4(my_array)      }

puts "Array used: #{my_array}"
puts
puts "Permutation sort result: #{per = permutation_sorting_n4(my_array)}"
puts "String sort result:      #{str = string_sorting_n4(my_array)}"
puts
puts "The results are #{per == str ? :equal : :not_equal}"
puts

string_method_benchmark      = Benchmark.measure { 5.times(&string_way)      }.real
permutation_method_benchmark = Benchmark.measure { 5.times(&permutation_way) }.real

puts "It took string sort #{string_method_benchmark} seconds to run 5 times"
puts "It took permutation sort #{permutation_method_benchmark} seconds to run 5 times"
puts
puts "Using permutations is #{permutation_method_benchmark / string_method_benchmark} times slower than using a sorting algorithm"
puts "or #{(string_method_benchmark / permutation_method_benchmark)*100} percenth of the time"

# Array used: [18, 30, 69, 10, 80, 38, 97, 43, 37, 76]
#
# Permutation sort result: 97807669433837301810
# String sort result:      97807669433837301810
#
# The results are equal
#
# It took string sort 0.00245954398997128 seconds to run 5 times
# It took permutation sort 35.3980373670347 seconds to run 5 times

# Using permutations is 14392.113949321169 times slower than using a sorting algorithm
# or 0.006948249600588849 percenth of the time

# Did not fail on the defaults, though I'd love to hear a counter in the comments.
def test_run(run_times: 100_000, max_int: 100, sample_size: 5)
  run_times.times.map { |n|
    my_a = (1..100).to_a.sample(5)
    per = permutation_sorting_n4(my_a)
    str = string_sorting_n4(my_a)
    {array: my_a, permutation: per, string: str} if per != str
  }.select(&:itself)
end
	def permutation_sorting_n4(my_array)
	my_array
	.map(&:to_s)
	.permutation
	.flat_map { \|a\|
	a.join.to_i
	}.max
	end

	def string_sorting_n4(my_array)
	# We make a scoring algorithm for comparing the numbers
	score = -> v {
	# We use the first digit and multiply it by the average of the other digits, such that:
	# 9 -> 81
	# 90 -> 40.5
	# 981 -> 54.0
	# 909 -> 54.0
	#
	# The above failure is compensated for below in the sort.
	v[0].to_i * (v.chars.map(&:to_i).reduce(:+) / v.length.to_f)
	}

	# Now to the solver
	my_array
	# First we want to have all the numbers as strings
	.map(&:to_s)
	# Then we lexigraphically sort it backwards
	.sort { \|a,b\| b <=> a }
	# and make groups based on the first digit (ie 9 and 90 end up in the same pool)
	# as the first digit being greater will always give priority
	.slice_when { \|b, a\| b[0] != a[0] }
	# Then we compact the results of the sort
	.flat_map { \|xs\|
	xs.sort { \|a,b\|
	# We use our scoring algorithm above
	sa, sb = score[a], score[b]
	# and use it with the comparator
	compare = sb <=> sa

	# If it's 0, we have a potential 981 vs 909 problem, so we compare numerically
	# to compensate
	compare.zero? ? (b.to_i <=> a.to_i) : compare
	}
	}
	.join
	.to_i # and there we have our number
	end

	my_array = (1..100).to_a.sample(10)
	permutation_way = -> _ { permutation_sorting_n4(my_array) }
	string_way = -> _ { string_sorting_n4(my_array) }

	puts "Array used: #{my_array}"
	puts
	puts "Permutation sort result: #{per = permutation_sorting_n4(my_array)}"
	puts "String sort result: #{str = string_sorting_n4(my_array)}"
	puts
	puts "The results are #{per == str ? :equal : :not_equal}"
	puts

	string_method_benchmark = Benchmark.measure { 5.times(&string_way) }.real
	permutation_method_benchmark = Benchmark.measure { 5.times(&permutation_way) }.real

	puts "It took string sort #{string_method_benchmark} seconds to run 5 times"
	puts "It took permutation sort #{permutation_method_benchmark} seconds to run 5 times"
	puts
	puts "Using permutations is #{permutation_method_benchmark / string_method_benchmark} times slower than using a sorting algorithm"
	puts "or #{(string_method_benchmark / permutation_method_benchmark)*100} percenth of the time"

	# Array used: [18, 30, 69, 10, 80, 38, 97, 43, 37, 76]
	#
	# Permutation sort result: 97807669433837301810
	# String sort result: 97807669433837301810
	#
	# The results are equal
	#
	# It took string sort 0.00245954398997128 seconds to run 5 times
	# It took permutation sort 35.3980373670347 seconds to run 5 times

	# Using permutations is 14392.113949321169 times slower than using a sorting algorithm
	# or 0.006948249600588849 percenth of the time

	# Did not fail on the defaults, though I'd love to hear a counter in the comments.
	def test_run(run_times: 100_000, max_int: 100, sample_size: 5)
	run_times.times.map { \|n\|
	my_a = (1..100).to_a.sample(5)
	per = permutation_sorting_n4(my_a)
	str = string_sorting_n4(my_a)
	{array: my_a, permutation: per, string: str} if per != str
	}.select(&:itself)
	end