# 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 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.

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!

Friday, March 2, 2012 5:54 PM

### 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
GraphicsWindow.PenColor = GraphicsWindow.GetRandomColor()

For r = 0 to radius Step stepSize

GraphicsWindow.DrawLine(lastX, lastY, nextX, nexty)
lastX = nextX
lastY = nextY
EndFor
Program.Delay(1500)
EndWhile

Sub OnHalt
continue = 0
EndSub

Friday, March 2, 2012 7:31 PM
• 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

Friday, March 2, 2012 9:30 PM

' 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

Friday, March 2, 2012 10:54 PM
• 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.
Friday, March 2, 2012 10:59 PM
• 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?

Saturday, March 3, 2012 12:10 PM
• 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])

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

Monday, March 5, 2012 7:32 PM
• 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?

Tuesday, March 6, 2012 8:36 PM
• 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.

renewed SJP969-0    (continuous slider)

Friday, March 9, 2012 5:54 AM
• 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.

• Edited by Friday, March 9, 2012 11:08 PM Added HTML Links
Friday, March 9, 2012 11:04 PM
• NaochanON,

Another great bit of programming.

Blue Falcon,

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

Saturday, March 10, 2012 9:02 PM
• 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.
Sunday, March 11, 2012 3:06 AM
• Love the orbit program!
Sunday, March 11, 2012 10:05 PM
• 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.

Thursday, March 15, 2012 8:01 PM
• Check out this site-- more for intermediate or expert challenges.

http://programmingpraxis.com/

Friday, March 16, 2012 2:38 PM
• 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?

Sunday, March 18, 2012 4:00 PM
• 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```

Sunday, March 18, 2012 4:23 PM
• 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
Sunday, March 18, 2012 5:30 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 Sunday, March 25, 2012 6:28 PM ---
Wednesday, March 21, 2012 8:11 PM
• Easy Challenge 1

Graphic version   SSG699

Thursday, March 22, 2012 2:02 PM
• This is for the Easy Challenge 1.

(GHZ805)

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

• Edited by Sunday, April 1, 2012 12:25 AM
Sunday, April 1, 2012 12:24 AM
• 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.

Sunday, April 1, 2012 6:59 PM
• ```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 theprogram!Thanks!	Ethan NetzGraphicsWindow.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:")
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```

Thursday, April 5, 2012 11:53 PM
• 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 ^^

Tuesday, April 10, 2012 5:44 PM