Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge #5
New Posts  All Forums:Forum Nav:

# Programming Challenge #5

So after almost 5 months , the fifth programming challenge is finally here.

Thanks to rush2049 because I'm using his suggestion for this programming challenge.

*A little change in the format of these challenges is that each challenge from now on will have three levels of difficulty: Beginner, Intermediate, Advanced. These difficulty levels will be divided up according to the extra conditions the solution program has to satisfy.*

THE CHALLENGE:

The program must take a non-negative integer (0 to infinity) as input and must output a particular pattern of symbols (asterisks in this case) depending on the integer input.
(This is in some way a bit similar to the first programming challenge if you remember doing that.)

The following specifies how different patterns will be output depending on the input.

INPUT:
Code:
````0`
```
OUTPUT:
Code:
````<NOTHING>`
```

INPUT:
Code:
````1`
```
OUTPUT:
Code:
````*`
```

INPUT:
Code:
````2`
```
OUTPUT:
Code:
``````*
* *
*```
```

INPUT:
Code:
````3`
```
OUTPUT:
Code:
``````*
* *
*
* * *
*
* *
*```
```

INPUT:
Code:
````4`
```
OUTPUT:
Code:
``````*
* *
*
* * *
*
* *
*
* * * *
*
* *
*
* * *
*
* *
*```
```

and so on... You get the pattern, I assume.

Now the CONDITIONS:
Beginner:

Must work for all integers >= 0.
Output must not be hard-coded, obviously.

Intermediate:

Solution must use a recursive algorithm (i.e. not iterative)

Make sure the solution is "significantly faster than" O(n^(1/2*n)) which is about equal to the run-time complexity of the typical solution of this problem.
(Here I'm taking rush2049's word for it because I haven't had time to test this myself since I'm a bit busy right now. I admit, I have only done the simple iterative solution, yet. )

Obviously, the subsequent difficulty levels must satisfy the conditions of the preceding difficulty levels. You may also wish to add input validation checks and what not to make your solution program more robust.

If you have any questions or suggestions, you may either post them here or PM me. Looking forward to see your codes. If you have any questions regarding the general format of the challenge, refer to The Programming Challenge Master Thread.

Code on... (I need a suggestion for what to say when signing off too. ...preferably something that elicits particular enthusiasm for programming )
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
Warning: Spoiler! (Click to show)
Code:
``````import java.util.Scanner;

public class fifthchallenge {

public static void main(String[] args) {
String star = "*";
String output = "\n";
String repeated = "";
System.out.println("Input the number of revisions please");

Scanner scan = new Scanner(System.in);

int input = scan.nextInt();
//System.out.println("The pattern will now evolve" + input + "times.");

int looprepeater = 0;

while (looprepeater <= input){
repeated = new String(new char[looprepeater]).replace("\0", star);
output = output + repeated + output;
looprepeater = looprepeater+1;
}
System.out.println(output);

}

}
```
```

Here it is in java.

I think this follows the rules well enough. I'm just not quite sure how I'd make the output lack the spaces between the lines without lumping it together on a single line.
Edited by De-Zant - 6/2/12 at 10:10am
 Toki (10 items)
CPUGraphicsRAMHard Drive
[i7 860] [XFX 5870] [4x2gb] [WD 500gb]
OSMonitorKeyboardPower
[W7] [HP LP3065 - CrossOver 27Q LED-P - Acer x243w] Ducky DK1087-CELLB Tenkeyless, MX Blue - Steels... [LC power 750W]
Audio
[ATH-A700] + [Asus Xonar DG]
 Toki (10 items)
CPUGraphicsRAMHard Drive
[i7 860] [XFX 5870] [4x2gb] [WD 500gb]
OSMonitorKeyboardPower
[W7] [HP LP3065 - CrossOver 27Q LED-P - Acer x243w] Ducky DK1087-CELLB Tenkeyless, MX Blue - Steels... [LC power 750W]
Audio
[ATH-A700] + [Asus Xonar DG]
Don't you think it'd be a better idea to print the asterisks as they are generated instead of first creating the whole String and then printing it out ?

