Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Assistance With Keep on Truckin programming problem
Author Message
vertdragon23

Posted: Thu Mar 26, 2015 8:28 am   Post subject: Assistance With Keep on Truckin programming problem

The problem J5 on https://cemc.math.uwaterloo.ca/contests/computing/2007/stage1/juniorEn.pdf , If someone could help me get started, I would be greatly appreciative!
In Java.

Insectoid

Posted: Thu Mar 26, 2015 3:18 pm   Post subject: RE:Assistance With Keep on Truckin programming problem

First thing you'll want to do is insert the new hotel locations into your hotel list. I'm gonna assume you can do that already, since that's the easy part.

It's basically a permutation problem. This can be done iteratively or recursively, whatever you prefer. If you're familiar with recursion it should be fairly simple and and quick to write.

Step one is to find a path to the end. Once you've found a single path, it's easy to adjust your code to find *all* paths, so we'll only deal with that for now.

Naturally, you'll need a counter that shows how many miles you've driven that day. When you iterate over your list of hotels, you check if the miles driven to get to that hotel is within the min and max distance given in the problem. From there, you have 3 options:
-The hotel is too close. You haven't driven enough miles. Go to the next hotel.
-The hotel is just right. Reset your mileage counter to 0, and check the next hotel on the list.
-The hotel is too far. This is the recursive step, if you take that approach. If the hotel is too far, you need to go back to a previous hotel and try another route.

When you go back to a previous hotel, you need to choose a different option. Depending on the miles driven to that hotel, you might not have another option, in which case you need to go back to the hotel before that one. A recursive approach will do this automatically.

There are two exit conditions- either you reach the last hotel at 7000km, in which case you've found your route, or you back up all the way to the beginning, which means there is no possible way to reach the end.

Once you have working code that can find one path or proves no path exists, try to find a way to make it count all paths instead. It's extremely simple and barely changes the algorithm at all.
vertdragon23

Posted: Thu Mar 26, 2015 6:47 pm   Post subject: Re: Assistance With Keep on Truckin programming problem

I'm stuck, as to how I can get it to somehow recursively add the counter while also cycling through motel locations. x_x

import java.util.Arrays;
import java.util.Scanner;

public class Truckproblem {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);

int ways = 0;
int min;
int max;
int m;
int size;
int n;
int distance=0;

int motel[] = new int[] {990,1010,1970,2030,2940,3060,3930,4060,4970,5030,5990,6010,7000 };

System.out.println("Minimal distance per day:");
min = in.nextInt();

System.out.println("Maximum distance per day:");
max = in.nextInt();

m= in.nextInt();

if (distance==7000) {

ways= ways+1;
}

else
{

for(int i=1; i < 14; i = i+1) {

}
Insectoid

Posted: Thu Mar 26, 2015 8:38 pm   Post subject: RE:Assistance With Keep on Truckin programming problem

Do you understand recursion?

Quote:
if (distance==7000) {

ways= ways+1;
}

I strongly suggest you completely ignore counting the number of ways to reach the end until you have figured out how to find a single way to the end.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 4 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: