Skip to content

Instantly share code, notes, and snippets.

@LeeXun
Last active October 27, 2017 06:18
Show Gist options
  • Save LeeXun/229e6aef18bbc575fd4700f6782520c2 to your computer and use it in GitHub Desktop.
Save LeeXun/229e6aef18bbc575fd4700f6782520c2 to your computer and use it in GitHub Desktop.
NCCU Assignment 4: Modified "hopscotch" game
#include <stdio.h>
#include <stdlib.h>
#define DATA_SIZE_LIMIT 30
#
# how to compile and execute:
# gcc hopscotch.c -o hopscotch
# ./hopscotch < input.txt
#
int n = 0, answer, step_limit;
typedef struct
{
int data[DATA_SIZE_LIMIT];
int size; // init at 0
} List;
void printList(List list)
{
if(list.size - 1 < 0)
{
printf("emtpy");
}
for (int i = 0; i < list.size; i += 1)
{
printf("%d", list.data[i]);
}
printf("\n");
}
void init(List *list, int a) {
for (int i = 0; i < list->size; i += 1) {
list->data[i] = a;
}
}
void append(List *list, int a)
{
list->data[list->size] = a;
list->size += 1;
}
void copyList(List *new_list, List list)
{
new_list->size = list.size;
for (int i = 0; i < list.size; i += 1)
{
new_list->data[i] = list.data[i];
}
}
int isDec(List list) {
for (int i = list.size - 1; i >= 1; i -= 1) { //只能到倒數第二個
if(list.data[i] < list.data[i - 1]) {
return 0;
}
}
return 1;
}
void walk(int n, List list)
{
if (n < 0){
return;
}
if (n == 0)
{
if(isDec(list) && list.size <= step_limit)
{
// printList(list);
answer += 1;
}
return;
}
for (int i = 1; i < 5; i += 1)
{
List new_list;
init(&new_list, 0);
copyList(&new_list, list);
append(&new_list, i);
walk(n - i, new_list);
}
}
int main()
{
while(scanf("%d\n", &n) == 1) {
List list;
init(&list, 0);
step_limit = (n - 1) / 10 * 10 + 7;
answer = 0;
walk(n, list);
printf("%d\n", answer);
}
return 0;
}
@LeeXun
Copy link
Author

LeeXun commented Oct 27, 2017

Below are the important rules during the jumping:

  1. The player never quits.
  2. The player never goes back.
  3. The player never jumps out-of-bounds.
  4. The player always randomly jumps 1, 2, 3 or 4 position(s) once at a time.
  5. The player always starts from the start position.
  6. If the specific position is 1 ~ 10, then the most jumps the player can jump is 7.
    If the specific position is 11 ~ 20, then the most jumps the player can jump is 17.
    If the specific position is 21 ~ 30, then the most jumps the player can jump is 27.

Input Format

There are several lines within the input file, each of which represents the position number n that the player would like to jump to. Those numbers are between 4 and 30. (i.e., 3 < n < 31).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment