118 WA: wtf

[jonaskoelker]

I get WA for problem 118, which frustrates me quite a bit, since it sounds deceptively simple. I think I've read the problem carefully enough, but I might be wrong. The only 'trick' I see is the fall-over-the-edge logic, which I understand as:

next.point = getmove(current.point)
if (next.point is inside bounds) current.point = next.point;
else if (has scent) do nothing;
else { fall over; set scent(current.point); }

Is this correct?
If so, where's my implementation off?

Any help will be greatly appreciated.

Code: Select all

# include <stdio.h>
# include <stdlib.h>

static const char angles [] = "NESW";

enum bool { false, true };
enum angle { north, east, south, west };

struct point { short x, y; };
struct bot { struct point p; enum angle angle; enum bool lost; };
struct hash { struct hash * next; struct point p; };

static struct point forward (struct bot bot)
{
   struct point p = bot.p;
   switch (bot.angle)
   {
   case north: ++ p.y; break;
   case east : ++ p.x; break;
   case south: -- p.y; break;
   case west : -- p.x; break;
   }
   return p;
}

# define HASHSIZE 31
# define HASH(p) (((p).x * 53 + (p).y) % HASHSIZE)
static struct hash * scents [HASHSIZE];

# define LEFT(b) (((b).angle - 1) % 4)
# define RIGHT(b) (((b).angle + 1) % 4)
int main (void)
{
   struct point max;
   struct bot bot;
   scanf ("%hd %hd", & max.x, & max.y);
   while (
      3 == scanf (
         "%hd %hd %1[NESW]",
         & bot.p.x, & bot.p.y, (char *) & bot.angle))
   {
      int i, ch;
      bot.lost = false;
      for (i = 0; i < 4; ++i)
         if ((char) bot.angle == angles[i])
            bot.angle = i;
      while (getchar () != '\n');
      while ((ch = getchar ()) == 'F' || ch == 'R' || ch == 'L')
         if (!bot.lost) switch (ch)
         {
         case 'F':
         {
            struct point p = forward (bot);
            if (p.x >= 0 && p.x <= max.x && p.y >= 0 && p.y <= max.y)
               bot.p = p;
            else
            {
               struct hash * hash = scents[HASH (p)];
               for (; hash; hash = hash -> next)
                  if (hash -> p.x == p.x && hash -> p.y == p.y)
                     break;
               if (hash == NULL) /* if unscented */
               {
                  /* insert new scent */
                  hash = malloc (sizeof * hash);
                  hash -> p = p;
                  hash -> next = scents [HASH (p)];
                  scents[HASH (p)] = hash;
                  bot.lost = true;
                  printf (
                     "%hd %hd %c LOST\n",
                     bot.p.x, bot.p.y, angles[bot.angle]);
               }
            }
         }
         break;
         case 'R': bot.angle = RIGHT (bot); break;
         case 'L': bot.angle = LEFT  (bot); break;
         }
      if (!bot.lost)
         printf ("%hd %hd %c\n", bot.p.x, bot.p.y, angles[bot.angle]);
   }
   return 0;
}


-- Jonas

[ImLazy]

This is the fall-over-the-edge logic:

Code: Select all

if(next step is Not fall-over)
  go to next step;
else if(current position has scent)
  do nothing;
else
  fall over and leave a scent;

Pay attention: if current position has a scent, then the instruction to fall over toward any direction is ignored. For example: the upper-right point is (5,3), and there is a scent at (5,3). Then when a robot stand at (5,3) both going toward North and toward East will be ignored.
Hope this helps.

[jonaskoelker]

To ImLazy: thanks for you reply. Unless I'm mistaken, your suggested logic is the same as mine, except that the first condition is doubly negated ('if not not ...'). Of course, I could very well be mistaken, in which case: could you point out which part of the code is wrong?

To everyone: it's driving me crazy. I'm hoping that someone with AC could be so kind as to run the following (randomly generated) input through their solution and post the output.

Code: Select all