With that, you won't get an "outOfMemory" error when the input integer is too large.
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
Warning: Spoiler! (Click to show)
Code:
``````#include <iostream>

using namespace std;
int count = 1;
string fact(int num, string o="*"){
if(count == num) return o;
if(num <= 1){
return o;
}else{
string ret;
for(int i=0; i<count+1; i++){
ret += "*";
}
count++;
return fact(num, o + "\n" + ret + "\n" + o);
}
}

int main() {
cout << fact(4);
return 0;
}```
```

I'm not sure if this counts as truly recursive. It uses a static variable and isn't as clean as I'd like, but it certainly works

On the line "cout << fact(4);", replace 4 with the desired number. Outputs "*" if the input is zero or less.
 Daily (16 items)
CPUMotherboardGraphicsRAM
i7 2600K @ 4.8GHz, 1.4V Maximus IV Extreme GTX 560 DCII TOP 4x4GB Kingston HyperX 1866MHz CL11
Hard DriveHard DriveCoolingCooling
Kingston HyperX 3K 120GB Samsung 640GB Thermochill PA120.2 Jingway DB-1 Pump
CoolingCoolingOSMonitor
2x Kaze Jyuni 1900RPM EK Supreme HF Copper plexi Arch Linux x64 Acer X223HQ 1920x1080
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750 Modded Corsair Carbide 500R Logitech M500
 Daily (16 items)
CPUMotherboardGraphicsRAM
i7 2600K @ 4.8GHz, 1.4V Maximus IV Extreme GTX 560 DCII TOP 4x4GB Kingston HyperX 1866MHz CL11
Hard DriveHard DriveCoolingCooling
Kingston HyperX 3K 120GB Samsung 640GB Thermochill PA120.2 Jingway DB-1 Pump
CoolingCoolingOSMonitor
2x Kaze Jyuni 1900RPM EK Supreme HF Copper plexi Arch Linux x64 Acer X223HQ 1920x1080
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750 Modded Corsair Carbide 500R Logitech M500
Nice challenge, here's a recursive solution in Java:
Warning: Spoiler! (Click to show)
Code:
``````import java.util.Scanner;

public class challenge5
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
if (num > 0)
System.out.println(getString(1, num));
}

public static String getString(int curr, int max)
{
if (curr == max)
{
return "*\n";
}

for (int i = curr; i <= max; i++)
{
}
String str = getString(curr + 1, max);
return str + toAdd + str;
}
}```
```

Edited by Waffleboy - 6/2/12 at 1:24pm
 Workstation (16 items)
CPUMotherboardGraphicsRAM
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj...
Hard DriveOptical DriveOptical DriveOS
OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner Win 7 Home Premium 64 bit
MonitorKeyboardPowerCase
Samsung 22 inch 1920x1080 60Hz Logitech g11 Corsair 750 Watt NZXT Tempest
Razer deathadder 3500 dpi OCZ Audigy SE Sony MDR-V6
 Workstation (16 items)
CPUMotherboardGraphicsRAM
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj...
Hard DriveOptical DriveOptical DriveOS
OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner Win 7 Home Premium 64 bit
MonitorKeyboardPowerCase
Samsung 22 inch 1920x1080 60Hz Logitech g11 Corsair 750 Watt NZXT Tempest
Razer deathadder 3500 dpi OCZ Audigy SE Sony MDR-V6
Here are my solutions in C. Idk if mine is truly recursive either, but it's definitely O(n^(n/2)). maybe when i have more time i'll try to make it run "significantly faster".
Iterative (Click to show)
Code:
``````#include <stdio.h>

