Downhill Maze Solver

9

Labirynt zjazdowy jest podawany jako seria rzędów cyfr oddzielonych spacją od 0 do 9 włącznie, plus jeden „S” i jeden „X”, gdzie S oznacza początek, a X oznacza koniec. W labiryncie zjazdowym możesz udać się tylko na pole sąsiadujące z tobą na północ, południe, wschód lub zachód (bez przekątnych) i możesz iść tylko na pola o wartości mniejszej lub równej wartości są obecnie włączone.

Program powinien wypisać ścieżkę do poruszania się po labiryncie w tym samym formacie co dane wejściowe, tylko wszystkie spacje powinny mieć znak „.” w nich, a wszystkie niezwiedzone miejsca powinny mieć znak „#”. Komórki początkowe i końcowe powinny również zachować odpowiednio swoje „S” i „X”. Możesz założyć, że labirynt zawsze jest rozwiązaniem.

Przykładowe dane wejściowe:

3 3 3 3 2 1 S 8 9
3 1 1 3 3 0 6 8 7
1 2 2 4 3 2 5 9 7
1 2 1 5 4 3 4 4 6
1 1 X 6 4 4 5 5 5

Przykładowe dane wyjściowe:

. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .
Łukasz D.
źródło
3
Można przenieść do iz Soraz Xw dowolnym kierunku? Czy labirynt jest zawsze do rozwiązania?
Calvin's Hobbies
Czy możemy również założyć, że wszystkie rzędy mają tę samą długość? I, aby wyjaśnić, „cyfra” oznacza jedną cyfrę dziesiętną od 0do 9włącznie, prawda?
Ilmari Karonen,
1
@ Calvin Tak, możesz poruszać się do S i X w dowolnym kierunku. Zakłada się, że labirynt jest do rozwiązania.
Łukasz D
1
@IImari Tak, wszystkie wiersze mają tę samą długość i tak, „cyfra” to jedna cyfra od 0 do 9 włącznie.
Łukasz D

Odpowiedzi:

3

JavaScript (ES6) 219

Funkcja zwracająca wartość prawda lub fałsz. Rozwiązanie (jeśli znaleziono) jest wyprowadzane na konsolę. Nie próbuje znaleźć optymalnego rozwiązania.

f=o=>(r=(m,p,w=0,v=m[p])=>
v>':'
  ?console.log(' '+m.map(v=>v<0?'#':v,m[f]='X').join(' '))
  :v<=w&&[1,-1,y,-y].some(d=>r([...m],d+p,v),m[p]='.')
)(o.match(/[^ ]/g).map((v,p)=>v>'S'?(f=p,0):v>':'?v:v<'0'?(y=y||~p,v):~v,y=0),f)

Nieśmiertelny i wyjaśnił więcej niż to konieczne

f=o=>{
  var r = ( // recursive search function
    m, // maze array (copy of)
    p, // current position
    w  // value at previous position
  )=> 
  {
    var v = m[p]; // get value at current position
    if (v == 'S') // if 'S', solution found, output and return true
    {
      m[f] = 'X'; // put again 'X' at finish position
      m = m.map(v => { // scan array to obtain '#'
        if (v < 0) // a numeric value not touched during search
          return '#'
        else  
          return v  
      }).join(' '); // array to string again, with added blanks (maybe too many)
      console.log(' '+m) // to balance ' '
      return true; // return false will continue the search and find all possible solutions
    }
    if (v <= w) // search go on if current value <= previous (if numeric, they both are negative)
    {
      m[p]='.'; // mark current position 
      return [1,-1,y,-y].some(d=>r([...m], d+p, v)) // scan in all directions
    }
    // no more paths, return false and backtrack
    return false
  }

  var f, // finish position (but it is the start of the search)
      y = 0; // offset to next/prev row
  o = o.match(/[^ ]/g) // string to char array, removing ' 's
  .map((v,p) => // array scan to find f and y, and transform numeric chars to numbers 
   {  
     if (v > 'S') // check if 'X'
     {
       f = p;
       return 0; // 'X' position mapped to min value
     }
     if (v > ':') // check if 'S'
       return v; // no change
     if (v < '0') // check if newline
     {
       if (!y) y = ~p; // position of first newline used to find y offset
       return v; // no change
     }
     return ~v; // map numeric v to -v-1 so have range (-1..-10)
   })

  return r(o, f, 0) // start with a fake prev value
}

Test w konsoli Firefox / FireBug

f('3 3 3 3 2 1 S 8 9\n3 1 1 3 3 0 6 8 7\n1 2 2 4 3 2 5 9 7\n1 2 1 5 4 3 4 4 6\n1 1 X 6 4 4 5 5 5')

Wynik

. . . . # # S . #   
. # # . . # # . .   
. # # # . # # # .   
. # # # . # # # .   
. . X # . . . . .  

true  
edc65
źródło
Wydaje się, że mamy wspólny niezgłębiony kod.
patrz
1
@Sieg dlaczego, czy to nie jest krystalicznie czyste? Jutro dodam wyjaśnienie
edc65,
@Sieg bardziej zrozumiały?
edc65
Rzeczywiście niezgłębiony.
patrz
4

C # - 463

Akceptuje dane wejściowe za pośrednictwem STDIN i powinien wygenerować optymalną ścieżkę, przetestowaną dla danego przypadku testowego, ale nie inaczej. Zakłada, że ​​zawsze istnieje rozwiązanie.

Trochę mi się spieszy, mam termin w ciągu 7 godzin, ale wyglądało to na zbyt zabawne, aby przegapić. Jestem również poza praktyką. To może być bardzo krępujące, jeśli pójdzie to źle, ale jest rozsądnie grał w golfa.

using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+');int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L;var K=new int[L];for(K[s]=s+2;j-->0;)for(i=0;i<L;i+=2){System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};M(2);M(-2);M(w);M(-w);}for(w=e;w!=s+1;w=i){i=K[w]-1;K[w]=-1;}for(;++j<L;)C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]);}}

Kod z komentarzami:

using C=System.Console;

class P
{
    static void Main()
    {
        var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+'); // read in the map, replace X with + because + < 0
        int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L; // find start, end, width, length

        var K=new int[L]; // this stores how we got to each point as loc+1 (0 means we havn't visited it)

        for(K[s]=s+2; // can't risk this being 0
            j-->0;) // do L passes
            for(i=0;i<L;i+=2) // each pass, look at every location
            {
                // if a whole load of bouds checks, point new location (i+z) at i
                System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};
                // try and move in each direction
                M(2);
                M(-2);
                M(w);
                M(-w);
            }

        for(w=e;w!=s+1;w=i) // find route back
        {
            i=K[w]-1; // previous location
            K[w]=-1; // set this so we know we've visited it
        }

        for(;++j<L;) // print out result
            C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]); // if K < 0, we visit it, otherwise we don't
    }
}
VisualMelon
źródło