mirror of
https://bitbucket.org/Mattrixwv/projecteulerlua.git
synced 2025-12-06 09:33:58 -05:00
105 lines
3.6 KiB
Lua
105 lines
3.6 KiB
Lua
--ProjectEuler/lua/Problem33.lua
|
|
-- Created: 02-07-21
|
|
--Modified: 02-07-21
|
|
--[[
|
|
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s
|
|
We shall consider fractions like, 30/50 = 3/5, to be trivial examples
|
|
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator
|
|
If the product of these four fractions is given in its lowest common terms, find the value of the denominator
|
|
]]
|
|
--All of my requires, unless otherwise listed, can be found at https://bitbucket.org/Mattrixwv/luaClasses
|
|
--[[
|
|
Copyright (C) 2021 Matthew Ellison
|
|
|
|
This program is free software: you can redistribute it and/or modify
|
|
it under the terms of the GNU Lesser General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU Lesser General Public License for more details.
|
|
|
|
You should have received a copy of the GNU Lesser General Public License
|
|
along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
]]
|
|
|
|
|
|
require "Stopwatch"
|
|
require "Algorithms"
|
|
|
|
|
|
--Setup the variables
|
|
local timer = Stopwatch:create();
|
|
local minNumerator = 10;
|
|
local maxNumerator = 98;
|
|
local minDenominator = 11;
|
|
local maxDenominator = 99;
|
|
local numerators = {};
|
|
local denominators = {};
|
|
local prodDenominator = 1;
|
|
|
|
--Start the timer
|
|
timer:start();
|
|
|
|
--Search every possible numerator/denominator pair
|
|
for denominator = minDenominator, maxDenominator do
|
|
for numerator = minNumerator, (denominator - 1) do
|
|
local num = tostring(numerator)
|
|
local denom = tostring(denominator)
|
|
local tempNum = 0;
|
|
local tempDenom = 1;
|
|
|
|
--Check that this isn't a trivial example
|
|
if((string.sub(num, 2, 2) == '0') and (string.sub(denom, 2, 2) == '0')) then
|
|
goto continue;
|
|
--Remove the offending digits if they exist
|
|
elseif(string.sub(num, 1, 1) == string.sub(denom, 1, 1)) then
|
|
tempNum = tonumber(string.sub(num, 2, 2));
|
|
tempDenom = tonumber(string.sub(denom, 2, 2));
|
|
elseif(string.sub(num, 1, 1) == string.sub(denom, 2, 2)) then
|
|
tempNum = tonumber(string.sub(num, 2, 2));
|
|
tempDenom = tonumber(string.sub(denom, 1, 1));
|
|
elseif(string.sub(num, 2, 2) == string.sub(denom, 1, 1)) then
|
|
tempNum = tonumber(string.sub(num, 1, 1));
|
|
tempDenom = tonumber(string.sub(denom, 2, 2));
|
|
elseif(string.sub(num, 2, 2) == string.sub(denom, 2, 2)) then
|
|
tempNum = tonumber(string.sub(num, 1, 1));
|
|
tempDenom = tonumber(string.sub(denom, 1, 1));
|
|
end
|
|
if(tempDenom == 0) then
|
|
goto continue;
|
|
end
|
|
|
|
--Test if the new fraction is the same as the old one
|
|
if((tempNum / tempDenom) == (numerator / denominator)) then
|
|
table.insert(numerators, numerator);
|
|
table.insert(denominators, denominator);
|
|
end
|
|
|
|
::continue::
|
|
end
|
|
end
|
|
|
|
--Get the product of the numbers
|
|
local numProd = getProd(numerators);
|
|
local denomProd = getProd(denominators);
|
|
--Get the gcd to reduce to lowest terms
|
|
local gcd = gcd(numProd, denomProd);
|
|
--Save the denominator
|
|
prodDenominator = denomProd / gcd;
|
|
|
|
--Stop the timer
|
|
timer:stop();
|
|
|
|
--Print the results
|
|
io.write("The denominator of the product is " .. prodDenominator .. '\n');
|
|
io.write("It took " .. timer:getString() .. " to run this algorithm\n");
|
|
|
|
|
|
--[[ Results:
|
|
The denominator of the product is 100.0
|
|
It took 4.000 milliseconds to run this algorithm
|
|
]]
|