• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 16:38
CEST 22:38
KST 05:38
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Weekly Cups (June 30 - July 6): Classic Doubles2[BSL20] Non-Korean Championship 4x BSL + 4x China9Flash Announces Hiatus From ASL66Weekly Cups (June 23-29): Reynor in world title form?14FEL Cracov 2025 (July 27) - $8000 live event22
StarCraft 2
General
The GOAT ranking of GOAT rankings The SCII GOAT: A statistical Evaluation Weekly Cups (June 23-29): Reynor in world title form? Weekly Cups (June 30 - July 6): Classic Doubles Program: SC2 / XSplit / OBS Scene Switcher
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays Korean Starcraft League Week 77
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
ASL20 Preliminary Maps [ASL19] Finals Recap: Standing Tall SC uni coach streams logging into betting site Flash Announces Hiatus From ASL BW General Discussion
Tourneys
[BSL20] Non-Korean Championship 4x BSL + 4x China [BSL20] Grand Finals - Sunday 20:00 CET CSL Xiamen International Invitational The Casual Games of the Week Thread
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Path of Exile What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Stop Killing Games - European Citizens Initiative US Politics Mega-thread Russo-Ukrainian War Thread Summer Games Done Quick 2024! Summer Games Done Quick 2025!
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion 2024 - 2025 Football Thread NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 589 users

[Math Puzzle] Day13 - Page 2

Blogs > evanthebouncy!
Post a Reply
Prev 1 2 3 4 Next All
illu
Profile Blog Joined December 2008
Canada2531 Posts
Last Edited: 2009-06-08 04:42:51
June 08 2009 04:37 GMT
#21
On June 08 2009 13:32 evanthebouncy! wrote:
Show nested quote +
On June 08 2009 13:27 illu wrote:
Pretty easy.

+ Show Spoiler +

Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:

1. At each position, move to any of the other possible positions that are not walls.

Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.

The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.


Too technical, i have no clue what you just said.
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.


You said it's more or less computer science. This is really standard stuffs. In fact I am not even a computer scientist and I know it.

EDIT:
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.

That is irrevalent. So long as there is one possible path for an exit in finite time non-deterministic turing machine will give a pass. Try wiki on turing machines first.
:]
Zozma
Profile Blog Joined November 2008
United States1626 Posts
June 08 2009 04:38 GMT
#22
Alright... I don't have anything yet, but a few observations are:

The sequence has to include up, right, left, and down, otherwise you can be trapped.

There has to be net motion in one direction in the case of a 1000x1000 maze with no walls or something.

Up, right, left, down does not work. In other words, you need multiple moves to up, right, left, down in some sequence?

If this is something I had no chance of getting in the first place, I would be pretty sad. It's midnight, so I'm going to try again tomorrow.



evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
June 08 2009 04:41 GMT
#23
On June 08 2009 13:37 illu wrote:
Show nested quote +
On June 08 2009 13:32 evanthebouncy! wrote:
On June 08 2009 13:27 illu wrote:
Pretty easy.

+ Show Spoiler +

Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:

1. At each position, move to any of the other possible positions that are not walls.

Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.

The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.


Too technical, i have no clue what you just said.
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.


You said it's more or less computer science. This is really standard stuffs. In fact I am not even a computer scientist and I know it.

I c, lemme do some search on it.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
ven
Profile Blog Joined December 2008
Germany332 Posts
Last Edited: 2009-06-08 04:48:31
June 08 2009 04:46 GMT
#24
On June 08 2009 13:37 Macavenger wrote:
Show nested quote +
On June 08 2009 13:32 evanthebouncy! wrote:
On June 08 2009 13:27 illu wrote:
Pretty easy.

+ Show Spoiler +

Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:

1. At each position, move to any of the other possible positions that are not walls.

Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.

The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.


Too technical, i have no clue what you just said.
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.

+ Show Spoiler +
It's been a couple years since I worked with Turning machines and non-determinism, so I'm a bit rusty, but reading his solution, I'm quite certain it correctly proves the existence of an algorithm. Non-deterministic Turing Machines can do some pretty interesting things, and can easily have paths that lead nowhere, which would be the equivalent of attempting to move into a wall.

His approach doesn't work. He can't move into a direction that isn't a wall because he doesn't know where they are. Even if he knew where the walls were it wouldn't be much different from a NDTM that moved into any direction at all and it would accept. This is nothing else than using a random direction every step.
You can reach the rainbow. I'll be there to help.
illu
Profile Blog Joined December 2008
Canada2531 Posts
June 08 2009 04:51 GMT
#25
On June 08 2009 13:46 ven_ wrote:
Show nested quote +
On June 08 2009 13:37 Macavenger wrote:
On June 08 2009 13:32 evanthebouncy! wrote:
On June 08 2009 13:27 illu wrote:
Pretty easy.

+ Show Spoiler +

Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:

