3
\$\begingroup\$

Kattis problem - ("I've been everywhere")
I would highly recommend looking at the problem through the link, however I will summarize it a bit here and explain the functionality of each part of my horrendous code.

Example input:

2
7
saskatoon
toronto
winnipeg
toronto
vancouver
saskatoon
toronto
3
edmonton
edmonton
edmonton

(line 1: number of test cases 2, lines 2 and 10: number of working trips 7 3)
Example output:

4
1

The goal is to ouput how many unique locations has been traveled to per test case. (correction, it does not matter if a location was visited already in a previous test case)

So, basically I want some help condensing my code as much as possible, and make it simpler also because I believe my code is a little bit much for such a basic coding question. Also, I want to extend my knowledge beyond spamming for loops XD

My Code

var readline = require('readline');

var input = [];

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', function (cmd) {
    input.push(cmd);
});

rl.on('close', function () {
    input.shift();
    let counter = 50; 
    for (let i = 0; i < input.length; i++) {
        value = parseInt(input[i]);
        if (value / value == 1) {
            input[i] = counter;
            counter++;
        }
    }

    let index = [];
    let unique = [...new Set(input)];
    //console.log(unique)
    for (let i = 0; i < unique.length; i++) {
        value = parseInt(unique[i]);
        if (value / value == 1) {
            unique[i] = unique.indexOf(unique[i]);
            index.push(unique.indexOf(unique[i]));
        }
    }
    index.push(unique.length);
    unique.push(unique.length);
    //console.log(unique);
    //console.log(index);

    let cityList = [];
    for (let i = 0; i < index.length; i++) {
        let start = index[i];
        let end = (index[i+1]);
        //console.log(start);
        //console.log(end);
        if (end == undefined) {
            break;
        }
        array = [];
        for (let j = start + 1; j < end; j++) {
            if (unique[j] == undefined) {
                array.push("");
            } else {
                array.push(unique[j]);
            }
            
        }
        cityList.push(array);
    }
    //console.log(cityList);

    for (let i = 0; i < cityList.length; i++) {
        console.log(cityList[i].length);
    }
    process.exit(0);
});

//i know it's bad

The code below removes the first element from the input array, changes the integers into distinct numbers to avoid removing them during the filtering later one:

    input.shift();
    let counter = 50; 
    for (let i = 0; i < input.length; i++) {
        value = parseInt(input[i]);
        if (value / value == 1) {
            input[i] = counter;
            counter++;
        }
    }

Next, create an array of the indexes of each integer in the input array so we can used them as lower and upper bound limits. Filter out an duplicates. Change the input arrays integer values to their positional value or index for future use as well. Push the length of the input array into the index array and input array so that we have an index for the last upper bound.

    let index = [];
    let unique = [...new Set(input)];
    //console.log(unique)
    for (let i = 0; i < unique.length; i++) {
        value = parseInt(unique[i]);
        if (value / value == 1) {
            unique[i] = unique.indexOf(unique[i]);
            index.push(unique.indexOf(unique[i]));
        }
    }
    index.push(unique.length);
    unique.push(unique.length);
    //console.log(unique);
    //console.log(index);

Establish an array that will include the unique locations per test case. Loop through the index array, using the value of index[i] for (start) and index[i+1] for (end). Create a nested array where it loops through the new input array known as the unique array, where we push every element between the start and end.

    let cityList = [];
    for (let i = 0; i < index.length; i++) {
        let start = index[i];
        let end = (index[i+1]);
        //console.log(start);
        //console.log(end);
        if (end == undefined) {
            break;
        }
        array = [];
        for (let j = start + 1; j < end; j++) {
            if (unique[j] == undefined) {
                array.push("");
            } else {
                array.push(unique[j]);
            }

        }
        cityList.push(array);
    }

Finally, output the length of each nested array within cityList

for (let i = 0; i < cityList.length; i++) {
        console.log(cityList[i].length);
    }

: )

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Thanks for posting here. I can't do better than @ggorlen's answer so I'll abstain from posting. \$\endgroup\$ Dec 10, 2022 at 1:39

1 Answer 1

2
\$\begingroup\$

Here's a general heuristic: for "easy" Kattis problems, the solution should typically only be a dozen or so lines of code. If you're writing on the order of 70 lines, a red flag should go off.

