Challenge of the Month - March 2012

Question

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 game.  The 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!

Answer 1

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

Answer 2

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
  

Answer 3

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

Answer 4

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.

Answer 5

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?

Answer 6

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

                      

Answer 7

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?

Answer 8

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)

Answer 9

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.

Answer 10

NaochanON,

Another great bit of programming.

Blue Falcon,

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

Answer 11

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.

Answer 12

Love the orbit program!

Answer 13

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.

Answer 14

Check out this site-- more for intermediate or expert challenges.

http://programmingpraxis.com/

Answer 15

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?

Answer 16

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

Answer 17

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

Answer 18

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!

---

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

Answer 19

Easy Challenge 1    

Graphic version   SSG699  

   

Answer 20

This is for the Easy Challenge 1.

(GHZ805)

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

Answer 21

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.

Answer 22

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

Answer 23

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 ^^