Project Euler...

michaeled314 · Post by **michaeled314** » Thu Aug 16, 2007 1:34 am

Problem #15 I can't get is there a formula behind it?

pdwyer · Post by **pdwyer** » Thu Aug 16, 2007 7:58 am

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

pdwyer · Post by **pdwyer** » Thu Aug 16, 2007 8:10 am

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	?????

pdwyer · Post by **pdwyer** » Thu Aug 16, 2007 8:16 am

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.

Dreamland Fantasy · Post by **Dreamland Fantasy** » Thu Aug 16, 2007 10:49 am

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.

pdwyer · Post by **pdwyer** » Thu Aug 16, 2007 1:25 pm

(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

pdwyer · Post by **pdwyer** » Thu Aug 16, 2007 1:39 pm

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

Dreamland Fantasy · Post by **Dreamland Fantasy** » Thu Aug 16, 2007 7:10 pm

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.

Demivec · Post by **Demivec** » Fri Aug 17, 2007 2:11 am

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))

pdwyer · Post by **pdwyer** » Fri Aug 17, 2007 4:14 am

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.

pdwyer · Post by **pdwyer** » Fri Aug 17, 2007 12:41 pm

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?

Demivec · Post by **Demivec** » Fri Aug 17, 2007 1:49 pm

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.

pdwyer · Post by **pdwyer** » Fri Aug 17, 2007 2:26 pm

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...

pdwyer · Post by **pdwyer** » Fri Aug 17, 2007 4:55 pm

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)

pdwyer · Post by **pdwyer** » Sat Aug 18, 2007 3:01 pm

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?" )