If you can get that 70-liner to be accepted, no problem. You can minimize the logic afterwards. But often, the 70-liner will have some sort of bug, in which case you shouldn't be afraid to toss it out or strip it down and start again based on what you learned from your attempt.

Back to the problem at hand: for each test case, the input is a list of simple strings representing city names, and the output should be the count of distinct items in this list.

You used a Set in your solution. This is the correct data structure! Given an array of items, putting it into a Set and taking its .size will return the number of distinct elements:

const dishes = ["cranberries", "mashed potatoes", "cranberries"];
console.log(new Set(dishes).size); // => 2

Based on this, the task becomes a matter of locating each test case subarray of the input, putting it into the set and taking its size:

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.once("line", () => {
  rl.on("line", line => lines.push(line));
});
rl.on("close", () => {
  lines.forEach((line, i) => {
    if (!isNaN(line)) {
      console.log(new Set(lines.slice(i + 1, i + +line + 1)).size);
    }
  });
});

Note that +lines parses a number from a string.

Another thing to note: Kattis problems are generally pretty verbose in Node because of the awkwardness of the callback-based readline API. My solution in Ruby was:

require "set"

gets.to_i.times do
  places = Set.new
  gets.to_i.times {places.add gets.chomp}
  p places.size
end

That said, for this particular problem, it's reasonable to slurp the lines into an array, then process it at the end and use O(n) .shift() and indexOf() calls. I also used .slice() which is similarly inefficient. But this resource-intensive strategy may not work well on future problems. When the input is large, O(n) operations and a large memory footprint will cause tests to fail.

Here's a more memory- and time-efficient setup to solve this problem. It's a bit more verbose and the solution needs to be triggered from a couple of places, but in some ways it's clearer than my above JS code since indexing is simplified.

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solve = () => console.log(places.size);

const places = new Set();

rl.once("line", () => {
  rl.on("line", line => {
    if (!isNaN(line)) {
      if (places.size) {
        solve();
        places.clear();
      }
    }
    else {
      places.add(line);
    }
  });
});
rl.on("close", solve);

When solving Kattis problems in Node, avoiding memory and time issues often comes down to successful readline management. For more readline tips and tricks for Kattis problems with Node, check out the links in this SO answer.

A few other pointers:

  • Use const rather than let to avoid reassigning things. Using let often is a code smell. var can be totally dropped at this point.
  • Watch out for accidental global variables like array = [];. A linter can find these errors for you.
  • Avoid counter loops when possible. Prefer semantically-meaningful, higher-order looping functions like forEach, map, filter, every, some, find and so forth.
  • Remove commented-out code you used to debug when finalizing it. Code shown for review should reflect the code you'd normally provide in a pull request or production commit.
\$\endgroup\$
5
  • \$\begingroup\$ Thanks for help! I guess what I have to do now is learn more advanced techniques in javascript because at the moment I am pretty limited on what I know and it's hard for me to understand code like you provided. Will do some research during the process, however I appreciate all the effort put into explaining everything! \$\endgroup\$
    – doroshm
    Dec 10, 2022 at 21:51
  • \$\begingroup\$ No problem. That said, I don't think the code is any more advanced than yours. The two things I'm doing that are new seem to only be taking the .size of the set and using a simple regular expression to detect numbers. isNaN is probably better anyway, so I'll update to use that. \$\endgroup\$
    – ggorlen
    Dec 10, 2022 at 21:52
  • \$\begingroup\$ You have a problem in your rewrite as it counts all unique place names in each test case, however OP states "...location... ...in a previous test case, it does not count as a unique location" \$\endgroup\$
    – Blindman67
    Dec 11, 2022 at 0:11
  • 1
    \$\begingroup\$ My code passes Kattis, as does OP's code. I think OP has simply misrepresented the problem there. Test cases are basically always self-contained, so I assume they're just referring to previous lines within a test case. \$\endgroup\$
    – ggorlen
    Dec 11, 2022 at 1:10
  • \$\begingroup\$ @Blindman67 yes ggorlen is correct, I misrepresented the problem. But, I believe this is an issue with the amount of hidden sample inputs that is tested with the Kattis solution check. They should have included more. My previous code worked with the sample inputs regardless of my misrepresentation. I will update the post with this correction. \$\endgroup\$
    – doroshm
    Dec 12, 2022 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.