20 20
5 11 E
FFFRFLFFFLFFRFRRFLR
15 7 S
RRLRRLLLLLLLLLLFRRRFFFRRLRL
4 17 N
LFRRLRRLLFLRRFFRFRLL
18 7 W
LFLRRRRRFFLLRFFFR
7 3 W
LLFRFFRRRLRFLFRFRRL
9 7 E
FLLRFRFFRRLLLLRRLLLFRFRRRRFLLLLRFLFFFRF
0 20 N
LFFFLFFLRLLFRRFRRLRFLLF
1 4 W
RRFRLFLFLR
5 4 S
LRFLFRFFFL
16 7 S
LFFRFFRLRFFRFL
9 4 S
FLRRLLLRLFFLLFR
5 19 E
RRLLRRLFLLFLLRFFLRLRRLFRLFLFFLRLLFRRRF
4 5 N
LLFRLRRLRLFLLRFRRRRLFRLF
7 12 N
RLFFFLRLLRFRLRLR
8 16 S
RFLFFRLLRFFLLL
6 7 N
LLLFLLRFFFLFLLRF
4 9 S
RLRLFFFRRLRLLLRFLLRRRRLRRRR
3 18 S
RLLFRFRFRLFRFFLFFRRRLRLLRRRFFRRRRLRF
9 9 N
LLFLRLLLLLFRFFRLRL
16 11 W
LFFFLLLRRFRLFLRLFFFLRRFFLLFRRFRF
3 17 N
LLLRRFFFLLLFL
18 3 S
FLLFRLFRFR
3 1 W
LFRFRRFFLLRFRLLFRRRLFRLRFRRLFLLRRRF
1 5 N
FLLLLFRFFLRRLRLRRLF
19 18 W
RLLRLFFFLRFRFFLFRLFLRFRFRFLFRLFFL
12 5 S
LLRRFFRRLFLLRRRFRFLFRLLFLFRRFLFRLFRRRFL
12 10 W
RFLFRFFLFLFFFFLF
3 12 N
RRLRLFFRRFFLLLFFRFFLLLRRLL
9 11 W
FLRFFRRRLFLFFFLLLL
5 18 N
LLFRRFRRFRRFLFLRFFRRLLLRFLRLRRFRRLRRLL
17 2 N
LRFRRFFFLFFLLLRRLRFRLRLR
5 7 W
FRFRRLLRRL
16 16 N
RRRLFRLFRLLFFFRFFLFRLFLFFFFRF
3 6 W
RRFRRFLFRFLFRLLFFR
20 11 N
LRRFLFFFRFRFLRFFLLRLLLFRRFRLRR
13 18 S
FRRLFRLFLFFRRRLRLRFRFF
3 3 S
FFLFFFRLLRRRF
11 17 W
LLFRLFRFLLRRLLRRLLLLLFFF
8 17 W
LLFRFFLFFFLRFRFLLLRF
18 12 S
LLFLFRLFLFLRLF
18 11 W
RRFFLRRRFLFLLLRLFFRFLRLRFRFRFLRF
14 15 E
RRFLFLFRRLFFFLRRRFFFRFFFRRLFFRRFRLRL
17 20 W
LRRRFFFLFRRRRRFLRRR
2 17 N
LRRRFFFLFR
20 10 W
LRRRRLFRFRLLLRRRRR
13 8 E
RRFRLFFLRRFRLLRFFLRFRR
5 14 S
FFRFRFFRFLRLFLFRLLF
8 10 W
FFLFLRRFFRFFFRFLLRLRFFFFRFFRRFFFRRLFLL
19 1 N
FFFRFLFLLFRFRRRLFLRRRRFRRRFFLFRLRRLLLFF
4 17 E
LFFRRRLLLFRRFRLLRLFRRRRLRFLLRFFRRFLFF
13 0 E
FLLLFLLRRRR
0 4 S
LRLFRLRLFRFFLRLRFFFFLRRLLLFFFFL
13 1 W
LRLRFLRRFLFRLRFFRLRLLRFRLFLRFLLFRRR
1 10 W
RFRRRRLFRFFLRLFLFRFRFFRRLLFLFL
6 9 E
LRLLLFLLRRFFRFRRRFRRLRFRRRFFRRFRL
13 10 E
LRRRFLFLRLFRFRRRFRL
6 9 E
RLLRFRLLRL
14 1 S
FLLRRFLFRLLFFLRLFRFFRLLRFLLFFRRLFRRFF
12 15 E
LRLLRFRFFLLRRRRRRRRLRFLFFLFLR
2 20 E
RLRRRFLLFRFRFFF
7 15 E
RLLRLLRRLLFFRLFLLRLRLFLFFFRRRFLRF
16 3 N
RRRRFLRFLRFFRRRFFLFRFLRRFLFFLL
2 12 S
RFFFLLRRLRFRLFRFLLRR
7 1 N
RLLFLLLLLFLRLRLLFLFFLFRRLLFFLRLR
14 19 W
LFRFRLFLLRFLFLFRRFFFLRRFR
1 17 W
FLRLFRRFRFLFLFLRRLLRR
20 15 S
FLLLFLLRFRLFFFLFLLLL
10 7 W
LLFLFFFFFRRLRLFLRFLLLF
11 19 W
RRRFFLFFRFLRRLRLLFLFLL
19 3 W
FLFFRRLRRRFFRLRFRLRFLLFRLRRRFFRRLLRRRF
8 2 W
FFLLRLLFLRRFLLFFFRRFRFRFRLLLRLRL
14 13 N
RLRRFFLFFLLFRRFRFRRRLLLRLL
2 8 S
LFFFRFRFRLLLRLRRRL
4 18 N
LFRRFLLRFFFRLLFRLFLLLLLLLRFFRLFLFFFLLLF
20 17 E
LFLLFFLLRLLRFLFFFFLRFFRFLRRRLLRLR
8 15 S
LRLFLFRLFLRRFRLFFRLLLRRLFFRRLF
10 8 W
LLLLRFFFRRRLFRFRRRFFRFRFFLRRFFFLRFFR
4 4 S
LLRRLLFLFRLFFRRRLRLLLRLRFLR
12 7 S
FLRFLLFLRFFFLRLRFL
5 3 N
RLFLRLFRLRLLFL
0 2 S
LRLLFFFLRRRFLFFLRFLFLRFRRFRLLFL
5 4 E
RRFFRRLLFFRRLRRLLFRLFLLLLRR
11 16 S
FFLFRRFLFRRFFLFRLFRFLF
16 13 N
RFLFRLFFLLLFFRLLFLFRFFLFFFL
1 8 N
FRLRRRFFLLFL
8 10 E
LLFRFLFFRRLFRLFFLRRLFRRRLR
18 20 W
LRFFFRFRFFRFLFLFFLLRLRRLFFFLLRRF
3 6 E
LRRRLLFLFFLFRFLFRFRRLLL
20 2 N
RFRLLRLFRFFRRLFRLFLRLLLFRRF
11 9 N
FFLLLFLLLLRLRLRLFL
1 0 S
RRLRRFLLLFLFRF
15 5 N
LFLLRFFLFFFFFRFFRRLRL
0 9 E
FLRRRLRLFFFFLRLRFFLLRFRLLLLLFLLRLLLR
11 6 E
LFFFFFRLFLRLLRFF
20 13 N
FLFLFFFRLLLLRLLRFLFRLFFFLRRRFLFFLFRLF
3 6 W
FRLLRFRLFLFRRRF
7 7 W
RRRFLFLLFFRRRLRL
4 7 W
RRFFLLRRFRLRLLLLLLLLFFRRLLFFRLL
17 0 S
LLFRRRFRRFRFRLLFFFLRFFLRRLRF
10 12 S
FFRFFLFFRFLFLLFRFRRLFFLLFRRRFR