1. At each position, move to any of the other possible positions that are not walls.

Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.

The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.


Too technical, i have no clue what you just said.
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.

+ Show Spoiler +
It's been a couple years since I worked with Turning machines and non-determinism, so I'm a bit rusty, but reading his solution, I'm quite certain it correctly proves the existence of an algorithm. Non-deterministic Turing Machines can do some pretty interesting things, and can easily have paths that lead nowhere, which would be the equivalent of attempting to move into a wall.

His approach doesn't work. He can't move into a direction that isn't a wall because he doesn't know where they are. Even if he knew where the walls were it wouldn't be much different from a NDTM that moves into any direction at all and it would accept. This is nothing else than using a random direction every step.


But there is always one way to exit, so when we expand our tree diagram we will have one accepting state somewhere. So I think my NDTM will accept any solvable mazes.
:]
Macavenger
Profile Blog Joined January 2008
United States1132 Posts
June 08 2009 04:55 GMT
#26
ven brings up a good point that it might be equivalent to a random solution, though.

Need to be less rusty, argh D:
ven
Profile Blog Joined December 2008
Germany332 Posts
Last Edited: 2009-06-08 05:01:50
June 08 2009 04:58 GMT
#27
That's not the issue. Your turing machine would work with information that it doesn't have (where the walls are). Also as far as I understand the question we have to provide a deterministic algorithm to solve the maze which your non-deterministic TM doesn't do. :o
You can reach the rainbow. I'll be there to help.
Zozma
Profile Blog Joined November 2008
United States1626 Posts
Last Edited: 2009-06-08 05:13:39
June 08 2009 05:10 GMT
#28
Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this:

