163 - City Directions

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu » Fri Jan 12, 2007 6:43 pm

shanto86, maybe a little bit late. Try this:
Input:

Code: Select all

A1W S50N E
TURN HALF LEFT
STOP
END
My AC program output:

Code: Select all

A0E S50N NE
Your output:

Code: Select all

Illegal stopping place
You may need to verify further the command read, say something like GO 12ss, GO STRAIGHT -1, TURN LEFT SHARP, TURN RIGHT xxxx, etc.

ar2rd, your input is invalid as the problem ensures that "At no stage will directions take you out of the confines of the city". My AC program crashed when reading your input.

Orlin
New poster
Posts: 2
Joined: Sun Sep 30, 2007 7:54 pm

Post by Orlin » Thu Oct 25, 2007 11:42 pm

rickyliu wrote:shanto86, maybe a little bit late. Try this:
Input:

Code: Select all

A1W S50N E
TURN HALF LEFT
STOP
END
My AC program output:

Code: Select all

A0E S50N NE
Your output:

Code: Select all

Illegal stopping place
You may need to verify further the command read, say something like GO 12ss, GO STRAIGHT -1, TURN LEFT SHARP, TURN RIGHT xxxx, etc.

ar2rd, your input is invalid as the problem ensures that "At no stage will directions take you out of the confines of the city". My AC program crashed when reading your input.
Your AC program's output for this case is wrong. You can't go northeast from one of the northmost intersections.

Londovir
New poster
Posts: 4
Joined: Thu Dec 30, 2004 8:04 am

Re: 163 - City Directions

Post by Londovir » Fri Jun 13, 2008 7:41 am

Can anyone give me any pointers as to any "tricks" for the input data when it comes to the starting position?

I've been using Java and constantly am getting RUNTIME ERROR when I submit, yet I have exactly correct answers when I run every example input posted on these boards, never once getting a RE.

I've used (by this point) Scanners, Regex, String.split(), Pattern, and even changed the input line to a character array and hand parsed it. No matter what I do, I keep getting a runtime error. With the judge, there's no way to tell which exception is being thrown so I can get a better idea of what the problem is, and without the input data being used to judge, I can't see what's being done that makes it fail.

Is the starting position being split over more than 1 line? I've put in, via Scanners or Regex or Patterns, the ability to handle any number of whitespace in between each portion. I've even gone so far as to assume that the A##[E|W] portion may not come first (even though it probably does - nothing in the spec stated they could be swapped). No matter what, I'm getting a RE.

Here's my most recent attempt at decoding the starting position (though this is iteration #20 or so, seriously):

Code: Select all

    public location decodeLocation(String inline)
    {
        String pieces[];
        int pmark = 0;
        String subpieces[];
        int smark = 0;
        int dist = 0;
        int pos = 0;
        char dir;
        location place = new location();
        int value = 0;
     
        // This should split the position line using whitespace delimiters
        pieces = inline.split("\\s+");
        // Choose the starting place, since any starting whitespace causes
        // an "empty" token due to regex.
        if (pieces[0].length() == 0)
            pmark = 1;
        else
            pmark = 0;
            
        // Do 1st piece...
        // Split this subpiece based upon non-numeric delimiters
        // (This should isolate just the street # portion
        subpieces = pieces[pmark].split("\\D+");
        // This shouldn't be needed, but I'm getting paranoid now...
        if (subpieces[0].length() == 0)
            smark = 1;
        else
            smark = 0;
        // Convert the piece to a whole number...this isn't causing the RE
        // (I thought perhaps it was a NumericFormat exception, so I commented
        // this out earlier and still got RE)
        dist = Integer.parseInt(subpieces[smark]);
        // Set this value in my special class/struct to hold the distance
        place.anx = dist;
        
        // Do 2nd piece
        pmark++;
        subpieces = pieces[pmark].split("\\D+");
        if (subpieces[0].length() == 0)
            smark = 1;
        else
            smark = 0;
        dist = Integer.parseInt(subpieces[smark]);
        
        place.any = dist;
        
        pmark++;
        
        // Direction brought in
        if (pieces[pmark].equals("N")) place.ahead = north;
        if (pieces[pmark].equals("S")) place.ahead = south;
        if (pieces[pmark].equals("E")) place.ahead = east;
        if (pieces[pmark].equals("W")) place.ahead = west;
        if (pieces[pmark].equals("NW")) place.ahead = nw;
        if (pieces[pmark].equals("NE")) place.ahead = ne;
        if (pieces[pmark].equals("SW")) place.ahead = sw;
        if (pieces[pmark].equals("SE")) place.ahead = se;
        
        return place;
    }