the input is generated with the following script, just in case you care, want to generate more input or w/e:

Code: Select all

#!/usr/bin/env python
# Copyright (c) 2005 Jonas Kolker
# licensed under the GNU GPL version 2 or
# (at your option) any later version
# ... google('GNU GPL')

from sys import stdout
from random import randrange, choice

dirs = "NSEW"
cmds = "FRL"
bounds = (20, 20)

print bounds[0], bounds[1]
for i in range (100):
   print randrange(0, bounds[0]+1),
   print randrange(bounds[1]+1),
   print choice(dirs)
   for i in xrange (randrange (10, 40)):
      stdout.write (choice (cmds))
   print


... thanks for saving me from becoming a nervous wreck

[teni_teni]

Maybe you already got AC...
If not, try this:

Code: Select all

1 1
0 0 N
LF

[jonaskoelker]

Nope, no AC yet.

my new implementation (in C++) gets your suggested input right: "0 0 W LOST". If any one of you have gotten AC, could you do me the favor of running my test input through your solution? Thanks in advance.

just in case you want to see the new code, here is it:

Code: Select all

# include <iostream>
# include <map>
# include <set>
# include <stdio.h>
# include <string>
# include <utility>

using namespace std;

struct point: public pair <int, int> { };
enum direction { east, north, west, south };