+ Show Spoiler +
Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes.
(For instance, in a 100x100 maze, you would move right 101 times first, and then move down 101 times, or move left 101 times and then down 101 times, or whatever. Thus, you can exit the maze if it's "blank")

Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape where the robot can move 50 times left, 0 times upward, 50 times right, 0 times downward- if he gets stuck in two shapes like [ and ].

To counter that, inject a random single move in any direction between every two long moves.


Even if this isn't it, hopefully I'm at least on to something.
ven
Profile Blog Joined December 2008
Germany332 Posts
June 08 2009 05:13 GMT
#29
On June 08 2009 14:10 Zozma wrote:
Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this:

+ Show Spoiler +
Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes. Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape like

[ r ]

R is the robot. He moves left 50 times or something, moves up forty times, and then moves right 50 times: an infinite loop.

To counter that, inject a random single move in any direction between every two long moves.


Even if this isn't it, hopefully I'm at least on to something.

You don't know the maximum number. I had a similar idea but without knowing how many times you can move you wouldn't know when to stop.
You can reach the rainbow. I'll be there to help.
Zozma
Profile Blog Joined November 2008
United States1626 Posts
Last Edited: 2009-06-08 05:15:14
June 08 2009 05:14 GMT
#30
+ Show Spoiler +
Yeah you do... Because the grid is only MxN, you can just use those numbers, right? If he runs into a wall, it's all good, he'll just stop there and continue going eventually in the next direction.
ven
Profile Blog Joined December 2008
Germany332 Posts
June 08 2009 05:17 GMT
#31
On June 08 2009 12:05 evanthebouncy! wrote:
The fine print:
By ANY valid maze it means that regardless of size of m, n, and regardless of maze design, the robot will be able to move outside the maze eventually. That is to say, while you are coding, you cannot assume a certain m, n, or design.

You can reach the rainbow. I'll be there to help.
Macavenger
Profile Blog Joined January 2008
United States1132 Posts
June 08 2009 05:18 GMT
#32
Yeah, not knowing m and n for the given maze really makes this more challenging. The only direction I can think to go with it at this point is some kind of spiraling thing, where you loop from 1 to k steps in each direction, then from k to 1, then increment k and repeat. Then you have to come up with some kind of crazy reordering of directions you're trying to avoid the collection points trap we were discussing early, I would think.
ven
Profile Blog Joined December 2008
Germany332 Posts
June 08 2009 05:19 GMT
#33
Yeah, I had the same idea of spiraling movement in my mind. Those pesky walls totally disrupting it of course :p
You can reach the rainbow. I'll be there to help.
Muirhead
Profile Blog Joined October 2007
United States556 Posts
Last Edited: 2009-06-08 05:55:46
June 08 2009 05:44 GMT
#34
+ Show Spoiler +
Suppose we are given the maze but not the starting position. Then we can solve the puzzle by looking at each possible starting position in turn. In short, we pick some box and assume the robot started there, giving it commands to solve the puzzle. Then, we pick a second box to assume the robot started in, see where the robot would be after our commands based on the first assumption, and give it commands to exit the maze. Etc.

Since the set of possible mazes is countable, we can adjoin the solutions for every given maze end to end and be done.
starleague.mit.edu
moriya
Profile Joined March 2009
United States54 Posts
Last Edited: 2009-06-08 07:01:28
June 08 2009 06:06 GMT
#35
Now I doubt that within finite steps the solution can be achieved...

The spiral path may be promising solution, if there exsits a solution.
evandi
Profile Joined June 2008
United States266 Posts
June 08 2009 06:25 GMT
#36
On June 08 2009 14:13 ven_ wrote:
Show nested quote +
On June 08 2009 14:10 Zozma wrote:
Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this:

+ Show Spoiler +
Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes. Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape like

[ r ]

R is the robot. He moves left 50 times or something, moves up forty times, and then moves right 50 times: an infinite loop.

To counter that, inject a random single move in any direction between every two long moves.


Even if this isn't it, hopefully I'm at least on to something.

You don't know the maximum number. I had a similar idea but without knowing how many times you can move you wouldn't know when to stop.


You don't have to know the maximum number. If you could guarantee that you had an algorithm capable of solving it for a given width/height you could run some loops varying the width height, increasing the maximum number the width and height can take each run through and then running the algorithm for those values. You would have to cover all of the possible width height combinations until you actually get to the real width/height.
evandi
Profile Joined June 2008
United States266 Posts
June 08 2009 07:09 GMT
#37
On June 08 2009 15:06 moriya wrote:
Now I doubt that within finite steps the solution can be achieved...

The spiral path may be promising solution, if there exsits a solution.


Muirhead solved it.
omG.[RaYnE]
Profile Joined October 2007
Philippines100 Posts
June 08 2009 07:18 GMT
#38
sure hope the op has an answer not just a trick question that has no answer to it
omG.[RaYnE] ---> rayne_ph :D
Monoxide
Profile Blog Joined January 2007
Canada1190 Posts
June 08 2009 09:33 GMT
#39
On June 08 2009 16:18 omG.[RaYnE] wrote:
sure hope the op has an answer not just a trick question that has no answer to it


evan's questions are always legit. Most of them are difficult(to me at least), but all of them have "real" answers.
DeathSpank
Profile Blog Joined February 2009
United States1029 Posts
June 08 2009 09:52 GMT
#40
+ Show Spoiler +
easy. bruteforce this shit. put your instructions in a dynamic array. Go through all the possibilities of instructions for the current size of the the array. ++the size of the array and you'll have it... eventually.
yes.
Prev 1 2 3 4 Next All
Please log in or register to reply.
Live Events Refresh
RotterdaM Event
16:00
Rotti Stream Rumble 4k Edition
RotterdaM927
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 927
StarCraft: Brood War
firebathero 211
Bonyth 144
Rock 19
Stormgate
NightEnD21
Dota 2
Pyrionflax223
League of Legends
Grubby4463
Counter-Strike
ScreaM1921
Fnx 1725
fl0m1621
shoxiejesuss1008
flusha376
oskar269
sgares142
Super Smash Bros
PPMD80
Heroes of the Storm
Liquid`Hasu562
Other Games
summit1g5909
tarik_tv2303
B2W.Neo753
mouzStarbuck285
KnowMe179
ToD165
Hui .123
Mew2King103
Trikslyr69
ZombieGrub66
Sick45
Organizations
Other Games
gamesdonequick54013
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 22 non-featured ]
StarCraft 2
• kabyraGe 254
• LUISG 31
• davetesta29
• Reevou 1
• musti20045 1
• Kozan
• sooper7s
• AfreecaTV YouTube
• intothetv
• Migwel
• IndyKCrew
• LaughNgamezSOOP
StarCraft: Brood War
• 80smullet 17
• Eskiya23 15
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
League of Legends
• Jankos2365
• TFBlade1410
Other Games
• imaqtpie1852
• Shiphtur522
• WagamamaTV200
Upcoming Events
Replay Cast
3h 22m
Sparkling Tuna Cup
13h 22m
WardiTV European League
19h 22m
MaNa vs sebesdes
Mixu vs Fjant
ByuN vs HeRoMaRinE
ShoWTimE vs goblin
Gerald vs Babymarine
Krystianer vs YoungYakov
PiGosaur Monday
1d 3h
The PondCast
1d 13h
WardiTV European League
1d 15h
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
uThermal 2v2 Circuit
1d 19h
Replay Cast
2 days
RSL Revival
2 days
ByuN vs SHIN
Clem vs Reynor
Replay Cast
3 days
[ Show More ]
RSL Revival
3 days
Classic vs Cure
FEL
3 days
RSL Revival
4 days
FEL
4 days
FEL
4 days
BSL20 Non-Korean Champi…
4 days
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
Sparkling Tuna Cup
5 days
RSL Revival
5 days
FEL
5 days
BSL20 Non-Korean Champi…
5 days
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Liquipedia Results

Completed

BSL Season 20
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.