int main(int argc, char* argv[]) {
int limit = 0;
int j = 0;
int k = 0;
int l = 0;

if(argc != 2){
printf("Usage: asterisk {0-infinity}");
exit(1);
}
else if(atoi(argv[1]) < 0){
printf("Use a non-negative integer!");
exit(1);
}
else{
limit = atoi(argv[1]);

if(limit != 0) printf("*\n");
for(j=2; j<=limit; j++){
for(k=0; k<j; k++){
printf("*");
}
printf("\n");
printf("*\n");
}

for(l=limit-1; l>1; l--){
for(k=0; k<l; k++){
printf("*");
}
printf("\n");
printf("*\n");
}

}

exit(0);
}```
```
Recursive (Click to show)
Code:
``````#include <stdio.h>

int half = 0;

void print(int line, int k){
int j = 0;
if(half == 1) printf("*\n");
if(line >= half*2) return;
if(line != (half*2)-1) printf("*\n");
for(j=0; j<k; j++) printf("*");
printf("\n");
if(line < half) return print(line+1, k+1);
return print(line+1, k-1);
}

int main(int argc, char* argv[]) {
if(argc != 2){
printf("Usage: asterisk {0-infinity}");
exit(1);
}
else if(atoi(argv[1]) < 0){
printf("Use a non-negative integer!");
exit(1);
}
else{
half = atoi(argv[1]);
print(2, 2);
}

exit(0);
}```
```
 Fractal Design (15 items) 775 4 life (15 items) Lenovo Thinkpad T410 Laptop (9 items)
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5
Mouse
Razor Abyssus
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ...
Power
9-cell plus Slice battery
 Fractal Design (15 items) 775 4 life (15 items) Lenovo Thinkpad T410 Laptop (9 items)
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5
Mouse
Razor Abyssus
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ...
Power
9-cell plus Slice battery
Completed the advanced one in C++.

It is made "significantly faster" by taking advantage of the fact that the pattern is mirrored within itself, so it is O(n).

Warning: Spoiler! (Click to show)
Code:
``````#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> printStars(int n);

int main(int argc, const char * argv[])
{
// Number of stars in center line
int number = 0;

// User input
cout << "Enter number: ";
cin  >> number;

// Vector to hold lines of output
vector<string> output;

// Call recursive function
output = printStars(number);

// Print output
vector<string>::iterator i;
for (i = output.begin(); i < output.end(); i++)
{
cout << *i << endl;
}
return 0;
}

vector<string> printStars(int n)
{
vector<string> output;

string currentLine;
for (int i = 0; i < n; i++)
currentLine.append("*");

if (n > 1)
{
vector<string> mirrors = printStars(n-1);

output.insert(output.begin(), mirrors.begin(), mirrors.end());
output.insert(output.begin(), currentLine);
output.insert(output.begin(), mirrors.begin(), mirrors.end());
}
else
{
output.insert(output.begin(), currentLine);
}

return output;
}```
```

Edited by Manyak - 6/2/12 at 12:29pm
 Server (10 items)
CPUMotherboardRAMHard Drive
Intel Xeon E3110 ASUS P5Q Premium 8GB G.Skill DDR2-800 2TB Caviar Green
Hard DriveCoolingOSCase
1TB Caviar Black Prolimatech Megahalems VMWare ESX CM Stacker STC-T01
OtherOther
LSI 9280-16i4e RAID Card Intel Pro/1000 PT Quad-Port Gigabit NIC
 Server (10 items)
CPUMotherboardRAMHard Drive
Intel Xeon E3110 ASUS P5Q Premium 8GB G.Skill DDR2-800 2TB Caviar Green
Hard DriveCoolingOSCase
1TB Caviar Black Prolimatech Megahalems VMWare ESX CM Stacker STC-T01
OtherOther
LSI 9280-16i4e RAID Card Intel Pro/1000 PT Quad-Port Gigabit NIC
Quote:
Originally Posted by Manyak

Completed the advanced one in C++.
It is made "significantly faster" by taking advantage of the fact that the pattern is mirrored within itself, so it is O(n).
-snip-

I'm confused - isn't this still O(n^n/2)? It looks like you're calling printstars n times each iteration to get the previous segment.

