mirror of
https://bitbucket.org/Mattrixwv/projecteulerlua.git
synced 2025-12-06 09:33:58 -05:00
115 lines
3.6 KiB
Lua
115 lines
3.6 KiB
Lua
--ProjectEuler/lua/Problem28.lua
|
|
--Matthew Ellison
|
|
-- Created: 09-15-19
|
|
--Modified: 06-19-20
|
|
--What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed by starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral
|
|
--All of my requires, unless otherwise listed, can be found at https://bitbucket.org/Mattrixwv/luaClasses
|
|
--[[
|
|
Copyright (C) 2020 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"
|
|
|
|
|
|
--Setup the variables
|
|
local timer = Stopwatch:create();
|
|
local grid = {};
|
|
local finalLocation = false; --A flag to indicate if the final location to be filled has been reached
|
|
local currentNum = 1; --Set the number that is going to be put at each location
|
|
--Make a 1001x1001 grid full of 0's
|
|
for row = 0, 1001 do
|
|
grid[row] = {};
|
|
for col = 0, 1001 do
|
|
grid[row][col] = 0;
|
|
end
|
|
end
|
|
|
|
--Start the timer
|
|
timer:start();
|
|
|
|
--Start with the middle location and set it correctly and advance the tracker to the next number
|
|
local xLocation = 500;
|
|
local yLocation = 500;
|
|
grid[yLocation][xLocation] = currentNum;
|
|
currentNum = currentNum + 1;
|
|
--Move right the first time
|
|
xLocation = xLocation + 1;
|
|
--Move in a circular pattern until you reach the final location
|
|
while(not finalLocation) do
|
|
--Move down until you reach a blank location on the left
|
|
while(grid[yLocation][xLocation - 1] ~= 0) do
|
|
grid[yLocation][xLocation] = currentNum;
|
|
currentNum = currentNum + 1;
|
|
yLocation = yLocation + 1;
|
|
end
|
|
--Move left until you reach a blank location above
|
|
while(grid[yLocation - 1][xLocation] ~= 0) do
|
|
grid[yLocation][xLocation] = currentNum;
|
|
currentNum = currentNum + 1;
|
|
xLocation = xLocation - 1;
|
|
end
|
|
|
|
--Move up until you reach a blank location to the right
|
|
while(grid[yLocation][xLocation + 1] ~= 0) do
|
|
grid[yLocation][xLocation] = currentNum;
|
|
currentNum = currentNum + 1;
|
|
yLocation = yLocation - 1;
|
|
end
|
|
|
|
--Move right until you reach a blank location below
|
|
while(grid[yLocation + 1][xLocation] ~= 0) do
|
|
grid[yLocation][xLocation] = currentNum;
|
|
currentNum = currentNum + 1;
|
|
xLocation = xLocation + 1;
|
|
--Check if you are at the final location and break the loop if you are
|
|
if(xLocation == #grid) then
|
|
finalLocation = true;
|
|
break;
|
|
end
|
|
end
|
|
end
|
|
|
|
--Get the sum of the diagonals
|
|
local leftSide = 0;
|
|
local rightSide = #grid - 1;
|
|
local row = 0;
|
|
local sumOfDiag = 0;
|
|
while(row < #grid) do
|
|
--This ensures the middle location is only counted once
|
|
if(leftSide == rightSide) then
|
|
sumOfDiag = sumOfDiag + grid[row][leftSide];
|
|
else
|
|
sumOfDiag = sumOfDiag + grid[row][leftSide];
|
|
sumOfDiag = sumOfDiag + grid[row][rightSide];
|
|
end
|
|
row = row + 1;
|
|
leftSide = leftSide + 1;
|
|
rightSide = rightSide - 1;
|
|
end
|
|
|
|
--Stop the timer
|
|
timer:stop();
|
|
|
|
--Print the results
|
|
io.write("The sum of the diagonals in the given grid is " .. sumOfDiag .. '\n');
|
|
io.write("It took " .. timer:getString() .. " to run this algorithm\n");
|
|
|
|
--[[ Results:
|
|
The sum of the diagonals in the given grid is 669171001
|
|
It took 81.680 milliseconds to run this algorithm
|
|
]]
|