Please note: This doesn't currently check to see if it should be northward, southward, eastward, or westward for either the avenue or street

Taking blind guesses as to the cause of the RE, I can only assume I'm overshooting the array size caused by the split() command. I wrapped all of that code above in a try-catch for an ArrayIndexOutOfBoundsException, forcing it to return a dummy location, and managed to get WA rather than RE -- so that tells me that my split() command is not giving me 3 (or 4 if there's an empty token due to prepended whitespace) tokens.

Did anyone else find that the starting position was split over two [or more] lines, or have an idea of what's going wrong here? Also, I'm checking ahead of time for the presence of "END" on the line and "STOP", along with blank lines in the input file, so I can't see how anything but the expected "A#[E|W] S#[N|S] [N|E|S|W|NE|NW|SE|SW]" is getting sent to this function.

Thanks for any help/tips!

Londovir

Londovir
New poster
Posts: 4
Joined: Thu Dec 30, 2004 8:04 am

Re: 163 - City Directions

Post by Londovir » Fri Jun 13, 2008 8:25 am

Update: AC now!

For future posterity for those attempting to solve this one, I strongly suspect there are blank lines between scenarios in the input file, even though there's no mention of that being the case in the problem statement. I modified my program to pattern match against this regex: "\\s*[AS]+\\d+[NSEW]+\\s+[AS]+\\d+[NSEW]+\\s+[NSEW]+" (my probably inefficient way of describing the starting position line), and reject a line if it didn't say "END" or match that regex.

Sure enough, it instantly flipped over to AC. I'll assume there were no invalid starting position lines, and that the invisible catch was 1 or more blank lines in between scenarios inside the input file.

Oh well -- at least I got AC, though I hate getting errors that are due to reading the input rather than the algorithm behind solving the problem.

Londovir

x22
New poster
Posts: 1
Joined: Mon Jun 23, 2008 4:06 pm

Re: 163 - City Directions

Post by x22 » Mon Jun 23, 2008 4:14 pm

There are no blank lines between scenarios. My AC (also Java) program would crash on blank line between scenarios.

craig_ka
New poster
Posts: 1
Joined: Thu Apr 29, 2010 1:37 am

Re: 163 - City Directions

Post by craig_ka » Thu Apr 29, 2010 4:23 am

I don't know if anyone will see this any time in the near future, but I'm at a loss on this problem. I believe I've implemented the valid turns to Per's instructions. I have typed in input by hand with debugging output showing where I'm at after each command and traversed through all of the "special" points. I've tried stopping on each of the throughways and above each of the throughways and can't seem to find why I keep getting WA. I've also added catches when parsing the input that will delete a pointer that hasn't been allocated to cause a RE if an unexpected character appears on the line that should designate the new location. I do the same at the end of execution checking that the last command given was END and don't get any RE's from the judge. I also check each command for extra words after a valid command which would invalidate that command. I know for sure that the judge has no whitespace at the end of lines and there are no blank lines between STOP and the next starting location. I know about everyting about the judges test input except why my program gets WA. Anyway, here is my code. It's alot

Code: Select all

code removed after ac
Just a tip to anyone stuck. I forgot to check for stopping on a boulevard throughway at intersection 0,0.
In debugging I output where I was at after each command and also if the current position and direction is a valid stopping place and caught my error after a few minutes of driving around.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 163 - City Directions

Post by metaphysis » Thu Feb 18, 2016 1:42 pm

I'm confused with this problem completely, according to Per, you may turn any direction as you like at nine intersections, leave the througways by truning left(sharp left in the case of boulevards), but according to uDebug(https://www.udebug.com/UVa/163, Solution by brianfry713):

test case 1:

INPUT:
A50W S49S S
TURN LEFT
GO 1
TURN LEFT
STOP
END

OUTPUT:
A48W S50S N

test case 2:

INPUT:
A50W S49S S
TURN LEFT
TURN LEFT
STOP
END

OUTPUT:
Illegal stopping place

