Page 10 of 13
Posted: Thu Aug 16, 2007 1:34 am
by michaeled314
Problem #15 I can't get is there a formula behind it?
Posted: Thu Aug 16, 2007 7:58 am
by pdwyer
I can think of a way to do it but with a 20x20 grid its taking FAR too long (think: "sun engulfs the earth" kind of time frame
)
0-0 to x-y add to either x or y (not both)
iterate or recurse out the combinations
2x2 grid
Lets Call "A" x=x+1
Lets Call "b" y=y+1
bbaa
aabb
abab
baba
abba
baab
0,0 to 3,3
aaabbb
aabbba
abbbaa
bbbaaa
bbaaab
aaabbb
aabbba
...
enum all the cobinations
Thinking binary 1 & 0 instead of a and b:
So, a 20x20 grid would be the same as (bare with me on this) a set of all 2^40 where the number that has 20 1's and 20 0s (exactly) but enuming out 1,099,511,627,776 iterations and counting the bits and adding up the matching ones is taking too long.
There might be a pattern though.
Here are 2 sides, 3,4,5,6,7
6
20
70
252
924
3432
There must be a pattern here that generates a shortcut
The code to generate this (which is slow in debug mode but still won't handle 40bits otherwise) looks like this:
Code: Select all
DisableDebugger
test.s = ""
count.l = 0
i.q = 0
top.q = Pow(2,14)
While i.q < top
test = RSet(Bin(i),14,"0")
If CountString(test, "0") = 7 And CountString(test, "1") = 7
count = count + 1
EnableDebugger
Debug test
DisableDebugger
EndIf
i = i+1
Wend
EnableDebugger
Debug count
I remember some code I saw once that enums number strings out, so if you have "123" (or "abc" etc) it would generate for you
123
132
213
231
312
321
very quickly. if you used it for
xxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyy
and counted it rather than disply it you would (I assuming I'm not talking out of my ass) have your answer. I'll think some more about it on the way home. perhaps you can build on this (or show me that I'm barking up the wrong tree)
I'm only a 6% genius afterall
Posted: Thu Aug 16, 2007 8:10 am
by pdwyer
So, my guess is I need a quick way to get this pattern and find "?????"
Code: Select all
sides bits iterat answer
1 2 4 2
2 4 16 6
3 6 64 20
4 8 256 70
5 10 1024 252
6 12 4096 924
7 14 16384 3432
....
20 40 1099511627776 ?????
Posted: Thu Aug 16, 2007 8:16 am
by pdwyer
I got it!!!
I put "2 6 20 70 252 924 3432" into a google search and there was a page of numbers enumed out.
Now I just need to find out how the hell they calced it as I need this algorithm for something else.
It was correct too.
Now I'm a 7% genius
(kind of cheated though, but my idea was correct)
More details here (but not the answer)
http://www.americanscientist.org/templa ... 5qf2cyt9yy
When I was a commuter in New York, I walked a diagonal route across midtown Manhattan morning and evening. I used to wonder how many different paths I could find through the grid of east-west and north-south streets without taking extra steps. Eventually I grew curious enough to calculate some solutions. For a square lattice of n-by-n blocks, any minimum-length diagonal path is necessarily 2n blocks long. How many such paths are there? For the 1-by-1 lattice the answer is 2: You can go east and then north or you can go north and then east. In a two-block square there are six paths, and in a 3-by-3 block there are 20. The sequence of values I calculated begins like this: 2, 6, 20, 70, 252, 924, 3432, 12870, 48620....
Do those numbers look familiar? They should. They are prominent members of one of the most ancient and famous families of numerical sequences. And yet I did not identify them until several years later, when I had a chance to submit them to Sloane's sequence server. The answer came back immediately: They were recognized as sequence M1645, the central binomial coefficients, the numbers that run down the middle of Pascal's triangle. My reaction was "Of course! Why didn't I see it all along?" But I doubt that I would have made the connection without help.
Posted: Thu Aug 16, 2007 10:49 am
by Dreamland Fantasy
michaeled314 wrote:Problem #15 I can't get is there a formula behind it?
You can either use Pascal's Triangle or combinatorics to get the answer.
I ultimately went for the combinatoric approach.
Kind regards,
Francis.
Posted: Thu Aug 16, 2007 1:25 pm
by pdwyer
(2n)!/(n!)^2
where N = 20 (grid size)
I can get to 10 very easily with this, then quads run out of space and I need to dig up those big number routines
Posted: Thu Aug 16, 2007 1:39 pm
by pdwyer
AAARRRRGGHHHH the expression above works with doubles, even though 40! will lose some of it's final digits of precision, the answer still comes out correct.
Code: Select all
n = 20
first.d = 1
Second.d = 1
For i = 1 To 2*n
first = first * i
Next
For i = 1 To n
Second = Second * i
Next
Debug first/Pow(second,2)
I need a drink
Posted: Thu Aug 16, 2007 7:10 pm
by Dreamland Fantasy
pdwyer wrote:AAARRRRGGHHHH the expression above works with doubles, even though 40! will lose some of it's final digits of precision, the answer still comes out correct.
Code: Select all
n = 20
first.d = 1
Second.d = 1
For i = 1 To 2*n
first = first * i
Next
For i = 1 To n
Second = Second * i
Next
Debug first/Pow(second,2)
I need a drink
Here's my solution which is similar to yours, but has some differences:
Code: Select all
; Project Euler - Problem 15
;
; Starting in the top left corner of a 2x2 grid, there are 6 routes (without
; backtracking) to the bottom right corner.
;
; How many routes are there through a 20x20 grid?
GridSize = 20
nFactorial.d = 1
For i = 1 To GridSize
nFactorial * i
Next
nFactorial_2.d = nFactorial
For i = GridSize + 1 To GridSize << 1
nFactorial_2 * i
Next
Result.q = nFactorial_2 / (nFactorial * nFactorial)
MessageRequester("Project Euler", "Answer to problem 15: " + StrQ(Result))
Kind regards,
Francis.
Posted: Fri Aug 17, 2007 2:11 am
by Demivec
Here was my solution to #15 using a pascal's triangle approach:
Code: Select all
#gridLength=20
Global Dim paths.q(#gridLength)
;-procedures
Procedure addPathsForLevel(level.l);compute # of paths for new level based on previous level
Protected I.l,a.q,b.q
If level=1
paths(1)=2 ;2 possible paths for grid of 1x1
ProcedureReturn
EndIf
addPathsForLevel(level-1)
For I=1 To level-1
a.q=paths(I):b.q=paths(I-1)
paths(I)=a+b
Next
paths(level)=paths(level-1)*2
EndProcedure
;-Solution
addPathsForLevel(#gridLength)
result.q=0
For I=1 To #gridLength
result+paths(I)
Next
MessageRequester("Project Euler", "Answer to problem 15: " + StrQ(result))
Posted: Fri Aug 17, 2007 4:14 am
by pdwyer
I'll be honest, I'd never even heard of a pascal triangle in my 36 years of existance till after this question. I still don't quite understand how the grids combinations turn out to match the middle set of numbers down the triangle. My method of trying to solve this was going to take quite a while.
In the end I found this stuff because I did a search on the number pattern that was ermerging on the way to the answer.
Well boys and girls, that should teach you not to drop out of school when you're 15
I'm learning a lot from doing these questions.
Posted: Fri Aug 17, 2007 12:41 pm
by pdwyer
Has anyone gotten through 69? The Sudoku one?
I thought I had it nailed. I didn't want to brute force it as I doubted I could do it in under a minute so I go through the 0s and check row,col,box and score it, Then depending on the result I have
9: (all numbers present so I have a bug or a wrong number (see beolw) )
8: (only one number can be written in so fill it in)
7 or less, skip
For easy grids I can get them out. Hard ones I get a board with a few 7's on it (ie, it's possibly one of two numbers) so I have a guess routine which takes each one in turn and tries one then the other of the two possible answers and continues, if I get a "9" then I know that the guess caused an impossible condition (usually a guess means I can get a few more numbers out then I hit a condition 9 and have to undo back to the guess.
It gets a little messy there where is as far as I've gotten but I can't solve them all yet.
Time is not an issue, using this I'll blits all 50 in a second or two but I can't solve some of them
Is this how others did it?
Posted: Fri Aug 17, 2007 1:49 pm
by Demivec
I got stuck on #96 also. I think it was because of a bug that I couldn't work out.
I computed which digits were unused for each row,column,box and then checked for squares where there was only one unknown that would fit, then re-evaluated the squares again if one was filled-in. I then guessed by computing and sorting the possibles for each square and guessed on squares that had the fewest ones (i.e. a square that needs [3, or 8] instead of one needing [0,3,8, or 9]) and then proceeded as above. Backtrack when no allowable options left for any unfilled space.
I ran into a bug where memory was being overwritten when it should't be, possibly a PB pug.
Posted: Fri Aug 17, 2007 2:26 pm
by pdwyer
I've abandoned the guess method.
I found a way forward but it's taking time to code. If you have a sitation where a zero only has two possibilities then rather than guess you can do another level of checking. Grid01 solves fine without this, grid02, if you take a look, pos (5,3) gets a 6 then it can't find anymore obvious ways through BUT, checking all the options that only have 2 possibilites (13 of them) one of them (6,3) which could be a 1 or a 4 can't be a 1 as the other three gaps in that row can't be 4's. When the 4 goes in position 4,1 which is a 4 or 9 combination can no longer be a 4 etc
It might not solve the puzzle but it's an extra level of checking that can be done before guessing.
the code is getting a lot longer than I thought it would though
perhaps brute force might have been the way to go after all...
Posted: Fri Aug 17, 2007 4:55 pm
by pdwyer
I gave up
I remember seeing someone do this on the powerbasic forum ages back so I decided to go search for the code.
http://www.powerbasic.com/support/forum ... 02925.html
The original perl looked like this (god know why people write like this)
Code: Select all
use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
==$i/9| |$_%9==$i%9| |$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R
The PB Version to solve the puzzel I ported from powerbasic
As a compiled exe it completes all 50 in under 10sec.
Now I'm gonna spend the next few hours trying to figure out how it works
Code: Select all
Procedure.l Resolve(Grid.l(1))
i.l : j.l : k.l : s.l
Dim t.l(9)
For i = 0 To 80
If Grid(i) = 0
Dim t(9)
For s = 0 To 80
If Grid(s)
If (s/9 = i/9) Or (s % 9 = i % 9) Or ((s/27 = i/27) And ((s % 9)/3 = (i % 9)/3))
t(Grid(s)) = Grid(s)
EndIf
EndIf
Next
For k = 1 To 9
If t(k) = 0
Grid(i)=k
If Resolve(Grid())
Goto nex
EndIf
EndIf
Next
Grid(i) = 0
ProcedureReturn 0
EndIf
nex:
Next
ProcedureReturn 1
EndProcedure
Dim Puzzel.s(50)
Puzzel(1) = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
Puzzel(2) = "200080300060070084030500209000105408000000000402706000301007040720040060004010003"
Puzzel(3) = "000000907000420180000705026100904000050000040000507009920108000034059000507000000"
Puzzel(4) = "030050040008010500460000012070502080000603000040109030250000098001020600080060020"
Puzzel(5) = "020810740700003100090002805009040087400208003160030200302700060005600008076051090"
Puzzel(6) = "100920000524010000000000070050008102000000000402700090060000000000030945000071006"
Puzzel(7) = "043080250600000000000001094900004070000608000010200003820500000000000005034090710"
Puzzel(8) = "480006902002008001900370060840010200003704100001060049020085007700900600609200018"
Puzzel(9) = "000900002050123400030000160908000000070000090000000205091000050007439020400007000"
Puzzel(10) = "001900003900700160030005007050000009004302600200000070600100030042007006500006800"
Puzzel(11) = "000125400008400000420800000030000095060902010510000060000003049000007200001298000"
Puzzel(12) = "062340750100005600570000040000094800400000006005830000030000091006400007059083260"
Puzzel(13) = "300000000005009000200504000020000700160000058704310600000890100000067080000005437"
Puzzel(14) = "630000000000500008005674000000020000003401020000000345000007004080300902947100080"
Puzzel(15) = "000020040008035000000070602031046970200000000000501203049000730000000010800004000"
Puzzel(16) = "361025900080960010400000057008000471000603000259000800740000005020018060005470329"
Puzzel(17) = "050807020600010090702540006070020301504000908103080070900076205060090003080103040"
Puzzel(18) = "080005000000003457000070809060400903007010500408007020901020000842300000000100080"
Puzzel(19) = "003502900000040000106000305900251008070408030800763001308000104000020000005104800"
Puzzel(20) = "000000000009805100051907420290401065000000000140508093026709580005103600000000000"
Puzzel(21) = "020030090000907000900208005004806500607000208003102900800605007000309000030020050"
Puzzel(22) = "005000006070009020000500107804150000000803000000092805907006000030400010200000600"
Puzzel(23) = "040000050001943600009000300600050002103000506800020007005000200002436700030000040"
Puzzel(24) = "004000000000030002390700080400009001209801307600200008010008053900040000000000800"
Puzzel(25) = "360020089000361000000000000803000602400603007607000108000000000000418000970030014"
Puzzel(26) = "500400060009000800640020000000001008208000501700500000000090084003000600060003002"
Puzzel(27) = "007256400400000005010030060000508000008060200000107000030070090200000004006312700"
Puzzel(28) = "000000000079050180800000007007306800450708096003502700700000005016030420000000000"
Puzzel(29) = "030000080009000500007509200700105008020090030900402001004207100002000800070000090"
Puzzel(30) = "200170603050000100000006079000040700000801000009050000310400000005000060906037002"
Puzzel(31) = "000000080800701040040020030374000900000030000005000321010060050050802006080000000"
Puzzel(32) = "000000085000210009960080100500800016000000000890006007009070052300054000480000000"
Puzzel(33) = "608070502050608070002000300500090006040302050800050003005000200010704090409060701"
Puzzel(34) = "050010040107000602000905000208030501040070020901080406000401000304000709020060010"
Puzzel(35) = "053000790009753400100000002090080010000907000080030070500000003007641200061000940"
Puzzel(36) = "006080300049070250000405000600317004007000800100826009000702000075040190003090600"
Puzzel(37) = "005080700700204005320000084060105040008000500070803010450000091600508007003010600"
Puzzel(38) = "000900800128006400070800060800430007500000009600079008090004010003600284001007000"
Puzzel(39) = "000080000270000054095000810009806400020403060006905100017000620460000038000090000"
Puzzel(40) = "000602000400050001085010620038206710000000000019407350026040530900020007000809000"
Puzzel(41) = "000900002050123400030000160908000000070000090000000205091000050007439020400007000"
Puzzel(42) = "380000000000400785009020300060090000800302009000040070001070500495006000000000092"
Puzzel(43) = "000158000002060800030000040027030510000000000046080790050000080004070100000325000"
Puzzel(44) = "010500200900001000002008030500030007008000500600080004040100700000700006003004050"
Puzzel(45) = "080000040000469000400000007005904600070608030008502100900000005000781000060000010"
Puzzel(46) = "904200007010000000000706500000800090020904060040002000001607000000000030300005702"
Puzzel(47) = "000700800006000031040002000024070000010030080000060290000800070860000500002006000"
Puzzel(48) = "001007090590080001030000080000005800050060020004100000080000030100020079020700400"
Puzzel(49) = "000003017015009008060000000100007000009000200000500004000000020500600340340200000"
Puzzel(50) = "300200000000107000706030500070009080900020004010800050009040301000702000000008006"
Answer.l
For PuzzelLoop = 1 To 50
Dim grid.l(80)
For i = 0 To 80
Grid(i)=Val(Mid(Puzzel(PuzzelLoop), i+1, 1))
Next
DisableDebugger
Resolve(Grid())
EnableDebugger
a.s = ""
For i = 0 To 80
a = a + Str(grid(i))
Next
Answer = Answer + Val(Mid(a,1,3))
Debug "Grid " + Str(PuzzelLoop) + " = " + a
Next
Debug "Answer = " + Str(answer)
Posted: Sat Aug 18, 2007 3:01 pm
by pdwyer
I'm a 13% genius now (but one question I gave up on and another I kinda cheated
so only about 12% really I suppose)
Doing these has been great though, there were 3 questions in there I needed to use my huge number procs (from the thread before) for and it turned out that they were full of bugs
getting through these questions really got them fixed and tested.
It's been a great way so far to learn to use a new compiler.
I loved the xor decrypt and the bank pin number crack ones best
I'm starting to find though that many of the remaining ones I don't even understand the question,
shows me how bad my math is I suppose. (I sit there scratching my head thinking, "what are they asking?" )