Пятничная головоломка

← →
sniknik © (2015-08-20 15:53) [40]

> как-то коряво из строки преобразовывает...
понял, оно его "наоборот" вставляет, не как число, а как хз знает что.
1234 и 12345 похожи, а 2345 и 12345 нет.

странно, может в этом и есть логика, но выглядит как подстава.

← →
SergP © (2015-08-20 15:56) [41]

Ладно. Тогда вот мой новый вариант:

function NearSergP_2(Phone1, Phone2: Int64): Boolean; const Pow10: array[1..19] of Int64 = ( 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000 ); var Diff,k: Int64; a,b,c,d:byte; begin a:=0; c:=20; while c-a>1 do begin b:=(a+c) shr 1; if (phone1 mod Pow10[b]) = (phone2 mod Pow10[b]) then a:=b else c:=b; end; a:=0; b:=20; while b-a>1 do begin d:=(a+b) shr 1; if (phone1 div Pow10[d]) = (phone2 div Pow10[d]) then b:=d else a:=d; end; result:=c-a=1; end;

Можно конечно ввести доп. переменные чтобы одно и то же значение из массива 2 раза не дергать, но не знаю, стоит ли?

← →
sniknik © (2015-08-20 15:57) [42]

+
TBcd.Precision разные, т.е. "внутри себя" оно это число правильно понимает, а вот как массив байт/полубайт не работает. у Int64 смещения одинаковые для любого значения.

← →
SergP © (2015-08-20 15:59) [43]

> SergP © (20.08.15 15:56) [41]
>
> Ладно. Тогда вот мой новый вариант:

Хотя он вроде и работает, но мне что-то не нравится. Буду думать еще.

← →
DayGaykin © (2015-08-20 15:59) [44]

> sniknik © (20.08.15 15:43) [39]

В любом случае это будет очень медленно. Преобразование в такой формат подразумевает операцию div и mod для каждого десятичного знака.

← →
DayGaykin © (2015-08-20 16:00) [45]

> SergP © (20.08.15 15:59) [43]

Мне тоже хочется избавиться от "плавающих точек".

← →
Sha © (2015-08-20 16:03) [46]

> SergP © (20.08.15 15:56) [41]
> Ладно. Тогда вот мой новый вариант:

А старый выбывает?

> Можно конечно ввести доп. переменные
> чтобы одно и то же значение из массива 2 раза не дергать,
> но не знаю, стоит ли?

Не стоит. Только хуже будет,
т.к. все равно переменная типа int64 всегда в памяти лежит.

← →
DayGaykin © (2015-08-20 16:03) [47]

> Хотя он вроде и работает, но мне что-то не нравится.

Добавил в тест телефоны: 110, 103 - теперь не проходит :)

← →
DayGaykin © (2015-08-20 16:06) [48]

Ладно, я своей работой позанимаюсь:) Удачи вам в поиске решения!

← →
SergP © (2015-08-20 16:08) [49]

>
> А старый выбывает?

Старый не проходит тест.

> DayGaykin © (20.08.15 15:30) [36]

← →
SergP © (2015-08-20 16:12) [50]

> SergP © (20.08.15 15:56) [41]
>
> Ладно. Тогда вот мой новый вариант:

будем считать его предварительным, так как там по меньшей мере уже видна неоптимальность: во втором цикле явно возможны лишние итерации.

← →
SergP © (2015-08-20 16:15) [51]

Ну и
Diff,k: Int64;
там тоже убрать нужно

← →
DayGaykin © (2015-08-20 16:55) [52]

Я, пожалуй, остановлюсь на варианте в лоб:
function NearDayGaykin3(const Phone1, Phone2: Int64): Boolean; var S1, S2: String; I, M1, M2: Integer; Dif: boolean; begin if Phone1 = Phone2 then Result := False else begin S1 := IntToStr(Phone1); S2 := IntToStr(Phone2); M1 := Length(S1); M2 := Length(S2); if M1 > M2 then begin M1 := M1 xor M2; M2 := M1 xor M2; M1 := M1 xor M2; end; if M2 - M1 > 1 then Result := False else begin Dif := M1 <> M2; for I := 0 to M1-1 do if S1[M1 - I] <> S2[M2 - I] then if Dif then begin Result := False; Exit; end else Dif := True; Result := True; end; end; end;
За счет необычной реализации функции IntToStr в моем XE5, работает быстрее чем вариант SergP

← →
Sha © (2015-08-20 17:32) [53]

> DayGaykin © (20.08.15 16:55) [52]

Насколько я понял, ты сравниваешь телефоны как строки,
выравнивая их по левому краю.

Наверное, для того, чтобы все решали одну и ту же задачу
и чтобы решение через строки не получало дополнительных преимуществ,
стоит добавить еще одно условие. А именно, будем считать,
что разряды при сравнении выравниваются по правому краю,
или, что то же самое, все телефоны имеют длину 19.

← →
DayGaykin © (2015-08-20 17:57) [54]

> Sha © (20.08.15 17:32) [53]

По правому и сравниваю. Все тесты что я сделал - проходятся.

← →
SergP © (2015-08-20 18:48) [55]

Вроде чуть оптимизировал:

function NearSergP_2(Phone1, Phone2: Int64): Boolean; const Pow10: array[1..19] of Int64 = ( 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000 ); var a,b,c:byte; // хз что лучше byte или integer begin a:=0; c:=20; while c-a>1 do begin b:=(a+c) shr 1; if phone1 mod Pow10[b] = phone2 mod Pow10[b] then a:=b else c:=b; end; result:=(c<20) and (phone1 div Pow10[c] = phone2 div Pow10[c]); end;

← →
Sha © (2015-08-20 18:57) [56]

NearDayGaykin52 failed 0
99
9

NearSergP55 failed 0
9223372036854775807
8223372036854775807

← →
SergP © (2015-08-20 19:00) [57]

Вобщем в процессе вычисления значения функции происходит от 4 до 5 итераций в цикле... Т.е. mod в итоге максимум используется 10 раз, и еще div используется 2 раза

Пока мыслей нет как сделать лучше.

← →
DayGaykin © (2015-08-20 19:01) [58]

> Sha © (20.08.15 18:57) [56]
> NearDayGaykin52 failed 0
> 99
> 9

9 и 99 отличаются одной цифрой. Ожидаемый ответ True. Ответ функции True. Что не так?

← →
SergP © (2015-08-20 19:03) [59]

> Sha © (20.08.15 18:57) [56]
>
> NearDayGaykin52 failed 0
> 99
> 9
>
> NearSergP55 failed 0
> 9223372036854775807
> 8223372036854775807

хм... да, с 19-разрядными числами, где отличается старший разряд действительно проблемы...

← →
Sha © (2015-08-20 19:06) [60]

> DayGaykin © (20.08.15 19:01) [58]

Возможно, ошибка в валидаторе, будем искать.

← →
SergP © (2015-08-20 19:15) [61]

function NearSergP_2(Phone1, Phone2: UInt64): Boolean; const Pow10: array[1..19] of UInt64 = ( 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000 ); var a,b,c:byte; begin a:=0; c:=20; while c-a>1 do begin b:=(a+c) shr 1; if phone1 mod Pow10[b] = phone2 mod Pow10[b] then a:=b else c:=b; end; if c=20 then result:=Phone1<>Phone2 else result:=(phone1 div Pow10[c] = phone2 div Pow10[c]); end;

← →
Sha © (2015-08-20 19:18) [62]

> DayGaykin © (20.08.15 19:01) [58]
> 9 и 99 отличаются одной цифрой. Ожидаемый ответ True.
> Ответ функции True. Что не так?

Сфэйлилось не на 9 и 99, а на 99 и 9. Там ваще вылезает за границу строки.

← →
Sha © (2015-08-20 19:39) [63]

> SergP © (20.08.15 19:15) [61]

По условию тип на входе должен быть int64.
Внутри функции можно делать что угодно.

Что будем делать? Изменим условия? Тогда как?
Разрешим 20-значные номера или только 19?
В любом случае в D7 его штатными средствами не вывести на экран,
поэтому, на мой взгляд, лучше не менять условия.

← →
Sha © (2015-08-20 19:43) [64]

> sniknik © (20.08.15 13:53) [14]

NearSniknik14 failed 1
9
9

← →
SergP © (2015-08-20 20:14) [65]