The result of second test case should be A49W S50S N according rules above, isn't it? Can anyone explain it to me?
Last edited by metaphysis on Thu Apr 07, 2016 11:13 am, edited 1 time in total.

pointless0
New poster
Posts: 9
Joined: Wed Jan 13, 2016 3:24 am

Re: 163 - City Directions

Post by pointless0 » Tue Feb 23, 2016 12:07 am

Input:

Code: Select all

A50W S49S S
TURN LEFT
TURN LEFT
STOP
END
FWIW, my AC output is:

Code: Select all

A49W S50S N

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re:

Post by rafastv » Sun Aug 06, 2017 10:08 pm

ar2rd wrote:
Sat Aug 19, 2006 8:06 pm
Is this case allowed? What's the AC program output?
Thanks for replies.

Code: Select all

A4W S1N SW
TURN RIGHT
TURN   HALF RIGHT
TURN SHARP RIGHT
  GO   STRAIGHT    41
GO -32
PW
  TURN   RIGHT   
  TURN   RIGHT   
GO STRAIGHT 21
TURN HALF LEFT
TURN SHARP LEFT
  GO          ON 47
TURN HALF LEFT
OPPEKEOBWFGFXRYISILEIMFGUFRZZZDWVO
TURN SHARP LEFT
TURN SHARP RIGHT
GO ON 28
GO STRAIGHT -16
  TURN SHARP       RIGHT
  TURN   RIGHT   
TURN RIGHT
  TURN HALF    LEFT
TURN       LEFT
TURN       LEFT
  GO   9
GO STRAIGHT -27
TURN       LEFT
TURN   HALF RIGHT
  TURN   RIGHT   
TURN SHARP RIGHT
TURN HALF LEFT
TURN LEFT
TURN       LEFT
TURN LEFT
  TURN HALF    LEFT
TURN       LEFT
TURN SHARP RIGHT
  TURN HALF    LEFT
GARL   NYU  QK      FZ 
TURN   HALF RIGHT
GO STRAIGHT 25
TURN HALF RIGHT
  GO          ON 29
XTQXBWEPTNUAPCDSHYOOUOLSBXGWZSBCEM
  TURN SHARP       RIGHT
  TURN         SHARP           LEFT
TURN   HALF RIGHT
TURN LEFT
  GO   STRAIGHT    -33
  GO   STRAIGHT    25
GO ON 78
TURN   HALF RIGHT
TURN SHARP LEFT
  GO   9
TURN SHARP LEFT
  GO   2
TURN SHARP RIGHT
  GO   STRAIGHT    -38
  TURN HALF    LEFT
GO 23
  GO   STRAIGHT    -14
GO ON 51
  AZ  L      RR FT
TURN HALF RIGHT
QKJNBYYJUHWBLICQMTJRF
  TURN SHARP       RIGHT
TURN HALF RIGHT
TURN HALF RIGHT
TURN SHARP RIGHT
GO STRAIGHT 11
TURN       LEFT
TURN HALF LEFT
TURN LEFT
GO 2
  GO   STRAIGHT    -8
TURN HALF RIGHT
GO ON 27
GO ON 22
  TURN HALF    LEFT
  TURN SHARP       RIGHT
TURN HALF LEFT
GO 22
TURN LEFT
GLDMAMTHAESFZQAS
  TURN   RIGHT   
STOP
END
My AC code outputs A26W S17N SE

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re:

Post by rafastv » Sun Aug 06, 2017 10:10 pm

rickyliu wrote:
Fri Jan 12, 2007 6:43 pm
shanto86, maybe a little bit late. Try this:
Input:

Code: Select all

A1W S50N E
TURN HALF LEFT
STOP
END
My AC program output:

Code: Select all

A0E S50N NE
Your output:

Code: Select all

Illegal stopping place
You may need to verify further the command read, say something like GO 12ss, GO STRAIGHT -1, TURN LEFT SHARP, TURN RIGHT xxxx, etc.

ar2rd, your input is invalid as the problem ensures that "At no stage will directions take you out of the confines of the city". My AC program crashed when reading your input.
My AC code outputs Illegal stopping place(If the last instruction is HALF RIGHT it outputs A0E S50N SE). The problem clearly states that no instruction should take us out of the city. The udebug's site solution has the same problem. Be careful!

Post Reply

Return to “Volume 1 (100-199)”