Asked by:
Challenge of the Month  March 2012
General discussion

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!
All replies

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

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.Widthdiameter)/2
p["centerY"] = (GraphicsWindow.Heightdiameter)/2
p["orbitCenterX"] = (GraphicsWindow.Widthdistance)/2
p["orbitCenterY"] =(GraphicsWindow.Heightdistance)/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

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 McGrawHill Book Company, 1990
' ISBN 0262031418 (MIT Press), ISBN 0070131430 (McGrawHill)
' 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 


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 McGrawHill Book Company, 1990
' ISBN 0262031418 (MIT Press), ISBN 0070131430 (McGrawHill)
' Section 24.2 The algorithms of Kruskal and Prim
' Section 37.2 The travelingsalesman 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 Primbased 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[i1]], y[destination[i1]], x[destination[i]], y[destination[i]])
approximateCost = approximateCost + edge[destination[i1]][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 
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?

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
 Edited by NaochanONEditor Friday, March 9, 2012 12:52 PM renewed

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.
 Edited by Blue Falcon Friday, March 9, 2012 11:08 PM Added HTML Links


Blue Falcon,
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.The front screen GUI looks very good, looking forward to seeing the game as it develops.


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.

Check out this site more for intermediate or expert challenges.


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

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
 Edited by Sanket J Patel Sunday, March 18, 2012 5:31 PM

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!

 Edited by Joman Mied Sunday, March 25, 2012 6:28 PM 



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.

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
