Programmieren lernen

/*	Update 14.01.2023:
	Lösung ohne Permutation -> nochmals Halbierung der Zeiten!
	C++ 20 | GCC
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath> // sqrt, log10 (GCC)

inline const auto get_vampire_numbers(size_t max) {
	std::map<size_t, std::vector<std::tuple<size_t, size_t>>> out{};
	max = size_t(sqrt(max));
	for (size_t left{ 10 }; left < max; ++left) {
		for (size_t right{ left + 1 }; right < max; ++right) {
			if (int(log10(left)) != int(log10(right)) || left % 10 == 0 && right % 10 == 0) continue;
			const auto pro{ left * right };
			if ((int(log10(pro)) + 1) & 1) continue;
			auto pro_str{ std::to_string(pro) };
			auto lr_str{ std::to_string(left) + std::to_string(right) };
			std::sort(pro_str.begin(), pro_str.end());
			std::sort(lr_str.begin(), lr_str.end());
			if (pro_str == lr_str) out[pro].push_back({ left, right });
		}
	}
	return out;
}

int main() {
	const auto vn{ get_vampire_numbers(1'000'000) };

	// Aufgabe 1 (bestimmte Vampirzahlen)
	const auto get_vn{ [&vn](const size_t& num) { return vn.size() < num ? 0 : std::next(vn.begin(), num - 1)->first; } };
	std::cout << "5. Vampirzahl: " << get_vn(5) << "\n";
	std::cout << "10. Vampirzahl: " << get_vn(10) << "\n";
	std::cout << "15. Vampirzahl: " << get_vn(15) << "\n";

	// Aufgabe 2 (erste mit mehr als 2 Eckzähnen)
	const auto find{ std::find_if(vn.begin(), vn.end(), [](const auto& i) {return i.second.size() > 1; }) };
	if (find != vn.end()) std::cout << "\nmehr als 2 Eckzaehne: " << find->first << "\n\n";

	// Aufgabe 3 (alle Vampirzahlen aus einem bestimmten Bereich)
	auto i{ 0 };
	for (const auto& num : vn) {
		std::cout << ++i << ". " << num.first << ": ";
		for (const auto& [left, right] : num.second) // C++ 20!
			std::cout << left << " x " << right << "   ";
		std::cout << "\n";
	}
}
                

Lösung von: Jens Kelm (@JKooP)

# Ein bisschen angelehnt an die interessante Lösung in C++
def vampires():
  import math, itertools, bisect, collections
  def count_digits(num):
    ret = 10 * [0]
    while num:
      num, rem = divmod(num, 10)
      ret[rem] += 1
    return ret
  for factor_digit_len in itertools.count(1):
    results = collections.defaultdict(lambda: [])
    factor_range = range(10**(factor_digit_len-1)+1, 10**factor_digit_len) # 2 to 9, 11 to 99, 101 to 999, ...
    for left_factor in factor_range: # for example with 101 to 999, 101 cannot be smaller, because 100*999 will not have 6 digits
      # find the minimum right factor, so that the product has double the amount of the factor digits
      right_factor_start_index = bisect.bisect_left(factor_range, 2*factor_digit_len, key=lambda n: int(math.log10(left_factor*n))+1)
      if right_factor_start_index == len(factor_range):
        # there is no such right factor, so skip
        continue
      # the maximum right factor is left_factor, so we avoid checking duplicates (when the left and right factors are swapped)
      for right_factor in range(factor_range[right_factor_start_index], left_factor+1):
        if left_factor % 10 == right_factor % 10 == 0:
          continue
        product = left_factor * right_factor
        product_digits = count_digits(product)
        left_digits, right_digits = count_digits(left_factor), count_digits(right_factor)
        # product is permutation, if it has the same amount of each digit as the left_factor and right_factor added
        if all((p == s for p, s in zip(product_digits, (l+r for l, r in zip(left_digits, right_digits))))):
          if left_factor != right_factor:
            results[product].extend((left_factor, right_factor))
          else:
            results[product].append(left_factor)
    yield from sorted(results.items(), key=lambda x: x[0])

found_smallest = False
for i, (n, v) in enumerate(vampires(), start=1):
  vamp_str = f"{n} mit Eckzähnen {', '.join(map(str, v))}"
  print(f"{i}. Vampirzahl: {vamp_str}")
  if len(v) > 2 and not found_smallest:
    print(f"Kleinste Vampirzahl mit mehr als zwei Eckzähnen: {vamp_str}")
    found_smallest = True
  if i == 155: # 939658 with factors 986, 953
    # it takes 2.79 seconds to get the first 155 vampire numbers until 939658
    break
                

Lösung von: Name nicht veröffentlicht

Number.prototype.getDivisors = function() {
  let out = [], i;
  for (i = 1; i <= Math.ceil(this/2); i++)
    if (this % i == 0) out.push(i);
  return out;
}

Number.prototype.getLength = function() { return this.toString().length; }

function isPermutation(a, b) {
  return (
    a.toString().split('').sort().join('') ==
    b.toString().split('').sort().join('')
  );
}

function hasCommonDigits(long, short) {
  long = long.toString(); short = short.toString();
  for (let i = 0; i < short.length; i++)
    if (long.indexOf(short[i]) == -1) return false;
  return true;
}

/* /!\ FREILICH NUR ALS AKTUELLER STAND DER ARBEIT ZU VERSTEHEN /!\
   vor allem fehlt noch eine zuverlässige methode, um zahlen
   von vornherein auszuschließen. */