static struct point bounds;
static map <int, int> directions;
static set <struct point> scent;

class bot
{
private:
   struct point p;
   int direction;
   bool lost;
   struct point next () const throw () {
      struct point n = p;
      switch (direction)
      {
      case east : ++n.first ; break;
      case north: ++n.second; break;
      case west : --n.first ; break;
      case south: --n.second; break;
      default: while (1) new int [16384];
      }
      return n;
   }

   static bool inside (const struct point n) throw () {
      return (
         n.first >= 0 and
         n.first <= bounds.first and
         n.second >= 0 and
         n.second <= bounds.second);
   }

public:
   bot (const struct point _p, int theta):
      p (_p), direction (theta), lost (false)
      {}

   bool islost () const throw () { return lost; }
   void left () throw () { direction = (direction + 1) & 3; }
   void right () throw () { direction = (direction + 3) & 3; }

   void forward (void) throw () {
      const struct point n = next ();
      if (inside (n)) p = n; // if not out of bounds, goto n.firstt point
      else if (scent.find (p) == scent.end ()) // else if no scent
      {
         scent.insert (p);
         lost = true;
         printf ("%d %d %c LOST\n", p.first, p.second, directions[direction]);
      }
      // else: (if scent) do nothing.
   }

   ~bot () {
      if (not lost)
         printf ("%d %d %c\n", p.first, p.second, directions[direction]);
   }
};

int main (void)
{
   directions ['E'] = east ;
   directions ['N'] = north;
   directions ['W'] = west ;
   directions ['S'] = south;
   directions [east ] = 'E';
   directions [north] = 'N';
   directions [west ] = 'W';
   directions [south] = 'S';

   cin >> bounds.first >> bounds.second;
   struct point start;
   char theta;
   while (cin >> start.first >> start.second >> theta)
   {
      struct bot b (start, directions[theta]);
      string move;
      cin >> move;
      for (unsigned i = 0; i < move.size() and not b.islost(); ++i)
         switch (move[i])
         {
         case 'L': b.left(); break;
         case 'R': b.right(); break;
         case 'F': b.forward(); break;
         }
   }
   return false;
}


this page is best viewed in emacs.

[lantimilan]

11 12 W
14 4 W
5 17 E
20 4 E LOST
10 2 S
7 9 N
0 20 W LOST
3 5 N
6 0 E
16 6 W
9 4 W
0 18 W
5 3 E
6 15 N
7 12 W
6 9 S
4 5 W
0 19 W LOST
10 6 S
20 10 S
0 18 W
19 4 S
3 1 N
3 6 S
13 12 S
9 4 E
11 9 E
5 14 S
7 14 N
1 19 E
19 1 E
4 8 E
20 12 E LOST
4 4 S
20 11 E LOST
12 13 S
5 1 W
16 16 E
13 15 N
17 12 E
18 10 S
17 13 N
20 20 N LOST
3 14 S
20 10 E LOST
10 12 S
4 14 S
4 17 S
20 4 E
6 20 N LOST
14 0 S LOST
2 0 S LOST
11 6 E
0 13 W LOST
4 6 E
14 8 E
7 9 N
15 3 E
14 14 E
2 20 N LOST
3 18 W
11 7 E
0 12 W LOST
4 0 S LOST
12 15 N
0 18 N
20 10 E
13 11 S
14 17 S
18 0 S LOST
4 2 E
16 10 E
4 7 W
4 20 N LOST
14 18 E
13 19 E
13 10 S
1 6 N
12 10 W
4 3 E
4 5 N
1 6 S
8 16 W
15 19 S
0 9 W LOST
5 15 W
15 20 N LOST
2 10 W
20 2 E LOST
13 11 N
3 0 S LOST
19 1 W
3 3 S
9 12 W
16 6 S
1 5 E
6 6 E
7 3 E
20 0 E LOST
7 7 N

