Forumdelen sponsras av

ELM : How to find Intersection Point in 2D Grid?

Trädvy Permalänk
Medlem
Registrerad
Aug 2015

ELM : How to find Intersection Point in 2D Grid?

Making a 2D Grid. Using X and Y axis. Inputs are a predetermined string called "instructions". I got some very helpful assistance on my elm code, and managed to solve my first function ( How to find final position) from a string of inputs.

I been working on the second function ( How to find intersection point ) and haven't found a solid solution. I think I'm almost there. Can someone help me with my intersection function in this 2D grid program?

At the moment compiled program outputs:
Final Position: { x = 2, y = 4 }
Intersection (position appear twice): { x = 0, y = 1 }

Final is correct. But the intersection point should be x = 2, y = 2 , Instructions tells it to go up 2 times "^^" then three steps right ">>>" and one step left. meaning the "snake" bites its own tail. Now it only looks at the first "char". ^ and not the rest.

Live code can be found here :
https://ellie-app.com/M76VPyJTLYa1

import Html exposing (Html)
type alias Location =
{ x : Int
, y : Int
}

instructions : String
instructions =
"^^>>><^>>>^<^v<v^^vv^><<"

firstInstruction : Char
firstInstruction =
instructions
|> String.toList
|> List.head
|> Maybe.withDefault '_'

main : Html msg
main =
let
initLoc =
{ x = 0, y = 0 }

finalLocation =
toString (calculateFinalLocation instructions initLoc)

firstIntersection =
toString (calculateIntersection firstInstruction initLoc)
in
Html.div []
[ Html.p [] [ Html.text ("Final: " ++ finalLocation) ]
, Html.p [] [ Html.text ("1st: " ++ firstIntersection) ]
]

// First Function ( Working )
calculateFinalLocation : String -> Location -> Location
calculateFinalLocation actions loc =
actions
|> String.toList
|> List.foldl calculateIntersection loc

// Second Function ( Gives wrong values )
calculateIntersection : Char -> Location -> Location
calculateIntersection action loc =
case action of
'^' ->
{ x = loc.x, y = loc.y + 1 }

'v' ->
{ x = loc.x, y = loc.y - 1 }

'>' ->
{ x = loc.x + 1, y = loc.y }

'<' ->
{ x = loc.x - 1, y = loc.y }

_ ->
loc

Trädvy Permalänk
Medlem
Plats
Mora
Registrerad
Jan 2011

Don't know C#, but why not create two arrays. One where you store visited points and before you store them you check if the exist in the array. If they do, store them in the second array.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

You need a way to keep track of already visited locations. Never used Elm, but a quick google-check suggests that Set exists. Set can hold Comparable elements and tuples of Int seems to be Comparable.

So one solution is to represent the visited places as the tuple (x, y). Check if the position already exists in the set, if it does then you have an intersection.

Example in C++, Elm looks functional with immutable types while this solution relies on mutable state.

#include <iostream> #include <set> #include <string> class Location { int x; int y; void up() { ++y; } void down() { --y; } void left() { --x; } void right() { ++x; } public: Location(int x, int y) : x(x), y(y) { } // std::set requires T to implement operator<() bool operator<(const Location &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); } void step(char instr) { switch (instr) { case '^': up(); break; case 'v': down(); break; case '<': left(); break; case '>': right(); break; } } std::string toString() const { return std::string("[ ") + std::to_string(x) + " " + std::to_string(y) + " ] "; } }; int main() { Location loc(0, 0); std::string instructions = "^^>>><^>>>^<^v<v^^vv^><<"; std::set<Location> visited; for (auto instr: instructions) { loc.step(instr); std::cout << '\n' << instr << ' ' << loc.toString(); if (!visited.insert(loc).second) { std::cout << "Intersection"; } } std::cout << "Final position" << std::endl; }

which prints

^ [ 0 1 ] ^ [ 0 2 ] > [ 1 2 ] > [ 2 2 ] > [ 3 2 ] < [ 2 2 ] Intersection ^ [ 2 3 ] > [ 3 3 ] > [ 4 3 ] > [ 5 3 ] ^ [ 5 4 ] < [ 4 4 ] ^ [ 4 5 ] v [ 4 4 ] Intersection < [ 3 4 ] v [ 3 3 ] Intersection ^ [ 3 4 ] Intersection ^ [ 3 5 ] v [ 3 4 ] Intersection v [ 3 3 ] Intersection ^ [ 3 4 ] Intersection > [ 4 4 ] Intersection < [ 3 4 ] Intersection < [ 2 4 ] Final position

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer