Uprising #1

This is the place for ALL of the user submitted challenges. If you create a little challenge/mission/riddle/whatever, post it here.
Forum rules
Do not post missions that you did NOT create without proper citing.

Uprising #1

Post by thetan on Sat Jan 25, 2014 3:28 pm
([msg=79103]see Uprising #1[/msg])

Been forever since i posted here. I actually don't even go by the alias "Thetan" anymore, you can find me on IRC these days as "lohkey".

Anyways, one of my favorite things to do on the site used to be post and participate in ad-hoc programming challenges here on the forum and "Uprising" is what i'm going to be calling this series i'll be curating. Anyone is welcome to participate in posting solutions, the more the merrier and discussing others solution is encouraged as well.

Uprising #1 - The Grid

The Plot
One day you wake up and you find you're a program stuck in a computer, some "Tron" type shit. The only other thing you know is that you're on a grid. You don't know how big this grid is because you can't see that far, it's dimensions are square (NxN). You see that each square has a number on it in the range of 1-9 and you know that your at the bottom of this grid and can start at any square on the bottom row. You can only move directly up and upwards diagonally (up/left and up/right) one square at a time. Every square you step on you're "wellness" degrades by the number on that square. Your goal is to make it to the top row of this grid with the least degraded wellness possible.

Trade Craft
The program you write to find the most optimal path should aim to be as efficient as possible. Any and all languages are welcome. Source code and how to run it is encouraged along with any generated output.

Move fast. Do shit that's different. Break shit.
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Uprising #1

Post by fashizzlepop on Sat Jan 25, 2014 3:52 pm
([msg=79104]see Re: Uprising #1[/msg])

Reminds me of http://projecteuler.net/problem=67

Probably could be solved by a similar algorithm.
The glass is neither half-full nor half-empty; it's merely twice as big as it needs to be.
User avatar
fashizzlepop
Developer
Developer
 
Posts: 2303
Joined: Sat May 24, 2008 1:20 pm
Blog: View Blog (0)


Re: Uprising #1

Post by Goatboy on Sat Jan 25, 2014 9:58 pm
([msg=79111]see Re: Uprising #1[/msg])

How far out can we see? Do I know that a square up 2 and left 2 has the number 9 while the square up 2 and right 2 has a 1 in it? Or can we only see a square one move away?
Assume that everything I say is or could be a lie.
1UHQ15HqBRZFykqx7mKHpYroxanLjJcUk
User avatar
Goatboy
Expert
Expert
 
Posts: 2782
Joined: Mon Jul 07, 2008 9:35 pm
Blog: View Blog (0)


Re: Uprising #1

Post by thetan on Sat Jan 25, 2014 10:33 pm
([msg=79112]see Re: Uprising #1[/msg])

There is no "fog of war" per se. The point about not being able to see that far may be a bit misleading. It was meant to convey that your solution should work with any size grid, probably took it the metaphor to far though. You can see the entire grid. It's really just a path finding problem ;)
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Uprising #1

Post by tgoe on Wed Jan 29, 2014 3:04 pm
([msg=79200]see Re: Uprising #1[/msg])

thetan! Wish you could post more on the forum. I like your challenges.
User avatar
tgoe
Contributor
Contributor
 
Posts: 633
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Uprising #1

Post by anon976 on Sun Feb 23, 2014 6:41 pm
([msg=79609]see Re: Uprising #1[/msg])

Ooooh, sounds like a fun challenge. It would also probably be good to write a short program to randomly generate said grid. I'm gonna write something in python for this, but first I wanna make sure I understand correctly. Can I see every number? I get what you mean about making an algorithm that works with any board size, but if the board was 100 x 100 could we still see all the numbers? And I can start in any column I want, but when I go up I can go straight up or up/left or up/right?
anon976
New User
New User
 
Posts: 12
Joined: Wed Jan 29, 2014 1:40 am
Blog: View Blog (0)


Re: Uprising #1

Post by pretentious on Mon Feb 24, 2014 3:31 am
([msg=79610]see Re: Uprising #1[/msg])

Code: Select all
from random import randint as rand
string = '|'
Range = rand(0,50)
for y in range(Range):
   for x in range(Range):
      string = string + str(rand(1,9)) + '|'
   print string
   string = '|'

If I read the brief correctly.
Goatboy wrote:Oh, that's simple. All you need to do is dedicate many years of your life to studying security.

IF you feel like exchanging ASCII arrays, let me know ;)
pretentious wrote:Welcome to bat country
User avatar
pretentious
Contributor
Contributor
 
Posts: 577
Joined: Wed Mar 03, 2010 12:48 am
Blog: View Blog (0)


Re: Uprising #1

Post by -Ninjex- on Mon Feb 24, 2014 7:58 am
([msg=79612]see Re: Uprising #1[/msg])

pretentious wrote:
Code: Select all
from random import randint as rand
string = '|'
Range = rand(0,50)
for y in range(Range):
   for x in range(Range):
      string = string + str(rand(1,9)) + '|'
   print string
   string = '|'

If I read the brief correctly.


If I'm correct, I think that the goal is to find the shortest path from the bottom to the top, while only being able to move up, up/left, and up/right, not to create a grid.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1204
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Uprising #1

Post by anon976 on Mon Feb 24, 2014 12:40 pm
([msg=79614]see Re: Uprising #1[/msg])

Well yes, but it would be nice to have a grid so that you can test whether or not your algorithm for getting to the top works.
Here's what I have so far. I works ok, but if I had a grid like this for example
Code: Select all
[9, 9, 0, 0]
[9, 9, 0, 0]
[9, 9, 0, 0]
[0, 1, 1, 1]


Then it would stay in the left row the whole time, because it only makes the best move for each row. So it would say 0 is the best move on the first row, but taking any of the 1's would be a much better Idea because then you get all the 0's after.
Also, if your best move is a duplicate (As in you could go up/left to a 6, up to a 4, or up/right to a 4) it would take the one furthest on the left. If there were two 6's and a 4, it would take the 4 though.

Code: Select all

import random

def main():
   n = input('enter n, and this program will make a board size, n by n: ') #Board size
   board = generate_board(n) #Creates a random board
   print_board(board) #Prints the board so that we can see it
   health_lost = 0 #Var for how much health is lost
   x , y = -1, -1 #Starting position
   string = "You started on the first "
   var = True #True until you make it to the top, makes the loop work
   while var == True:
      list = find_best_move(board, x, y) #Returns a list
      x, y = list[0], list[1] #Moves your character
      health_lost += list[2] #Takes away health
      var = list[3] #Checks if you are at the top or not
      string = string + list[4] #So that you can know what path you took
   print string + str(health_lost) + ' health.'
         
def print_board(board):
   n = len(board) - 1
   while n > -1:
      print str(board[n]) + ' = ' + str(n)
      n -= 1
            
def generate_board(n): #Randomly creates a list with n lists in it, and n random numbers
                   #in each mini list
   list = []
   for i in range(0, n):
      list.append([])
      for j in range(0, n):
         list[i].append(random.randint(0, 9))
   return list
      
def find_best_move(board, x, y): #Finds the best move
   l = len(board[0])
   try:
      smallest_num = 10
      y += 1
      if y == 0: #First row, x is undefined so far
         for i in range(0, l):
            if board[y][i] < smallest_num:
               smallest_num = board[y][i]
               x = i #x = smallest number location
      elif y < len(board): #If y is not on the first row
         if x == 0: #If you are on the left side
            if board[y][x] < smallest_num:
               smallest_num = board[y][x]
            if board[y][x+1] < smallest_num:
               smallest_num = board[y][x+1]
               x += 1
         elif x < l: #If you are in the middle
            if board[y][x-1] < smallest_num:
               smallest_num = board[y][x-1]
               x -= 1
            if board[y][x] < smallest_num:
               smallest_num = board[y][x]
            if board[y][x+1] < smallest_num:
               smallest_num = board[y][x+1]
               x += 1
         elif x == l: #If you are on the right
            if board[y][x-1] < smallest_num:
               smallest_num = board[y][x-i]
               x -= 1
            if board[y][x] < smallest_num:
               smallest_num  = board[y][x]
            
      else:
         print board[y] #This intentionally causes an index error, which is then caught
                     #by the except statement, which defines var as False and ends
                     #The Main Loop

   except IndexError:
      return (x, y-1, 0, False, 'end. You lost a total of ')
         
   return (x, y, smallest_num, True, str(smallest_num) + ', then went to the ')      

if __name__ == '__main__':
   main()


Up next, I'm gonna make it so that It checks every path possible and returns the best one, because that would be a lot more efficient then just moving to smallest number possible each time. What do you guys think?

Also, thanks a lot thetan, I loved this challenge, do you have any more?
anon976
New User
New User
 
Posts: 12
Joined: Wed Jan 29, 2014 1:40 am
Blog: View Blog (0)


Re: Uprising #1

Post by -Ninjex- on Tue Feb 25, 2014 12:32 am
([msg=79622]see Re: Uprising #1[/msg])

anon976 wrote:Well yes, but it would be nice to have a grid so that you can test whether or not your algorithm for getting to the top works.

I would agree, but I believe he was posting that source as a solution to this challenge.

anon976 wrote:Up next, I'm gonna make it so that It checks every path possible and returns the best one, because that would be a lot more efficient then just moving to smallest number possible each time. What do you guys think?


When thetan said 'You don't know how large the grid is' I think that he means the grid could be of any size, including measurements of great length. A brute force approach in my opinion would not be ideal for an extremely large grid
I think the key to this challenge is figuring out a way to efficiently sort through the grid without being constrained by the size itself.
Maybe we can get him over here to clear it up though.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1204
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)



Return to User Submitted

Who is online

Users browsing this forum: No registered users and 0 guests