function vanHelsingTest(num) {
  let out = {
    coffin: num,
    result: false,
    fangs: []
  }
  // ungerade anzahl von ziffern? vade retro!
  if (num.getLength() % 2 != 0) return out;
  // teiler: nur halbe länge und mögliche ziffern
  let divs = num.getDivisors().filter(function(x) {
    return (x.getLength() == num.getLength() / 2) && (hasCommonDigits(num, x));
  });
  // teiler aneinanderhalten
  for (let i = 0; i < divs.length; i++)
    for (let j = i+1; j < divs.length; j++) {
      if (
        divs[i] * divs[j] == num &&
        isPermutation(num, '' + divs[i] + divs[j]) &&
        // beide divisoren dürfen nicht auf 0 enden
        !(divs[i] % 10 == 0 && divs[j] % 10 == 0)
      ) out.fangs.push([divs[i], divs[j]]);
    }
  // hat eckzähne = vampir!
  if (out.fangs.length != 0) out.result = true;
  return out;
}

// vampirzahl mit fängen ausgeben
function exposeToSunlightml(corpse) {
  let out = `<b>${corpse.coffin.toLocaleString()}</b> `;
  if (!corpse.result) out += 'ne estas vampira.';
  else for (let i of corpse.fangs)
    out += ` = ${i.join(' × ')}`;
  return out;
}

/********\
|* MAIN *|
\********/

// genereller speedtest
let tests = [
  12,             //        1 ms
  1234,           //        2 ms
  123456,         //       15 ms
  12345678,       //    1.218 ms
  1234567890      //  117.516 ms
  //123456789012  //  ab hier wird's ein geduldspiel
];
for (let i of tests) {
  console.time();
  console.log( vanHelsingTest(i) );
  console.timeEnd();
}

// zur aufgabe;
let theCount = 1000,
    found15 = false, belaLugosisDead = false,
    hallOfHeads = [];

console.time();
for (theCount; !(found15 && belaLugosisDead); theCount++) {
  // keine zahl mit ungerader anzahl an ziffern!
  if (theCount.getLength() % 2 != 0) theCount *= 10;
  let suspect = vanHelsingTest(theCount);
  if (suspect.result) hallOfHeads.push(suspect);
  if (hallOfHeads.length == 15) found15 = true;
  if (suspect.fangs.length > 1) belaLugosisDead = true;
}
console.timeEnd(); // in etwa die zeit um ein ei zu kochen :(
                   // »Hmm.. lecker gekochtes ei!« (DeNiro, »Angel Heart«)

// ausgabe
for (theCount = 0; theCount < hallOfHeads.length; theCount++)
  switch (true) {
    case (theCount == 5-1):
    case (theCount == 10-1):
    case (theCount == 15-1):
      document.write(`
        <p>La ${theCount+1}<sup>a</sup> vampirnombro:</br>
        ${exposeToSunlightml(hallOfHeads[theCount])}</p>
      `);
    break;
    case (hallOfHeads[theCount].fangs.length > 1):
      document.write(`
        <p>L’unua vampirnombro kun pli ol 2 ?irdentoj:</br>
        ${exposeToSunlightml(hallOfHeads[theCount])}</p>
      `);
  }

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// NET 7.x | C# 11.x | VS-2022
static SortedDictionary<uint, List<(uint, uint)>> GetVampireNumbers(uint max) {
    var out_ = new SortedDictionary<uint, List<(uint, uint)>>();
    max = (uint)Math.Sqrt(max);
    for (uint left = 10; left < max; ++left) {
        for (uint right = left + 1; right < max; ++right) {
            if ((int)Math.Log10(left) != (int)Math.Log10(right) || left % 10 == 0 && right % 10 == 0) continue;
            var pro = left * right;
            if (((int)Math.Log10(pro) + 1) % 2 != 0) continue;
            if (pro.ToString().OrderBy(x => x).SequenceEqual((left.ToString() + right.ToString()).OrderBy(x => x)))
                if (out_.TryGetValue(pro, out List<(uint, uint)>? value))
                    value.Add((left, right));
                else
                    out_.Add(pro, new List<(uint, uint)> { (left, right) });
        }
    }
    return out_;
}
var vn = GetVampireNumbers(1_000_000); // 206 ms

// Aufgabe 1 (bestimmte Vampirzahlen)
new List<uint> { 5, 10, 15 }.ForEach(x => Console.WriteLine($"{x}. Vampirzahl: {vn.Skip((int)x - 1).FirstOrDefault().Key}"));

// Aufgabe 2 (erste mit mehr als 2 Eckzähnen)
Console.WriteLine($"\nmehr als 2 Eckzähne: {vn.Where(x => x.Value.Count > 1).FirstOrDefault().Key}\n");

// Aufgabe 3 (alle aus einem bestimmten Bereich)
var i = 0;
foreach (var num in vn)
{
    Console.Write($"{++i}. {num.Key}: ");
    foreach (var (left, right) in num.Value)
        Console.Write($"{left} x {right}    ");
    Console.WriteLine();
}
                

Lösung von: Jens Kelm (@JKooP)