[lantimilan]

Here are some pitfalls I encounter for p118, seemingly trivial problem

1. What you code do if enum type var was assigned soemthing off bounds, e.g.
enum direction { S,N,E,W }; and enum direction dir = 5; what is dir+1 then?

2. is your buffer large enough? instructions are length 100 at most, coordinates are 50 at most

[razor_blue]

I've tried the input above and compared to the lantimilan's output.
It's absolutely identical, so I'm very confused why my code is wrong.
Does someone can help?

Code: Select all

/* removed after AC */


[Jan]

I think you havent understood the 'scent' properly. The problem states

lost robots leave a robot ``scent'' that prohibits future robots from dropping off the world at the same grid point

Check the samples...

Input:

Code: Select all

3 3
0 0 S
FFFFFF
0 0 W
FFFFFF

Output:

Code: Select all

0 0 S LOST
0 0 W

Because the first robot is dropped off from (0,0) and thus leaves a 'scent', the second robot sees the 'scent' in (0,0) and so it remains in the grid. Hope it helps.

[razor_blue]

Thank you Jan, now I understand the problem and I got AC.

[joebin]

i tried above all , but i got WA , either.
following is my code :

Code: Select all

#include<iostream>
using namespace std;
int main( int argc, char * argv[] )
{
  int a,i,j,m,n,l[51][51],x,y,p[4]={1,1,-1,-1};
  char k,d[4]={'N','E','S','W'},t[100];
  cin >>m>>n;
  for(i=0;i<=m;i++)
    for(j=0;j<=n;j++)
      l[i][j]=1;
  while(cin >>x>>y>>k!=NULL){
    j=0;i=0;a=1;
    while(d[j]!=k)
      j++;
    cin.getline(t,100);cin.getline(t,100);
    while(t[i]!='\0'){
      if(t[i]=='F'){
        if(j%2==0)
          y+=p[j];
        else
          x+=p[j];
      }
      if(t[i]=='R')
        j=(j+1)%4;
      if(t[i]=='L')
        j=(j+3)%4;
      i++;
      if(x>m||y>n||x<0||y<0){
        if((j%2==0&&l[x][y-p[j]]==0)||(j%2==1&&l[x-p[j]][y]==0)){
          if(j%2==0)
            y-=p[j];
          else
            x-=p[j];
        }
        else{
          a=0;
          if(j%2==0)
            y-=p[j];
          else
            x-=p[j];
          l[x][y]=0;
          cout <<x<<" "<<y<<" "<<d[j]<<" LOST"<<endl;
          break;
        }
      }
    }
    if(a==1)
      cout <<x<<" "<<y<<" "<<d[j]<<endl;
  }
  return 0;
}

could anyone tell me why ?? THX!!

[gareve25]

my code works with that big input, but im still getting WA, can someone tell me why...

Code: Select all

Accepeted...


I try and try this problem, for a long time, and my two errors are this:
-If the robor fall in a corner the signal have effect on 1 or 2 or 3 or 4 squares
- a newline at the end of output(!!!!!!!!!! mi long time error, frustating);

[amr saqr]

There is a mistake in the problem description

All instruction strings will be less than 100 characters in length.

when i submitted my code with a 100 char array it gave me WA, and when i changed it to 101 with the same logic it was AC

be careful ...

[Obaida]

There is no fault in the program description.
For a 100 length string you can't get Accepted by a 100 SIZE array.(Think why ).
You will get the answer.

[amr saqr]

Again ,

All instruction strings will be less than 100 characters in length.

less less less less less

that means that there will be 99 instructions at maximum not 100, so it's enough to make an array of 100 characters, 99 for the instructions and an extra char for the null character, but the 100 array didn't work, when i changed it to 101 i got AC, that's why i said there is a mistake in the problem description .