> Sha © (20.08.15 19:39) [63]
>
> > SergP © (20.08.15 19:15) [61]
>
> По условию тип на входе должен быть int64.

это я хотел в массив впихнуть 10 000 000 000 000 000 000
но потом, когда вернул все назад, забыл и тип назад поменять.
Прошу прощения, должно быть так:

function NearSergP_2(Phone1, Phone2: Int64): Boolean; const Pow10: array[1..19] of Int64 = ( 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000 ); var a,b,c:byte; begin a:=0; c:=20; while c-a>1 do begin b:=(a+c) shr 1; if phone1 mod Pow10[b] = phone2 mod Pow10[b] then a:=b else c:=b; end; if c=20 then result:=Phone1<>Phone2 else result:=(phone1 div Pow10[c] = phone2 div Pow10[c]); end;

← →
Sha © (2015-08-20 20:27) [66]

>Sha © (20.08.15 19:43) [64]
>NearSniknik14 failed 1
>9
>9

Сорри. Не то скопировал.

NearSniknik14 failed 0
999999999999999
989999999999999

← →
Mystic © (2015-08-20 20:39) [67]

Лучше хранить номера телефонов в bcd формате. Тогда просто xor, получить индекс самого левого бита, установленного в единиду, округлить по границе 4, сдвинуть и посмотреть, результат больше 15 или нет.

> Mystic © (20.08.15 20:39) [67]

Тогда бы не было задачи)

На самом деле нечто похожее было на практике.
Оптимизировалась похожая функция для целых чисел в интервале 0000..9999.
Правда тогда не удалось найти красивого решения.

Вроде как была такая ассемблерная команда? AAA или что-то в этом роде.

Хорошо, рассмотрим модуль разности. По сути это число вида d00..00, где d лежит в диапазоне 1-9, а число нулей от нуля до 18. Итого 19*9 вариантов, что уже неплохо.

Далее можно построить FSM, которому скармливать части числа (например по байтам). На выходе будем иметь удолетворяет/не удовлетворяет. Не хочешь строить FSM сам - перевели в base64 и натправи pcre, где просто перечисли все 19*9 альтернатив.

Также можно реализовать некоторую hash-функцию, которая бы для указанных альтернатив выдавала уникальный номер, а потом по таблице проверяли бы, совпало или нет. Например, просится нечто вроде value * magic >> (64-bit_count). Потом просто написать подбор оптимальных magic и count.

> Mystic © (20.08.15 21:19) [69]

сегодня так и сделал, самому странно, что раньше ходил вокруг да около:
function NearSha(p1, p2: pint64): boolean; var d: Int64Rec; begin int64(d):=p2^-p1^; if d.Hi or d.Lo<>0 then begin; //d<>0 if d.Hi and $80000000<>0 then begin; //d<0 p2:=p1; //p2->max int64(d):=-int64(d); //d:=abs(d) end; p1:=@MagicArray[int64(d) mod MagicMod]; //адрес разности в хеш-таблице if p1^=int64(d) then begin; //если нашли круглую разность в таблице //берем младшие разряды большего числа или все число, если различие в старшем разряде inc(p1); //p1->MagicArray[].Power if pInt64Rec(p1).Hi and $80000000=0 then begin; int64(d):=p2^ mod p1^; p2:=@d; end; //и сравниваем с круглой разностью dec(p1); //p1->MagicArray[].Delta if p1^<=p2^ then begin; Result:=true; exit; end; end; end; Result:=false; end;

Хеш-таблица заполняется так:
type PMagicRecord= ^TMagicRecord; TMagicRecord= record Delta: int64; Power: int64; end; const MagicMod= 207; var MagicArray: array[0..MagicMod-1] of TMagicRecord; procedure FillMagicArray; var i, j, n: integer; Power: int64; begin; for i:=0 to MagicMod-1 do begin; MagicArray[i].Delta:=-1; MagicArray[i].Power:=-1; end; Power:=1; for i:=1 to 19 do begin; for j:=1 to 9 do begin; n:=j*Power mod MagicMod; MagicArray[n].Delta:=Power*j; if i<19 then MagicArray[n].Power:=Power*10 else MagicArray[n].Power:=-1; end; Power:=Power*10; end; end;

