Project Euler Q20

here's the question.

n! means n (n 1) ... 3 2 1

Find the sum of the digits in the number 100!

And my version of Lua for window, kinda hard to add more library to it, so I can't just get the BigInt and do the simple coding.

I google the amount of 100! instead and do the lazy man way.

here's the code,

---------------------------------------

z=0

a = "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000"
length = string.len(a)
for i=1, length do
z=z+a:byte(i)-("0"):byte(1)
end
print(z)

Project Euler Q19

Question 19, here's the Problem

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

nothing much I'll just brute force, counting from first day to the last.
first create a function for get the how many day in that month.
then just create 3 for loops eh? lol
_________________________here's the code__________
function getMonthDate(month,year)
if (month == 2) then
if (year % 4) == 0 and year ~= 1900 then
return 29
else
return 28
end
elseif (month == 1) or
(month == 3) or
(month == 5) or
(month == 7) or
(month == 8) or
(month == 10) or
(month == 12) then
return 31
else
return 30
end
end
function getDay(day)
if day == 1 then
return "sunday"
elseif day == 2 then
return "monday"
elseif day == 3 then
return "tuesday"
elseif day == 4 then
return "wednesday"
elseif day == 5 then
return "thursday"
elseif day == 6 then
return "friday"
elseif day == 7 then
return "saturday"
else
return "error"
end
end


d = { num = 1, day = 2, month = 1, year = 1900}
match = 0

for i = d.year, 2000 do
for j = d.month, 12 do
--print("_____________________________")
--print("the month is "..d.month)
--print ("this month has "..getMonthDate(d.month, d.year).." days")
for k = d.num, getMonthDate(d.month, d.year) do
--print("the day is "..d.num.." on "..getDay(d.day))
if (d.num == 1) and (d.day == 1) and (d.year > 1900) then
match = match + 1
end
if d.day == 7 then d.day = 0 end
if d.num == getMonthDate(d.month, d.year) then d.num = 0 end
d.day = d.day + 1
d.num = d.num + 1

end
if d.month == 12 then d.month = 0 end
d.month = d.month + 1
end
d.year = d.year + 1
end

print (match)

Project Euler Q18, Q67

here's the question

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

After read the problem, u might wanna try brute force the problem right? if wasn't for that note on the 100 lines problem.

So I do some research on the net and found some method that they already solve the problem.
I try to just read it and understand the solution then come back and write my own lua code.

the general idea of solving this kinda problem is.

1. assume that u already have the answer


2. work our way from bottom not top


3. say on the line just above the bottom line, each member of that line will have only one possible maximum choice, say item number 1 on line 99 will look at item number 1 and 2 on line 100 and choose the maximum out come,


4. use math.max(line[100]item[1], line[100]item[2]) to pick the greater number.


5. combine the greater number with the item on the above line we'll have something like
   1. line[99][item[1]] = line[99][item[1] + math.max(line[100]item[1],line[100][item[2])
      
6. now just create two for loop to get through the line and the item
7. this will 'flaten' the triangle until it has only posible maximum result.

the code will look like this.
-----
triangle = {
{75},
{95, 64},
{17, 47, 82},
{18, 35, 87, 10},
{20, 04, 82, 47, 65},
{19, 01, 23, 75, 03, 34},
{88, 02, 77, 73, 07, 63, 67},
{99, 65, 04, 28, 06, 16, 70, 92},
{41, 41, 26, 56, 83, 40, 80, 70, 33},
{41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
{53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
{70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
{91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
{63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
{04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23}
}

local myMax = math.max

for i = #triangle, 2, -1 do
for j = 1, #triangle[i-1] do
triangle[i-1][j] = triangle[i-1][j] + (myMax(triangle[i][j],triangle[i][j+1]))
end
end

print (triangle[1][1])
-----

on Question 67 u just replace the triangle data with the new data...
which I just type it in :P with laziness to find new readIn method

Introduction

Well, As a game designer I think it'll be beneficial if I know some programming,
I did take some courses on C++ and java long time ago when I was in Master School.
Over the years it almost all forgotten, even though I wrote some of my games myself on actionscript.

Sooo I found this ProjectEuler.net, where I think I will test my skill one question per day.
just for fun. I use Lua as my weapon of choice... well if u play WoW u might wanna write ur own mod one day, so it's not bad to practice on it eh? :P

ok let us begin.