29
\$\begingroup\$

On the advice of Ms. Pac-Man who's worried about him getting overweight, Pac-Man has decided to keep track of his daily Pac-Dot intake. Help him count the number of Pac-Dots on a given path in the maze!

The maze

maze

To help you build your own encoding of the maze, you can get some raw data here.

Pac-Man's journey

In the context of this challenge, the following rules apply:

  • First, the good news: the ghosts aren't there.
  • Pac-Man always starts his race at the position indicated on the above picture, heading to the East. There is no Pac-Dot at the starting position.
  • As long as he's following a straight path, he keeps advancing to the next squares.
  • When he encounters a 90° turn without any other available path (orange squares on the map), he automatically and systematically takes the turn.
  • When he encounters a junction where several paths are available (green squares on the map), he may either continue on the same direction -- if applicable -- or choose another direction (including doing a U-turn).
  • When Pac-Man passes through one of the exits on the middle left or middle right side of the maze, he immediately reappears on the opposite side.
  • Pac-Man eats all the Pac-Dots on the path he's following. Once a Pac-Dot has been eaten, it is removed from the maze.

The challenge

Input

You'll be given a string describing Pac-Man's behavior on the junctions that he's going to reach. This string will be made of the following characters:

  • L: do a 90° turn to the left
  • R: do a 90° turn to the right
  • F: go forwards (no direction change)
  • B: go backwards (do a U-turn)

When all characters have been processed, Pac-Man stops at the next junction he encounters.

Output

You have to print or output the number of Pac-Dots eaten along the input path.

Rules

  • You can write a full program or a function.
  • You can take input in either uppercase or lowercase, as either a string or an array of characters. You may also use other characters (but only one character per direction) or integers in [0 .. 9]. If you do so, please specify it clearly in your answer.
  • You can assume that the input is always valid. (The jsFiddle below will detect errors, but you're not supposed to.)
  • This is code-golf, so the shortest code in bytes wins.
  • Standard loopholes are forbidden.

Hint

It may not be required nor optimal to store the exact shape of the maze.

Test cases and demo

The following test cases -- or any other input -- can be tested in this jsFiddle.

1. Input  : ""
   Output : 1
   Comment: Pac-Man just advances to the first junction, eats the Pac-Dot on it and stops.

2. Input  : "L"
   Output : 7

3. Input  : "FFR"
   Output : 13

4. Input  : "LFLR"
   Output : 17
   Comment: Pac-Man will exit on the middle right side and re-appear on the left side.

5. Input  : "BBBB"
   Output : 2

6. Input  : "BRRFFFL"
   Output : 15

7. Input  : "LFFRLFFFFRF"
   Output : 50

8. Input  : "BRFRLRFRLFR"
   Output : 54
   Comment: Pac-Man will exit on the middle left side and re-appear on the right side.

9. Input  : "FFLRLFFLLLLFFBFLFLRRRLRRFRFLRLFFFLFLLLLFRRFBRLLLFBLFFLBFRLLR"
   Output : 244
   Comment: All cleared!
\$\endgroup\$
  • 1
    \$\begingroup\$ Here's some more data to help out: pastebin.com/G4MnbVww . It's a list of every junction and the number of pac-dots on the road to the next junction depending on which direction you go (0=up, 1=left, 2=down, 3=right). There might be some errors, and keep in mind that junctions 12, 13, 15, 16, 18, and 19 have no dot in the middle, while all the others do. \$\endgroup\$ – Esolanging Fruit Apr 4 '17 at 1:23
  • \$\begingroup\$ @Challenger5 This is looking good. Because the moves are relative, you'd probably want to also keep track of the new orientation of Pac-Man when the next junction is reached, though. \$\endgroup\$ – Arnauld Apr 4 '17 at 2:30
  • \$\begingroup\$ BTW In the game pac man cannot do a u-turn \$\endgroup\$ – Matthew Roh Apr 4 '17 at 6:57
  • 4
    \$\begingroup\$ @SIGSEGV By 'u-turn', I just mean changing to the opposite direction, which is possible at any time in the original arcade game and all the clones I know. Should I use another term? \$\endgroup\$ – Arnauld Apr 4 '17 at 7:16
  • \$\begingroup\$ I'm pretty sure Pac-Man started heading left in the arcade game, not right. \$\endgroup\$ – mbomb007 Apr 4 '17 at 20:40
10
\$\begingroup\$

Pyth, 356 345 + 1 = 346 bytes

The code contains some unprintables, so here is the reversible xxd hexdump.

0000000: 4a4b 304c 2c3d 2b4b 4062 4a58 624a 3041  JK0L,=+K@bJXbJ0A
0000010: 2c63 6a43 2201 e120 49b4 efbc e267 27f4  ,cjC".. I....g'.
0000020: a11b f5d5 7f79 d1a0 ab8a 7689 449f 0c50  .....y....v.D..P
0000030: b2d4 7c30 99c3 368e aa67 4213 ab9b d276  ..|0..6..gB....v
0000040: d75f 6e99 5757 04a6 08cc 99d0 7141 3d2f  ._n.WW......qA=/
0000050: d854 7cf7 4a70 954e 6e35 f9b9 e0c5 1d53  .T|.Jp.Nn5.....S
0000060: 36d5 63f9 cf13 0f66 c113 4dec 956e 5225  6.c....f..M..nR%
0000070: b14a 1659 dcb5 6822 3534 2034 6a43 2203  .J.Y..h"54 4jC".
0000080: ffe3 8fff 2232 3d59 636a 4322 0b8a 4624  ...."2=YcjC"..F$
0000090: 7815 4a94 192c 79f6 d6e5 e098 5e97 76bc  x.J..,y.....^.v.
00000a0: 23cf 027c 35c5 5098 2a83 68f1 823a 83f6  #..|5.P.*.h..:..
00000b0: dfa4 7e12 443f 0257 7adb ab2d 8e6f 1199  ..~.D?.Wz..-.o..
00000c0: 9a3e 3f9d a524 d331 c5ff 94ae e5a2 3507  .>?..$.1......5.
00000d0: bd22 3334 2032 3d6b 2b30 6a43 2202 25f2  ."34 2=k+0jC".%.
00000e0: f55c 2252 c250 0002 c250 0000 065c 225c  .\"R.P...P...\"\
00000f0: 2247 5289 3698 4227 5350 8822 3136 3d64  "GR.6.B'SP."16=d
0000100: 636a 4322 8223 a80e 5c22 981d d272 729d  cjC".#..\"...rr.
0000110: d88d 981d 5c22 5c22 2bd7 91dd 9428 73d7  ....\"\"+....(s.
0000120: 1dd7 2234 2032 5651 2079 483d 547e 4a40  .."4 2VQ yH=T~J@
0000130: 4047 4a2b 5a78 2246 5242 4c22 4e20 796b  @GJ+Zx"FRBL"N yk
0000140: 3d5a 4040 647e 4a40 4059 4a3d 5421 7840  =Z@@d~J@@YJ=T!x@
0000150: 594a 5454 2968 7948 0a                   YJTT)hyH.

Requires the -M flag to disable memoization. Unfortunately, this can't be done in any online executor I know of.

Here is a readable printable ASCII version:

JK0L,=+K@bJXbJ0A,cj746957013238413906925468440008893181365431681519974815772691846219267045007717553452313017550830370829477591340658010575885616582299429376501117428763541235628345630376341520044712982918668584832091126800263024965443560007480163218792 54 4j17178005503 2=Ycj664551201217474826979459068682259492333017695780569003557724234375880492114440213266014621594427584622393511454741615093293082181365458295035985321888753898774398909 34 2=k+0j883734055588186287049718559289059922762611092840989558085734536 16=dcj53536195844172273707047543644202986760006840011986146398708374999 4 2VQ yH=T~J@@GJ+Zx"FRBL"N yk=Z@@d~J@@YJ=T!x@YJTT)hyH

Explanation

This is very much work in progress, so I won't post a complete explanation yet.

Basically, the program represents the board as a (somewhat weird) graph using five lookup tables: 2 for connectivity, 1 for junction directions, and 2 for dot counts. This was built by a 200-line Python script I spent way too many hours on. Then the program just walks through the input and counts the dots, updating the dot tables to zero as the dots are collected.

TODO:

  • Write Python routine for reordering the nodes until the lookup table contains as few escape-requiring characters as possible
  • Try to remove section handling altogether (should remove one lookup table)
    • UPDATE: tried this, seems to not remove the table and lengthen code
  • Rewrite Pyth-side logic (the current one isn't very golfed)
    • UPDATE: somewhat done, code's still imperfect
\$\endgroup\$
  • \$\begingroup\$ Why don't you just generate the URL so that you can run the real code on TIO? Maybe Dennis should add an easier way to do that. \$\endgroup\$ – mbomb007 Apr 4 '17 at 20:42
  • \$\begingroup\$ @mbomb007 TIO doesn't support test suites (for Pyth, anyway), so I like to use Pyth's own host. Also, I'm not very confident with browsers handling null bytes correctly. \$\endgroup\$ – PurkkaKoodari Apr 4 '17 at 20:44
  • \$\begingroup\$ For the non-test suite, you could. And you can still code with nulls, you just can't copy/paste them, which is why you have to generate the URL. \$\endgroup\$ – mbomb007 Apr 4 '17 at 20:45
  • \$\begingroup\$ Longest Pyth answer yet? \$\endgroup\$ – Luis Mendo Apr 4 '17 at 22:06
  • \$\begingroup\$ @LuisMendo At least for me, based on a quick search. :~) \$\endgroup\$ – PurkkaKoodari Apr 4 '17 at 22:09
