• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 04:38
CEST 10:38
KST 17: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
RSL Season 1 - Final Week5[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles6[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL70
StarCraft 2
General
RSL Season 1 - Final Week RSL Revival patreon money discussion thread The GOAT ranking of GOAT rankings We need to be discussing a new patch right now! Firefly given lifetime ban by ESIC following match-fixing investigation
Tourneys
$25,000 Streamerzone StarCraft Pro Series announced RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
https://www.facebook.com/SAINTSKINVitaminCSerumCan
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
Script to open stream directly using middle click A cwal.gg Extension - Easily keep track of anyone BW General Discussion ASL20 Preliminary Maps BGH Auto Balance -> http://bghmmr.eu/
Tourneys
Small VOD Thread 2.0 [Megathread] Daily Proleagues Last Minute Live-Report Thread Resource! [BSL20] Non-Korean Championship 4x BSL + 4x China
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
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
US Politics Mega-thread Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion 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
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 526 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
Next event in 1h 22m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
mouzHeroMarine 98
StarCraft: Brood War
Sea 3822
Zeus 657
Nal_rA 512
PianO 251
Leta 249
Light 196
ToSsGirL 172
JulyZerg 166
soO 85
GoRush 59
[ Show more ]
Mind 44
NaDa 33
NotJumperer 29
Dota 2
ODPixel423
XcaliburYe379
League of Legends
JimRising 615
Counter-Strike
Stewie2K1720
Heroes of the Storm
Khaldor174
Other Games
tarik_tv488
SortOf120
Trikslyr29
Organizations
Other Games
gamesdonequick32941
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 11 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2209
Upcoming Events
RSL Revival
1h 22m
SHIN vs Clem
Cure vs TBD
FEL
3h 22m
FEL
7h 22m
Gerald vs PAPI
Spirit vs ArT
CSO Cup
7h 22m
BSL20 Non-Korean Champi…
9h 22m
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
DaveTesta Events
9h 22m
Sparkling Tuna Cup
1d 1h
RSL Revival
1d 1h
Classic vs TBD
FEL
1d 6h
BSL20 Non-Korean Champi…
1d 9h
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
[ Show More ]
Wardi Open
2 days
Replay Cast
3 days
WardiTV European League
3 days
PiGosaur Monday
3 days
uThermal 2v2 Circuit
4 days
Replay Cast
4 days
The PondCast
5 days
Replay Cast
5 days
Epic.LAN
6 days
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
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

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
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
Underdog Cup #2
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.