Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
class PseudoVamp {
public int num;
public boolean truevamp = false;
public int x;
public int y;
public int n1;
public int n2;
public int n3;
public int n4;
void breaknsort() {
n1 = num % 10;
n2 = num / 10 % 10;
n3 = num / 100 % 10;
n4 = num / 1000;
int tmp;
for (int i = 0; i < 4; i++) {
if (n1 > n2) {
tmp = n1;
n1 = n2;
n2 = tmp;
}
if (n2 > n3) {
tmp = n2;
n2 = n3;
n3 = tmp;
}
if (n3 > n4) {
tmp = n3;
n3 = n4;
n4 = tmp;
}
}
}
public PseudoVamp(int a, int b) {
x = a;
y = b;
num = x * y;
breaknsort();
}
}
public class Test {
static void checkvamp(PseudoVamp vamp) {
int x1 = vamp.x % 10;
int x2 = vamp.x / 10;
int y1 = vamp.y % 10;
int y2 = vamp.y / 10;
int tmp;
for (int i = 0; i < 4; i++) {
if (x1 > x2) {
tmp = x1;
x1 = x2;
x2 = tmp;
}
if (x2 > y1) {
tmp = x2;
x2 = y1;
y1 = tmp;
}
if (y1 > y2) {
tmp = y1;
y1 = y2;
y2 = tmp;
}
}
if (vamp.n1 == x1 && vamp.n2 == x2 && vamp.n3 == y1 && vamp.n4 == y2)
vamp.truevamp = true;
}
public static void main(String[] args) {
for (int i = 11; i < 100; i++) {
for (int j = 11; j < 100; j++) {
PseudoVamp v = new PseudoVamp(i, j);
if (v.num < 1000)
continue;
if (v.num > 9999)
return;
checkvamp(v);
if (v.truevamp)
System.out.println(v.x + " * " + v.y + " = " + v.num);
}
}
}
}
A vampire number has an even number of digits and is formed by multiplying a pair of numbers containing half the number of digits of the result. The digits are taken from the original number in any order. Pairs of trailing zeroes are not allowed. Examples include:
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
Write a program that finds all the 4-digit vampire numbers.
w/o using of arrays.
import Data.List (sort)
makeKey :: [Int] -> String
makeKey xs = sort $ concat $ map show xs
isVampirePair :: Int -> Int -> Bool
isVampirePair x y = (makeKey [x * y]) == (makeKey [x,y])
vampireNumbers :: Int -> Int -> [Int]
vampireNumbers from to = [x * y | x <- [from..to], y <- [from..to], isVampirePair x y]
main = do
putStrLn $ "Number of vampires numbers: " ++ (show $ length $ vampireNumbers 10 99)
У меня так же получилось, но опять же с нарушением условия - я использовал массивы/списки (в вашем случае даже больше, ведь строки в Haskell - это списки). А как без них? Есть идея использовать регулярки, но это читерство опять же. Думаю, задачу решить только с использованием чисел.
Да, преобразуя число в строку, а потом сравнивая 2 сортированных массива символов получается очень элегантное решение.
Но гораздо интересней работать только с числами, без массивов / списков. Попробуйте =)
Не "говнорешение" у меня укладывается в 28 строк.
Если есть какой-то интересный теоретико-числовой способ проверить одинаковый состав цифр в множителях и в произведении (или получать потенциальные "множители" из самого числа), поведайте нам, пожалуйста (я всю голову сломал). Если "w\o arrays" означает просто вычислять остатки от деления и сортировать цифры самостоятельно, меня такое решение не очень интересует.
умножения, целочисленные деления, вычеты... Прям как в школе про системы счисления...
уж не проще ли обойтись без математики, а обращаться с числами как со строками?
Думаю, что разобраться в нем можно. В реальном проекте я бы комментариев дописал... наверное 🙂 Во всяком случае переменные лучше вынести в начало процедуры и описать предназначение каждой (хотя я старался давать наиболее осмысленные имена). Тогда алгоритм будет виднее.
Видите ли, ваш код на Haskell неподготовленному человеку еще менее понятен. Хотя, конечно, я считаю такой код в функциональном стиле более выразительным, чем та императивная каша, что я написал.
На самом деле код в хаскеле я понял сразу, хотя хаскела я в жизни не видал ...
а вот JS вроде как и лучше дожен воспринимать, так наоборот нифига не понял каким образом оно решает поставленную задачу...
haskell не так труден, как кажется. Программирование на нём доставляет огромное удовольствие. Пленяет строгая типизация и минимальное кол-во строк, необходимое для решения задачи в сочетании с довольно высокой скоростью работы. И самое удивительное, что очень часто работает правило "Компилируется - значит, работает правильно".
Разобраться в нём можно, не спорю. Однако потребуется немало пунктов мозгосилы. Особо порадовала идея использовать числа как небольшие битовые карты =) От order можно избавиться, вычисляя порядки чисел внутри функции (если порядки разные, можно сразу возвращать false).
>(если порядки разные, можно сразу возвращать false)
С чего это? order - это число цифр в десятичной записи, которые нам нужно рассмотреть. Избавиться от него мы не можем.
К тому же, мы проверяем совпадение всех цифр в числе без учета их позиции, поэтому отсекать по принципу "разные порядки" мы не можем - если вы это имели в виду под "порядки разные".
>Особо порадовала идея использовать числа как небольшие битовые карты =)
Именно благодаря этому я смог уйти от массивов. Другого способа отмечать найденные совпадения я не придумал.
> Избавиться от него мы не можем.
Ещё как можем. Какой смысл сравнивать 12345 с 1234? Число цифр в десятичной записи у них разное, поэтому совпадать наборы цифр не могут априори. Вы и сами без труда сможете написать функцию определения числа десятичных знаков в записи числа:
function getOrder(base, number) {
var order = 0;
var product = 1;
do {
product *= base;
order += 1;
} while (product < number);
return order;
}
/* getOrder(10, 12345) == 5 */
> Именно благодаря этому я смог уйти от массивов
Спасибо, кэп )
Попробовал реализовать ваше решение в общем виде (с одним существенным ограничением: не отбрасываются случаи, когда у обоих множителей нули на конце), вот что получилось:
import Data.List (permutations)
strToTuple :: String -> (Integer, Integer)
strToTuple s = let n = (length s) `div` 2
a = read $ take n s
b = read $ drop n s
in (a, b)
strToCandidates :: [String] -> [(Integer, Integer)]
strToCandidates l = map strToTuple l
candidates :: Integer -> [(Integer, Integer)]
candidates n = if (even len)
then strToCandidates $ permutations str
else []
where str = show n
len = length str
hasVampirePair :: [(Integer, Integer)] -> Integer -> Bool
hasVampirePair l n = any (\p -> (fst p) * (snd p) == n) l
vampireNumbers :: Integer -> Integer -> [Integer]
vampireNumbers from to = [x| x <- [from..to], isVampireNumber x]
main = do
putStrLn $ "Vampire numbers: " ++ show (vampireNumbers 1000 9999)
Ответы выдаёт верные, но код работает очень медленно (скорее всего, его тормозит вычисление всевозможных перестановок цифр, которые у вас вычислены ручками, ибо замена Integer на Int ничего не изменила).
Исходный вариант решает задачу за 0.012 сек, этот - за 3.253 сек.
Решения задачи этим вариантом для размерности 6 я не дождался, исходный вариант считает задачу этой размерности 1 сек. Ваш вариант на java у меня отрабатывает за 0.035 сек.
у меня не было цели "не использовать массивы/списки", поскольку без них можно обойтись только для заранее известной размерности (вы очень наглядно продемонстрировали это решение). Мне было интересно сравнить производительность и простоту реализации разных решений. К моему удивлению, самый простой первый алгоритм в три строчки (объявления типов опциональны и нужны для людей /оптимизации, haskell вывел бы их самостоятельно) работает быстрее всего. Опять даёт о себе знать волшебное правило "сначала простой и понятный код, потом (возможно) - оптимизация".
так что, новая формула для гетов, товарищи.
Уже не прокатит, 6880 - максимальное.
Вывод:
Но гораздо интересней работать только с числами, без массивов / списков. Попробуйте =)
Не "говнорешение" у меня укладывается в 28 строк.
Но "самостоятельность" все равно в таком случае никуда не убрать:
это решение конкретной задачи. Для маштабирования нужны списки полюбому.
Вот математический способ проверить, совпадают ли все цифры в двух числах (JS):
Вот тесты:
уж не проще ли обойтись без математики, а обращаться с числами как со строками?
Видите ли, ваш код на Haskell неподготовленному человеку еще менее понятен. Хотя, конечно, я считаю такой код в функциональном стиле более выразительным, чем та императивная каша, что я написал.
а вот JS вроде как и лучше дожен воспринимать, так наоборот нифига не понял каким образом оно решает поставленную задачу...
С чего это? order - это число цифр в десятичной записи, которые нам нужно рассмотреть. Избавиться от него мы не можем.
К тому же, мы проверяем совпадение всех цифр в числе без учета их позиции, поэтому отсекать по принципу "разные порядки" мы не можем - если вы это имели в виду под "порядки разные".
>Особо порадовала идея использовать числа как небольшие битовые карты =)
Именно благодаря этому я смог уйти от массивов. Другого способа отмечать найденные совпадения я не придумал.
how much watch?
Ещё как можем. Какой смысл сравнивать 12345 с 1234? Число цифр в десятичной записи у них разное, поэтому совпадать наборы цифр не могут априори. Вы и сами без труда сможете написать функцию определения числа десятичных знаков в записи числа:
> Именно благодаря этому я смог уйти от массивов
Спасибо, кэп )
Ответы выдаёт верные, но код работает очень медленно (скорее всего, его тормозит вычисление всевозможных перестановок цифр, которые у вас вычислены ручками, ибо замена Integer на Int ничего не изменила).
Исходный вариант решает задачу за 0.012 сек, этот - за 3.253 сек.
Решения задачи этим вариантом для размерности 6 я не дождался, исходный вариант считает задачу этой размерности 1 сек. Ваш вариант на java у меня отрабатывает за 0.035 сек.
p.s. неделя бенчмарков на ГК
week PseudoTroll {}
}
Я конечно плохо незнаю хаскель, но тут явное читерство 😛
общего решения, мне кажется, простой арифметикой не добиться