So far, the only way I can think to do it in < O(n^n/2) would be to have some structure storing all previous outputs as you iterate through, but then it wouldn't be recursive.
 Workstation (16 items)
CPUMotherboardGraphicsRAM
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj...
Hard DriveOptical DriveOptical DriveOS
OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner Win 7 Home Premium 64 bit
MonitorKeyboardPowerCase
Samsung 22 inch 1920x1080 60Hz Logitech g11 Corsair 750 Watt NZXT Tempest
Razer deathadder 3500 dpi OCZ Audigy SE Sony MDR-V6
 Workstation (16 items)
CPUMotherboardGraphicsRAM
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj...
Hard DriveOptical DriveOptical DriveOS
OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner Win 7 Home Premium 64 bit
MonitorKeyboardPowerCase
Samsung 22 inch 1920x1080 60Hz Logitech g11 Corsair 750 Watt NZXT Tempest
Razer deathadder 3500 dpi OCZ Audigy SE Sony MDR-V6
Quote:
Originally Posted by Waffleboy

I'm confused - isn't this still O(n^n/2)? It looks like you're calling printstars n times each iteration to get the previous segment.
So far, the only way I can think to do it in < O(n^n/2) would be to have some structure storing all previous outputs as you iterate through, but then it wouldn't be recursive.

Nope, it's O(n). You can prove it by making a global counter variable and incrementing it in the printStars() function, then outputting the result back in main().
 Server (10 items)
CPUMotherboardRAMHard Drive
Intel Xeon E3110 ASUS P5Q Premium 8GB G.Skill DDR2-800 2TB Caviar Green
Hard DriveCoolingOSCase
1TB Caviar Black Prolimatech Megahalems VMWare ESX CM Stacker STC-T01
OtherOther
LSI 9280-16i4e RAID Card Intel Pro/1000 PT Quad-Port Gigabit NIC
 Server (10 items)
CPUMotherboardRAMHard Drive
Intel Xeon E3110 ASUS P5Q Premium 8GB G.Skill DDR2-800 2TB Caviar Green
Hard DriveCoolingOSCase
1TB Caviar Black Prolimatech Megahalems VMWare ESX CM Stacker STC-T01
OtherOther
LSI 9280-16i4e RAID Card Intel Pro/1000 PT Quad-Port Gigabit NIC
Quote:
Originally Posted by Manyak

Nope, it's O(n). You can prove it by making a global counter variable and incrementing it in the printStars() function, then outputting the result back in main().

I don't really understand the big O notation, but doesn't that mean that mine is also O(n)?
 Daily (16 items)
CPUMotherboardGraphicsRAM
i7 2600K @ 4.8GHz, 1.4V Maximus IV Extreme GTX 560 DCII TOP 4x4GB Kingston HyperX 1866MHz CL11
Hard DriveHard DriveCoolingCooling
Kingston HyperX 3K 120GB Samsung 640GB Thermochill PA120.2 Jingway DB-1 Pump
CoolingCoolingOSMonitor
2x Kaze Jyuni 1900RPM EK Supreme HF Copper plexi Arch Linux x64 Acer X223HQ 1920x1080
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750 Modded Corsair Carbide 500R Logitech M500
 Daily (16 items)
CPUMotherboardGraphicsRAM
i7 2600K @ 4.8GHz, 1.4V Maximus IV Extreme GTX 560 DCII TOP 4x4GB Kingston HyperX 1866MHz CL11
Hard DriveHard DriveCoolingCooling
Kingston HyperX 3K 120GB Samsung 640GB Thermochill PA120.2 Jingway DB-1 Pump
CoolingCoolingOSMonitor
2x Kaze Jyuni 1900RPM EK Supreme HF Copper plexi Arch Linux x64 Acer X223HQ 1920x1080
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750 Modded Corsair Carbide 500R Logitech M500
New Posts  All Forums:Forum Nav:
Return Home
Back to Forum: Coding and Programming
• Programming Challenge #5
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge #5