Front page | perl.golf |
Postings from August 2002
> Could someone annotate some of the various working solutions,
> emphasizing how they work around the problem with large numbers?
>
> I was able to make solutions that worked for n! where n < 25.
> But, at 25! the numbers got to large. I tried regex'ing the last
> zeroes, without success. I was still loosing digits.
You need to regex last zeroes AND remove extra numbers in the
beginning keeping only last 6 (or so) numbers.
> What does $`%9e9 do?
9e9 == 9000000000 and 1e6 == 1000000
$` %9e9 gives the remainder when variable $` is divided with 9e9,
which in effect returns only last 9 (or so) digits of $`
$`%1e6 is better example as it returns exactly last 6 digits of $`.
This is used to limit the size of the number so it can't grow too
big. 6 digits is enough precision for this problem and 9e9 only gives
better tiebreaker score.
$` is special 'pre-match' variable which contains string preceding
whatever was matched by the last successful pattern match.
I can annotate shortly my best solution:
#!perl -l
$_*=$z%9e9,/0*$/,$z=$`for++$z..pop;print$z%10
for++$z..pop
Initialize $z to 1, repeat for 1..pop with variable $_
$_*=$z%9e9
Remove all except last 9 (or so) digits from $z, and then multiply
with $_ saving result to $_
/0*$/
This matches zeroes at the end of $_, so everything except
the zeroes will be in special 'pre-match' variable $`
$z=$`
Copy $` to $z, to be ready for next iteration. This must be done
because print-command can't use $` variable as it's hidden inside for-
loop. (best factorial solution seemed to get over this)
print$z%10
And finally print the last digit
I can't resist mentioning my other solution which doesn't compute n!
at all, but just uses kind-of 3D lookup-table to find the result.
It's fast but unfortunately code is far too long :(
$z=pop;sub g{vec"\x10\xd7\xa9\x98b\xef",pop,2}
print$z<2||(1+g$z%25)*(1,3,2,4)[g 24-$z/25%25]*6*(1+g$z/625)%10,$/
Explanation would be somewhat longer, but if anyone wants I can write
it.
Has anyone else tried lookup instead of computing n!. I'd like to
know shortest possible solution for this sub-problem also.
--
Markus Laire 'malaire' <markus.laire@nic.fi>
Thread Previous
|
Thread Next