none
Challenge of the Month - March 2012

    การสนทนาทั่วไป

  • Welcome to the monthly SmallBasic Challenge! 

    These challenges are intended for people who are learning to program or for more experienced programmers who want to start using SmallBasic after using a different language.  Some will be easy, some will be hard - but they will all make you think, and more importantly be GREAT FUN!

    Please post your solutions / partial solutions / questions / feedback etc. into this thread that will remain 'sticky' for the month.  The only rule is that your solution must use standard SmallBasic methods (no extensions).

    It would be good if people could post their problems with these challenges so that a discussion can start so that everyone can learn from each other.

    Easy Challenge 1

    Write a number guessing gameThe program selects a random number between 1 and 100 and asks the player to guess it.  The program then checks the input and states if it is too high, too low or correct.  If it is correct then the player is told how many guesses they took and asked if they want to play again, if it is incorrect they get another guess.

    Easy Challenge 2

    Ask the user to input some characters and the program outputs them in alphabetical order.  For example:

    Input: hyeldksnsy

    Output: dehklnssyy

    Easy Challenge 3

    Draw a spiral in the GraphicsWindow.

    Intermediate Challenge 1

    Create a dominoes game between two players, or possibly between the computer and a human player.

    Intermediate Challenge 2

    Create a program in the GraphicsWindow that shows the Earth orbiting the Sun.  Then add the Moon orbiting the Earth and a rocket orbiting the Moon.

    Advanced Challenge

    Create some random points with x and y coordinates (say about 20 points).  Then write a program to find the order in which to join all of the points with straight lines with the shortest total length.

    As a test you can use your algorithm on these coordinates.

    138, 211
    546, 102
    105, 264
    92, 100
    215, 383
    511, 307
    151, 347
    376, 276
    76, 468
    52, 368
    260, 501
    459, 336
    410, 143
    461, 58
    316, 454
    468, 93
    535, 162
    456, 324
    162, 231
    391, 283

     

    Do you have an idea for a future challenge? Please post it here!

    2 มีนาคม 2555 17:54

ตอบทั้งหมด

  • Re: Easy challenge 3.. this should *sometimes* draw a spiral, sometimes something more interesting

    ' Spirograph, sort of


    continue = 1
    GraphicsWindow.MouseDown = OnHalt


    While (continue = 1)
      GraphicsWindow.Clear()
      radius = Math.Min(GraphicsWindow.Height, GraphicsWindow.Width) / 2
      stepSize = Math.GetRandomNumber(100)/100 + 0.15
      radian = Math.GetRandomNumber(180) + 45
      lastX = radius
      lastY = radius
      nextRadian = radian
      GraphicsWindow.PenColor = GraphicsWindow.GetRandomColor()


      For r = 0 to radius Step stepSize
        nextX = r*Math.Cos(nextRadian) + radius
        nextY = r*Math.Sin(nextRadian) + radius
          
        GraphicsWindow.DrawLine(lastX, lastY, nextX, nexty)
        lastX = nextX
        lastY = nextY
        nextRadian = nextRadian + radian
      EndFor
      Program.Delay(1500)
    EndWhile


    Sub OnHalt
      continue = 0
    EndSub

    2 มีนาคม 2555 19:31
  • A little of a twist on Intermediate 2 -- the inner solar system [minus Phobos and Deimos :( ]

    ' Orbits
    ' Not to scale, obviously...


    earthDistance = 400
    earthDiameter = 20


    GraphicsWindow.Width = earthDistance * 1.8
    GraphicsWindow.Height = earthDistance * 1.8
    GraphicsWindow.MouseDown = EndProgram
    GraphicsWindow.BackgroundColor = "Black"
    GraphicsWindow.PenColor = "White"
    GraphicsWindow.PenWidth = 0.3




    DrawSol()


    continue = 1
    day = 0
    While (continue = 1)
      UpdateMercury()
      UpdateVenus()
      UpdateEarth()
      UpdateMars()
      Program.Delay(30)
      day = day + 1
    EndWhile




    Sub EndProgram
      continue = 0
    EndSub


    Sub DrawSol
      p["name"] = "Sol"
      p["angle"] = 0
      p["planetDiameter"] = 80
      p["distance"] = 0
      p["color"] = "Yellow"
      DrawPlanet()
    EndSub


    Sub UpdateMercury
      p["name"] = "Mercury"
      p["angle"] = 360 * -day / 116 
      p["distance"] = earthDistance * 0.38
      p["planetDiameter"] = earthDiameter * 0.383
      p["color"] = "Brown"
      DrawPlanet()
    EndSub


    Sub UpdateVenus
      p["name"] = "Venus"
      p["angle"] = 360 * -day / 225 
      p["distance"] = earthDistance * 0.723
      p["planetDiameter"] = earthDiameter * 0.95
      p["color"] = "Tan"
      DrawPlanet()
    EndSub


    Sub UpdateEarth
      p["name"] = "Earth"
      p["angle"] = 360 * -day / 365.25 
      p["planetDiameter"] = earthDiameter
      p["distance"] = earthDistance
      p["color"] = "Blue"
      DrawPlanet()
      UpdateLuna()
    EndSub


    Sub UpdateMars
      p["name"] = "Mars"
      p["angle"] = 360 * -day / 780 
      p["planetDiameter"] = earthDiameter * 0.533
      p["distance"] = earthDistance * 1.67
      p["color"] = "Red"
      DrawPlanet()
    EndSub


    Sub UpdateLuna
      p["name"] = "Luna"
      p["angle"] = 360 * -day / 27.3
      p["planetDiameter"] = earthDiameter * 0.273
      p["distance"] = earthDistance * 0.15
      p["color"] = "White"
      p["centerX"] = p["EarthpriorX"] + earthDiameter/2
      p["centerY"] = p["EarthpriorY"] + earthDiameter/2
      p["drawOrbit"] = 0
      DrawPlanetoid()
    EndSub


    Sub DrawPlanet
      distance = p["distance"]
      diameter = p["planetDiameter"]
      p["centerX"] = (GraphicsWindow.Width-diameter)/2  
      p["centerY"] = (GraphicsWindow.Height-diameter)/2
      p["orbitCenterX"] = (GraphicsWindow.Width-distance)/2
      p["orbitCenterY"] =(GraphicsWindow.Height-distance)/2
      p["orbitColor"] = "White"
      p["drawOrbit"] = 1
      DrawPlanetoid()
    EndSub


    Sub DrawPlanetoid
      distance = p["distance"]
      diameter = p["planetDiameter"]
      angle = p["angle"] * Math.Pi / 180  ' Convert to radians
      leftX = Math.Cos(angle) * distance/2 + p["centerX"]
      topY = Math.Sin(angle) * distance/2 + p["centerY"]
      
      ' Clear old position
      priorX = p[p["name"] + "priorX"]
      priorY = p[p["name"] + "priorY"]
      GraphicsWindow.BrushColor = GraphicsWindow.BackgroundColor
      GraphicsWindow.FillRectangle(priorX, priorY, diameter+1, diameter+1)  
      
      ' redraw path
      If (p["drawOrbit"] <> 0) Then
        DrawOrbit()
      EndIf
      
      ' Draw current position
      GraphicsWindow.BrushColor = p["color"]
      GraphicsWindow.FillEllipse(leftX, topY, diameter, diameter)  
      
      ' Store current position as the prior
      p[p["name"] + "priorX"] = leftX
      p[p["name"] + "priorY"] = topY  
    EndSub


    Sub DrawOrbit
      distance = p["distance"]  
      GraphicsWindow.PenColor = p["orbitColor"]
      GraphicsWindow.PenWidth = 0.1
      GraphicsWindow.DrawEllipse(p["orbitCenterX"], p["orbitCenterY"], distance, distance)
    EndSub
      

    2 มีนาคม 2555 21:30
  • Re the advanced challenge:

    ' An attempt to find the Minimum Spanning Tree
    ' based on Prim's Algorithm
    ' [ that's Robert C. Prim, *not* Prim Everdeen]
    '
    ' Reference: 
    ' Cormen, Thomas H.; Leiserson, Charles E.; and Rivest, Ronald L
    ' Introduction to Algorithms
    ' The MIT Press and McGraw-Hill Book Company, 1990
    ' ISBN 0-262-03141-8 (MIT Press), ISBN 0-07-013143-0 (McGraw-Hill)
    ' Section 24.2 The algorithms of Kruskal and Prim


    range = 500
    margin = 100
    vertices = 20


    ' Setup a black background with room for all the points
    GraphicsWindow.BackgroundColor = "Black"
    GraphicsWindow.Height = range + margin
    GraphicsWindow.Width = range + margin


    GenerateGraph()
    RunGreedy()
    RunPrim()
    ShowVertices()
    TextWindow.WriteLine("Results: greedy score=" + greedyTotal + " vs Prim score=" + primTotal)


    Sub GenerateGraph
      ' Randomly generate vertices
      For i = 1 To vertices
        x[i] = Math.GetRandomNumber(range) + margin/2
        y[i] = Math.GetRandomNumber(range) + margin/2
      EndFor


      ' Find the cost of going from onve vertex tgo another
      For i = 1 To vertices
        For j = 1 To vertices
          edge[i][j] = Math.SquareRoot(Math.Power(x[i]-x[j],2) + Math.Power(y[i]-y[j], 2))
        EndFor
      EndFor
    EndSub


    ' This greedy algorithm runs through each vertex, finding the lowest cost to traverse
    ' to another vertex not already in the path...
    Sub RunGreedy
      greedyTotal = 0
      GraphicsWindow.PenWidth=3
      GraphicsWindow.PenColor = "Red"
      For i = 1 To vertices
        smallest = (range+margin) * 2
        For j = i+1 To vertices
          If (edge[i][j] < smallest) Then
            smallest = edge[i][j]
            origin = i
            destination = j
          EndIf
        EndFor
        GraphicsWindow.DrawLine(x[origin], y[origin], x[destination], y[destination])
        greedyTotal = greedyTotal + edge[origin][destination]
      EndFor
    EndSub


    ' An attempt to implement Prim's algorithm
    Sub RunPrim
      GraphicsWindow.PenWidth=1
      GraphicsWindow.PenColor = "Blue"
      
      ' Begin by setting all vertices outside the connected graph
      For i = 1 To vertices
        connected[i] = 0  
      EndFor
      
     
      ' Pick the first vertex (arbitrary), and add it to the connected graph
      connected[1] = 1
      
      primTotal = 0
      fullyConnected = 0
      ' Keep running the algorithm until the graph is fully connected
      While (fullyConnected = 0)
        smallest = (range + margin) * 2
        
        ' Traverse all of the vertices in the currently connected graph
        ' and find the least expensive edge to add another vertex not already in it
        For i = 1 To vertices
          If (connected[i] = 1) Then
            For j = 1 to vertices
              If (j <> i And edge[i][j] < smallest and connected[j] = 0) Then
                smallest = edge[i][j]
                fromVertex = i
                toVertex = j
              EndIf
            EndFor
          EndIf
        EndFor
        
        ' Connect the new node, and tally its cost
        connected[toVertex] = 1
        primTotal = primTotal + edge[fromVertex][toVertex]
        GraphicsWindow.DrawLine(x[fromVertex], y[fromVertex], x[toVertex], y[toVertex])
        
        ' Determine if all nodes are connected to the graph
        fullyConnected = 1
        For i = 1 to vertices
          If (connected[i] = 0) Then
            fullyConnected = 0
          EndIf
        EndFor  
      EndWhile 
    EndSub


    Sub ShowVertices
      size = 6
      GraphicsWindow.PenColor="White"
      For i = 1 To vertices
        GraphicsWindow.DrawEllipse(x[i]-size/2, y[i]-size/2, size, size)
      EndFor
    EndSub

    2 มีนาคม 2555 22:54
  • As an aside, I set the value of vertices to 200, and yes it was slower (what do you want for an O(n^2) algorithm?) but also appeared "animated" in its discovery of Prim's path.
    2 มีนาคม 2555 22:59
  • wow - good answers to all these.

    On the advanced challenge I was thinking of a single path that joins all the dots with a single path that is minimum - also known as the 'traveling salesman problem'.  Any ideas for this?

    3 มีนาคม 2555 12:10
  • Here's an approximation for the shortest path, guaranteed to be no more than twice as long as the optimal path--  there are other solutions which are better, but more complicated to derive....

    ' An attempt to find the Minimum Spanning Tree
    ' based on Prim's Algorithm
    ' [ that's Robert C. Prim, *not* Prim Everdeen]
    '
    ' Reference: 
    ' Cormen, Thomas H.; Leiserson, Charles E.; and Rivest, Ronald L
    ' Introduction to Algorithms
    ' The MIT Press and McGraw-Hill Book Company, 1990
    ' ISBN 0-262-03141-8 (MIT Press), ISBN 0-07-013143-0 (McGraw-Hill)
    ' Section 24.2 The algorithms of Kruskal and Prim
    ' Section 37.2 The traveling-salesman problem


    range = 500
    margin = 100
    vertices = 20


    ' Setup a black background with room for all the points
    GraphicsWindow.BackgroundColor = "Black"
    GraphicsWindow.Height = range + margin
    GraphicsWindow.Width = range + margin


    GenerateGraph()
    ShowVertices()
    RunGreedy()
    RunPrim()
    ShowApproximateTSP()
    ShowVertices()
    TextWindow.WriteLine("Results: greedy score=" + greedyTotal + " vs Prim score=" + primTotal)
    TextWindow.WriteLine("Cost of Prim-based TSP approximation=" + approximateCost)


    Sub GenerateGraph
      ' Randomly generate vertices
      For i = 1 To vertices
        x[i] = Math.GetRandomNumber(range) + margin/2
        y[i] = Math.GetRandomNumber(range) + margin/2
      EndFor


      ' Find the cost of going from onve vertex tgo another
      For i = 1 To vertices
        For j = 1 To vertices
          edge[i][j] = Math.SquareRoot(Math.Power(x[i]-x[j],2) + Math.Power(y[i]-y[j], 2))
        EndFor
      EndFor
    EndSub


    ' This greedy algorithm runs through each vertex, finding the lowest cost to traverse
    ' to another vertex not already in the path...
    Sub RunGreedy
      greedyTotal = 0
      GraphicsWindow.PenWidth = 7
      GraphicsWindow.PenColor = "Red"
      For i = 1 To vertices
        smallest = (range+margin) * 2
        For j = i+1 To vertices
          If (edge[i][j] < smallest) Then
            smallest = edge[i][j]
            origin = i
            destination = j
          EndIf
        EndFor
        GraphicsWindow.DrawLine(x[origin], y[origin], x[destination], y[destination])
        greedyTotal = greedyTotal + edge[origin][destination]
      EndFor
    EndSub


    ' An attempt to implement Prim's algorithm
    Sub RunPrim
      GraphicsWindow.PenWidth = 5
      GraphicsWindow.PenColor = "Blue"

      ' Begin by setting all vertices outside the connected graph
      For i = 1 To vertices
        connected[i] = 0  
      EndFor


      ' Pick the first vertex (arbitrary), and add it to the connected graph
      connected[1] = 1

      primTotal = 0
      fullyConnected = 0




      visit = 1
      destination[visit] = 1 

      ' Keep running the algorithm until the graph is fully connected
      While (fullyConnected = 0)
        smallest = (range + margin) * 2

        ' Traverse all of the vertices in the currently connected graph
        ' and find the least expensive edge to add another vertex not already in it
        For i = 1 To vertices
          If (connected[i] = 1) Then
            For j = 1 to vertices
              If (j <> i And edge[i][j] < smallest and connected[j] = 0) Then
                smallest = edge[i][j]
                fromVertex = i
                toVertex = j
              EndIf
            EndFor
          EndIf
        EndFor

        ' Connect the new node, and tally its cost
        connected[toVertex] = 1
        primTotal = primTotal + edge[fromVertex][toVertex]
        GraphicsWindow.DrawLine(x[fromVertex], y[fromVertex], x[toVertex], y[toVertex])


        '  Track the newest vertex added
        visit = visit + 1
        destination[visit] = toVertex

        ' Determine if all nodes are connected to the graph
        fullyConnected = 1
        For i = 1 to vertices
          If (connected[i] = 0) Then
            fullyConnected = 0
          EndIf
        EndFor  
      EndWhile 
    EndSub


    ' Show a path through all of the connections, in prim order, without duplicating edges
    Sub ShowApproximateTSP
      approximateCost = 0
      GraphicsWindow.PenColor = "Green"
      GraphicsWindow.PenWidth = 3

      For i = 2 To vertices
        GraphicsWindow.DrawLine(x[destination[i-1]], y[destination[i-1]], x[destination[i]], y[destination[i]])
        approximateCost = approximateCost + edge[destination[i-1]][destination[i]]
      EndFor
      GraphicsWindow.DrawLine(x[destination[vertices]], y[destination[vertices]], x[destination[1]], y[destination[1]])
      approximateCost = approximateCost + edge[destination[vertices]][destination[1]]
    EndSub




    Sub ShowVertices
      size = 7
      GraphicsWindow.PenColor="White"
      GraphicsWindow.BrushColor = "Yellow"
      For i = 1 To vertices
        GraphicsWindow.FillEllipse(x[i]-size/2, y[i]-size/2, size, size)
        GraphicsWindow.DrawEllipse(x[i]-size/2, y[i]-size/2, size, size)
      EndFor
    EndSub

                          
    5 มีนาคม 2555 19:32
  • JP Taylor,

    Your method works well and is a good bit faster than mine.  I took a different approach playing with simple genetic algorithms.  Basically set up some random orders of points - select the best and create a new set of random child variants based on the best and test these and keep going.  I found that my method works best with good initial guesses so I refined it to select some decent first tries, by looking at nearest neighbours.

    For the 20 points I listed as the test sample, the best I have so far is a total length of 1621 in 41 generations of the algorithm.  Due to the random nature of the algorithm the results vary from run to run but are consistently below 2000.

    Can anyone do better?

    6 มีนาคม 2555 20:36
  • IntermediateChallenge 2   SJP969

    This is a planet simulator.  You can see today's planet location.( seen from north polar position.)

    It is based on March 20.

    and ±1day 1week 1month 1year 10years before or after state.

    refered http://4d2u.nao.ac.jp/html/program/mitaka/index_E.html  

     

    renewed SJP969-0    (continuous slider)

    • แก้ไขโดย NaochanON 9 มีนาคม 2555 12:52 renewed
    9 มีนาคม 2555 5:54
  • Easy Challenge 1

    I'm working on the Intermediate Challenge 1, this is what I have so far, just the GUI. For now, I'm just working on a 2 player game, although I will probably work on making a computer opponent as well.



    • แก้ไขโดย Blue Falcon 9 มีนาคม 2555 23:08 Added HTML Links
    9 มีนาคม 2555 23:04
  • NaochanON,

    Another great bit of programming.

    Blue Falcon,

    The front screen GUI looks very good, looking forward to seeing the game as it develops.

    10 มีนาคม 2555 21:02
  • Blue Falcon,

    The front screen GUI looks very good, looking forward to seeing the game as it develops.

    Thank you! I'm still working out the placing of the dominoes or how the dots will be displayed, but I think I'll use some sort of invisible(Well, not really, just blending in with the background) shapes.
    11 มีนาคม 2555 3:06
  • It tricky thinking up new, original and interesting and varied level challenges, especially when its not clear which ones people get the most out of.

    So are there any suggestions - not necessarily full questions; more what sort of problems work well and people want to see more of.

    15 มีนาคม 2555 20:01
  • Check out this site-- more for intermediate or expert challenges.

    http://programmingpraxis.com/

    16 มีนาคม 2555 14:38
  • I'm  stuck on easy problem 2. Actually I've not even a clue how to start. I've no idea how I can seperate the letters in a given word. Can anyone help?

    18 มีนาคม 2555 16:00
  • Try looking at and experiment with the Text methods.

    The following is an example to check each character in a piece of text and get each character's ascii code (unique number for each letter or character symbol).

    testString = "My test string" ' A test string of characters
    length = Text.GetLength(testString) 'The number of characters in the string
    For i = 1 To length
      char = Text.GetSubText(testString, i, 1) 'Each character
      ascii = Text.GetCharacterCode(char) 'ASCII code for character
      TextWindow.WriteLine(char+" "+ascii) 'Print the character and its UNICODE, ASCII) value
    EndFor

    18 มีนาคม 2555 16:23
  • Take each input as a string or convert it into character array and access all elements separately using it's index and then try to sort array using ASCII values or any other method you prefer
    • แก้ไขโดย Sanket J Patel 18 มีนาคม 2555 17:31
    18 มีนาคม 2555 17:30
  • Here's my program for Easy Challenge 1: QLN628

    I have to admit: I couldn't have done it without some of litdev's help! Thank you litdev!


    ------------------------------------------------------------------------------------------





    • แก้ไขโดย Joman Mied 25 มีนาคม 2555 18:28 ---
    21 มีนาคม 2555 20:11
  • Easy Challenge 1    

    Graphic version   SSG699  

       

    22 มีนาคม 2555 14:02
  • This is for the Easy Challenge 1.

    (GHZ805)

    I am a begginer programer so tell me your feedback and tips!


    • แก้ไขโดย EthanNetz 1 เมษายน 2555 0:25
    1 เมษายน 2555 0:24
  • EthanNetz,

    Your program works very well.  My only suggestion is to try to use GoTo less, it can result in code that is hard to read or debug, but it does run well.  Also you can use TextWindow.ReadNumber() in place of TextWindow.Read() if you know that the user must enter a number.

    1 เมษายน 2555 18:59
  • Hi guys! This is a more complex version for easy challenge number 3.

    Please comment any suggestions or tips. I am a begginer programer so I appolagize for any messines in the

    program!

    Thanks!

    Ethan Netz

    GraphicsWindow.Title = "Spiral Maker" Turtle.Move(0) GraphicsWindow.Clear() GraphicsWindow.Height = 600 GraphicsWindow.Width = 500 start: GraphicsWindow.PenColor = C GraphicsWindow.BrushColor = C C = GraphicsWindow.GetRandomColor() GraphicsWindow.Clear() GraphicsWindow.DrawBoundText(160,25,100,"Angle:") GraphicsWindow.DrawBoundText(120,50,100,"Lines Drawn:") AngelBox = Controls.AddTextBox(205,25) IBox = Controls.AddTextBox(205,50) Skip = Controls.AddButton("Skip",400,37.5) turtle.PenUp() Turtle.MoveTo(250,350) Turtle.PenDown() z = Math.GetRandomNumber(180) If z <= 45 Then Goto start Else Controls.SetTextBoxText(AngelBox,z) Turtle.Speed = 100000 For i = 1 To 200 Controls.SetTextBoxText(IBox,i) Turtle.Turn(z) Turtle.Move(i) If Controls.LastClickedButton = Skip Then Goto start EndIf EndFor Goto Start EndIf


    5 เมษายน 2555 23:53
  • My try at the Easy challenge 1 :

    Import this : VVS563

    (You will need Data Extension)

    I don't think I can do the others since i'm horrible at maths ^^

    10 เมษายน 2555 17:44