2
+150
\$\begingroup\$

k, 264 bytes

b:,/16 16\'108_a:-135#0+1:"p.k"
(#(?27,r 1)^(12+!8)^14 17)+/b@?*|r:+1 27 0{i:a?64/(4!2+y+*x;x 1);(4 64\a i+1-2*2!i),_i%2}\0:""
\
...binary data...

Hex dump:

$ xxd p.k
00000000: 623a 2c2f 3136 2031 365c 2731 3038 5f61  b:,/16 16\'108_a
00000010: 3a2d 3133 3523 302b 313a 2270 2e6b 220a  :-135#0+1:"p.k".
00000020: 2823 283f 3237 2c72 2031 295e 2831 322b  (#(?27,r 1)^(12+
00000030: 2138 295e 3134 2031 3729 2b2f 6240 3f2a  !8)^14 17)+/b@?*
00000040: 7c72 3a2b 3120 3237 2030 7b69 3a61 3f36  |r:+1 27 0{i:a?6
00000050: 342f 2834 2132 2b79 2b2a 783b 7820 3129  4/(4!2+y+*x;x 1)
00000060: 3b28 3420 3634 5c61 2069 2b31 2d32 2a32  ;(4 64\a i+1-2*2
00000070: 2169 292c 5f69 2532 7d5c 303a 2222 0a5c  !i),_i%2}\0:"".\
00000080: 0a02 4005 c006 4109 c103 8008 8143 c244  ..@...A......C.D
00000090: c345 c446 c547 c648 c749 c84a 820a 830c  .E.F.G.H.I.J....
000000a0: 840d 870b 8889 cb0e 8a11 8b0f 4c4d cc10  ............LM..
000000b0: cd4e d14f ce51 d014 8e12 8f13 9017 9153  .N.O.Q.........S
000000c0: d215 9216 931e 5455 d41a d51b 5657 d61f  ......TU....VW..
000000d0: d718 941d 9759 d85a d95b da5c db5d dc98  .....Y.Z.[.\.]..
000000e0: de20 9921 9c5f 9d5e 60df e161 e089 9833  . .!._.^`..a...3
000000f0: 4222 2247 2662 7550 0000 0500 5000 c255  B""G&buP....P..U
00000100: 2c22 2202 2588 5ff2                      ,"".%._.

The binary data at the end encodes two arrays:

  • a consists of pairs of bytes, each representing (64*direction)+junctionId

  • b is the number of Pacman dots between each pair of junctions in a

The program reads its own source file (p.k) and decodes the data.

The input comes from stdin and uses 0x00,0x01,0x02,0x03 (a.k.a. NUL,SOH,STX,ETX - the first four ASCII codes) instead of FLBR.

I use my own implementation of k which is limited, bloated, crashy, and slow compared to the real thing. I test with the following program:

t:{e:($y),"\n"; a:`sys[("/path/to/k";"./p.k");`c$"FLBR"?x]
   1@$[a~e;"ok\n";"failed ",x,"\n expected: ",e," actual: ",a,"\n"];}
t["";1]
t[,"L";7]
t["FFR";13]
t["LFLR";17]
t["BBBB";2]
t["BRRFFFL";15]
t["LFFRLFFFFRF";50]
t["BRFRLRFRLFR";54]
t["FFLRLFFLLLLFFBFLFLRRRLRRFRFLRLFFFLFLLLLFRRFBRLLLFBLFFLBFRLLR";244]
\
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.