Earn extra honor and gain new allies!
Honor is earned for each new codewarrior who joins.
Learn more
  • Done :)

  • This comment is hidden because it contains spoiler information about the solution

  • This comment is hidden because it contains spoiler information about the solution

  • manual notification, see above

  • This comment is hidden because it contains spoiler information about the solution

  • This comment is hidden because it contains spoiler information about the solution

  • here are some cases I could extract from the small random tests (doing what I told you before... ;p )

    every call is done with "(grid, start, end, 150, true)"
    
     start,end = [ 1, 4 ] [ 12, 1 ] 
     [ [ -7, -17, Infinity, 9, Infinity ],
      [ 18, -18, 16, 6, 2 ],
      [ -4, -11, Infinity, -13, 0 ],
      [ Infinity, Infinity, Infinity, 7, -3 ],
      [ -6, 6, Infinity, 2, 15 ],
      [ 14, -19, 0, 18, -10 ],
      [ -9, 0, 8, Infinity, -7 ],
      [ -5, 15, 1, 0, 15 ],
      [ 5, -7, 16, Infinity, Infinity ],
      [ -17, -6, Infinity, 19, 18 ],
      [ -9, 5, 16, Infinity, 14 ],
      [ 6, 17, 20, -4, 3 ],
      [ 3, 1, 3, 9, Infinity ] ]
    =======
     start,end = [ 4, 2 ] [ 0, 0 ] 
     [ [ -10, Infinity, -2, -8, Infinity, 10, -14 ],
      [ -14, 9, Infinity, -12, -8, 3, Infinity ],
      [ -4, 18, 18, 9, 4, -13, 5 ],
      [ -2, 11, -10, -16, -16, -16, -8 ],
      [ 0, Infinity, 2, 4, 16, 1, 4 ] ]
    =======
     start,end = [ 2, 1 ] [ 12, 4 ] 
     [ [ 15, 10, -12, 8, 14, -6, -12 ],
      [ -3, -6, -9, -13, Infinity, -8, 16 ],
      [ -12, -15, 17, Infinity, -19, 6, 0 ],
      [ 13, 15, 3, 4, Infinity, -15, 14 ],
      [ -14, -18, -5, -5, 14, 14, 5 ],
      [ -14, 15, -2, 1, -6, 15, 9 ],
      [ 13, -6, Infinity, -11, Infinity, -16, Infinity ],
      [ -15, -10, 4, 18, -13, -17, -16 ],
      [ -18, 10, -8, Infinity, 18, -10, -3 ],
      [ Infinity, -17, -14, -8, 14, Infinity, 11 ],
      [ -16, Infinity, -17, -9, -11, -7, 15 ],
      [ 14, -5, -7, -12, -17, 8, -6 ],
      [ 4, -11, -7, -1, 3, Infinity, 4 ] ]
    =======
     start,end = [ 10, 5 ] [ 0, 5 ] 
     [ [ Infinity, -7, 17, 8, -12, -9, -5 ],
      [ -4, -17, -19, 19, Infinity, -9, 19 ],
      [ -14, -11, Infinity, 10, 6, -2, 9 ],
      [ 2, -8, Infinity, -4, -15, -6, -3 ],
      [ -13, -14, Infinity, -9, 7, Infinity, 8 ],
      [ 20, -7, 1, 11, -19, Infinity, -10 ],
      [ 1, 9, Infinity, 9, -7, -3, Infinity ],
      [ 17, 4, -5, 6, 4, Infinity, 0 ],
      [ 12, 1, Infinity, -7, -8, 17, -18 ],
      [ -3, -4, -8, -4, -13, -11, 18 ],
      [ 16, 3, 0, -11, 18, -7, 11 ],
      [ -17, -12, -3, -4, Infinity, Infinity, 12 ],
      [ 9, 5, -6, 4, -3, 18, 7 ] ]
    =======
    
  • This comment is hidden because it contains spoiler information about the solution

  • It's about computing a cost+heuristic higher than it actually is, for the current (looping) path and so discard that path because the wrong cost+h becomes higher than the limit. At least, I believe that's what actually happened.

    Even if you don't aim the problem for this version, it's always good to have the test. Try generating small grids but with a "pretty low" limit, you should be able to generate an edge case of reasonnable size, I guess (with enough tests generation...)

    EDIT: my faulty solution has been invalidated, but just because with the republishing it didn't had as much luck as the other time => plz find/add this edge case. ;)

  • This comment is hidden because it contains spoiler information about the solution

  • all your inputs are valid, afaik.

    I believe you need start and end points in corners (EDIT: actually near corners, I guess), looping enabled, with possibility to actually loop in the grid. I linked the two versions above. The only difference is in the heuristic function.

  • The two sets of random tests use the exact same generation method, the only difference is the grid size (and hence start/end locations) and the time cutoff.

    The only invalid inputs I am aware of would be starting or ending on an Infinity square, which is accounted for in the random tests.

    With regards to your particular heuristic issue, could you comment on how your computation was incorrect, so I could add a non-random test case for it?

  • ok, There is an edge case that is missing in the fixed tests. It appears only in the huge random tests, so I cannot print the inputs (too big, output is truncated even printing it row by row aand even so, this leads to a max buffer limit error...). I tracked down the source of the problem: the computation of my heuristic is incorrect when looping is involved.

    => you'll have to find a way to get a viable input to add to the fixed tests. Maybe you generate the mazes in different ways, too, between the two batches of random tests? Because this never occurd in the small grid (which seems a bit weird... Maybe related to the range of the random heights too, so?)

  • Loading more items...