А как-то так низя?

uint64_t unique[19*9]; void init_unique() { int i = 0; uint64_t f = 1; for (int p=0; p<19; ++p) { for (uint64_t d=1; d<10; ++d) { unique[i++] = d*f; } f *= 10; } } void fill_magic(uint64_t mod) { for (int i=0; i<19*9; ++i) { uint64_t index = unique[i] % mod; magic[index] = unique[i]; } } int is_similar(uint64_t a, uint64_t b) { uint64_t diff = a>b ? a-b : b-a; uint64_t magic_value = magic[diff % mod]; if (magic_value == 0) { // ASM conditional MOV diff = 0; } return diff == magic_value; }

> Mystic © (20.08.15 22:23) [73]

Так не получится, одной этой проверки мало, например, для чисел 19 и 20.
Нужна вторая проверка, поэтому у меня в хеш-таблице 2 значения.

Удалось избавиться от одного деления, стало заметно быстрее:
const
MagicMod= 207;
MagicInv= -356458822680377809; //=MagicMod^-1
MagicShift= 56;
MagicLen= 1 shl (64-MagicShift);

var
MagicArray2: array[0..MagicLen-1] of TMagicRecord;

procedure FillMagicArray2; var i, j, n: integer; Power: int64; begin; for i:=0 to MagicLen-1 do begin; MagicArray2[i].Delta:=-1; MagicArray2[i].Power:=-1; end; Power:=1; for i:=1 to 19 do begin; for j:=1 to 9 do begin; n:=j*Power*MagicInv shr MagicShift; MagicArray2[n].Delta:=Power*j; if i<19 then MagicArray2[n].Power:=Power*10 else MagicArray2[n].Power:=-1; end; Power:=Power*10; end; end; function NearSha2(p1, p2: pint64): boolean; var d: Int64Rec; begin int64(d):=p2^-p1^; if d.Hi and $80000000<>0 then begin; //d<0 p2:=p1; //p2->max int64(d):=-int64(d); //d:=abs(d) end; p1:=@MagicArray2[int64(d) * MagicInv shr MagicShift]; //адрес разности в хеш-таблице if p1^=int64(d) then begin; //если нашли круглую разность в таблице //берем младшие разряды большего числа или все число, если различие в старшем разряде inc(p1); //p1->MagicArray[].Power if pInt64Rec(p1).Hi and $80000000=0 then begin; int64(d):=p2^ mod p1^; p2:=@d; end; //и сравниваем с круглой разностью dec(p1); //p1->MagicArray[].Delta if p1^<=p2^ then begin; Result:=true; exit; end; end; Result:=false; end;

> P.S. Некоторое время назад я уже решал эту задачу,
> но сейчас знаю более красивое решение, так что тоже поучаствую
> в конкурсе )

Интерестно тогда, а этот вариант был какой?

> SergP © (21.08.15 12:14) [76]

Первоначально задачу сформулировал один англоговорящий товарищ на форуме EMB.

Т.к. ему требовалось решение для четырехзначных чисел,
то тогда оказалось достаточно какого-то (сейчас точно не помню)
решения примерно из середины этой заметки:
http://guildalfa.ru/alsha/node/16

Заметку я написал уже потом, после спокойного обдумывания задачи.
Выше Mystic © (20.08.15 21:19) [69] совершенно правильно сказал,
что сюда просится хеш. И я его использовал там в последних решениях.

Но есть проблема с подбором множителя. Вместо того, чтобы еще немного
подумать, я тупо запускал перебор. Хотя можно было бы догадаться,
что для уменьшения коллизий и уплотнения таблицы ее надо делать
через деление (или умножение на обратный делителю).

Вот, собственно, вчера, когда писал условие и решил это реализовать.
А пост Мистика застал меня на полпути). В итоге сейчас для 19-значных чисел размерность таблицы такая же, как там в заметке для 10-значных.

Четыре десятичных знака можно перевести в BCD сравнительно быстро, а дальше просто.
http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html

> Mystic © (21.08.15 16:59) [78]

Огромное спасибо ссылку на статью.

Будет повoд вернуться к IntToStr снова,
проверить, не протух ли уже мой старый задел)

Пятничная головоломка Найти похожие ветки